Атака на основе расширения длины

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

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

Хеш-функции семейства MD5, SHA-1 и SHA-2 (кроме SHA-3) основаны на конструкции Меркла — Дамгора. В этой конструкции сообщение разбивается на блоки фиксированного размера (например, 512 или 1024 бита), каждый блок обрабатывается сжатием, а результат передаётся на следующий блок. Последний блок дополняется паддингом (выравниванием) до полного размера, включая длину исходного сообщения.

Атака возможна, если злоумышленник знает:

• хеш H(M) исходного сообщения M;
• длину M (или может её оценить);
• алгоритм хеширования.

Злоумышленник может:

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

Условия уязвимости

Атака применима к хеш-функциям, которые:

• используют конструкцию Меркла — Дамгора (MD5, SHA-1, SHA-256, SHA-512);
• не имеют механизма финализации, предотвращающего продолжение вычисления (например, SHA-3 на основе губки не уязвим);
• не защищены от восстановления внутреннего состояния (например, через HMAC).

Критическим условием является то, что злоумышленник не знает исходное сообщение M, но может вычислить хеш от M || pad || X, не зная M. Это возможно только если хеш-функция не скрывает внутреннее состояние.

Примеры уязвимых конструкций

Конструкция H(секрет || сообщение)

Наиболее распространённый сценарий — использование хеш-функции для вычисления кода аутентичности сообщения (MAC) по схеме H(K || M), где K — секретный ключ, M — сообщение. Если злоумышленник знает H(K || M) и длину K (или может её оценить), он может вычислить H(K || M || pad || X) для произвольного X, не зная K. Это позволяет подделать MAC для сообщения M || pad || X, что нарушает аутентичность.

Пример: в протоколе Flickr API (2009) использовалась конструкция MD5(secret || message) для аутентификации запросов. Атака позволила злоумышленникам выполнять несанкционированные действия, подделывая подписи.

Протоколы аутентификации

В некоторых протоколах (например, в ранних версиях SSH, IPsec) использовалась конструкция H(ключ || сообщение) для генерации ключей сеанса. Атака расширения длины позволяла предсказывать последующие ключи, зная первый.

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

Использование HMAC

HMAC (Hash-based Message Authentication Code) — стандартный механизм, предотвращающий атаку расширения длины. Он вычисляется по формуле HMAC(K, M) = H((K' ⊕ opad) || H((K' ⊕ ipad) || M)), где K' — ключ, дополненный до размера блока, opad и ipad — константы. Двойное хеширование и XOR с константами делают невозможным восстановление внутреннего состояния.

Использование хеш-функций, не уязвимых к атаке

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

Изменение порядка данных

Вместо H(K || M) использовать H(M || K) — в этом случае атака невозможна, так как злоумышленник не знает конечное состояние после обработки M (оно зависит от K). Однако эта конструкция уязвима к другим атакам (например, к коллизиям).

Использование других схем MAC

• CMAC (Cipher-based MAC) на основе блочных шифров.
• Poly1305-AES — аутентифицированное шифрование.

Исторические примеры и последствия

• 2009 год: Атака на Flickr API (MD5). Уязвимость позволила злоумышленникам загружать произвольные файлы от имени других пользователей. Исправлено переходом на HMAC.
• 2011 год: Атака на протокол OAuth 1.0 (использовал HMAC-SHA1, но некоторые реализации допускали H(ключ || сообщение)). Привело к рекомендации использовать только HMAC.
• 2014 год: Атака на протокол WPA2 (использовал PBKDF2 с SHA-1, но в некоторых реализациях — конструкцию H(ключ || сообщение) для генерации временных ключей). Уязвимость была частично устранена в WPA3.

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

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

Ограничения атаки:

• Требуется знание длины исходного сообщения (или её точная оценка). Если длина неизвестна, злоумышленник может перебирать возможные длины, но это увеличивает сложность.
• Атака не позволяет изменить исходное сообщение M — только дописать к нему данные.
• Атака не работает, если хеш-функция использует финализацию (например, SHA-3).

Современное состояние

С 2020-х годов атака расширения длины считается классической, но всё ещё актуальной для устаревших систем, использующих MD5, SHA-1 или SHA-2 без HMAC. В современных криптографических стандартах (TLS 1.3, Signal Protocol, SSH) рекомендуется использовать HMAC или AEAD-шифры (AES-GCM, ChaCha20-Poly1305), которые не подвержены этой атаке. В России атака учитывается при разработке стандартов ГОСТ Р 34.11-2012 («Стрибог»), который не уязвим к расширению длины благодаря конструкции на основе сжатия с финализацией.

Источники

• Ferguson N., Schneier B., Kohno T. Cryptography Engineering. — Wiley, 2010. — Глава 6.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — Раздел 9.3.
• RFC 2104 (HMAC: Keyed-Hashing for Message Authentication).
• Stevens M., Lenstra A., de Weger B. «Length Extension Attack on MD5 and SHA-1» (2009).