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

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

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

Атака удлинением сообщения эксплуатирует особенность итеративных хеш-функций, таких как MD5, SHA-1 и SHA-2. В этих функциях хеш вычисляется последовательно: сообщение разбивается на блоки фиксированного размера, и каждый блок обрабатывается функцией сжатия, которая принимает на вход предыдущее состояние (внутренний буфер) и текущий блок. Начальное состояние (вектор инициализации) является константой, заданной в спецификации алгоритма.

Если злоумышленнику известен хеш H(M) некоторого сообщения M, а также длина L этого сообщения (в байтах или битах), он может:

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

Таким образом, злоумышленник может подделать код аутентификации, вычисленный по схеме MAC(K, M) = H(K || M), где K — секретный ключ. В этом случае M — это исходное сообщение, а K — секретный префикс. Зная H(K || M) и длину K, злоумышленник может вычислить H(K || M || P || X).

Уязвимые хеш-функции

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

• MD5 — устаревшая, широко известна уязвимость к атакам на коллизии и удлинение.
• SHA-1 — также устаревшая, подвержена атаке.
• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) — все варианты семейства SHA-2 уязвимы к атаке удлинением сообщения, если не используются дополнительные меры защиты (например, HMAC).
• RIPEMD-160 — также уязвима.

Хеш-функции, не подверженные этой атаке:

• SHA-3 (Keccak) — основана на конструкции «губка», не использующей схему Меркла — Дамгора.
• BLAKE2 и BLAKE3 — используют модифицированную конструкцию, устойчивую к удлинению.
• SHAKE и другие XOF (extendable-output functions) — также устойчивы.

Пример атаки

Пусть сервер использует схему аутентификации: token = MD5(secret || message), где secret — секретный ключ длиной 16 байт, а message — строка "data". Сервер проверяет подлинность запроса, сверяя переданный токен с вычисленным.

Злоумышленник перехватывает пару (message, token). Он знает длину secret (например, из утечки или подбора), длину message и сам токен. Он может сформировать новое сообщение "data" + padding + "&admin=true" и вычислить для него новый токен, не зная secret. Если сервер не проверяет длину исходного сообщения, он примет поддельный запрос как подлинный.

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

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

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

HMAC (Hash-based Message Authentication Code) — стандартный механизм, который устраняет уязвимость. В HMAC ключ подаётся на вход хеш-функции дважды (внутренний и внешний ключи), что делает невозможным восстановление состояния после первого вызова хеш-функции без знания ключа. HMAC устойчив к атаке удлинением независимо от используемой хеш-функции.

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

Применение SHA-3, BLAKE2 или BLAKE3 полностью исключает возможность атаки, так как эти функции не используют схему Меркла — Дамгора.

Изменение схемы аутентификации

Вместо H(K || M) можно использовать H(M || K) (суффиксный ключ), что также делает атаку удлинением невозможной, так как злоумышленник не может вычислить хеш для сообщения, дополненного после ключа. Однако эта схема уязвима к другим атакам (например, к атаке на коллизии). Более надёжным вариантом является H(K || M || K).

Ограничение длины сообщения

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

Применение в реальных атаках

Атака удлинением сообщения была известна с середины 1990-х годов, но получила широкую огласку в 2009 году, когда исследователи продемонстрировали её практическую применимость против протоколов, использующих H(K || M) для аутентификации. В частности, атака использовалась для подделки подписей в протоколах Flickr API, Amazon S3 и других веб-сервисах, что привело к их уязвимости.

В 2012 году атака была применена к протоколу DNSSEC (Domain Name System Security Extensions), где для аутентификации записей использовался H(K || M). Это позволило злоумышленникам подделывать цифровые подписи и перенаправлять трафик.

В 2013 году атака была продемонстрирована на примере протокола WPA2 (Wi-Fi Protected Access 2), где для аутентификации клиента использовался H(K || M). Однако практическая реализация требовала знания длины ключа и была ограничена.

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

Атака удлинением сообщения не является универсальной. Она требует:

• Знания точной длины исходного сообщения (или ключа).
• Возможности подобрать padding, который будет корректно обработан сервером.
• Отсутствия проверки длины сообщения на стороне сервера.

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

Несмотря на свою известность, атака удлинением сообщения остаётся актуальной для устаревших систем, которые до сих пор используют MD5 или SHA-1 для аутентификации. Современные протоколы и библиотеки (например, OpenSSL, GnuTLS) по умолчанию используют HMAC или SHA-3, что делает атаку неэффективной.

Источники

• Ferguson, N., Schneier, B., Kohno, T. (2010). Cryptography Engineering. Wiley.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press.
• NIST SP 800-107 Rev. 1 (2012). Recommendation for Applications Using Approved Hash Algorithms.
• RFC 2104 (1997). HMAC: Keyed-Hashing for Message Authentication.
• Saarinen, M.-J. (2012). SHA-3 and the Hash Length Extension Attack. IACR ePrint Archive.