Хеш-функции: коллизии и length extension

Хеш-функция должна быть тремя вещами одновременно: сжимать данные в фиксированный дайджест, не давать восстановить прообраз и не давать найти два разных сообщения с одним дайджестом. Криптографические протоколы полагаются ровно на эти три свойства — и рушатся, когда конструкция даёт четвёртое, о котором никто не просил.

Тема разбирает SHA-256 изнутри: функцию сжатия, дополнение Меркла — Дамгора, итеративное вычисление. Из итеративности растёт первая атака — удлинение сообщения: если тег вычислен как SHA-256(key || msg), противник, зная msg и тег, достраивает сообщение и получает валидный тег, не зная ключа. Вторая атака — коллизии: метод дней рождения даёт их за 2^(n/2) операций, а для усечённых хешей это буквально минуты. Третья часть — деревья Меркле: как из «неудобного» свойства хешей сделать прозрачный журнал, в котором доказуемо нет подмены.

Свойства хеш-функции

Три задачи

Для хеш-функции H: {0,1}* → {0,1}^n различают три задачи. Прообраз: по y найти m с H(m) = y — сложность 2^n. Второй прообраз: по m найти m' ≠ m с H(m') = H(m) — тоже 2^n. Коллизия: найти любые m ≠ m' с равными хешами — 2^(n/2) по парадоксу дней рождения. Коллизия — самая дешёвая задача, и именно поэтому 128-битный хеш даёт только 64 бита стойкости к коллизиям.

Хеш не шифрует и не аутентифицирует сам по себе: он сжимает. Аутентификацию даёт конструкция поверх хеша — HMAC, подпись, дерево Меркле.

Требования к протоколам

Подпись документа требует стойкости ко второму прообразу. Прозрачный журнал — стойкости к коллизиям. Хранение паролей — медленности и соли, а не «криптостойкости» хеша. Разные задачи — разные требования, и путать их дорого: MD5 был приемлем для checksum и катастрофой для подписи.

Merkle — Дамгор и SHA-256

Функция сжатия

SHA-256 обрабатывает сообщение блоками по 64 байта. Внутреннее состояние — восемь 32-битных слов H_0…H_7, инициализированных константами FIPS 180-4. Каждый блок расширяется до 64 слов расписания, затем 64 раунда перемешивают состояние: сложения по модулю 2^32, XOR, циклические сдвиги и выборки Ch/Maj ¹. Функция сжатия f(state, block) — это и есть вся криптографическая начинка; всё остальное — режим итерации.

Дополнение фиксирует длину: байт 0x80, нули, затем 64-битная длина сообщения в битах, чтобы итог делился на 64. Без длины два разных сообщения могли бы дать одинаковую последовательность блоков.

Итеративность и её цена

Схема Меркла — Дамгора: h_0 = IV, h_i = f(h_{i-1}, M_i), дайджест — h_k. Это позволяет хешировать поток и не хранить сообщение целиком. Плата — структурная: состояние после обработки префикса полностью определяет продолжение; Келси и Шнайер показали, что из этого следуют и атаки на второй прообраз ³. Если противник знает h_i, он может продолжить вычисление на любых данных, как будто префикс уже обработан.

Именно это свойство эксплуатирует атака удлинения. Оно не является «багом SHA-256»: так устроена любая итеративная хеш-функция. Лечится оно не изменением хеша, а правильной конструкцией MAC.

Удлинение сообщения

Схема атаки

Пусть сервис выдаёт пропуск msg и тег tag = SHA-256(key || msg), а затем проверяет пару целиком. Противник знает msg, tag и не знает key. Он строит new_msg = msg || padding(len(key) + len(msg)) || suffix и вычисляет new_tag, продолжив хеширование с состояния, восстановленного из tag, на данных suffix. Ключ при этом не нужен: он уже «съеден» вместе с префиксом.

Длина ключа неизвестна, но она коротка: перебор от 1 до 64 байт занимает мгновения. Для каждой гипотезы строится своя попытка, и сервис сам скажет, какая верна.

Условия и последствия

Атака работает, когда MAC вычисляется как «хеш от ключа и сообщения» — в любом порядке, где ключ стоит в начале. Она не работает с HMAC, потому что HMAC хеширует ключ дважды и внешний слой не позволяет продолжить вычисление; не работает и с SHA-3, потому что губка не даёт доступа к состоянию между блоками ⁷.

SHA-3 устроен иначе: губка (sponge) с внутренним состоянием, из которого наружу отдаётся только часть, поэтому продолжить вычисление нельзя ⁸.

Правило: хеш-функция — не MAC. Если нужен MAC, берётся HMAC или AEAD; если нужна подпись — подписывается хеш, но не «хеш с секретом внутри».

Коллизии и дни рождения

Парадокс дней рождения

Если n бит хеша, то после примерно 1.18·2^(n/2) случайных сообщений вероятность коллизии превышает половину. Для 256-битного хеша это 2^128 — недостижимо; для усечённого до 32 бит — около 77 тысяч попыток, то есть секунды.

Коллизия ломает не конфиденциальность, а целостность: два разных документа с одинаковым хешем проходят любую проверку, основанную на хеше. Для подписи это означает возможность подсунуть один документ вместо другого.

Ро-метод

Хранить все значения дорого; ро-метод Флойда находит цикл в последовательности x → h(encode(x)) за O(1) памяти. Вход в цикл даёт два разных прообраза одного значения — коллизию. Для 24–32 бит это учебная задача на минуту; для 256 бит — недостижимо, и это ровно та граница, на которой держится стойкость.

Реальные коллизии

MD5 практически ломается с 2004 года ⁴, и это использовали: в 2012 году вредонос FLAME подписывался поддельным сертификатом, построенным на коллизии MD5, выданным удостоверяющим центром ⁶. SHA-1 получил первую практическую коллизию в 2017 году (SHAttered): два разных PDF с одинаковым SHA-1, стоимость — около 110 тысяч GPU-лет ⁵. Обе истории закончились отзывом алгоритмов из протоколов, но не мгновенно.

Деревья Меркле

Зачем дерево

Хеш одного файла проверяется легко, но если файлов миллион — проверять все нельзя. Дерево Меркле позволяет доказать включение одного листа за O(log n) хешей: корень публикуется, путь аудита передаётся вместе с листом, проверяющий пересчитывает корень.

Такая конструкция лежит в основе Certificate Transparency: журнал сертификатов публикует корень, а любой может проверить, что его сертификат включён и что журнал не подменяет историю ². Важная деталь — доменная сепарация: листья хешируются с префиксом 0x00, узлы — с 0x01, иначе можно подставить узел вместо листа (атака второй прообраз).

Что даёт и чего не даёт

Дерево даёт доказуемость включения и согласованности, но не конфиденциальность: листья видны. Оно не защищает от «журнала, который вообще не существует», — для этого нужны сплетни (gossip) и подписанные контрольные точки.

Итоги темы

• Хеш решает три задачи с разной сложностью; коллизии — самая дешёвая (2^(n/2)).
• SHA-256 итеративен: состояние после префикса определяет продолжение.
• SHA-256(key || msg) — не MAC: атака удлинения достраивает сообщение без ключа.
• HMAC и губка SHA-3 закрывают удлинение конструктивно.
• Коллизии ломают целостность; MD5 и SHA-1 сломаны практически.
• Дерево Меркле превращает хеш в доказуемый журнал; доменная сепарация обязательна.

Литература

1. NIST. FIPS 180-4: Secure Hash Standard. 2015. — SHA-256, функция сжатия и дополнение.
2. RFC 9162: Certificate Transparency Version 2.0. 2021. — деревья Меркле, пути аудита и доказательства согласованности.
3. Kelsey J., Schneier B. Second Preimages on n-bit Hash Functions for Much Less than 2^n Work. EUROCRYPT 2005. — структурные атаки на итеративные хеши.
4. Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. 2004. — практический взлом MD5.
5. Stevens M., Bursztein E., Karpman P., Albertini A., Markov Y. The First Collision for Full SHA-1. CRYPTO 2017. — SHAttered.
6. Sotirov A. et al. MD5 Considered Harmful Today. 2008. — поддельный сертификат для FLAME.
7. Krawczyk H., Bellare M., Canetti R. RFC 2104: HMAC: Keyed-Hashing for Message Authentication. 1997. — почему HMAC устойчив к удлинению.
8. NIST. FIPS 202: SHA-3 Standard. 2015. — губка, устойчивая к удлинению конструктивно.

Дополнительные материалы к апокрифу 7

Вопросы для самопроверки

1. Какие три задачи решает хеш-функция и какая из них самая дешёвая?
2. Почему 128-битный хеш даёт 64 бита стойкости к коллизиям?
3. Чем функция сжатия отличается от режима итерации?
4. Зачем в дополнении SHA-256 участвует длина сообщения?
5. Почему дайджест можно использовать как внутреннее состояние?
6. Как работает атака удлинения сообщения?
7. Почему перебор длины ключа не мешает атаке?
8. Почему SHA-256(key || msg) не является MAC?
9. Как HMAC мешает продолжить вычисление?
10. Почему SHA-3 устойчив к удлинению конструктивно?
11. Что такое доменная сепарация в дереве Меркле?
12. Сколько хешей в доказательстве включения для n листьев?
13. Что доказывает контрольная точка журнала и чего она не доказывает?
14. Почему MD5 и SHA-1 выведены из протоколов?
15. Что такое proof of work и почему среднее число попыток равно 2^k?

Глоссарий темы

Шпаргалка

cp sha256_template.py sha256.py           && python3 check_hashes.py TestSHA256 TestPadding
cp length_ext_template.py length_ext.py   && python3 check_hashes.py TestLengthExt
cp collision_template.py collision.py     && python3 collision.py birthday 24
cp merkle_template.py merkle.py           && python3 check_hashes.py TestMerkle

Что почитать и посмотреть

• FIPS 180-4 — SHA-256 с константами и описанием раундов.
• RFC 2104 — HMAC и объяснение, почему он не подвержен удлинению.
• FIPS 202 — SHA-3 и конструкция губки.
• RFC 9162 — Certificate Transparency: деревья, пути аудита, доказательства согласованности.
• Kelsey, Schneier. Second Preimages on n-bit Hash Functions (2005) — почему итеративность опасна.
• Wang et al. Collisions for MD5 (2004) — как ломали MD5.
• Stevens et al. The First Collision for Full SHA-1 (2017) — SHAttered и его стоимость.
• Документация hashlib — https://docs.python.org/3/library/hashlib.html.

Углубление: почему HMAC устроен именно так

Наивная попытка «защитить» хеш от удлинения — хешировать msg || key вместо key || msg. Это тоже плохо: при таком порядке возможна атака на основе коллизий в самом сообщении, а для некоторых хешей — и подбор суффикса. HMAC решает задачу иначе: HMAC(K, M) = H((K ⊕ opad) || H((K ⊕ ipad) || M)). Внутренний хеш сжимает сообщение вместе с ключом, внешний — хеширует результат снова с ключом. Противник, знающий внутренний хеш, не может продолжить вычисление, потому что внешний слой начинается с блока, зависящего от ключа, а не от известных данных.

Доказательство стойкости HMAC (Беллар, Канетти, Кравчик) показывает: если функция сжатия стойка как PRF при известном IV, то HMAC — стойкий MAC. Это важный пример того, как из «слабого» примитива (итеративного хеша) получается стойкая конструкция за счёт правильного обрамления.

Углубление: зачем деревьям Меркле доменная сепарация

Без префиксов лист и узел хешируются одинаково: H(data) и H(left || right). Тогда противник может предъявить узел как лист: внутренний хеш H(L0 || L1) выглядит как хеш «сообщения» L0 || L1. Проверяющий, которому доказывают включение, не отличит одно от другого, и доказательство перестаёт что-либо значить.

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

Углубление: почему коллизии дешевле прообраза

Интуиция подсказывает, что найти «ещё одно сообщение с тем же хешем» так же трудно, как найти прообраз. Разница в том, что при поиске коллизии противник сравнивает все пары найденных значений между собой. Если собрать q значений, число пар — q(q−1)/2, а вероятность совпадения растёт как q^2/2^n. Приравняв к единице, получаем q ≈ 2^(n/2).

Отсюда практическое правило: длина хеша должна быть вдвое больше требуемого уровня стойкости к коллизиям. 256-битный SHA-256 даёт 128 бит коллизионной стойкости — этого достаточно; 128-битный MD5 давал 64 бита, и этого не хватило.

Лабораторная работа 7. Хеш, который можно продолжить

• Раздел курса: апокриф 7 «Хеш-функции: коллизии и length extension»

Введение

«Сейф» выдаёт пропуска к файлам: строка user=bob&role=reader&file=report.pdf и тег к ней. Тег считается как SHA-256(ключ || сообщение) — «хеш с секретом, чем не MAC». Мэллори получает свой пропуск, достраивает к нему &role=admin и предъявляет сервису валидный тег, не зная ключа: SHA-256 итеративен, и состояние после ключ || сообщение можно продолжить.

Работа идёт от устройства хеша к последствиям. Сначала SHA-256 своими руками: дополнение, функция сжатия, продолжение с произвольного состояния. Потом атака удлинения против учебного сервиса и проверка, что HMAC и SHA-3 ей не подвержены. Затем коллизии: метод дней рождения и ро-метод на усечённом хеше. В продвинутой части — дерево Меркле и прозрачный журнал, где хеш работает уже на пользу целостности.

Части: SHA-256, удлинение сообщения, коллизии, дерево Меркле, продвинутая.

Цель работы

Научиться объяснять, почему хеш-функция не является MAC, и показывать это рабочей атакой, а также оценивать стойкость усечённых хешей.

После выполнения работы получится:

• реализовывать SHA-256 по FIPS 180-4 и сверять с hashlib;
• продолжать хеширование с произвольного состояния;
• подделывать MAC вида SHA-256(key || msg), перебирая длину ключа;
• показывать, что HMAC и SHA-3 к удлинению устойчивы;
• находить коллизии усечённого хеша за 2^(n/2) операций;
• строить дерево Меркле и проверять доказательство включения.

Теоретический минимум

Разделы «Свойства хеш-функции», «Merkle — Дамгор и SHA-256», «Удлинение сообщения», «Коллизии и дни рождения», «Деревья Меркле» апокрифа 7. Соотношения:

h_0 = IV;  h_i = f(h_(i−1), M_i);  H(M) = h_k
padding: 0x80, нули, длина в битах (64 бита big-endian)
tag = SHA-256(key || msg)              уязвимая схема
new_msg = msg || padding(len(key)+len(msg)) || suffix
≈1.18·2^(n/2)                          число попыток до коллизии

Перечень оснащения

Ubuntu 24.04, Python 3.10+. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-07 && cd ~/lab-apocrypha-07
unzip ~/lr-env.zip
cp sha256_template.py sha256.py
python3 check_hashes.py TestSHA256

Заготовки копируются в файлы без суффикса _template: sha256.py, length_ext.py, collision.py, merkle.py.

Порядок выполнения работы

В журнал записывайте: длину дополнения для контрольных значений, состояние, с которого продолжили хеширование, угаданную длину ключа и число попыток до коллизии. Для каждой атаки — что именно утекло: продолжение состояния, ключ (не утекает) или целостность.

Часть 1. SHA-256

Задание

1. Реализуйте padding(msg_len): байт 0x80, нули, 64-битная длина в битах; проверьте, что (msg_len + len(padding)) % 64 == 0.
2. Реализуйте compress(state, block) строго по FIPS 180-4: расписание из 64 слов, 64 раунда, прибавление исходного состояния.
3. Реализуйте sha256(msg, state=IV, prefix_len=0) — с возможностью продолжить вычисление с заданного состояния.
4. Запустите python3 check_hashes.py TestSHA256 TestPadding: совпадение с hashlib на пустой строке, abc, килобайтном сообщении и всех байтах.
5. Объясните, зачем в дополнении участвует длина сообщения и что произойдёт, если её убрать.
6. Ответьте: почему state_from_digest — это просто struct.unpack(">8I", digest), то есть никакого «обратного хеша» не требуется.

Что должно получиться

Работающая реализация, совпадающая с hashlib на всех контрольных значениях, и понимание, что дайджест — это и есть состояние.

Часть 2. Удлинение сообщения

Задание

1. Изучите mac_service.py: три схемы (sha256, sha3, hmac), длина ключа случайна от 8 до 40 байт, при разборе повтор поля получает последнее значение.
2. Реализуйте forge(msg, tag, key_len, suffix): склейте msg, дополнение для key_len + len(msg), затем suffix; тег продолжите с состояния tag.
3. Реализуйте attack: получите пропуск, переберите длину ключа от 1 до 64, проверяя попытку через svc.verify.
4. Запустите python3 check_hashes.py TestLengthExt: sha256 должен подделываться, sha3 и hmac — нет.
5. Ответьте: почему атака не требует знания ключа и почему перебор длины ключа не мешает.
6. Объясните, что именно ломает HMAC: как два прохода хеширования и внешний слой мешают продолжить состояние.

Что должно получиться

Поддельный пропуск с role=admin, принятый сервисом, и сравнение трёх схем MAC.

Часть 3. Коллизии

Задание

1. Реализуйте birthday(bits): словарь «хеш → сообщение», случайный старт, перебор encode(start + i).
2. Запустите python3 collision.py birthday 24 и запишите число попыток. Сравните с 2^12.
3. Реализуйте rho(bits): поиск цикла Флойда, затем поиск входа в цикл; верните два разных прообраза.
4. Запустите python3 check_hashes.py TestCollision: обе функции должны давать коллизию на 24 битах.
5. Оцените, сколько времени займёт коллизия для 32, 40 и 64 бит при миллионе хешей в секунду.
6. Ответьте: почему для подписи критична стойкость ко второму прообразу, а для прозрачного журнала — к коллизиям, и что это меняет в требованиях к длине хеша.

Что должно получиться

Две найденные коллизии, таблица оценок по битовым длинам и понимание, что 128-битный хеш даёт только 64 бита коллизионной стойкости.

Часть 4. Дерево Меркле

Задание

1. Реализуйте leaf_hash и node_hash с доменной сепарацией: префиксы 0x00 и 0x01.
2. Реализуйте root(leaves) по рекурсивному определению через split_point.
3. Реализуйте proof(m, leaves) и verify(data, m, n, path, expected_root) по RFC 9162.
4. Запустите python3 check_hashes.py TestMerkle: доказательство для листа 2 проверяется, чужой лист отвергается.
5. Уберите доменную сепарацию и покажите, что лист можно подставить вместо узла. Верните её.
6. Ответьте: сколько хешей в пути аудита для миллиона листьев и почему это логарифм.

Что должно получиться

Работающее дерево, проверка включения и понимание, зачем нужны префиксы листьев и узлов.

Часть 5. Продвинутая: прозрачный журнал и proof of work

Задание

1. Соберите журнал из 1000 записей: корень Меркле, путь аудита для случайной записи, проверка.
2. Реализуйте контрольную точку: подпись корня и номера дерева. Объясните, зачем нужна подпись, если корень и так хеш.
3. Разберите доказательство согласованности между двумя контрольными точками: что оно показывает и чего не показывает.
4. Реализуйте pow_template.py: подбор nonce для k ведущих нулей. Оцените среднее число попыток как 2^k и сравните с измеренным.
5. Сформулируйте, почему для журнала нужны и дерево, и сплетни между клиентами.

Что должно получиться

Работающий журнал с проверяемыми контрольными точками и понимание границ: дерево доказывает включение, но не существование журнала.

Журнал работы

Фиксируйте: длину дополнения, угаданную длину ключа, число попыток до коллизии, глубину дерева. Провал проверки записывайте причиной — перепутано порядок байт в длине, неверная инициализация w[16..63], потерян префикс домена, — а не отметкой «не вышло».

Контрольные вопросы

1. Чем отличаются задачи прообраза, второго прообраза и коллизии?
2. Почему коллизия требует 2^(n/2) операций?
3. Что делает функция сжатия SHA-256 и что — режим итерации?
4. Зачем в дополнении SHA-256 длина сообщения?
5. Почему дайджест можно использовать как состояние?
6. Как работает атака удлинения сообщения?
7. Почему SHA-256(key || msg) — не MAC?
8. Чем HMAC защищён от удлинения?
9. Почему SHA-3 устойчив к удлинению конструктивно?
10. Что даёт доменная сепарация в дереве Меркле?
11. Сколько хешей в доказательстве включения для n листьев?
12. Почему MD5 и SHA-1 выведены из протоколов, а SHA-256 — нет?