Источник: https://github.com/AnaktaCTF/CTF/blob/main — Cryptography/introduction_to_the_crypto.md

Что такое криптография в CTF?

Криптография — это наука о методах защиты информации путем преобразования ее в форму, непонятную без специального ключа или знания. В контексте CTF (Capture the Flag) соревнований, криптографические задания требуют от участников применения знаний и навыков для расшифровки или анализа зашифрованных данных с целью получения флага.

Основные концепции

Шифрование и дешифрование

  • Шифрование — процесс преобразования открытого текста в зашифрованный с использованием алгоритма и ключа.
  • Дешифрование — обратный процесс, преобразование зашифрованного текста обратно в открытый текст с помощью ключа.

Пример:

Используя шифр Цезаря со сдвигом на 3, слово "HELLO" преобразуется в "KHOOR".

Симметричные и асимметричные алгоритмы

  • Симметричные алгоритмы используют один и тот же ключ для шифрования и дешифрования.
  • Асимметричные алгоритмы используют пару ключей: открытый для шифрования и закрытый для дешифрования.

Типы задач в криптографии CTF

Классические шифры

Шифр Цезаря

Описание:

Простой шифр, в котором каждая буква заменяется на букву, находящуюся на фиксированном количестве позиций дальше по алфавиту.

Как решить:

  • Попробовать все 25 возможных сдвигов.
  • Использовать инструменты для автоматизации перебора.

Пример использования в терминале:

echo 'KHOOR' | caesar -d

Шифр Виженера

Описание:

Использует ключевое слово для шифрования текста посредством серии сдвигов.

Как решить:

  • Определить длину ключа методом каскадного анализа.
  • Использовать инструменты для автоматизации дешифрования.

Пример использования в терминале:

echo 'RIJVSUYVJN' | vigenere -d -k 'KEY'

Математическая криптография

RSA

Описание:

RSA — асимметричный алгоритм шифрования, основанный на математических концепциях теории чисел, таких как простые числа и модульная арифметика. Безопасность RSA базируется на сложности факторизации больших чисел.

Принципы работы:

  1. Генерация ключей:

    • Выбираются два больших простых числа ( p ) и ( q ).
    • Вычисляется ( n = p \times q ).
    • Вычисляется функция Эйлера: ( \phi(n) = (p - 1)(q - 1) ).
    • Выбирается открытый экспонент ( e ), взаимно простое с ( \phi(n) ).
    • Вычисляется закрытый экспонент ( d ), такое что ( d \times e \mod \phi(n) = 1 ).

  2. Шифрование:

    • Зашифрованное сообщение вычисляется как ( c = m^e \mod n ), где ( m ) — исходное сообщение.

  3. Дешифрование:

    • Открытое сообщение восстанавливается как ( m = c^d \mod n ).

Пример задачи:

  • Дано:
    • ( n = 3233 )
    • ( e = 17 )
    • Зашифрованное сообщение ( c = 855 )
  • Требуется: Расшифровать сообщение.

Решение:

  1. Факторизуем ( n ):

    • ( n = 61 \times 53 ), где ( p = 61 ), ( q = 53 ).

  2. Вычисляем ( \phi(n) ):

    • ( \phi(n) = (61 - 1)(53 - 1) = 3120 ).

  3. Находим ( d ):

    • ( d \times 17 \mod 3120 = 1 ).
    • Решая уравнение, находим ( d = 2753 ).

  4. Дешифруем сообщение:

    • ( m = 855^{2753} \mod 3233 ).
    • Вычисляем ( m = 123 ).

  5. Преобразуем число в символ:

    • Если используется кодировка ASCII, то 123 соответствует символу {.

Как решить в CTF:

  • Использовать инструменты для факторизации ( n ), такие как Yafu, Msieve или онлайн-сервисы.
  • Использовать скрипты на Python с библиотекой Crypto или Cryptodome.

Пример использования в Python:

from Crypto.Util.number import inverse, long_to_bytes

n = 3233
e = 17
c = 855

# Факторизация n
p = 61
q = 53

phi = (p - 1) * (q - 1)

# Вычисление d
d = inverse(e, phi)

# Дешифрование
m = pow(c, d, n)
print(long_to_bytes(m))

Дискретное логарифмирование и Diffie-Hellman

Описание:

В криптографии на основе дискретного логарифма безопасность алгоритмов основана на сложности вычисления дискретного логарифма в конечных полях.

Принципы работы Diffie-Hellman:

  1. Общие параметры:

    • Простое число ( p ) и генератор ( g ).

  2. Обмен ключами:

    • Пользователь A выбирает секретное число ( a ) и вычисляет ( A = g^a \mod p ).
    • Пользователь B выбирает секретное число ( b ) и вычисляет ( B = g^b \mod p ).
    • A и B обмениваются значениями ( A ) и ( B ).
    • A вычисляет общий секрет ( s = B^a \mod p ).
    • B вычисляет общий секрет ( s = A^b \mod p ).

Как решить в CTF:

  • Если используются малые параметры ( p ) или ( g ), можно вычислить секретные ключи ( a ) или ( b ) через дискретный логарифм.
  • Использовать алгоритмы для вычисления дискретного логарифма, такие как алгоритм «Ро Полларда».

Пример использования в Python:

from sympy.ntheory import discrete_log

p = 23
g = 5
A = 8

# Вычисление секретного числа a
a = discrete_log(p, A, g)
print(f"Секретное число a: {a}")

Стеганография

LSB-стеганография

Описание:

Метод стеганографии, при котором данные скрываются в наименее значащих битах (LSB) пикселей изображения.

Как решить:

  • Использовать инструменты для извлечения LSB-данных.
  • Проверить каждый цветовой канал (RGB) на наличие скрытой информации.

Пример использования инструментов:

  • stegsolve.jar — графический инструмент для анализа изображений.

  • zsteg — для анализа PNG и BMP файлов:

    zsteg -a image.png

  • bitplane — для визуализации битовых плоскостей изображения.

Криптоанализ

Анализ частот

Описание:

Метод взлома моноалфавитных шифров путем сравнения частоты символов в зашифрованном тексте с известной частотой символов в языке.

Как решить:

  • Подсчитать частоту каждого символа в шифротексте.
  • Сопоставить наиболее часто встречающиеся символы с наиболее частыми буквами в языке (например, E, T, A в английском).
  • Постепенно заменять символы и проверять осмысленность получаемого текста.

Пример использования в Python:

from collections import Counter

ciphertext = 'ZHOFRPH WR FUBSWRJUDSKB'
frequency = Counter(ciphertext.replace(' ', ''))
print(frequency)

Атаки на одноразовый блокнот с повторным использованием ключа

Описание:

Одноразовый блокнот (One-Time Pad) является абсолютно стойким шифром, если ключ используется только один раз. Однако, если один и тот же ключ используется для шифрования нескольких сообщений, это приводит к уязвимости.

Как решить:

  • Если два сообщения зашифрованы одним ключом, их XOR дает XOR открытых текстов.
  • Можно использовать статистические методы и известные шаблоны для восстановления исходных сообщений.

Пример задачи:

  • Даны два шифротекста ( C1 ) и ( C2 ), зашифрованные одним ключом.
  • Требуется: найти открытые тексты ( M1 ) и ( M2 ).

Решение:

  1. Вычислить ( C1 \oplus C2 = M1 \oplus M2 ).
  2. Проанализировать полученный результат на предмет известных слов или фраз.
  3. Использовать методы криптоанализа для восстановления ( M1 ) и ( M2 ).

Инструменты и ресурсы

Онлайн-инструменты

  • CyberChef

    Универсальный инструмент для различных преобразований данных.

    Пример использования:

    • Расшифровать Base64:

      1. Вставить зашифрованный текст в поле ввода.
      2. Добавить операцию "From Base64" в рецепт.

  • dCode

    Сайт с множеством инструментов для криптоанализа и стеганографии.

    Пример использования:

    • Решить шифр Виженера, не зная ключ:

      1. Перейти на страницу шифра Виженера.
      2. Вставить зашифрованный текст.
      3. Выбрать опцию автоматического взлома.

Программные инструменты

Hashcat

Описание:

Мощный инструмент для взлома хешей с использованием GPU.

Пример использования:

  • Взломать MD5-хеш с помощью словаря rockyou.txt:

    hashcat -m 0 -a 0 hash.txt /usr/share/wordlists/rockyou.txt

  • Взломать хеш SHA-1:

    hashcat -m 100 -a 0 hash.txt /usr/share/wordlists/rockyou.txt

John the Ripper

Описание:

Инструмент для взлома паролей и хешей.

Пример использования:

  • Взломать хеши с помощью rockyou.txt:

    john --wordlist=/usr/share/wordlists/rockyou.txt hash.txt

Steghide

Описание:

Инструмент для скрытия и извлечения данных из изображений и аудио файлов.

Пример использования:

  • Извлечь скрытый файл:

    steghide extract -sf image.jpg -p 'password'

Ghidra

Описание:

Инструмент для обратной разработки, полезен для анализа бинарных файлов и понимания собственных алгоритмов шифрования.

Пример использования:

  • Открыть бинарный файл, проанализировать функции, найти алгоритм шифрования.

RockYou.txt

Предыстория RockYou.txt

RockYou.txt — это набор скомпрометированных паролей от компании RockYou . В декабре 2009 года компания столкнулась с утечкой данных, в результате чего было раскрыто более 32 миллионов учетных записей пользователей. Это случилось главным образом из-за политики компании, связанной с хранением паролей в незашифрованном виде. это один из самых популярных словарей паролей, используемых для перебора паролей.

Пример использования RockYou.txt

Использование с Hashcat:

  • Взломать MD5-хеш с использованием RockYou.txt:

    hashcat -m 0 -a 0 hash.txt /usr/share/wordlists/rockyou.txt

Использование с John the Ripper:

  • Взломать хеши с помощью RockYou.txt:

    john --wordlist=/usr/share/wordlists/rockyou.txt hash.txt

Поиск паролей в RockYou.txt:

  • Проверить, есть ли определенный пароль в словаре:

    grep 'password123' /usr/share/wordlists/rockyou.txt

  • Создать персонализированный словарь на основе RockYou.txt, фильтруя по определенным условиям (например, пароли длиной от 8 до 12 символов):

    awk 'length($0) >= 8 && length($0) <= 12' /usr/share/wordlists/rockyou.txt > filtered.txt

Подходы к решению криптографических задач

  1. Анализ задания

    • Внимательно прочитайте условие и выявите ключевые моменты.
    • Обратите внимание на форматы файлов и возможные подсказки.

  2. Использование подходящих инструментов

    • Выберите инструменты, наиболее подходящие для задачи.
    • Ознакомьтесь с их документацией и примерами использования.

  3. Автоматизация процессов

    • Если задача требует повторяющихся действий, напишите скрипт.
    • Используйте языки программирования, такие как Python.

    Пример:

    Написать скрипт для перебора паролей из словаря с помощью steghide:

    import subprocess

wordlist = '/usr/share/wordlists/rockyou.txt'
image = 'image.jpg'

with open(wordlist, 'r', encoding='utf-8', errors='ignore') as f:
    for line in f:
        password = line.strip()
        try:
            result = subprocess.run(['steghide', 'extract', '-sf', image, '-p', password], capture_output=True, text=True)
            if 'wrote extracted data' in result.stdout:
                print(f'Password found: {password}')
                break
        except Exception as e:
            pass

  4. Обратная разработка и анализ файлов

    • Используйте binwalk, strings, exiftool для анализа файлов.
    • Проверьте наличие скрытых данных или нестандартных заголовков.