Строительство Меркле-Дамгарда - Merkle–Damgård construction

В криптография, то Строительство Меркле-Дамгарда или же Хэш-функция Меркла – Дамгарда это метод построения стойкий к столкновениям криптографические хеш-функции из ударопрочного функции одностороннего сжатия.^[1]:145 Эта конструкция использовалась при разработке многих популярных алгоритмов хеширования, таких как MD5, SHA-1 и SHA-2.

Конструкция Меркла-Дамгарда была описана в книге Ральфа Меркла. Кандидат наук. Тезис в 1979 г.^[2] Ральф Меркл и Иван Дамгард независимо доказали, что конструкция является доброкачественной: то есть при наличии соответствующего схема заполнения используется и функция сжатия стойкий к столкновениям, то хеш-функция также будет устойчивой к коллизиям.^[3][4]

Хэш-функция Меркла – Дамгарда сначала применяет Прокладка, совместимая с MD функция для создания ввода, размер которого кратен фиксированному числу (например, 512 или 1024) - это потому, что функции сжатия не могут обрабатывать вводы произвольного размера. Затем хеш-функция разбивает результат на блоки фиксированного размера и обрабатывает их по одному с помощью функции сжатия, каждый раз комбинируя блок входных данных с выходными данными предыдущего раунда.^[1]:146 Чтобы сделать конструкцию безопасной, Меркл и Дамгард предложили дополнять сообщения отступом, который кодирует длину исходного сообщения. Это называется длина набивки или же Укрепление Меркла-Дамгарда.

Конструкция хэша Меркла – Дамгарда

На схеме функция одностороннего сжатия обозначена как ж, и преобразует два входа фиксированной длины в выход того же размера, что и один из входов. Алгоритм начинается с начального значения, вектор инициализации (IV). IV - это фиксированное значение (зависит от алгоритма или реализации). Для каждого блока сообщения функция сжатия (или сжатия) ж берет полученный результат, объединяет его с блоком сообщения и выдает промежуточный результат. Последний блок при необходимости дополняется нулями, и добавляются биты, представляющие длину всего сообщения. (См. Ниже подробный пример заполнения длины.)

Чтобы еще больше укрепить хэш, последний результат иногда пропускается через функция завершения. Функция финализации может иметь несколько целей, таких как сжатие большего внутреннего состояния (последний результат) в меньший размер выходного хэша или обеспечение лучшего смешивания и лавинный эффект на битах в хеш-сумме. Функция финализации часто строится с использованием функции сжатия.^{[нужна цитата ]} (Обратите внимание, что в некоторых документах используется другая терминология: действие заполнения длины называется «завершением».^{[нужна цитата ]})

Характеристики безопасности

Популярность этой конструкции объясняется тем, что Меркл и Damgård, что если функция одностороннего сжатия ж является стойкий к столкновениям, то и хэш-функция, построенная на его основе. К сожалению, у этой конструкции есть еще несколько нежелательных свойств:

• Второй атака на прообраз против длинных сообщений всегда намного эффективнее грубой силы.^[5]
• Множественные коллизии (много сообщений с одним и тем же хешем) можно найти, приложив немного больше усилий, чем коллизии.^[6]
• "Стадная атакаs ", который сочетает в себе каскадную конструкцию для поиска множественных коллизий (аналогичную описанной выше) с коллизиями, найденными для данного префикса (коллизии с выбранным префиксом). Это позволяет создавать узкоспециализированные конфликтующие документы, и это может быть сделано для большей работы, чем поиск столкновение, но гораздо реже, чем можно было бы ожидать от случайный оракул.^[7][8]
• Увеличение длины: Учитывая хеш ${displaystyle H(X)}$ неизвестного входа Икс, легко найти значение ${displaystyle H({mathsf {Pad}}(X)|Y)}$, куда подушечка - это функция заполнения хеша. То есть можно найти хэши входов, связанных с Икс хотя Икс остается неизвестным.^[9] Атаки на расширение длины фактически использовались для атаки на ряд коммерческих схем аутентификации веб-сообщений, например, используемых Flickr.^[10]

Конструкция с широкой трубой

Хэш-конструкция с широкой трубкой. Значения промежуточных цепочек удвоены.

Из-за нескольких структурных недостатков конструкции Меркла-Дамгарда, особенно проблемы удлинения длины и атак с множественными столкновениями, Стефан Люкс предложил использовать хеш с широкой трубкой^[11] вместо конструкции Меркла – Дамгарда. Хеш-код с широким каналом очень похож на конструкцию Меркла-Дамгарда, но имеет больший размер внутреннего состояния, что означает, что длина в битах, которая используется внутри, больше, чем длина выходных бит. Если хеш п битов, функция сжатия ж берет 2n биты значения цепочки и м бит сообщения и сжимает его до вывода 2n биты.

Следовательно, на заключительном этапе вторая функция сжатия сжимает последнее внутреннее хеш-значение (2n бит) до окончательного хеш-значения (п кусочек). Это можно сделать так же просто, как отбросить половину последнего 2n-бит-вывод. SHA-512/224 и SHA-512/256 принимают эту форму, поскольку они являются производными от варианта SHA-512. SHA-384 и SHA-224 аналогичным образом получены из SHA-512 и SHA-256 соответственно, но ширина их канала намного меньше, чем 2n.

Быстрое строительство широких труб

Конструкция Fast wide pipe hash. Половина значения цепочки используется в функции сжатия.

Это было продемонстрировано Мридул Нанди и Сурадьюти Пол что хэш-функция Widepipe может быть выполнена примерно в два раза быстрее, если состояние Widepipe можно разделить пополам следующим образом: одна половина вводится в следующую функцию сжатия, а другая половина объединяется с выходом этой функции сжатия.^[12]

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

Прокладка, совместимая с MD

Как упоминалось во введении, схема заполнения, используемая в конструкции Меркла-Дамгарда, должна быть тщательно выбрана для обеспечения безопасности схемы. Михир Белларе дает достаточные условия для схемы заполнения, чтобы гарантировать, что конструкция MD является безопасной: достаточно, чтобы схема была «MD-совместимой» (исходная схема заполнения длины, используемая Мерклом, является примером MD-совместимого заполнения).^[1]:145 Условия:

• ${displaystyle M}$ является префиксом ${displaystyle {mathsf {Pad}}(M).}$
• Если ${displaystyle |M_{1}|=|M_{2}|}$ тогда ${displaystyle |{mathsf {Pad}}(M_{1})|=|{mathsf {Pad}}(M_{2})|.}$
• Если ${displaystyle |M_{1}|eq |M_{2}|}$ затем последний блок ${displaystyle {mathsf {Pad}}(M_{1})}$ отличается от последнего блока ${displaystyle {mathsf {Pad}}(M_{2}).}$

При соблюдении этих условий мы обнаруживаем конфликт в хеш-функции MD когда именно мы обнаруживаем конфликт в базовой функции сжатия. Следовательно, конструкция Меркла – Дамгарда доказуема безопасна, когда безопасна лежащая в основе функция сжатия.^[1]:147

Пример заполнения длины

Чтобы передать сообщение функции сжатия, последний блок должен быть дополнен постоянными данными (обычно нулями) до полного блока.

Например, предположим, что хешируемое сообщение называется «HashInput», а размер блока функции сжатия составляет 8 байтов (64 бита). Итак, мы получаем два блока, которые выглядят так:

HashInpu t0000000

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

В нашем примере, например, измененное сообщение «HashInput00» будет генерировать те же блоки, что и исходное сообщение «HashInput».

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

В нашем примере мы получаем что-то вроде этого:

HashInpu t1000000

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

Итак, в нашем примере мы получим три таких блока:

HashInpu t1000000 00001001

Чтобы избежать двусмысленности, значение длины сообщения должно быть устойчивым к атаки удлинения длины. Наиболее распространенные реализации используют фиксированный битовый размер (обычно 64 или 128 бит в современных алгоритмах) и фиксированную позицию в конце последнего блока для кодирования значения длины сообщения (см. Объяснение, Псевдокод SHA-1 ), хотя это было бы в соответствии с логикой, представленной на этой странице, было бы менее эффективно, чем размещение длины в начале сообщения, где оно само не подвержено атаке на расширение длины, но требует знания до инициирования контрольной суммы длины данных. проверка контрольной суммы или вставка нескольких таких значений по блокам в поток контрольной суммы^{[нужна цитата ]}.

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

Скажем, здесь, что в нашем примере значение длины закодировано в 5 байтах (40 бит), таким образом, оно дополняется в последнем блоке как «00009», а не просто «9» или слишком большим количеством ненужных нулей. Так:

HashInpu t1001001

Обратите внимание, что внеполосное сохранение длины сообщения в метаданных или иным образом встроенное в начало сообщения является эффективным средством предотвращения атаки на увеличение длины.^{[нужна цитата ]}до тех пор, пока недействительность как длины сообщения, так и контрольной суммы считается ошибкой проверки целостности.

Рекомендации

• Справочник по прикладной криптографии Менезес, ван Оршот и Ванстон (2001), глава 9.
• Введение в современную криптографию, Джонатан Кац и Иегуда Линделл. Чепмен и Холл / CRC Press, август 2007 г., стр. 134 (конструкция 4.13).

1. Гольдвассер, С. и Белларе, М. «Конспект лекций по криптографии». Летний курс по криптографии, Массачусетский технологический институт, 1996-2001 гг.
2. R.C. Меркл. Системы секретности, аутентификации и открытых ключей. Стэнфордский доктор философии диссертация 1979 г., стр. 13-15.
3. R.C. Меркл. Сертифицированная цифровая подпись. В достижениях в криптологии - Труды CRYPTO '89, Конспект лекций по информатике Vol. 435, изд. G. Brassard, Springer-Verlag, 1989, стр. 218-238.
4. И. Дамгард. Принцип разработки хеш-функций. В достижениях в криптологии - Труды CRYPTO '89, Конспекты лекций по информатике, том. 435, изд. G. Brassard, Springer-Verlag, 1989, стр. 416-427.
5. Келси, Джон; Шнайер, Брюс (2004). «Вторые прообразы n-битных хэш-функций для работы гораздо меньше, чем 2 ^ n» (PDF) - через Cryptology ePrint Archive: Report 2004/304.
6. Антуан Жу. Мультиколлизии в повторяющихся хэш-функциях. Применение в каскадном строительстве. In Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, М. Франклин, изд., Springer-Verlag, 2004 г., стр. 306–316.
7. Джон Келси и Тадаёши Коно. Собирание хеш-функций и атака Нострадамуса В Eurocrypt 2006, Lecture Notes in Computer Science, Vol. 4004. С. 183–200.
8. Стивенс, Марк; Ленстра, Арьен; де Вегер, Бенн (30 ноября 2007 г.). "Нострадамус". Проект HashClash. TU / e. Получено 2013-03-30.
9. Евгений Додис, Томас Ристенпарт, Томас Шримптон. Спасение Меркла-Дамгарда для практического применения. Предварительная версия в Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, изд. A. Joux, Springer-Verlag, 2009, стр. 371–388.
10. Тай Дуонг, Джулиано Риццо, Уязвимость подделки подписи API Flickr, 2009
11. Удачи, Стефан (2004). «Принципы разработки итерированных хеш-функций» - через Cryptology ePrint Archive, Отчет 2004/253.
12. Мридул Нанди и Сурадьюти Пол. Ускорение Widepipe: безопасное и быстрое хеширование. В Гуан Гун и Кишан Гупта, редактор Indocrypt 2010, Springer, 2010.