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

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

В криптографии, то строительство Merkle-Damgård или Merkle-Damgård хэш - функция представляет собой метод построения коллизий резистентных криптографической хэш - функции от столкновения устойчивые функции сжатия односторонними. Эта конструкция использовалась при разработке многих популярных алгоритмов хеширования, таких как MD5, SHA-1 и SHA-2.

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

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

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

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

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

СОДЕРЖАНИЕ

1 Характеристики безопасности
2 Широкая трубная конструкция
3 Быстрое строительство широких труб
4 MD-совместимая набивка
5 Пример заполнения длины
6 Ссылки

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

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

Атаки второго прообраза на длинные сообщения всегда намного эффективнее грубой силы.
Мультиколлизии (множество сообщений с одним и тем же хешем) можно найти, приложив немного больше усилий, чем коллизии.
« Стачивая атака », которая сочетает в себе каскадную конструкцию для поиска множественных коллизий (аналогичную описанной выше) с коллизиями, обнаруженными для данного префикса (коллизии с выбранным префиксом). Это позволяет создавать узкоспециализированные конфликтующие документы, и это может быть сделано для большей работы, чем поиск столкновения, но гораздо меньше, чем можно было бы ожидать от случайного оракула.
Расширение длины : учитывая хэш неизвестного входа X, легко найти значение, где pad - это функция заполнения хеша. То есть можно найти хэши входных данных, относящихся к X, даже если X остается неизвестным. Атаки на увеличение длины фактически использовались для атаки на ряд коммерческих схем аутентификации веб-сообщений, например, используемых Flickr. ${\ Displaystyle H (X)}$ $H (X)$ ${\ Displaystyle Н ({\ mathsf {Pad}} (X) \ | Y)}$ ${\ Displaystyle Н ({\ mathsf {Pad}} (X) \ | Y)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48 61 73 68 49 6e 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

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

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

Однако наиболее распространенные реализации используют фиксированный битовый размер (обычно 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.

^ ^a ^b ^c ^d Голдвассер, С. и Белларе, М. «Конспект лекций по криптографии». Летний курс по криптографии, Массачусетский технологический институт, 1996-2001 гг.
^ RC Меркл. Системы секретности, аутентификации и открытых ключей. Стэнфордский доктор философии диссертация 1979 г., стр. 13-15.
^ RC Меркл. Сертифицированная цифровая подпись. В достижениях в криптологии - Труды CRYPTO '89, Лекционные заметки по информатике, том. 435, изд. G. Brassard, Springer-Verlag, 1989, стр. 218-238.
^ I. Damgård. Принцип проектирования хеш-функций. В достижениях в криптологии - Труды CRYPTO '89, Лекционные заметки по информатике, том. 435, изд. G. Brassard, Springer-Verlag, 1989, стр. 416-427.
^ Келси, Джон; Шнайер, Брюс (2004). «Вторые прообразы n-битных хэш-функций для работы гораздо меньше, чем 2 ^ n» (PDF) - через Cryptology ePrint Archive: Report 2004/304. Цитировать журнал требует |journal=( помощь )
^ Антуан Жу. Множественные коллизии в повторяющихся хэш-функциях. Применение в каскадном строительстве. In Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, М. Франклин, изд., Springer-Verlag, 2004 г., стр. 306–316.
^ Джон Келси и Тадаёши Коно. Хэш-функции Хердинга и атака Нострадамуса в Eurocrypt 2006, Lecture Notes in Computer Science, Vol. 4004, стр. 183–200.
^ Стивенс, Марк; Ленстра, Арьен ; де Вегер, Бенн (30 ноября 2007 г.). «Нострадамус». Проект HashClash. ТУ / э. Проверено 30 марта 2013.
^ Евгений Додис, Томас Ristenpart, Томас Shrimpton. Спасение Меркла-Дамгарда для практического применения. Предварительная версия в Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, изд. A. Joux, Springer-Verlag, 2009, стр. 371–388.
^ Тайский Дуонг, Джулиано Риццо, Уязвимость подделки подписи API Flickr, 2009 г.
^ Удачи, Стефан (2004). «Принципы проектирования для итерированных хеш-функций» - из архива Cryptology ePrint, отчет 2004/253. Цитировать журнал требует |journal=( помощь )
^ Mridul Нанди и Саурадють Пол. Ускорение Widepipe: безопасное и быстрое хеширование. В Гуан Гун и Кишан Гупта, редактор Indocrypt 2010, Springer, 2010.