Jump to content

Строительство Меркле – Дамгорда

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

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

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

Построение хеша Меркла – Дамгорда

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

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

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

[ редактировать ]

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

  • вторым Атаки прообразом на длинные сообщения всегда намного эффективнее, чем перебор. [ 5 ]
  • Мультиколлизии (множество сообщений с одинаковым хэшем) можно найти, приложив лишь немного больше усилий, чем коллизии. [ 6 ]
  • Они уязвимы для « стадийных атак », которые сочетают в себе каскадную конструкцию для обнаружения мультиколлизий (аналогично приведенному выше) с коллизиями, обнаруженными для данного префикса (коллизии с выбранным префиксом). Это позволяет создавать весьма специфические конфликтующие документы, и на это может потребоваться больше работы, чем на поиск коллизии, но гораздо меньше, чем можно было бы ожидать для случайного оракула . [ 7 ] [ 8 ]
  • Они уязвимы для атак расширения длины : учитывая хэш H ( X ) неизвестного входа X , легко найти значение H (Pad( X ) || Y ) , где Pad — это функция заполнения хеша. То есть можно найти хэши входных данных, связанных с X, даже если X остается неизвестным. [ 9 ] Атаки с расширением длины фактически использовались для атаки на ряд коммерческих схем аутентификации веб-сообщений, таких как одна, используемая Flickr . [ 10 ]

Широкотрубная конструкция

[ редактировать ]
Конструкция хеша с широкой трубой. Значения промежуточной цепочки увеличены вдвое.

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

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

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

[ редактировать ]
Быстрая конструкция хэша с широкой трубой. Половина значения цепочки используется в функции сжатия.

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

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

Параллельный алгоритм

[ редактировать ]

Построение МД по своей сути является последовательным. Есть параллельный алгоритм [ 13 ] который конструирует устойчивую к коллизиям хеш-функцию из устойчивой к коллизиям функции сжатия. Хэш-функция ПАРША-256 [ 14 ] был разработан с использованием параллельного алгоритма и функции сжатия SHA-256.

MD-совместимое дополнение

[ редактировать ]

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

  • M является префиксом Pad( M ) .
  • Если | М 1 | = | М 2 | , тогда | Подушка( М 1 ) | = | Пад( М 2 ) | .
  • Если | М 1 | ≠ | М 2 | , то последний блок Pad( M 1 ) отличается от последнего блока Pad( M 2 ) .

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

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

[ редактировать ]

Чтобы иметь возможность передать сообщение функции сжатия, последний блок должен быть дополнен постоянными данными (обычно нулями) до полного блока. Например, предположим, что хэшируемое сообщение — «HashInput» (строка из 9 октетов, 0x48617368496e707574 в ASCII ), а размер блока функции сжатия — 8 байтов (64 бита). Мы получаем два блока (октеты заполнения показаны голубым цветом фона):

48 61 73 68 49 6е 70 75, 74 00 00 00 00 00 00 00

Это означает, что другие сообщения, имеющие такое же содержание, но заканчивающиеся дополнительными нулями в конце, будут иметь такое же значение хеш-функции. В приведенном выше примере другое почти идентичное сообщение (0x48617368496e7075 74 00 ) будет генерировать то же значение хеш-функции, что и исходное сообщение «HashInput» выше. Другими словами, любое сообщение, имеющее в конце лишние нули, делает его неотличимым от сообщения без них. Чтобы предотвратить эту ситуацию, первый бит первого октета заполнения изменяется на «1» (0x80), что дает:

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00

Однако в наиболее распространенных реализациях используется фиксированный размер бит (обычно 64 или 128 бит в современных алгоритмах) в фиксированной позиции в конце последнего блока для вставки значения длины сообщения (см. псевдокод SHA-1 ). Дальнейшее улучшение можно внести, вставив значение длины в последний блок, если достаточно места. Это позволяет избежать дополнительного блока для длины сообщения. Если предположить, что значение длины закодировано в 5 байтах (40 бит), сообщение будет выглядеть следующим образом:

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 09

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

  1. ^ Jump up to: а б с д Гольдвассер, Шафи ; Белларе, Михир (июль 2008 г.). «Конспект лекций по криптографии» . Архивировано из оригинала 14 июля 2021 г. Проверено 28 марта 2023 г.
  2. ^ RC Меркл . Системы секретности, аутентификации и открытых ключей. Стэнфордский доктор философии диссертация 1979 г., стр. 13-15.
  3. ^ RC Меркл . Сертифицированная цифровая подпись . В достижениях в криптологии - Труды CRYPTO '89, конспекты лекций по информатике, том. 435, Г. Брассард, изд. Springer-Verlag, 1989, стр. 218-238.
  4. ^ И. Дамгорд . Принцип проектирования хеш-функций . В достижениях в криптологии - Материалы CRYPTO '89, конспекты лекций по информатике, том. 435, Г. Брассард, изд. Springer-Verlag, 1989, стр. 416-427.
  5. ^ Келси, Джон; Шнайер, Брюс (2004). «Вторые прообразы n-битных хеш-функций для работы намного меньше 2 ^ n» (PDF) - из архива Cryptology ePrint: отчет 2004/304. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  6. ^ Антуан Жу. Мультиколлизии в итерированных хэш-функциях. Применение в каскадном строительстве. В достижениях в криптологии - CRYPTO '04 Proceedings, конспекты лекций по информатике, Vol. 3152, М. Франклин, изд. Springer-Verlag, 2004, стр. 306–316.
  7. ^ Джон Келси и Тадаёши Коно. Пассивные хэш-функции и атака Нострадамуса в Eurocrypt 2006, Конспекты лекций по информатике, Vol. 4004, стр. 183–200.
  8. ^ Стивенс, Марк; Ленстра, Арьен ; де Вегер, Бенне (30 ноября 2007 г.). «Нострадамус» . Проект HashClash . ТУ/е . Проверено 30 марта 2013 г.
  9. ^ Евгений Додис, Томас Ристенпарт, Томас Шримптон. Спасение Меркла-Дамгорда для практического применения . Предварительная версия в журнале «Достижения в области криптологии» – Труды EUROCRYPT '09, конспекты лекций по информатике, том. 5479, А. Жу, изд. Springer-Verlag, 2009, стр. 371–388.
  10. ^ Тай Дуонг, Джулиано Риццо, Уязвимость подделки подписи API Flickr , 2009 г.
  11. ^ Удача, Стефан (2004). «Принципы проектирования итерированных хеш-функций» - из архива Cryptology ePrint, отчет 2004/253. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  12. ^ Мридул Нанди и Сурадьюти Пол (2010). «Ускорение Widepipe: безопасное и быстрое хеширование» - из архива Cryptology ePrint, документ 2010/193.
  13. ^ Саркар, Палаш; Шелленберг, Пол Дж. (2001). Параллельный алгоритм расширения криптографических хеш-функций . Конспекты лекций по информатике. Том. 2247. Шпрингер-Верлаг. стр. 40–49. дои : 10.1007/3-540-45311-3_4 . ISBN  978-3-540-45311-6 .
  14. ^ Пал, Пинакпани; Саркар, Палаш (2003). PARSHA-256 — новая распараллеливаемая хеш-функция и многопоточная реализация . Конспекты лекций по информатике. Том. 2887. Шпрингер-Верлаг. стр. 347–361. дои : 10.1007/978-3-540-39887-5_25 . ISBN  978-3-540-39887-5 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3f0e7404f9a5fd36b510f4a41fba844f__1724450280
URL1:https://arc.ask3.ru/arc/aa/3f/4f/3f0e7404f9a5fd36b510f4a41fba844f.html
Заголовок, (Title) документа по адресу, URL1:
Merkle–Damgård construction - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)