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

В криптографии конструкция Меркла -Дамгорда или хеш-функция Меркла-Дамгорда — это метод построения устойчивых к коллизиям криптографических хеш-функций из устойчивых к коллизиям односторонних функций сжатия . ^{[ 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 | \neq | М 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

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

Ссылки

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

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

[GoldwasserBellare-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= ( помощь )

[NP10-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 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]