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

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

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

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

Для атаки злоумышленнику достаточно знать:

• Хеш-значение H(M) исходного сообщения M.
• Длину L исходного сообщения M (в байтах или битах).

Зная H(M), которое является внутренним состоянием хеш-функции после обработки последнего блока M, злоумышленник может начать обработку с этого состояния, как если бы оно было начальным. Затем он дополняет сообщение произвольными данными X (например, «/admin» или «&role=admin»), обрабатывая их как новые блоки. В результате получается хеш H(M || padding || X), где padding — это дополнение, которое хеш-функция добавляет к M для выравнивания длины. Поскольку злоумышленник знает длину M, он может вычислить правильное дополнение.

Важно, что атака не требует знания исходного сообщения M; достаточно лишь его хеша и длины. Полученное новое сообщение M' = M || padding || X будет иметь корректный хеш, что позволяет злоумышленнику выдать его за аутентичное, если система проверяет целостность данных на основе хеша.

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

Атака на удлинение сообщения возможна при выполнении следующих условий:

• Используется хеш-функция, построенная по схеме Меркла — Дамгора (например, MD5, SHA-1, SHA-256).
• Хеш-функция не применяет финальное преобразование, которое делает невозможным восстановление внутреннего состояния (например, добавление длины сообщения в конце перед финальным XOR).
• Злоумышленник знает хеш-значение исходного сообщения и его длину.
• Атакуемый протокол или схема аутентификации не проверяет длину сообщения или не использует дополнительные меры защиты (например, HMAC).

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

¶MAC-конструкции на основе конкатенации

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

¶Веб-приложения и API

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

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

Некоторые протоколы аутентификации, такие как ранние версии протокола аутентификации в сетях Wi-Fi (WEP), использовали уязвимые схемы, основанные на хешировании. Однако современные протоколы (например, WPA2) используют более стойкие конструкции, такие как HMAC.

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

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

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

¶Хеш-функции с финальным преобразованием

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

¶Дополнительные проверки

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

¶Исторический контекст

Атака на удлинение сообщения была впервые описана в криптографической литературе в 1990-х годах, но стала широко известна после публикации работ по уязвимостям хеш-функций MD5 и SHA-1. В 2005 году исследователи показали, что атака может быть применена для подделки MAC-кодов в протоколах, использующих конструкцию H(K || M). С тех пор она считается стандартной угрозой для хеш-функций семейства Меркла — Дамгора.

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

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

¶Примеры в реальной жизни

Одним из известных примеров уязвимости к атаке на удлинение сообщения является протокол Flickr API, который в ранних версиях использовал MD5(secret || params) для аутентификации запросов. Исследователи показали, что злоумышленник может модифицировать параметры запроса, добавив к ним произвольные данные, и вычислить новый корректный хеш. После обнаружения уязвимости Flickr перешёл на использование HMAC.

Другой пример — уязвимость в некоторых реализациях протокола OAuth 1.0, где использовалась конструкция H(K || M). В 2009 году была опубликована работа, демонстрирующая возможность атаки на удлинение сообщения в OAuth 1.0, что привело к рекомендациям по использованию HMAC.

¶См. также

• Атака на коллизию
• Атака на прообраз
• Конструкция Меркла — Дамгора
• HMAC
• SHA-3

¶Источники

• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. Handbook of Applied Cryptography. — CRC Press, 1996.
• Ferguson, N., Schneier, B., Kohno, T. Cryptography Engineering. — Wiley, 2010.
• Bellare, M., Canetti, R., Krawczyk, H. Keying Hash Functions for Message Authentication. — Advances in Cryptology — CRYPTO '96, 1996.
• Saarinen, M. J. O. A Note on the Length Extension Attack and Its Applications. — 2005.
• Duong, T., Rizzo, J. Flickr's API Signature Forgery. — 2009.