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

Атака на расширение длины (англ. length extension attack) — это класс криптографических атак, направленных на хеш-функции, построенные по схеме Меркла — Дамгора (Merkle–Damgård). Атака позволяет злоумышленнику, зная хеш-значение некоторого сообщения M (но не само сообщение), вычислить хеш нового сообщения M' = M || pad || X, где pad — выравнивающие биты, добавленные при хешировании M, а X — произвольное дополнительное сообщение. При этом для вычисления нового хеша не требуется знание исходного сообщения M, а лишь его длины и хеш-значения. Данная уязвимость является следствием итеративной структуры хеш-функций, где состояние внутреннего контекста (так называемый «цепной» вектор) после обработки каждого блока данных полностью определяется предыдущим состоянием и обрабатываемым блоком.

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

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

1. Исходное сообщение M дополняется выравнивающими битами (padding) так, чтобы его длина стала кратной размеру блока. В padding обычно включается бит «1», необходимое количество нулей и 64-битное представление исходной длины сообщения.
2. Хеш-функция инициализируется фиксированным начальным вектором (IV).
3. Каждый блок данных последовательно подаётся на вход сжимающей функции f, которая принимает текущее состояние (выход предыдущего блока) и текущий блок данных, а возвращает новое состояние.
4. После обработки последнего блока итоговое состояние выдаётся в качестве хеш-значения.

При атаке на расширение длины злоумышленник действует следующим образом:

• Имеет хеш H(M) и длину L исходного сообщения M.
• Конструирует новое сообщение M' = M || pad || X, где pad — это в точности те же выравнивающие биты, которые были бы добавлены к M при вычислении H(M).
• Зная, что после обработки M и pad внутреннее состояние хеш-функции равно H(M), злоумышленник может продолжить хеширование с этого состояния, добавляя блоки X.
• Для этого он инициализирует новый экземпляр хеш-функции не стандартным IV, а значением H(M), и обрабатывает блоки X. Результат будет равен H(M').

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

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

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

• MD5 — широко использовалась, но в настоящее время считается криптографически слабой.
• SHA-1 — также признана устаревшей из-за коллизионных атак.
• SHA-256 и SHA-512 — семейство SHA-2, всё ещё широко применяемое, но уязвимое к данной атаке.
• RIPEMD-160 — также уязвим.

Хеш-функции, использующие другие конструкции, например, SHA-3 (основана на губчатой конструкции) или BLAKE2 (использует модифицированную схему с ха-шингом), не подвержены атаке на расширение длины. Также устойчивы к этой атаке хеш-функции, построенные на основе схемы с финальным XOR или с использованием HMAC.

Пример атаки

Рассмотрим простой пример. Пусть хеш-функция SHA-256, сообщение M = «secretpassword», его длина L = 14 байт. Вычислен хеш H(M) = «abc123...». Злоумышленник, не зная M, хочет создать сообщение, хеш которого будет соответствовать расширению M.

1. Он вычисляет выравнивающие биты для сообщения длиной 14 байт. Для SHA-256 это будет: один бит «1», 425 нулевых бит и 64-битное представление числа 112 (14 байт * 8 бит).
2. Он конструирует M' = «secretpassword» + pad + «&admin=true».
3. Он инициализирует SHA-256 с начальным состоянием, равным H(M), и обрабатывает блок «&admin=true».
4. Полученный хеш H(M') будет корректен, и если система проверяет подпись, основанную на хеше исходного сообщения, злоумышленник сможет подделать подпись для нового сообщения.

Практические последствия

Атака на расширение длины имеет серьёзные последствия для ряда протоколов и систем, где хеш-функции используются для проверки целостности или аутентификации без дополнительных мер защиты. Основные уязвимые сценарии:

• Аутентификация по схеме «секрет + сообщение»: если для вычисления HMAC или подписи используется конструкция вида H(secret || message), злоумышленник может вычислить H(secret || message || padding || extra), не зная секрета. Это позволяет подделывать аутентификационные данные.
• Протоколы аутентификации на основе хешей: некоторые старые реализации аутентификации в веб-приложениях (например, в системах с передачей хеша пароля) могут быть подвержены атаке.
• Системы контроля версий и целостности: если хеш используется для проверки целостности цепочки данных (например, в Git), атака может позволить вставить дополнительные данные без нарушения целостности всей цепочки.
• Криптовалюты и блокчейн: некоторые ранние реализации протоколов, использующие хеши для подписей транзакций, могли быть уязвимы.

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

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

• Использование HMAC (Hash-based Message Authentication Code): HMAC использует два прохода хеширования с разными ключами, что делает атаку неэффективной, так как злоумышленник не знает внутреннего состояния после первого прохода.
• Применение хеш-функций, не подверженных атаке: SHA-3, BLAKE2, SHA-512/256 (усечённая версия) не уязвимы к расширению длины.
• Использование схемы «хеш-функция с ключом»: конструкция вида H(key || message) небезопасна, но если ключ добавляется после сообщения (H(message || key)), атака становится невозможной, так как злоумышленник не может вычислить хеш расширения без знания ключа.
• Добавление финального преобразования: некоторые реализации используют дополнительный XOR или перестановку после обработки последнего блока, что предотвращает атаку.

История и контекст

Атака на расширение длины была впервые описана в криптографической литературе в 1990-х годах, когда стали активно использоваться хеш-функции семейства MD и SHA. Она не является новой или неизвестной, но её практическое применение часто недооценивается разработчиками. В 2000-х годах атака была продемонстрирована на реальных протоколах, таких как Flickr API (2009 год), где использовалась конструкция H(secret || message) для аутентификации запросов. После этого многие сервисы перешли на HMAC или другие защищённые схемы.

В 2012 году атака была использована для взлома протокола аутентификации в некоторых реализациях OAuth 1.0, что привело к переходу на OAuth 2.0 с использованием HMAC.

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

Несмотря на свою опасность, атака на расширение длины имеет ограничения:

• Требует знания длины исходного сообщения. В некоторых случаях длина может быть неизвестна, что усложняет атаку, но не делает её невозможной (можно перебирать возможные длины).
• Не позволяет восстановить исходное сообщение, а только вычислить хеш его расширения.
• Не работает против HMAC и хеш-функций, не основанных на схеме Меркла — Дамгора.

Тем не менее, атака остаётся актуальной для систем, использующих устаревшие или неправильно спроектированные протоколы аутентификации.

Источники

• 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: Design Principles and Practical Applications. Wiley.
• Саати, Т. (2002). Криптография: теория и практика. Москва: Вильямс.
• RFC 2104 — HMAC: Keyed-Hashing for Message Authentication.
• NIST SP 800-107 — Recommendation for Applications Using Approved Hash Algorithms.