Введение
Метод построения криптографических хеш-функций, устойчивых к коллизиям
В криптографии конструкция Меркле — Дамгорда или хеш-функция Меркле — Дамгорда — это метод построения криптографических хеш-функций, устойчивых к коллизиям, из односторонних сжимающих функций, устойчивых к коллизиям. Эта конструкция использовалась при разработке многих популярных хеш-алгоритмов, таких как MD5, SHA-1 и SHA-2. Конструкция Меркле — Дамгорда была описана в докторской диссертации Ральфа Меркле в 1979 году. Ральф Меркле и Иван Дамгард независимо друг от друга доказали надёжность этой структуры: то есть, если используется подходящая схема дополнения и сжимающая функция устойчива к коллизиям, то и хеш-функция также будет устойчива к коллизиям. Хеш-функция Меркле — Дамгорда сначала применяет функцию дополнения, соответствующую стандарту MD, для создания входных данных, размер которых кратен фиксированному числу (например, 512 или 1024) — это необходимо, поскольку сжимающие функции не могут обрабатывать входные данные произвольного размера. Затем хеш-функция разбивает результат на блоки фиксированного размера и обрабатывает их последовательно с помощью сжимающей функции, каждый раз объединяя блок входных данных с результатом предыдущего раунда. Многоколлизии (множество сообщений с одинаковым хешем) можно найти, затратив лишь немного больше усилий, чем на поиск коллизий. "Атаки скопления", которые объединяют каскадную конструкцию для поиска многоколлизий (аналогично описанному выше) с коллизиями, найденными для заданного префикса (коллизии выбранного префикса). Это позволяет создавать высокоспецифичные коллизионные документы, и это можно сделать, затратив больше усилий, чем на поиск коллизии, но гораздо меньше, чем потребовалось бы для случайного оракула. Расширение длины: имея хеш H(X) неизвестного входного значения X, легко найти значение H(X || pad), где pad — функция дополнения хеша. То есть, можно найти хеши входных данных, связанных с X, даже если X остаётся неизвестным. Атаки на расширение длины фактически использовались для взлома ряда коммерческих схем аутентификации веб-сообщений, например, используемой Flickr.
In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision resistant cryptographic hash functions from collision resistant one way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA 1 and SHA 2. The Merkle–Damgård construction was described in Ralph Merkle's Ph. D. thesis in 1979. Ralph Merkle and Ivan Damgård independently proved that the structure is sound: that is, if an appropriate padding scheme is used and the compression function is collision resistant, then the hash function will also be collision resistant. The Merkle–Damgård hash function first applies an MD compliant padding function to create an input whose size is a multiple of a fixed number (e. g. 512 or 1024) — this is because compression functions cannot handle inputs of arbitrary size. The hash function then breaks the result into blocks of fixed size, and processes them one at a time with the compression function, each time combining a block of the input with the output of the previous round. Multicollisions (many messages with the same hash) can be found with only a little more work than collisions. "Herding attacks", which combines the cascaded construction for multicollision finding (similar to the above) with collisions found for a given prefix (chosen prefix collisions). This allows for constructing highly specific colliding documents, and it can be done for more work than finding a collision, but much less than would be expected to do this for a random oracle. Length extension: Given the hash H(X) of an unknown input X, it is easy to find the value of , where pad is the padding function of the hash. That is, it is possible to find hashes of inputs related to X even though X remains unknown. Length extension attacks were actually used to attack a number of commercial web message authentication schemes such as one used by Flickr.
Широкопроводные трубы
Из-за нескольких структурных слабостей конструкции Меркла — Дамгорда, в частности, проблемы расширения длины и атак на множественные коллизии, Стефан Лакс предложил использовать хэш с широкой трубой вместо конструкции Меркла — Дамгорда. Хэш с широкой трубой очень похож на конструкцию Меркла — Дамгорда, но имеет больший внутренний размер состояния, что означает, что длина битов, используемая внутри, превышает длину выходных битов. Если требуется хэш длиной 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.
Строительство труб с быстрой шириной
Мридул Нанди и Сурадюти Пол показали, что хеш-функцию Widepipe можно ускорить примерно в два раза, если состояние widepipe разделить пополам следующим образом: одна половина подается на вход следующей функции сжатия, а другая объединяется с выходом этой функции сжатия. Основная идея хэш-конструкции заключается в передаче половины предыдущего значения цепи вперед для XOR-сложения с выходом функции сжатия. Таким образом, конструкция на каждой итерации обрабатывает блоки сообщений большей длины, чем оригинальная Widepipe. Используя ту же функцию f, она принимает на вход цепочные значения длиной n бит и n+m бит сообщения. Однако, эта оптимизация требует дополнительной памяти для реализации механизма обратной связи.
Параллельный алгоритм
Алгоритм MD изначально последовательный. Существует параллельный алгоритм, который строит хэш-функцию, устойчивую к коллизиям, из функции сжатия, устойчивой к коллизиям. Хэш-функция PARSHA 256 была разработана с использованием параллельного алгоритма и функции сжатия SHA 256.
Пример наполнения длиной
Чтобы передать сообщение в функцию сжатия, последний блок должен быть дополнен постоянными данными (обычно нулями) до полного блока. Например, предположим, что сообщение, которое необходимо хешировать, – это "HashInput" (строка из 9 октетов, 0x48617368496e707574 в ASCII), а размер блока функции сжатия составляет 8 байт (64 бита). В результате получается два блока (октеты дополнения показаны светло-синим цветом):
Это означает, что другие сообщения с тем же содержимым, но заканчивающиеся дополнительными нулями, будут иметь такое же хеш-значение. В приведенном выше примере другое почти идентичное сообщение (0x48617368496e707574) сгенерирует такое же хеш-значение, как и исходное сообщение "HashInput". Иными словами, любое сообщение с дополнительными нулями в конце становится неотличимым от сообщения без них. Чтобы предотвратить эту ситуацию, первый бит первого октета дополнения изменяется на "1" (0x80), что дает:
Однако большинство распространенных реализаций используют фиксированный размер (обычно 64 или 128 бит в современных алгоритмах) в фиксированной позиции в конце последнего блока для вставки значения длины сообщения (см. псевдокод SHA-1). Дальнейшее улучшение можно достичь, вставив значение длины в последний блок, если там достаточно места. Это позволяет избежать использования дополнительного блока для длины сообщения. Если предположить, что значение длины кодируется на 5 байтах (40 бит), сообщение становится:
Обратите внимание, что хранение длины сообщения вне основного потока данных в метаданных или включение ее в начало сообщения является эффективным способом защиты от атаки расширения длины, при условии, что недействительность как длины сообщения, так и контрольной суммы рассматривается как сбой проверки целостности.