Криптография в CTF для начинающих: классические шифры, XOR и атаки на RSA

Криптография в CTF для начинающих: классические шифры, XOR и атаки на RSA

На DEF CON CTF 2024 задача Rotisserie продержала сотни команд более шести часов — и не из-за экзотического алгоритма. Народ тянулся к lattice-атакам и Coppersmith, а решение оказалось в шифре Цезаря и одном base64-декоде. Типичная история. По данным hackerxone.com, такая картина повторяется раз за разом: crypto CTF задания уровня easy-medium решаются тремя приёмами — распознаванием классического шифра, brute-force XOR и факторизацией слабого RSA-модуля. Разберём каждый из приёмов руками, с рабочими командами и кодом.

Место crypto-задач в CTF и операционный контекст

В формате Jeopardy crypto-задачи стоят отдельной категорией, но на практике криптография всплывает как слой внутри задач web, forensics и reverse. Типичная цепочка решения crypto CTF задач:

1. Получить файл или соединение с сервером
2. Определить тип шифрования (кодировка, классика, XOR, RSA, AES)
3. Применить подходящую атаку
4. Извлечь plaintext и найти флаг

Снятие слоёв кодировок — это, по сути, техника MITRE ATT&CK Deobfuscate/Decode Files or Information (T1140). В реальных атаках злоумышленники используют Standard Encoding (T1132.001) и Non-Standard Encoding (T1132.002) для маскировки C2-трафика, и навык распознавания кодировок с CTF напрямую переносится в blue team-работу. Для справки: техники Weaken Encryption (T1600) и Reduce Key Space (T1600.001) описывают действия атакующего на уже скомпрометированной системе (например, downgrade TLS) и не соответствуют CTF-сценарию, где криптосистема изначально слабая по замыслу организаторов.

На площадках CryptoHack, picoCTF и Cryptopals задачи расположены по нарастающей сложности. Начальный уровень — кодировки и классические шифры. Средний — XOR шифрование CTF и слабый RSA. Продвинутый — эллиптические кривые, lattice-атаки, padding oracle. Криптография в CTF для начинающих покрывает первые два уровня, и на них нарабатывается фундамент для всего остального.

Workflow: как распознать тип задачи за 30 секунд

По данным HackTricks Crypto CTF Workflow, первый шаг — классификация: перед тобой кодировка, шифрование, хэш или подпись. Ошибка на этом этапе стоит десятков минут впустую. Видел, как люди пишут RSA-факторизатор, а у них на входе — base64 в три слоя.

Вот triage-чеклист, который работает на любом соревновании:

1. Посмотри на символы. Base64 — A-Za-z0-9+/= с паддингом = в конце. Base32 — A-Z2-7= (много паддинга). Hex — только 0-9a-f. Группы из двух символов (A/B или точки/тире) — Бэкон или Морзе.
2. CyberChef Magic. Открой CyberChef для CTF в браузере (gchq.github.io/CyberChef), вставь данные, добавь операцию Magic с глубиной 3. Он сам пробует десятки кодировок и показывает лучших кандидатов. Часто этого хватает за глаза для easy-задач.
3. Определи, что контролируется. Только шифротекст? Или есть возможность отправлять данные на сервер (oracle)? Это определяет класс атаки.
4. Формат RSA. Переменные n, e, c в задании — RSA. Если n меньше 512 бит — модуль слабый. Если e = 3 — атака низким показателем степени RSA.
5. Hex-строка без явных признаков? Подозревай XOR. Попробуй однобайтовый перебор.

Этот чеклист закрывает подавляющее большинство easy-задач. Дальше — предметная работа с конкретным алгоритмом.

Предусловия и ограничения workflow: чеклист предполагает, что задача — чистая криптография. Если crypto-слой спрятан внутри стеганографии или бинарного реверса, сначала нужно извлечь данные из контейнера. Определить наличие сжатия можно по magic bytes: gzip (1f 8b), zlib (часто 78 9c), zip (50 4b 03 04). CyberChef имеет операции Raw Inflate / Gunzip для быстрой распаковки.

Классические шифры и криптоанализ через CyberChef

Шифр Цезаря и ROT: разминка перед боем

Шифр Цезаря — сдвиг каждого символа алфавита на фиксированное число позиций. ROT13 — частный случай со сдвигом 13. Криптоанализ классических шифров такого типа тривиален, но новички регулярно тратят на них 15-20 минут из-за одной ошибки: пытаются угадать сдвиг вместо перебора всех вариантов. Не надо так.

В CyberChef для CTF используй операцию ROT13 Brute Force — она показывает все 25 сдвигов одновременно. Ищи осмысленный текст или формат флага (FLAG{...}, CTF{...}, picoCTF{...}). Если префикс флага известен — посчитай разницу между первым символом шифротекста и первой буквой префикса. Это и есть ключ.

Для автоматизации по-английски: Nayuki Caesar cipher breaker (nayuki.io) — частотный анализ и наиболее вероятный сдвиг. Работает прямо в браузере.

Когда не работает: кириллический алфавит, кастомная таблица подстановки, аффинный шифр (сдвиг + умножение). На аффинный шифр CyberChef из коробки не рассчитан — используй dCode.fr, там есть специализированный солвер с перебором по всем допустимым коэффициентам.

Подстановочный шифр и частотный анализ шифротекста

Моноалфавитная подстановка заменяет каждую букву другой буквой по фиксированной таблице. Ключевое пространство — 26! (порядка 4 * 10^26 вариантов), brute-force невозможен. Зато частотный анализ шифротекста ломает этот шифр за минуты.

Принцип прост: в английском тексте E встречается примерно 12.7%, T — 9.1%, A — 8.2%. Если в шифротексте символ B появляется в 18% позиций — вероятнее всего это E. Подсчёт частот делается в несколько строк на Python: модуль collections.Counter по шифротексту, потом сопоставление топ-8 символов с таблицей частот английского алфавита (или русского, если plaintext на кириллице).

Для практической работы два онлайн-инструмента закрывают 90% случаев: - quipqiup.com — вставляешь шифротекст, получаешь варианты расшифровки с ранжированием по вероятности - Boxentriq Cryptogram Solver (boxentriq.com/code-breaking/cryptogram) — визуальный интерфейс с интерактивной подстановкой

Предусловия: частотный анализ работает на текстах от 50-100 символов. На коротких строках (менее 30 символов) распределение частот не успевает стабилизироваться, и метод даёт ложные маппинги. Тут уже приходится угадывать, а не анализировать.

Лайфхак для CTF: если формат флага известен — ищи в шифротексте 4-5-символьный кластер с паттерном, совпадающим с FLAG{ или CTF{. Четыре-пять подстановок получаешь мгновенно, и остаток решается по контексту слов. На соревнованиях этот приём экономит 10-15 минут на задачу. Проверено.

XOR шифрование в CTF: brute-force за секунды

XOR — самая частая криптографическая операция в CTF-задачах. Организаторы её любят, потому что hex-строка шифротекста выглядит устрашающе, но ломается элементарно — если знаешь ключевое свойство: операция обратима. plaintext ^ key = ciphertext, значит ciphertext ^ key = plaintext и ciphertext ^ plaintext = key. На этом свойстве строятся все атаки на XOR. По сути XOR — это не шифрование, а остаток от деления на здравый смысл.

Single-byte XOR: 256 ключей и Python

Если весь plaintext зашифрован одним байтом (0x00–0xFF), задача сводится к перебору 256 вариантов. Оценочная функция — подсчёт частых английских букв в каждом кандидате на plaintext. Ключ, дающий максимум читаемых символов, почти наверняка правильный.

import binascii

ct = binascii.unhexlify(
    "1b37373331363f78151b7f2b783431333d"
    "78397828372d363c78373e783a393b3736")
best, key_found = 0, 0
for k in range(256):
    pt = bytes([b ^ k for b in ct])
    score = sum(pt.lower().count(c) for c in b"etaoinshrdlu")
    if score > best:
        best, key_found = score, k
print(f"Key: 0x{key_found:02x}")
print(bytes([b ^ key_found for b in ct]).decode("ascii"))

Классика из Cryptopals Set 1 Challenge 3 — задача, через которую прошёл каждый, кто серьёзно занимается crypto в CTF. Ключ 0x58 полностью вскрывает шифротекст, выдавая фразу Cooking MC's like a pound of bacon. Скрипт пишется за две минуты и решает любую single-byte XOR задачу.

Когда scoring по буквам не работает: если plaintext — бинарные данные (PNG, ZIP, ELF). В таком случае ищи magic bytes. PNG начинается с 89 50 4E 47, ZIP — с 50 4B 03 04. XOR-и первые 4 байта шифротекста с известными magic bytes — получишь однобайтовый ключ. Этот приём часто встречается в forensics-задачах, где crypto — один из слоёв матрёшки.

Repeating-key XOR и xortool

Multi-byte (repeating-key) XOR — CTF-аналог шифра Виженера. Ключ повторяется циклически: KEYKEYKEYKEY... и XOR-ится с plaintext посимвольно. Сложнее single-byte? Да, но не принципиально.

Алгоритм атаки в три шага:

1. Определить длину ключа через расстояние Хэмминга. Разбиваешь шифротекст на блоки размером 2, 3, 4, ... 40 байт. Для каждого размера считаешь нормализованное расстояние Хэмминга между первыми блоками. Размер с минимальным расстоянием — вероятная длина ключа.
2. Разбить на потоки. При длине ключа 6 собираешь байты 0, 6, 12, 18... в одну группу; 1, 7, 13, 19... в другую; и так далее. Каждая группа зашифрована single-byte XOR.
3. Применить single-byte brute к каждой группе. Собрать полный ключ побайтово.

Вручную — 15-20 минут. Автоматически — одна команда. Если входной файл содержит hex-строку: xortool -x encrypted.hex. Флаг -x указывает, что вход в hex-формате. По умолчанию xortool считает наиболее частым байтом plaintext 0x00; флаг -c 20 переключает на пробел (0x20), что лучше подходит для текстовых данных: xortool -x -c 20 encrypted.hex. Результаты сохраняются в директорию xortool_out/. Флаг -l N принудительно задаёт длину ключа, если автодетект ошибся.

Предусловия и ограничения: шифротекст должен быть минимум в 5-6 раз длиннее ключа. На коротких текстах Hamming distance даёт шум, и определение длины ключа становится ненадёжным. Если plaintext не на английском — нужно указать xortool другой частый символ через -c.

По данным ctf101.org, XOR шифрование CTF «экспоненциально сложнее с ростом длины ключа», но на практике ключи в задачах редко превышают 20-30 байт, и xortool справляется за секунды.

Атака на RSA с малым модулем: факторизация и RsaCtfTool

RSA в CTF — почти всегда с преднамеренной слабостью. Настоящий RSA с модулем 2048+ бит факторизовать невозможно (ну, пока квантовые компьютеры не подвезли). Но CTF-задачи специально делают модуль маленьким, используют близкие простые числа или ставят экспоненту e = 3. Такие ошибки OWASP классифицирует как Cryptographic Failures (A02:2021) — и именно их мы учимся эксплуатировать.

Факторизация малого модуля: sympy и FactorDB

Требования к окружению для RSA-атак: - Python 3.8+ (для pow(e, -1, phi) — модулярный обратный без gmpy2; на практике часто встречается 3.10+) - pip install "pycryptodome>=3.21.0" sympy (дополнительно gmpy2 — для iroot, атак Wiener/Boneh-Durfee и работы с большими числами) - RAM: 512 МБ минимум (для SageMath-атак рекомендуется 2+ ГБ) - Режим: offline, интернет нужен только для FactorDB lookup

Задача даёт n, e, c. Первый рефлекс — оценить размер n. Если модуль помещается в 64-битное число или имеет менее 256 бит — факторизация тривиальна. В примере из hackerxone.com, n = 2461182143756758461 раскладывается на p = 1230926867 и q = 2000003303 мгновенно:

from sympy import factorint
from Crypto.Util.number import long_to_bytes

n, e = 2461182143756758461, 65537
c = 2155617055038674401  # пример для демонстрации
p, q = list(factorint(n).keys())
assert p * q == n, "p*q != n — проверьте входные данные"
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)))

Если sympy.factorint не справляется за пару секунд — проверь FactorDB (factordb.com). Это краудсорсинговая база факторизаций: многие CTF-модули уже кем-то разложены и лежат в базе. Факторизация RSA онлайн через FactorDB — первое, что стоит попробовать, прежде чем запускать тяжёлые инструменты. Зачем тратить CPU, если кто-то уже всё посчитал?

Таблица слабостей RSA в CTF-задачах

Слабость	Как распознать	Метод атаки
Малый модуль (< 256 бит)	n помещается в несколько десятков цифр	sympy.factorint(n) или FactorDB
Близкие простые (p ≈ q)	n большой, но isqrt(n) близок к делителю	Метод Ферма: инкремент a = isqrt(n) пока a^2 - n не станет полным квадратом
Малая экспонента e = 3	e = 3 в условии, сообщение короткое	Кубический корень от c: gmpy2.iroot(c, 3) без модуля (только если m^e < n; иначе — атака Håstad: ≥e шифротекстов одного сообщения, зашифрованных разными модулями, восстановление через CRT)
Общий делитель двух ключей	Даны два публичных ключа (n1, n2)	math.gcd(n1, n2) — общий простой p за микросекунды
Большой e (Wiener)	e ≈ n по порядку	Атака Винера через разложение в непрерывную дробь
Общий модуль (common modulus)	Одно сообщение, два ключа с одинаковым n	Расширенный алгоритм Евклида для двух экспонент

RsaCtfTool: десяток атак одной командой

RsaCtfTool (github.com/Ganapati/RsaCtfTool) — основной инструмент для решения RSA-задач на CTF. Он последовательно прогоняет более дюжины атак: Wiener, Fermat, Hastad, Boneh-Durfee, small q, common modulus и другие. По сути — швейцарский нож для слабого RSA.

Установка: git clone https://github.com/Ganapati/RsaCtfTool && cd RsaCtfTool && pip install -r requirements.txt. Для полного набора атак нужны системные пакеты libgmp-dev и libmpc-dev (Ubuntu/Debian: apt install libgmp-dev libmpc-dev).

Базовый вызов: python3 RsaCtfTool.py -n <modulus> -e <exponent> --uncipher <ciphertext>. Инструмент сам определяет подходящую атаку и выводит расшифрованный текст.

Если задача даёт PEM-файл публичного ключа: python3 RsaCtfTool.py --publickey pub.pem --uncipherfile cipher.enc. RsaCtfTool извлечёт n и e из PEM, попробует факторизовать модуль всеми доступными методами, и при успехе — расшифрует.

Для двух ключей с предполагаемым общим делителем: python3 RsaCtfTool.py --publickey key1.pem --publickey key2.pem --uncipherfile cipher.enc.

Когда RsaCtfTool не справляется: - Модуль действительно большой (2048+ бит) без известных слабостей — ищи другой вектор: padding oracle, related messages, fault injection - Задача требует lattice-атак (Coppersmith) — переходи в SageMath с методом small_roots() - Нестандартная криптосистема (Paillier, ElGamal, ECC) — RsaCtfTool бесполезен, нужны специфичные скрипты

Инструменты для crypto CTF: когда что использовать

Инструмент	Задачи	Преимущества	Ограничения	Когда использовать	Когда не использовать
CyberChef	Кодировки, классика, AES, XOR	Визуальный, без установки, Magic-автодетект	Нет RSA-атак, нет lattice	Первый шаг — снять слои кодировок	RSA, ECC, oracle-атаки
xortool	Repeating-key XOR	Автоопределение длины ключа, CLI	Только XOR	Длинный шифротекст с повторяющимся ключом	Single-byte XOR (проще руками)
RsaCtfTool	RSA со слабыми ключами	12+ автоматических атак	Медленно на больших n, бесполезен на сильных ключах	Любая RSA-задача — запусти первым	Non-RSA криптосистемы
SageMath	Lattice, ECC, advanced RSA	Полный математический стек	2+ ГБ RAM, крутая кривая обучения	Coppersmith, small_roots, ECC	Простые задачи — overkill
dCode.fr	Классические шифры, нестандартные	Огромная коллекция, онлайн	Нет программного API	Неизвестный классический шифр	Современная криптография
pycryptodome (≥ 3.21.0)	AES, RSA, DES и все стандартные примитивы	Полные реализации в Python	Нет автоатак, нужно писать код; в старых версиях есть CVE	Расшифровка после получения ключа	Факторизация, взлом
Ciphey	Автодетект и декодирование	Пробует тысячи вариантов	Нестабилен на нестандартных кодировках	Первичная разведка — вдруг повезёт	Oracle, нетривиальная логика

Рекомендуемый набор для локальной машины (по рекомендации HackTricks): pip install "pycryptodome>=3.21.0" gmpy2 sympy pwntools z3-solver. Этот стек покрывает абсолютное большинство crypto CTF заданий без необходимости ставить SageMath. Z3 нужен для задач, где криптография сводится к системе ограничений (constraint-based challenges).

Чеклист: решение crypto-задачи от получения до флага

1. Скачать файл или подключиться к серверу (nc host port).
2. Определить формат данных: hex, base64, ASCII, бинарный.
3. Загрузить в CyberChef, применить Magic. Если декодируется — снимать слои до plaintext.
4. Если остался шифротекст — классифицировать: классика, XOR, RSA, AES, другое.
5. Классика — ROT Brute Force в CyberChef или quipqiup.com.
6. XOR — single-byte brute (цикл по 256 ключам) или xortool для repeating-key.
7. RSA — проверить размер n. Маленький: sympy.factorint. Средний: RsaCtfTool. Большой: искать специфическую слабость (Wiener, Hastad, common modulus).
8. AES/DES — искать утечку ключа, повторное использование IV, padding oracle.
9. Получен plaintext — искать формат флага.
10. Ничего не сработало — читать исходный код задачи (если дан), искать логические ошибки в реализации криптосистемы.

Большинство crypto-тасков ломаются не высшей математикой, а распознаванием паттерна. После полусотни решённых задач взгляд начинает цепляться за характерные признаки — маленький e, повторяющийся XOR-ключ, подозрительно короткий n — и руки тянутся к нужному инструменту автоматически. Проблема новичков не в отсутствии знаний теории чисел, а в попытке решить задачу «в лоб» вместо того, чтобы потратить 30 секунд на классификацию. Видел команды, которые писали собственный факторизатор с нуля, когда sympy.factorint(n) выдал бы ответ за 0.3 секунды. Зачем?

80% crypto-задач на CTF — про pattern matching, а не про математику. Кто разобрался с тремя базовыми векторами из этой статьи — закрывает easy-уровень на любом соревновании. Но эти же три вектора формируют ложное чувство уверенности. На medium и hard задачах — padding oracle, elliptic curve discrete log, lattice reduction — начинается другая игра, где без понимания алгебры и теории чисел вообще не продвинуться. Cryptopals (cryptopals.com) и CryptoHack (cryptohack.org) дают задачи от simple XOR до lattice-атак с нарастающей сложностью, и на них нарабатывается переход от «умею brute-force» к «понимаю, почему работает». После того как easy-таски щёлкаются за минуту — не оставайся в зоне комфорта, переходи на CryptoHack Introduction to RSA и Cryptopals Set 4. Там и начинается настоящая криптография в CTF для начинающих, которые хотят перестать быть начинающими.

🚀 Хочешь закрепить на практике? Реши задачи по теме на HackerLab — категория «pentest-machines».