К списку уроков

Урок 8. Crypto Hard

Онлайн, 28 ноября (пятница), 15:10

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

1. Введение

В "Crypto Easy" мы учили алфавит. В "Crypto Hard" мы пишем эксплойты. Современная криптография (AES, RSA) математически стойкая, если реализована идеально. Но в CTF (и в жизни) разработчики допускают ошибки:

  • Слабые ключи.

  • Неправильные режимы шифрования (ECB).

  • Предсказуемый рандом.

  • Утечка части информации (Oracle).

Для работы нам понадобятся библиотеки, которые уже упоминались: PyCryptodome для Python и мощнейшая математическая система SageMath.

2. XOR — Самый частый гость в CTF

XOR (Исключающее ИЛИ) — основа большинства симметричных шифров. Свойство: A⊕B=C⇒A⊕C=B. Если вы знаете кусок исходного текста (например, формат флага CTF{...) и шифротекст, вы можете восстановить часть ключа.

Типовые задачи на XOR:

Single Byte XOR

Весь текст ксорится с одним байтом (0-255).

  • Решение: Перебор (Brute-force) всех 256 вариантов. Ищем читаемый текст.

Repeated Key XOR

Ключ короче текста и повторяется (как в шифре Виженера, но с байтами).

  • Атака: Определить длину ключа (анализ совпадений), разбить текст на блоки и брутить каждый блок как Single Byte XOR.

Known Plaintext Attack (Атака с известным текстом)

Если вы знаете, что файл — это PNG, значит, он начинается с байтов 89 50 4E 47....

  • Формула: K = Ciphertext[:4] ^ Header_PNG. Мы нашли начало ключа!

3. RSA

Мы помним, что RSA зависит от сложности факторизации N=p⋅q. Если мы найдем p и q, мы вычислим приватный ключ и расшифруем всё.

Векторы атак на RSA:

  1. Маленькое N: Если N имеет размер менее 512 бит, его можно факторизовать (разложить на множители) за минуты на домашнем ПК.

    • Инструмент: SageMath или сайт factordb.com.

  2. Маленькое e (e=3): Если отправитель зашифровал одно и то же сообщение для 3-х разных получателей с малым экспонентой (e=3), работает Chinese Remainder Theorem (Китайская теорема об остатках). Можно восстановить сообщение без ключа.

  3. Multi-Prime RSA: Иногда N состоит не из двух больших простых чисел, а из множества маленьких (N=p1​⋅p2​⋅p3​…). Это ломается мгновенно.

SageMath Snippet для факторизации:

n = 12345... # Ваше N
factors = factor(n)
print(factors)

4. Блочные шифры: AES и режимы работы

Сам по себе AES (Rijndael) взломать практически невозможно. Но важно то, в каком режиме он работает.

Режим ECB (Electronic Codebook)

Самый наивный режим. Каждый блок (16 байт) шифруется отдельно одним и тем же ключом.

  • Уязвимость: Одинаковые блоки открытого текста дают одинаковый шифротекст.

  • Пример: Если зашифровать картинку в ECB, вы увидите контуры изображения, так как паттерны цветов сохраняются.

Режим CBC (Cipher Block Chaining) и Bitflipping

В этом режиме каждый блок зависит от предыдущего (через XOR).

  • Атака Bitflipping: Изменив 1 бит в шифротексте (блоке N), мы полностью ломаем расшифровку блока N, но предсказуемо меняем 1 бит в расшифровке блока N+1.

  • Практика: Если вы хотите поменять admin=0 на admin=1 в зашифрованной куке, вы меняете байт в предыдущем блоке шифротекста.

5. Инструментарий (Практика)

На этом уроке мы не смотрим слайды, мы запускаем софт.

  • xortool: Автоматически подбирает длину ключа и сам ключ для XOR-шифрования.

    xortool cipher.bin -c 20
# (попробуй подобрать ключ, зная, что наиболее частый символ — пробел/код 20)

  • RsaCtfTool: Комбайн для взлома RSA. В него вшиты десятки атак (Wiener's attack, Hastad's attack и др.).

    python3 RsaCtfTool.py --publickey key.pub --uncipherfile flag.enc

  • CyberChef: Визуальный конструктор. Идеально для быстрых проверок (From Hex -> XOR -> To Base64).

  • SageMath: Python на стероидах для математики. Обязателен для решения задач на эллиптические кривые (ECC) и сложную алгебру.

6. Методология решения задач (Crypto Hard)

Получили таск? Действуем по алгоритму:

  1. Определите тип: Это текст? Файл? Числа?

    • Если просто странный текст — пробуем кодировки (Base64/Hex) и XOR.

    • Если даны числа (N,e,c) — это RSA.

  2. Анализ RSA:

    • Проверьте N на factordb.com. Разложилось? Считайте задачу решенной.

    • Посмотрите на e. Если e=3, ищите атаку "Coppersmith" или "Broadcast Attack".

    • Если e огромное (близко к N), ищите "Wiener's Attack".

  3. Анализ шифров:

    • Видите повторяющиеся блоки в Hex-редакторе? Это ECB.

    • Можете регистрироваться на сайте и получать токен? Попробуйте атаку Padding Oracle (если сервер говорит "Ошибка отступа") или Bitflipping (если нужно стать админом).

7. Полезные материалы для практики

Так как урок практический, вот где нужно набивать руку (по возрастанию сложности):

  • CryptoHack: (Must have!) Лучшая в мире платформа для изучения криптографии через практику. Покрывает всё: от XOR до эллиптических кривых.

    • Ссылка: cryptohack.org

  • PicoCTF (Cryptography): Хороший набор задач для старта.

  • Attacks on RSA: Репозиторий с реализацией всех атак на RSA на Python.

    • Искать на GitHub: RsaCtfTool или RSA-attacks.