Введение

Структура Меркла-Дамгарда, называемая структурой MD, в основном используется в алгоритме хеширования для защиты от коллизий. Эта структура является основой для некоторых превосходных алгоритмов хеширования, таких как MD5, SHA-1 и SHA-2. Сегодня я объясню эту структуру MD и атаку на расширение длины.

MD структура

Структура доктора медицины Ральфа Меркла описана в докторской диссертации 1979 года. Поскольку Ральф Меркле и Иван Дамгард соответственно обосновывают эту структуру, эта структура известна как структура Меркле-Дамгарда.

Далее давайте посмотрим, как работает структура MD.

Структура MD сначала дополняет входное сообщение, чтобы сделать сообщение целым числом, кратным фиксированной длине (например, 512 или 1024). Это связано с тем, что алгоритм сжатия не может обрабатывать сообщения произвольной длины, поэтому перед обработкой необходимо выполнить заполнение.

Обычно мы заполняем весь блок сообщения постоянными данными, скажем, 0.

Например, если наше сообщение "HashInput", а размер сжатого блока 8 байт (64 бита), то наше сообщение будет разделено на два блока, а последний блок будет заполнен 0, и мы получим: "HashInput т0000000".

Но этого часто бывает недостаточно, потому что обычно для функции сжатия лишний 0 в конце будет убран, поэтому итоговое вычисленное значение хеш-функции будет таким же, как padding и не padding.

Чтобы этого избежать, необходимо изменить первый бит, заполняющий константные данные. Поскольку постоянное заполнение обычно состоит из нулей, первый бит заполнения принудительно изменяется на «1».

То есть «Хашинпу Т1000000».

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

Но использование дополнительного блока часто немного расточительно.Более компактный подход — поместить туда длину сообщения, если в 0 последнего блока достаточно места.

После заполнения блока сообщение может быть сжато далее.Давайте посмотрим на блок-схему MD:

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

атака удлинения длины

При расширенной атаке на криптографическую среду злоумышленник может узнать значение хэша (Сообщение1‖Сообщение2) по длине злоумышленника через известные хэш (Сообщение1) и Сообщение1. Среди них указаны разъемы. И агрессивно, и нужно знать, что такое message1.

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

В качестве примера предположим, что у нас есть следующий запрос:

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

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

Предположим, злоумышленник хочет изменить значение слова «вафель» с «яйцо» на «льедж».

Тогда новые данные будут выглядеть так:

count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

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

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

New Data: 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

Таким образом, мы можем получить новое значение MAC:

New Signature: 0e41270260895979317fff3898ab85668953aaa2

Wide pipe

Чтобы избежать атак с увеличением длины, мы можем внести некоторые деформации в структуру MD.

Первый взгляд на структуру Wide Pipe:

Процесс работы с широким каналом и MD в основном одинаков, разница в том, что длина сгенерированного промежуточного временного зашифрованного сообщения в два раза превышает длину конечного сгенерированного сообщения.

Вот почему на приведенном выше рисунке есть два начальных вектора IV1 и IV2. Если длина конечного результата равна n, то длина результата, сгенерированного в середине, равна 2n. Нам нужно уменьшить данные длины 2n до данных длины n на последнем шаге.

SHA-512/224 и SHA-512/256 просто отбрасывают половину данных.

Fast wide pipe

Существует также более быстрый алгоритм, чем широкая труба, называемая быстрой широкой трубой:

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

Эта статья была включена вwoohoo.floydpress.com/face-length-oh…

Самая популярная интерпретация, самая глубокая галантерея, самые краткие уроки и множество трюков, о которых вы не знаете, ждут вас!

Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: «Программируйте эти вещи», разбирайтесь в технологиях, лучше поймите себя!