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

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

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

Атака на основе удлинения сообщения была впервые описана в криптографической литературе в конце 1990-х годов, хотя её теоретическая основа была заложена ещё в 1979 году с публикацией Ральфа Меркла и Ивана Дамгора, предложивших конструкцию хеш-функций. С развитием протоколов аутентификации и цифровых подписей, использующих хеш-функции, эта атака приобрела практическое значение. Особую известность она получила в 2009 году, когда была продемонстрирована уязвимость в протоколах аутентификации, таких как HMAC (Hash-based Message Authentication Code), при неправильной реализации.

Наиболее уязвимыми к атаке являются хеш-функции семейства MD5, SHA-1 и SHA-2 (SHA-256, SHA-512), построенные по схеме Меркла — Дамгора. В 2012 году с введением стандарта SHA-3 (Keccak), основанного на конструкции «губка» (sponge construction), проблема удлинения сообщения была решена на архитектурном уровне. Тем не менее, SHA-2 продолжает широко использоваться в криптографических протоколах, что сохраняет актуальность атаки.

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

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

Хеш-функции, подверженные атаке, работают следующим образом:

1. Исходное сообщение разбивается на блоки фиксированной длины (например, 512 бит для SHA-256).
2. Если последний блок короче, он дополняется (паддинг) до полной длины с добавлением бита «1», нулей и длины исходного сообщения в битах.
3. Каждый блок последовательно обрабатывается через компрессионную функцию, которая принимает предыдущее внутреннее состояние (начальный вектор или результат предыдущего блока) и текущий блок, выдавая новое состояние.
4. Итоговое состояние после обработки последнего блока является хешем сообщения.

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

Предположим, злоумышленник знает хеш H(M) сообщения M (например, секретного ключа, конкатенированного с данными) и длину |M|. Он не знает само M. Для атаки:

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

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

Математическая формализация

Пусть H — хеш-функция, работающая по схеме Меркла — Дамгора. Тогда:

• H(M) = f(IV, M) (где IV — начальный вектор, f — итеративная компрессия).
• Для любого сообщения M и любого дополнительного блока B: H(M || pad(M) || B) = f(H(M), B || pad(B)).

Таким образом, зная H(M) и |M|, можно вычислить H(M || pad(M) || B) для любого B.

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

Аутентификация с помощью хеша секрета

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

• Схема K || M: сервер вычисляет H(K || M) и отправляет его вместе с M. Злоумышленник, перехватив H(K || M) и зная длину K (часто фиксированную), может вычислить H(K || M || pad(K || M) || D) для любого D. Это позволяет подделать аутентифицированное сообщение, добавив произвольные данные.
• Схема M || K: аналогично, но злоумышленник может добавить данные после K, что также нарушает целостность.

Цифровые подписи

В некоторых реализациях цифровых подписей (например, в протоколах, использующих хеш для подписи сообщения) атака может быть применена для создания подписи для сообщения, которое никогда не подписывалось. Если подписывается хеш H(M), а не само M, то злоумышленник, зная H(M), может предъявить подпись для M || pad(M) || D, так как хеш этого сообщения будет другим, но подпись для H(M) останется той же. Это нарушает свойство экзистенциальной неподдельности.

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

• HMAC: Стандартный HMAC (RFC 2104) не подвержен атаке, так как использует два ключа и два прохода хеширования. Однако неправильные реализации, например, использование простого хеша вместо HMAC, уязвимы.
• Протоколы с хешированием паролей: Системы, хранящие хеши паролей (например, в формате H(password)), уязвимы к атаке, если злоумышленник может добавить данные к паролю. Однако на практике это редко используется, так как пароли обычно хешируются с солью.

Пример атаки на SHA-256

Рассмотрим упрощённый пример. Пусть:

• Секретный ключ K = «secret» (6 байт).
• Сообщение M = «data» (4 байта).
• Сервер вычисляет H = SHA-256(K || M) = SHA-256(«secretdata»).

Злоумышленник перехватывает H и знает, что длина K + M = 10 байт. Он хочет добавить «extra». Для этого:

1. Вычисляет pad для сообщения длиной 10 байт (согласно спецификации SHA-256, добавляется бит «1», нули и 64-битная длина).
2. Строит новое сообщение: «secretdata» || pad(10 байт) || «extra».
3. Начинает хеширование с состояния H и обрабатывает блоки «extra» с дополнением.
4. Получает хеш H', который совпадает с SHA-256(«secretdata» || pad(10 байт) || «extra»).

Сервер, получив сообщение «data» || pad(10 байт) || «extra» и хеш H', проверит его, вычислив SHA-256(«secret» || «data» || pad(10 байт) || «extra»), и результат совпадёт, так как хеш-функция обрабатывает сообщение идентично. Таким образом, злоумышленник успешно подделал аутентифицированное сообщение.

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

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

• SHA-3 (Keccak): Конструкция «губка» не подвержена удлинению сообщения, так как выходное состояние не используется для последующего хеширования без дополнительной обработки.
• BLAKE2: Вариант BLAKE2b и BLAKE2s, основанные на схеме HAIFA, также устойчивы, так как включают в себя счётчик длины в компрессионную функцию.

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

Стандарт HMAC (RFC 2104) определяет формулу: HMAC(K, M) = H((K' ⊕ opad) || H((K' ⊕ ipad) || M)), где K' — ключ, дополненный до длины блока, opad и ipad — константы. Эта конструкция предотвращает удлинение, так как внешний хеш использует ключ, а внутренний хеш не раскрывает состояние.

Дополнительные меры

• Фиксация длины сообщения: Включение длины сообщения в хеш (например, H(length || M)) предотвращает атаку, так как злоумышленник не может изменить длину.
• Использование соли: Добавление случайной соли к сообщению перед хешированием усложняет атаку, но не устраняет её полностью, если соль известна.
• Применение цифровых подписей с хешированием сообщения целиком: Подпись вычисляется не для хеша, а для самого сообщения, что исключает возможность подмены.

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

Атака на основе удлинения сообщения часто рассматривается как теоретическая, но она имеет практические последствия. Основные ограничения:

• Злоумышленник должен знать точную длину исходного сообщения. В реальных системах длина ключа или сообщения может быть неизвестна, что затрудняет атаку.
• Атака не позволяет восстановить исходное сообщение M, а только создать новое, содержащее M. Это ограничивает её применение в сценариях, где требуется раскрытие секрета.
• Многие современные протоколы (например, TLS 1.3) используют HMAC или SHA-3, что делает атаку неэффективной.

Тем не менее, атака остаётся важным напоминанием о необходимости правильного выбора криптографических примитивов и их корректной реализации.

Источники

• Меркл, Р. (1979). «Secrecy, authentication, and public key systems». Stanford University.
• Дамгор, И. (1989). «A design principle for hash functions». Advances in Cryptology — CRYPTO’89.
• Фергюсон, Н., Шнайер, Б. (2003). «Practical Cryptography». Wiley.
• RFC 2104 — «HMAC: Keyed-Hashing for Message Authentication».
• Национальный институт стандартов и технологий (NIST). «FIPS PUB 180-4: Secure Hash Standard (SHS)».