Атаки на хеширование в CTF: коллизии, радужные таблицы и length extension на практике

Атаки на хеширование в CTF: коллизии, радужные таблицы и length extension на практике

Типичная ситуация на Jeopardy-CTF: crypto-задача на 500 очков, в исходниках — хеш длиной 32 hex-символа, половина команд запускает hashcat на полный перебор и ждёт часами. Правильный ответ — вбить хеш в CrackStation, получить plaintext за пять секунд. Следующая задача на 750 очков: MAC формата md5(secret + data) в cookie. Hashcat тут бесполезен — нужен hashpump для length extension attack. Разница между «знаю, что MD5 сломан» и «знаю, как именно эксплуатировать конкретную слабость» — это разница между нулём очков и закрытой crypto-категорией. Разберём каждый тип атаки на хеширование в CTF с инструментами, скриптами и decision tree для выбора метода.

Слабые алгоритмы хеширования: что именно сломано в MD5 и SHA1

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

Pre-image resistance — по хешу H(m) невозможно найти исходное сообщение m. Для MD5 (128 бит) полный перебор — 2^128 операций. Ни MD5, ни SHA1 не сломаны по этому критерию. По данным систематического обзора Electric Coin Company, «почти ни одна широко изученная хеш-функция никогда не поддавалась атаке на (второй) прообраз» — единственное исключение Snefru 1989 года.

Second pre-image resistance — зная сообщение m1, невозможно найти другое m2 с тем же хешем. Тоже не сломано практически.

Collision resistance — невозможно найти любую пару m1 и m2, где H(m1) = H(m2). А вот тут MD5 и SHA1 разгромлены в хлам.

Для CTF это означает конкретную вещь: задача требует восстановить прообраз хеша — нужен brute force или радужные таблицы. Задача позволяет подать два разных входа с одинаковым хешем — нужна коллизия, и это на порядки быстрее.

MD5 (128 бит, 1992 год). По данным SecureFlag, подозрения в уязвимости к коллизиям существовали ещё с середины 90-х. В 2005 году опубликован алгоритм генерации двух 128-байтных блоков с идентичным MD5. Сегодня MD5-коллизию можно получить на обычном ноутбуке за секунды. MD5 — полностью мёртвый алгоритм.

SHA1 (160 бит, 1995 год). В 2005 году обнаружена атака за 2^69 операций вместо ожидаемых 2^80 (brute force). В 2017 году Google продемонстрировал SHAttered — практическую коллизию: два PDF-файла с разным содержимым, но одинаковым SHA1. По данным SecPod, SHAttered «всё ещё в 100 000 раз быстрее brute force». NIST депрекейтил SHA1 в 2011 году.

Использование MD5 и SHA1 для критических функций — прямое нарушение OWASP A02:2021 Cryptographic Failures. Реальные последствия: по данным SecureFlag, в утечке Yahoo (обнаружена в 2016 году, более 500 миллионов аккаунтов) пароли были захешированы слабым алгоритмом, что позволило их восстановить. В CTF-задачах моделируются именно такие ошибки.

В терминах MITRE ATT&CK атаки на хеширование CTF-задачи покрывают несколько техник: Password Cracking (T1110.002, Credential Access) для словарных и brute-force атак, Exploitation for Credential Access (T1212) для эксплуатации криптографических слабостей, и Weaken Encryption (T1600) как общий принцип ослабления криптозащиты.

Место атаки на хеширование в цепочке CTF-задачи

В реальном пентесте взлом хеша — этап credential access: дамп паролей из SAM (T1003.002) или /etc/shadow (T1003.008) с последующим Pass the Hash (T1550.002, Lateral Movement). В CTF цепочка короче, но логика та же:

1. Получение хеша — из исходников, трафика, базы данных
2. Идентификация алгоритма — длина, формат, контекст приложения
3. Классификация атаки — rainbow table, brute force, collision, length extension
4. Эксплуатация и получение флага

Новичок видит хеш и запускает hashcat на перебор. Опытный CTF-игрок сначала смотрит на контекст задачи: нужна атака на прообраз или коллизия? Это два принципиально разных подхода с разными инструментами, и путать их — терять время.

Радужные таблицы и CrackStation: взлом хешей в CTF за секунды

Радужная таблица — предвычисленная структура для поиска прообраза хеша без полного перебора. Вместо хранения всех пар «пароль — хеш» используются цепочки с функцией редукции: компромисс между временем поиска и объёмом хранилища.

CrackStation онлайн и другие сервисы для CTF

CrackStation (crackstation.net) — первое, куда идёшь, встретив неизвестный хеш на CTF. Сервис содержит таблицу из порядка 15 миллиардов записей, покрывающую словарные слова, распространённые пароли и их вариации. Поддерживает MD5, SHA1, SHA256 и другие алгоритмы. Альтернативы: hashes.com, cmd5.org, hashkiller.io.

На Jeopardy-CTF, где разрешён интернет, проверка через онлайн-сервисы — первые 30 секунд работы. Если хеш — MD5 от словарного слова или короткой строки, результат мгновенный. Не изящно, зато приносит очки.

[Применимо: Jeopardy CTF с доступом в интернет, несолёные хеши стандартных алгоритмов]

Когда радужные таблицы не работают

Радужные таблицы бесполезны в трёх случаях:

Соль (salt). Если хеш вычислен как H(salt || password), предвычисленная таблица не поможет — каждая соль требует отдельной таблицы. По данным SecureFlag, «data to be hashed should incorporate a salt so, even if the input is the same, the algorithm will produce a different hash.» В CTF наличие соли — сигнал переходить к hashcat или John the Ripper.

Нестандартный алгоритм. Сервер использует кастомную хеш-функцию (частая ситуация в задачах на стыке reverse и crypto) — онлайн-таблицы бесполезны. Нужен анализ кода и написание собственного решателя.

Длинный или сложный пароль. Радужные таблицы покрывают ограниченное пространство. Для строк длиннее 12-14 символов из расширенного алфавита покрытие стремится к нулю.

В продакшене радужные таблицы практически бесполезны — bcrypt, scrypt, argon2 делают их нерелевантными. Но в CTF они остаются рабочим инструментом, потому что задачи намеренно используют слабые алгоритмы хеширования.

MD5 коллизии в CTF: birthday attack и практическая эксплуатация

Birthday attack — почему 2^64, а не 2^128

Birthday attack — фундаментальная атака на коллизионную стойкость хеш-функций. Для хеша с выходом n бит ожидаемое число операций для нахождения коллизии — 2^(n/2), а не 2^n. Для MD5 (128 бит) это 2^64 вместо 2^128 — разница в 2^64 раз.

Как показывает David Buchanan в исследовании по коллизиям усечённых хешей, наивный birthday brute force для 32-битного усечённого SHA-256 находит коллизию за 0.066 секунды: каждый новый хеш проверяется на совпадение со всеми ранее вычисленными, что даёт сложность O(2^(n/2)). Проблема масштабирования — в памяти: для полного 128-битного MD5 birthday brute force потребует хранить порядка 2^64 записей (петабайты). Поэтому на практике применяют алгоритмы вроде Pollard's Rho с distinguished points — O(2^(n/2)) по времени, но O(1) по памяти.

Для CTF всё проще: MD5 сломан не через birthday attack, а через дифференциальный криптоанализ, дающий коллизию за секунды. Birthday attack важен для понимания принципа и для атак на усечённые или кастомные хеши.

Практический пример: два блока с одинаковым MD5

По данным SecureFlag, в 2005 году описан алгоритм генерации пар блоков по 128 байт с идентичным MD5. Классическая пара отличается всего шестью байтами, но оба блока дают один и тот же дайджест: 79054025255fb1a26e4bc422aef54eb4.

Для CTF-задач это означает: сервер проверяет, что два загруженных файла имеют одинаковый MD5, но разное содержимое — задача решается подстановкой collision pair. Готово.

Инструменты для генерации MD5 коллизий:

fastcoll (Marc Stevens) — генерирует MD5-коллизии за секунды на обычном CPU. Создаёт два файла одинакового размера с идентичным хешем. Рабочая лошадка CTF-сообщества. HashClash — фреймворк для chosen-prefix коллизий MD5. Позволяет создать два файла с произвольными разными префиксами, но одинаковым хешем. Мощнее fastcoll, но и возни с ним больше. UniColl — техника identical-prefix коллизий, позволяющая внедрить коллизию в произвольный формат файла (PDF, JPEG, PE).

Типовой сценарий CTF crypto задания: сервер принимает два файла, проверяет md5(file1) == md5(file2) и file1 != file2. Решение — fastcoll -o file1.bin file2.bin, затем добавить к каждому файлу нужный payload.

[Применимо: CTF-задачи с проверкой MD5-хеша загружаемых файлов, веб-задачи с file upload и hash comparison]

SHA1 уязвимости: SHAttered и CTF

После демонстрации SHAttered в 2017 году SHA1-коллизии тоже стали практически достижимыми, хотя значительно дороже MD5. Google потребовался эквивалент 6500 лет вычислений на одном CPU. Для CTF это значит: задачи на SHA1-коллизию обычно дают усечённый хеш (truncated SHA1) или серверный оракул, ускоряющий поиск. Полноценную SHA1-коллизию на турнире не сгенерируешь, но готовые collision pairs (из SHAttered) можно использовать, если задача построена на них.

Hash length extension attack: расширяем MAC без знания ключа

Hash length extension attack — одна из самых красивых атак в CTF-криптографии. Она эксплуатирует свойство конструкции Меркла-Дамгорда, на которой построены MD5, SHA1 и SHA256.

Суть уязвимости

Если MAC вычисляется как H(secret || message), атакующий, знающий значение хеша и длину secret, может вычислить H(secret || message || padding || extension) без знания самого secret.

Работает это потому, что Merkle-Damgard хеш обрабатывает данные блоками. Финальное состояние после обработки secret || message — это внутреннее состояние хеш-функции, с которого можно продолжить вычисление для дополнительных данных. Хеш, который видит атакующий, и есть это внутреннее состояние (с точностью до финализации).

Как это выглядит в CTF-задаче

Типичный сценарий: веб-приложение генерирует токен mac = sha256(SECRET_KEY + "user=guest&role=viewer") и отдаёт его в cookie. Задача — получить валидный токен для строки с добавленным &role=admin.

Атакующий не знает SECRET_KEY, но знает: значение mac (из cookie), предполагаемую длину ключа (подбирается от 8 до 32 байт), алгоритм (SHA256, Merkle-Damgard). Этого хватает для length extension attack.

Инструменты: hashpump и hlextend

hashpump — утилита командной строки. Принимает оригинальный хеш, длину ключа, оригинальные данные и данные для добавления. Выдаёт новый хеш и новую строку данных с padding.

hlextend — Python-библиотека, удобная для скриптования в CTF:

import hlextend
sha = hlextend.new('sha256')
# extend(append, original_data, secret_length, original_hash)
new_data = sha.extend(
    b'&role=admin',
    b'user=guest&role=viewer',
    16,                        # длина секретного ключа
    'a1b2c3d4e5f6...')         # оригинальный хеш из cookie
new_hash = sha.hexdigest()     # новый валидный MAC
# new_data содержит original + padding + extension

На практике длина ключа неизвестна. Перебор от 8 до 32 байт — 25 запросов к серверу, занимает секунды.

Когда техника НЕ работает:

HMAC. Конструкция H(K xor opad || H(K xor ipad || message)) — двойное хеширование с ключом делает length extension невозможным. Видите HMAC в исходниках — ищите другой вектор.

SHA-3 (Keccak). Использует конструкцию sponge, а не Merkle-Damgard. Иммунна к length extension.

BLAKE2/3. По данным SecureFlag, «purportedly faster than SHA-1/2/3 and immune to length extension».

[Применимо: CTF-задачи с MAC вида H(secret || message), серверы на MD5/SHA1/SHA256 без HMAC]

Hashcat и John the Ripper: крекинг хешей с GPU для CTF

Требования к окружению

• ОС: Kali Linux 2023+, Ubuntu 20.04+, Windows 10+ — hashcat работает на всех трёх
• RAM: минимум 4 ГБ, рекомендуется 8 ГБ
• GPU (для hashcat): NVIDIA с CUDA (GTX 1060 6 ГБ VRAM и выше) или AMD с OpenCL. Без GPU hashcat работает на CPU, но в 10-50 раз медленнее — для CTF часто хватает
• Версии: hashcat 6.2.6+ (активно поддерживается), John the Ripper bleeding-jumbo (регулярные коммиты в репозитории)
• Словари: rockyou.txt (14 млн паролей, входит в Kali по адресу /usr/share/wordlists/), SecLists (github.com/danielmiessler/SecLists)

Типовые режимы для CTF crypto заданий

# hashcat: MD5 (-m 0), SHA1 (-m 100), SHA256 (-m 1400)
hashcat -m 0 -a 0 hash.txt rockyou.txt          # словарная атака MD5
hashcat -m 100 -a 3 hash.txt '?a?a?a?a?a?a'     # маска SHA1, 6 символов
# john the ripper: авто-определение типа хеша
john --wordlist=rockyou.txt hash.txt
john --show hash.txt                              # показать результат

Режим -a 0 — словарная атака (dictionary), -a 3 — маска (brute force с шаблоном). Для CTF-задач обычно хватает словарной атаки с rockyou.txt или маски для коротких строк (до 8 символов).

Когда hashcat, когда john, когда CrackStation

Ситуация	Инструмент	Почему
Стандартный хеш без соли	CrackStation онлайн	Мгновенный результат, не нужен GPU
Солёный хеш, известен формат	hashcat CTF с GPU	Самый быстрый brute force
Неизвестный формат хеша	John the Ripper	Авто-определение типа
Кастомная хеш-функция из исходников	Python-скрипт	Только ручной анализ алгоритма
Нужна коллизия, а не прообраз	fastcoll / HashClash	hashcat ищет прообраз — это другая задача

Hashcat хорош для стандартных алгоритмов, но бесполезен для кастомных хеш-функций (а на CTF они встречаются постоянно). Видите в исходниках задачи нестандартные преобразования — пишите собственный скрипт на Python. И помните: hashcat не поможет, если задача требует не прообраз, а коллизию или length extension — это принципиально другие атаки.

Пошаговый алгоритм: от неизвестного хеша до флага

Шаг 1 — Идентификация алгоритма хеширования

Длина хеша в hex-символах — первый ориентир: 32 символа — MD5 или NTLM, 40 символов — SHA1, 64 символа — SHA256, 128 символов — SHA512. Инструменты hash-identifier (встроен в Kali), hashid или nth (Name That Hash) автоматизируют определение. Контекст задачи подсказывает: PHP-приложение скорее всего использует MD5, Django — SHA256 с солью через PBKDF2.

И ещё момент, на котором регулярно спотыкаются (в разборе OTUS CTF это тоже всплывало): иногда то, что выглядит как хеш, оказывается простым hex-кодированием строки. Прежде чем запускать тяжёлую артиллерию, проверьте: echo "666c6167" | xxd -r -p выдаст flag. Обидно тратить полчаса на hashcat, когда ответ — в xxd.

Шаг 2 — Выбор метода атаки на хеширование

Decision tree, который отличает опытного CTF-игрока от новичка:

Вопрос 1. Нужен прообраз конкретного хеша (пароль, строка)? Да — радужная таблица, затем словарь, затем brute force.

Вопрос 2. Нужны два разных входа с одинаковым хешем? Да — коллизия. Для MD5 — fastcoll. Для SHA1 — усечённый хеш или готовые collision pairs.

Вопрос 3. Есть MAC формата H(secret || data), нужно добавить данные? Да — hash length extension attack через hashpump.

Вопрос 4. Хеш кастомный (из реверса исходников)? Да — анализ алгоритма, поиск обратимых операций, Z3 solver для символьного вычисления.

Шаг 3 — Порядок эксплуатации

Самая частая ошибка на CTF — запускать тяжёлый инструмент до лёгкого:

1. Вбить хеш в CrackStation / hashes.com (10 секунд)
2. Если не нашлось — john --wordlist=rockyou.txt (1-5 минут)
3. Если не нашлось — hashcat с GPU и расширенным словарём или маской (минуты-часы)
4. Параллельно со всеми шагами: перечитать описание задачи — может, она не про прообраз вообще?

На CTF шаг 4 надо делать первым. Описание задачи, исходники, формат ввода — всё это подсказывает тип атаки до запуска любого инструмента. Я видел, как команда два часа крутила hashcat на SHA256, а задача решалась length extension за пять минут. Читайте условие.

Ограничения: когда атаки на хеширование не дают флаг

Хеш как отвлечение. В задаче фигурирует хеш, но уязвимость — в логике приложения: SQL-инъекция, path traversal, ошибка авторизации. Не каждая задача с хешем — задача на хеширование. Иногда хеш — просто красивый фантик.

Сильные алгоритмы паролей. bcrypt, scrypt, argon2 спроектированы для медленного вычисления. По данным SecureFlag, argon2 — победитель Password Hashing Competition 2015, позволяет точно настроить вычислительную нагрузку. Brute force bcrypt с cost factor 12 — десятки хешей в секунду против миллиардов для MD5. Если в задаче bcrypt — ищите другой вектор, перебор тут не вариант.

Правильный HMAC. HMAC-SHA256 не уязвим к length extension. Видите HMAC — hashpump бесполезен, ищите утечку ключа или логическую ошибку.

SHA-3 и BLAKE2. По данным Electric Coin Company, «ни одна новая хеш-функция, разработанная после примерно 2000 года, не поддалась коллизионным атакам». SHA-3 (sponge-конструкция) и BLAKE2/3 иммунны к length extension и не имеют известных практических атак. На хороших CTF-турнирах задачи с современными алгоритмами тоже встречаются, но уязвимость будет в реализации (padding oracle, timing attack, неправильное использование API), а не в самой хеш-функции.

Полтора года решаю CTF-задачи категории crypto на уровне medium-hard, и картина стабильная: команды делятся на «крекеров» и «математиков». Первые умеют запустить hashcat с правильным -m, но не отличают collision resistance от pre-image resistance. Вторые знают теорию Меркла-Дамгорда, но не могут собрать рабочий exploit за полчаса турнира. Между ними — пропасть. Реальный навык CTF crypto — мгновенная классификация: вижу H(secret || data) в исходниках — length extension, а не brute force; вижу проверку md5(f1) == md5(f2) && f1 != f2 — коллизия, и мне нужен fastcoll, а не rockyou.txt. Большинство гайдов по «взлому хешей» учат крекать пароли, но не учат эксплуатировать криптографические конструкции. Password cracking — про вычислительную мощность. Эксплуатация слабой криптографии — про понимание архитектуры. На CTF побеждает второе, а первое можно вообще делегировать облачному GPU. Если writeups уже не дают роста и хочется пройти полную цепочку веб-атаки от разведки до эксплуатации — WAPT на codeby.school даёт 30 уровней прогрессии с лабой на каждый кейс.

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