В криптографии конструкция Меркла –Дамгарда или хэш-функция Меркла–Дамгарда представляет собой метод построения устойчивых к коллизиям криптографических хэш-функций из устойчивых к коллизиям односторонних функций сжатия . [1] : 145 Эта конструкция использовалась при разработке многих популярных алгоритмов хэширования, таких как MD5 , SHA-1 и SHA-2 .
Конструкция Меркла–Дамгарда была описана в докторской диссертации Ральфа Меркла в 1979 году. [2] Ральф Меркл и Иван Дамгард независимо друг от друга доказали, что эта структура является надежной: то есть, если используется соответствующая схема заполнения и функция сжатия устойчива к коллизиям , то хеш-функция также будет устойчива к коллизиям. [3] [4]
Хэш-функция Меркла–Дамгарда сначала применяет функцию заполнения, совместимую с MD, для создания входных данных, размер которых кратен фиксированному числу (например, 512 или 1024) — это связано с тем, что функции сжатия не могут обрабатывать входные данные произвольного размера. Затем хэш-функция разбивает результат на блоки фиксированного размера и обрабатывает их по одному с помощью функции сжатия, каждый раз объединяя блок входных данных с выходными данными предыдущего раунда. [1] : 146 Чтобы сделать конструкцию безопасной, Меркл и Дамгард предложили дополнять сообщения заполнением, которое кодирует длину исходного сообщения. Это называется заполнением длины или усилением Меркла–Дамгарда .
На схеме односторонняя функция сжатия обозначена как f и преобразует два фиксированных входных значения длины в выходное значение того же размера, что и одно из входных значений. Алгоритм начинается с начального значения, вектора инициализации (IV). IV — это фиксированное значение (зависящее от алгоритма или реализации). Для каждого блока сообщения функция сжатия (или уплотнения) f берет полученный результат, объединяет его с блоком сообщения и выдает промежуточный результат. Последний блок дополняется нулями по мере необходимости, а биты, представляющие длину всего сообщения, добавляются. (Подробный пример дополнения длины см. ниже.)
Чтобы еще больше укрепить хэш, последний результат иногда передается через функцию финализации . Функция финализации может иметь несколько целей, например, сжатие большего внутреннего состояния (последнего результата) в меньший размер выходного хеша или обеспечение лучшего смешивания и лавинного эффекта на битах в сумме хэша. Функция финализации часто создается с использованием функции сжатия. [ необходима цитата ] (Обратите внимание, что в некоторых документах используется другая терминология: действие заполнения длины называется «финализацией». [ необходима цитата ] )
Популярность этой конструкции обусловлена фактом, доказанным Мерклем и Дамгардом , что если односторонняя функция сжатия f устойчива к коллизиям , то таковой является и хэш-функция, построенная с ее использованием. К сожалению, эта конструкция также имеет несколько нежелательных свойств:
Из-за нескольких структурных недостатков конструкции Меркла–Дамгарда, особенно проблемы расширения длины и атак с множественными коллизиями, Стефан Люкс предложил использовать хэш с широким каналом [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 n .
Мридул Нанди и Соурадьюти Пол продемонстрировали , что хеш-функцию с широким каналом можно сделать примерно в два раза быстрее, если состояние широкого канала можно разделить пополам следующим образом: одна половина является входом для последующей функции сжатия, а другая половина объединяется с выходом этой функции сжатия. [12]
Основная идея конструкции хэша заключается в том, чтобы переслать половину предыдущего значения цепочки вперед, чтобы выполнить XOR на выходе функции сжатия. При этом конструкция принимает более длинные блоки сообщений на каждой итерации, чем исходный широкий канал. Используя ту же функцию f , что и раньше, она принимает n -битные значения цепочки и n + m бит сообщения. Однако цена, которую нужно заплатить, — это дополнительная память, используемая при конструкции для прямой связи.
Конструкция MD по своей сути является последовательной. Существует параллельный алгоритм [13] , который создает устойчивую к коллизиям хэш-функцию из устойчивой к коллизиям функции сжатия. Хэш-функция PARSHA-256 [14] была разработана с использованием параллельного алгоритма и функции сжатия SHA-256.
Как упоминалось во введении, схема заполнения, используемая в конструкции Меркла–Дамгарда, должна быть тщательно выбрана, чтобы обеспечить безопасность схемы. Михир Белларе приводит достаточные условия для схемы заполнения, чтобы гарантировать безопасность конструкции MD: достаточно, чтобы схема была «совместимой с MD» (исходная схема заполнения длины, используемая Мерклом, является примером совместимой с MD заполнения). [1] : 145 Условия таковы:
Здесь | X | обозначает длину X . При наличии этих условий коллизия в хэш-функции MD существует точно тогда, когда есть коллизия в базовой функции сжатия. Следовательно, конструкция Меркла–Дамгарда доказуемо безопасна, когда базовая функция сжатия безопасна. [1] : 147
Чтобы передать сообщение функции сжатия, последний блок должен быть дополнен постоянными данными (обычно нулями) до полного блока. Например, предположим, что сообщение, которое нужно хешировать, — это «HashInput» (9-октетная строка, 0x48617368496e707574 в ASCII ), а размер блока функции сжатия составляет 8 байт (64 бита). Мы получаем два блока (октеты заполнения показаны на светло-голубом фоне):
Это подразумевает, что другие сообщения с тем же содержимым, но заканчивающиеся дополнительными нулями в конце, дадут то же значение хэша. В приведенном выше примере другое почти идентичное сообщение (0x48617368496e7075 74 00 ) сгенерирует то же значение хэша, что и исходное сообщение "HashInput" выше. Другими словами, любое сообщение, имеющее дополнительные нули в конце, делает его неотличимым от сообщения без них. Чтобы предотвратить эту ситуацию, первый бит первого октета заполнения изменяется на "1" (0x80), что дает:
Однако наиболее распространенные реализации используют фиксированный размер бит (обычно 64 или 128 бит в современных алгоритмах) в фиксированной позиции в конце последнего блока для вставки значения длины сообщения (см. псевдокод SHA-1 ). Дальнейшее улучшение может быть достигнуто путем вставки значения длины в последний блок, если там достаточно места. Это позволяет избежать наличия дополнительного блока для длины сообщения. Если предположить, что значение длины закодировано в 5 байтах (40 бит), сообщение становится:
Сохранение длины сообщения вне диапазона в метаданных или иным образом встраивание ее в начало сообщения является эффективным средством противодействия атаке с расширением длины [ требуется ссылка ] , при условии, что недействительность длины сообщения и контрольной суммы будет считаться сбоем проверки целостности.
{{cite journal}}: Цитировать журнал требует |journal=( помощь ){{cite journal}}: Цитировать журнал требует |journal=( помощь )