Строительство Меркле – Дамгорда
В криптографии конструкция Меркла -Дамгорда или хеш-функция Меркла-Дамгорда — это метод построения устойчивых к коллизиям криптографических хеш-функций из устойчивых к коллизиям односторонних функций сжатия . [ 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
Сохранение длины сообщения вне диапазона в метаданных или иным образом встроенное в начало сообщения является эффективным средством защиты от атаки расширения длины. [ нужна ссылка ] , пока недействительность длины сообщения и контрольной суммы считается неудачей проверки целостности.
Ссылки
[ редактировать ]- Справочник по прикладной криптографии Менезеса, ван Оршота и Ванстона (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 .