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

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

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

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

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

Механизм атаки

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

1. Восстановить внутреннее состояние хеш-функции, соответствующее H(M). Для большинства хеш-функций это состояние просто равно дайджесту.
2. Начать обработку с этого состояния, используя функцию сжатия, как если бы она обрабатывала следующий блок.
3. Добавить к сообщению M произвольные данные E (расширение), предварительно вычислив правильный паддинг для исходного сообщения, чтобы сохранить корректность структуры.

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

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

Подверженные атаке

• MD5 — устаревшая хеш-функция с длиной дайджеста 128 бит. Подвержена атаке расширения длины, а также коллизиям.
• SHA-1 — устаревшая хеш-функция с длиной дайджеста 160 бит. Подвержена атаке расширения длины, а также коллизиям (с 2017 года).
• SHA-2 (SHA-256, SHA-512 и др.) — семейство хеш-функций, используемых в современных криптосистемах. Подвержены атаке расширения длины, но не имеют известных коллизий.
• RIPEMD-160 — хеш-функция, используемая в некоторых криптовалютах (например, Bitcoin). Подвержена атаке расширения длины.

Не подверженные атаке

• SHA-3 (Keccak) — основана на конструкции «губка» (sponge construction), которая не подвержена атаке расширения длины, так как выход не равен внутреннему состоянию.
• BLAKE2 — хеш-функция, оптимизированная для скорости, использует модифицированную схему, устойчивую к расширению длины.
• HMAC — не является хеш-функцией, а схемой аутентификации, которая использует хеш-функцию, но включает секретный ключ, что предотвращает атаку расширения длины.

Пример атаки

Рассмотрим простой пример с хеш-функцией SHA-256. Пусть сервер аутентифицирует пользователя, вычисляя H(secret || message), где secret — секретный ключ, а message — сообщение, например, команда. Злоумышленник, перехватив H(secret || "command1"), может вычислить H(secret || "command1" || pad || "command2"), не зная secret. Если сервер принимает любые сообщения, начинающиеся с правильного хеша, злоумышленник может выполнить несанкционированную команду.

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

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

• Flickr API (исторически) — использовал конструкцию H(secret || message) для подписи запросов, что позволяло злоумышленникам подделывать запросы.
• PBKDF2 (в некоторых реализациях) — функция формирования ключа на основе пароля, использующая HMAC, но при неправильной реализации может быть уязвима.
• Протоколы с MAC на основе хеширования — любые схемы, где MAC вычисляется как H(key || message), уязвимы к атаке расширения длины.

Криптовалюты

• Bitcoin — использует SHA-256 для хеширования транзакций и блоков. Атака расширения длины не представляет прямой угрозы для Bitcoin, так как хеши используются в контексте Proof-of-Work, где требуется поиск хеша с определённым количеством нулей, а не аутентификация. Однако некоторые протоколы второго уровня (например, Lightning Network) могут быть уязвимы при неправильной реализации.
• Ethereum — использует Keccak-256 (SHA-3), который не подвержен атаке, что делает его более безопасным в этом аспекте.

Методы защиты

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

HMAC (Hash-based Message Authentication Code) — стандартный метод аутентификации сообщений, который использует хеш-функцию, но включает секретный ключ и специальную конструкцию, предотвращающую атаку расширения длины. HMAC вычисляется как H((key XOR opad) || H((key XOR ipad) || message)), где opad и ipad — константы. Это делает атаку невозможной, так как ключ используется дважды и не раскрывает внутреннее состояние.

Конструкция «губка»

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

Двойное хеширование

Простой метод защиты — использовать H(H(message)) или H(message || H(message)). Однако эти методы не являются стандартизированными и могут быть менее надёжными, чем HMAC.

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

Переход на SHA-3 или BLAKE2 полностью устраняет уязвимость к атаке расширения длины. Эти хеш-функции рекомендуются для новых проектов.

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

Атака расширения длины была впервые описана в криптографической литературе в 1990-х годах, но широкую известность получила в 2000-х годах с развитием веб-приложений, использующих хеширование для аутентификации. В 2009 году исследователи продемонстрировали атаку на Flickr API, что привело к переходу многих сервисов на HMAC. В 2011 году атака была использована для взлома некоторых реализаций протокола OAuth 1.0.

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

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

Источники

• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Ferguson, N., Schneier, B., Kohno, T. (2010). Cryptography Engineering. Wiley.
• NIST. (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (FIPS PUB 202).
• Bellare, M., Canetti, R., Krawczyk, H. (1996). Keying Hash Functions for Message Authentication. Advances in Cryptology — CRYPTO '96.