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

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

Описание

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

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

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

• Итеративная обработка блоков фиксированной длины
• Деление входного сообщения на блоки
• Заполнение последнего блока в случае, когда соответствующая часть входного сообщения меньше размера блока
• Вывод внутреннего состояния функции после обработки последнего блока

То есть на самом деле хэшируется сообщение

m’ = m || Padding,

где m — исходное сообщение, Padding — то, чем хеш-функция заполнила последний блок.

Чтобы провести атаку, необходимо хешировать сообщение

m’ = m || Padding || NewData || NewPadding ,

то есть приписать к исходному сообщению новую информацию.

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

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

В качестве защиты от атаки удлинением сообщения можно использовать следующие способы

• Использование HMAC
• Добавление в конструкцию Merkle-Damgard односторонней функции f, которая будет дополнительно обрабатывать значение хэша H от сообщения m:

H' = f(H(m))

• Двойное хеширование, например, следующим образом:

H' = H(K || H(K || m)), где K - секретный ключ

• Добавление секретного ключа в конец сообщения перед хешированием:

H' = H(K || Padding || m || K ), где Padding дополняет сообщение до целого количества блоков

• Конкатенация секрета с каждым блоком сообщения

Пример

Сервис доставки вафель заданного типа waffle конкретному пользователю user_id реализованы для обработки запросов данного формата :

Исходное сообщение: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Исходная подпись: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

Сервер будет выполнять данный запрос (доставить вафли типа «Eggo» для пользователя с идентификатором 1), только если подпись действительна для этого пользователя. Подпись является кодом аутентификации сообщения, она подписана ключом, не известным злоумышленнику . Этот пример также уязвим для атак повторного воспроизведения , при отправлении того же запроса и подписи второй раз.

Злоумышленник может изменить запрос, в данном примере поменяв требуемый тип вафель «Eggo» на «Liege». Это возможно сделать, воспользовавшись гибкостью формата сообщений: если в строчке указаны несколько заказов, предпочтение отдается последнему. Обеспечение криптографической безопасности в данном примере целиком лежит на подписи.

Желаемое сообщение: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

Чтобы подписать новый запрос, злоумышленник должен знать ключ, которым было подписано исходное сообщение. Однако здесь он может применить атаку удлинением.

Угадав длину сообщения , злоумышленник формирует новый запрос:

Новое сообщение: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
         \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
         \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
         \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
         \x00\x00\x02\x28&waffle=liege

Это сообщение включает в себя исходные данные и добавленную к нему часть, которую раньше хеш-функция генерировала в процессе своей работы ( Padding ). В примере эта часть представлена в шестнадцатеричном виде. В данном случае функция дополняет сообщение единицей, далее следуют нули и в конце приписывается длина сообщения. Злоумышленник знает, что состояние хеш-функции для исходного сообщения идентично её состоянию для нового сообщения до последнего «&». Внутреннее состояние функции хеширования в этой точке определяется значением хэша от исходного сообщения, то есть подписью.

Далее алгоритм находящейся в правильном состоянии хеш-функции обработает оставшуюся часть нового сообщения и создаст новую действительную подпись.

Новая подпись: 0e41270260895979317fff3898ab85668953aaa2

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

Получив новый запрос, сервер посчитает его действительным, так как подпись идентична той, которая сгенерировалась бы, если секрет был бы известен.

Источники

• Нильс Фергюсон, Брюс Шнайер. Практическая криптография. — Издательский дом, 2004. — 432 с. — ISBN 5–8459–0733–0.

Ссылки