Атака удлинения сообщения

Атака удлинения сообщения (англ. length extension attack) — это тип криптографической атаки на хеш-функции, построенные по схеме Меркла — Дамгора, которая позволяет злоумышленнику, зная хеш некоторого сообщения, но не зная самого сообщения, вычислить хеш нового сообщения, полученного путём дописывания к исходному сообщению дополнительных данных. Атака возможна из-за того, что в таких хеш-функциях итоговое значение хеша вычисляется путём последовательного применения сжимающей функции к блокам данных, причём последний блок содержит длину исходного сообщения, а итоговое состояние хеш-функции (внутреннее состояние) становится известным атакующему.

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

Схема Меркла — Дамгора

Большинство классических хеш-функций, таких как MD5, SHA-1 и семейство SHA-2, основаны на конструкции Меркла — Дамгора. В этой конструкции сообщение разбивается на блоки фиксированного размера (например, 512 бит для MD5 и SHA-1, 1024 бита для SHA-256). Если длина сообщения не кратна размеру блока, к нему добавляется дополнение (padding), которое включает в себя единичный бит, нули и 64-битное (или 128-битное) представление длины исходного сообщения в битах. Это дополнение гарантирует, что сообщение будет иметь длину, кратную размеру блока.

Хеширование происходит следующим образом:

1. Инициализируется начальное состояние (IV — initial vector) — фиксированная константа, определённая в спецификации хеш-функции.
2. Каждый блок сообщения (включая блок дополнения) последовательно обрабатывается сжимающей функцией, которая принимает текущее состояние и блок сообщения и выдаёт новое состояние.
3. После обработки всех блоков итоговое состояние становится хеш-значением.

Суть атаки

Атака удлинения сообщения использует тот факт, что итоговое состояние хеш-функции после обработки всех блоков сообщения является одновременно и начальным состоянием для обработки следующего блока. Если атакующий знает хеш исходного сообщения H(M), он может:

1. Восстановить внутреннее состояние хеш-функции, соответствующее этому хешу (для большинства хеш-функций это просто само значение хеша).
2. Продолжить хеширование, начиная с этого состояния, обрабатывая новые блоки данных, которые он сам выбирает (M').
3. В результате он получит хеш H(M || padding || M'), где padding — это дополнение, которое было бы добавлено к исходному сообщению M в процессе хеширования. Атакующий не знает M, но может вычислить padding для него, зная только длину M (или предполагая её).

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

Условия для атаки

Для успешного проведения атаки удлинения сообщения необходимо выполнение следующих условий:

• Хеш-функция должна быть построена по схеме Меркла — Дамгора (или аналогичной, где итоговое состояние равно внутреннему состоянию).
• Хеш-функция не должна быть устойчивой к удлинению (length extension resistant). Современные хеш-функции, такие как SHA-3 (Keccak) и BLAKE2, спроектированы так, чтобы быть устойчивыми к этой атаке.
• Атакующий должен знать хеш исходного сообщения H(M) и длину M (или иметь возможность её оценить).
• Атакующий должен иметь возможность дописать произвольные данные к сообщению.

Примеры уязвимых протоколов

Атака удлинения сообщения представляет серьёзную угрозу для протоколов, которые используют хеш-функции в качестве механизма аутентификации без дополнительных мер защиты. Классический пример — уязвимость в протоколах, использующих MAC-конструкцию (Message Authentication Code) вида H(secret || message), где secret — секретный ключ, а message — сообщение. Если злоумышленник перехватывает пару (сообщение, MAC) и знает длину секрета, он может вычислить MAC для нового сообщения message || padding || extra_data, где extra_data — произвольные данные, добавляемые злоумышленником. Атакующий не знает секрета, но может подделать аутентификацию для нового сообщения.

Уязвимые протоколы

• Аутентификация по паролю в некоторых старых протоколах: Например, в протоколе HTTP Digest Authentication (RFC 2617) в некоторых конфигурациях использовалась схема, уязвимая к атаке удлинения.
• Протоколы, использующие H(secret || message) для MAC: Многие реализации протоколов, таких как Flickr API, Amazon Web Services (AWS) Signature Version 1 и 2, были уязвимы к этой атаке. Впоследствии они были заменены на более безопасные схемы, например, HMAC (Hash-based Message Authentication Code).
• Протоколы целостности данных: Если злоумышленник может модифицировать сообщение и пересчитать хеш, используя атаку удлинения, он может нарушить целостность данных, не зная исходного содержимого.

Защита от атаки

Устойчивые хеш-функции

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

• SHA-3 (Keccak): Использует губчатую конструкцию (sponge construction), которая не позволяет восстановить внутреннее состояние из хеша.
• BLAKE2: Использует модифицированную схему, в которой итоговое состояние не равно внутреннему состоянию после обработки всех блоков.
• SHA-256/512 в режиме SHA-256/512-t (усечённый): Усечение хеша до меньшего размера может частично затруднить атаку, но не устраняет её полностью.

Безопасные MAC-конструкции

Для аутентификации сообщений следует использовать схемы, не подверженные атаке удлинения:

• HMAC (Hash-based Message Authentication Code): HMAC(K, M) = H((K' ⊕ opad) || H((K' ⊕ ipad) || M)), где K' — ключ, дополненный до размера блока, opad и ipad — константы. Эта конструкция не уязвима к атаке удлинения, так как хеш применяется дважды, и внутреннее состояние не раскрывается.
• KMAC (Keccak Message Authentication Code): Основан на SHA-3 и также устойчив к атаке.
• Использование H(message || secret): Вместо H(secret || message) можно использовать H(message || secret), что делает атаку удлинения невозможной, так как атакующий не может дописать данные после секрета. Однако эта схема уязвима к другим атакам (например, к атакам на основе коллизий), поэтому не рекомендуется.

Дополнительные меры

• Использование соли (salt): Включение случайной соли в сообщение перед хешированием может затруднить атаку, но не является полной защитой.
• Ограничение длины сообщения: Если длина сообщения фиксирована, атакующий не может дописать данные, не нарушив формат.
• Использование цифровых подписей: Вместо хешей для аутентификации можно использовать асимметричную криптографию (например, RSA или ECDSA), которая не подвержена атаке удлинения.

История и известные случаи

Атака удлинения сообщения была впервые описана в криптографической литературе в 1990-х годах. Она стала широко известна после публикации в 2009 году работы «Hash Length Extension Attacks» (M. Stevens, A. Lenstra, B. de Weger), где были продемонстрированы практические атаки на протоколы, использующие MD5 и SHA-1. В 2011 году атака была использована для взлома протокола аутентификации в некоторых реализациях Flickr API. В 2014 году атака была продемонстрирована на протоколе HTTP Digest Authentication, что привело к его замене на более безопасные схемы.

Критика и ограничения

Атака удлинения сообщения не является универсальной. Она не работает против хеш-функций, устойчивых к удлинению, таких как SHA-3. Кроме того, для её успешного проведения атакующий должен знать точную длину исходного сообщения, что не всегда возможно. В некоторых случаях атакующий может перебирать возможные длины, что увеличивает сложность атаки, но не делает её невозможной. Также атака требует, чтобы дополнение (padding) было корректно вычислено, что может быть затруднено, если формат сообщения строго определён.

Источники

1. M. Stevens, A. Lenstra, B. de Weger. «Hash Length Extension Attacks». 2009.
2. NIST. «FIPS PUB 180-4: Secure Hash Standard (SHS)». 2015.
3. NIST. «FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions». 2015.
4. RFC 2104: «HMAC: Keyed-Hashing for Message Authentication». 1997.
5. RFC 2617: «HTTP Authentication: Basic and Digest Access Authentication». 1999.
6. J. Kelsey, B. Schneier. «Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work». 2005.