25 декабря 2013
Алгоритм хэширования MD6: альтернативные варианты структуры
Панасенко С. П.
Базовый вариант алгоритма хэширования MD6 был рассмотрен в предыдущей статье.
Под базовым вариантом понимается вариант, в котором все опциональные параметры алгоритма MD6 имеют значения по умолчанию, а различные значения может иметь только обязательный параметр d, определяющий размер выходного значения алгоритма.
В этой и следующей статьях рассмотрим согласно [1] опциональные параметры алгоритма MD6 и то воздействие, которое различные значения данных параметров оказывают на структуру алгоритма, область его применения, криптостойкость и его прочие важные свойства.
Один из важнейших параметров алгоритма – это параметр L (был упомянут в предыдущей статье, поскольку входит в состав дополнительного слова V – комплексного параметра функции сжатия алгоритма). Данный параметр определяет «степень параллельности» алгоритма MD6 и непосредственно влияет на структуру алгоритма.
Параметр L может принимать любое целочисленное значение в диапазоне от 0 до 64 включительно. По умолчанию L = 64, в этом случае алгоритм имеет структуру в виде кватернарного дерева, которая приведена на рис. 1. Данная структура предоставляет максимальные возможности по распараллеливанию вычислений.
Рис. 1 Структура базового варианта алгоритма MD6
Противоположный вариант структуры при L = 0 приведен на рис. 2. Данный вариант предполагает строго последовательное вычисление хэш-значения путем поочередной обработки блоков входных данных.
Рис. 2 Последовательный вариант алгоритма MD6
В данной структуре возможности по распараллеливанию вычислений существуют только в рамках выполнения функции сжатия f(), на верхнем уровне вычисления выполняются строго последовательно. С другой стороны, такая структура предъявляет значительно меньшие требования к оперативной памяти и поэтому может быть с успехом применена в устройствах с ограниченными ресурсами.
При L = 0 оригинальная древовидная структура алгоритма полностью вырождается и становится аналогичной схеме Меркля-Дамгаарда (с удвоенным размером внутреннего состояния алгоритма относительно размера выходного значения – Double-pipe Merkle-Damgard Construction), которая была рассмотрена нами ранее в [2].
В такой схеме алгоритм MD6 имеет обычные атрибуты схемы Меркля-Дамгаарда:
- вектор инициализации IV – заполненный нулями блок из 16 слов;
- состояние алгоритма (начальным значением которого является IV) – результат выполнения функции сжатия на промежуточных этапах.
Выходное значение алгоритма образуется усечением до d битов результата выполнения последней функции сжатия.
Поскольку, в отличие от древовидной структуры, необходимо каким-то образом передавать текущее состояние, функция сжатия обрабатывает не по 4, а по 3 блока (каждый блок состоит из 16 слов) данных; вместо одного из блоков данных функция сжатия принимает на вход текущее состояние алгоритма. Таким образом, входная последовательность функции сжатия отличается по своей структуре от входной последовательности функции сжатия базового варианта алгоритма и имеет структуру, изображенную на рис. 3, где текущее состояние алгоритма обозначено как S.
Рис. 3 Входные данные функции сжатия при последовательном вычислении хэш-значения
Допускаются промежуточные значения L между 0 и 64 – в общем случае L определяет максимально допустимое количество уровней в древовидной структуре алгоритма. Уровни нумеруются снизу вверх, начиная с нуля, при этом нулевой уровень всегда обозначает уровень блоков хэшируемого сообщения. Например, в структуре на рис. 1 содержатся уровни с нулевого по третий включительно, а структура, приведенная на рис. 2, состоит из нулевого и первого уровней.
Алгоритм MD6 предполагает, что перед каждым переходом к более верхнему уровню функций сжатия производится сравнение значения параметра L и номера текущего уровня (до перехода) level. Если level < L, то алгоритм продолжает параллельные вычисления по древовидной структуре. В противном случае новый уровень level + 1 становится последним уровнем структуры алгоритма и вычисления выполняются последовательно.
Таким образом, промежуточные значения L представляют собой комбинацию параллельного и последовательного вариантов алгоритма MD6, что дает промежуточные возможности по распараллеливанию вычислений и промежуточные требования к памяти. Это проиллюстрировано на рис. 4, где приведена структура для L = 1. Отметим, что и при небольших значениях L алгоритм может оставаться строго параллельным при хэшировании сообщений небольших размеров – если 4L превышает размер сообщения в блоках по 16 слов, то перехода к последовательным вычислениям не происходит.
Рис. 4 Структура алгоритма MD6 при L = 1
Легко определить максимальное количество уровней алгоритма, исходя из максимально возможного размера хэшируемого сообщения (не более 264 битов) и размера выходного значения функции сжатия (16 слов, т. е. 1024 бита):
Lmax = log4 ( 264 / 210 ) = 27.
Таким образом, все значения L в диапазоне от 27 до 64 включительно приводят к идентичной структуре алгоритма. При этом результирующие хэш-значения для всех этих значений L оказываются различными, поскольку, как было сказано выше, значение L входит в слово V, т. е. является параметром каждого вызова функции f().
Нельзя сказать, что наличие альтернативных структур алгоритма и внесение L в параметры функции сжатия выглядит бесспорным решением – представим вполне имеющую право на существование систему, в которой во взаимодействие с использованием алгоритма хэширования MD6 вовлечены как устройства с ограниченными ресурсами (скажем, беспроводные сенсоры – см., например, [3]), так и мультипроцессорный сервер, который занимается сбором и анализом присылаемых сенсорами данных. Выглядит логичным последовательное хэширование на стороне сенсоров с параметром L = 0 и параллельное хэширование на стороне сервера с L = 64. Однако, такой вариант при корректной реализации алгоритма согласно спецификации [1] невозможен, поскольку результаты хэширования одного и того же сообщения с различными значениями L не эквивалентны.
В результате, по параметру L можно сделать неоднозначный вывод: полезная гибкость в реализации алгоритма хэширования MD6 приводит к потере совместимости между реализациями алгоритма. В любой системе, в которой выполняется хэширование с различными значениями L, данное значение необходимо каким-либо образом учитывать и передавать для последующего хэширования с тем же значением L на проверяющей стороне.
Литература
- Rivest R. L., Agre B., Bailey D. V., Crutchfield C., Dodis Y., Fleming K. E., Khan A., Krishnamurthy J., Lin Y., Reyzin L., Shen E., Sukha J., Sutherland D., Tromer E., Yin Y. L. The MD6 hash function. A proposal to NIST for SHA-3. // http://csrc.nist.gov – Massachusetts Institute of Technology, Cambridge, MA – October 27, 2008.
- Панасенко С. Алгоритм хэширования MD4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=32437 – 19.03.2012 г.
- Wireless sensor network. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
Об авторе:
Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.
