Рейтинг@Mail.ru

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 на проверяющей стороне.

 

Литература

  1. 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.
  2. Панасенко С. Алгоритм хэширования MD4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=32437 – 19.03.2012 г.
  3. Wireless sensor network. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.

 

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

Просмотров: 1300

Мнения экспертов

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

  • Левицкий О.И.Левицкий О.И.
    ОАО НПО «Наука»
    Ведущий специалист по информационной безопасности
В настоящей статье автор раскрывает опциональные параметры алгоритма MD6 и их воздействие, при различных значениях, на структуру самого алгоритма, его область применения, криптостойкость и другие важные свойства. Материал статьи изложен чётко, с наглядными графическими примерами и обоснованными выводами. Написано профессионалом и для профессионалов.

Автор продолжает развивать тему в отношении особенностей алгоритма хэширования MD6. В своей статье автор обращает внимание на параметр L, его влияние на структуру алгоритма. Особенно следует обратить внимание на сделанный автором обоснованный вывод. Как всегда, автор понятно излагает достаточно сложные выкладки, приводит необходимый поясняющий графический материал. Полагаю, представленная работа вызовет интерес как специалистов, так и интересующихся данной предметной областью.

Ваши комментарии:

Для того, чтобы оставлять коментарии, Вам нужно авторизоваться на Sec.Ru. Если У Вас еще нет аккаунта, пройдите процедуру регистрации.


Автор

Информация

  • Снимай крутую видеорекламу - выкладывай на Sec.Ru!

    Рекламный ролик - один из самых эффективных способов донесения информации. И он отлично подходит для рекламирования любой продукции, в т.ч. и продукции рынка систем безопасности.
    Поэтому редакция Портала решила составить свой рейтинг лучших рекламных видеороликов. Все они разные и все чем-то покоряют: красотой, задумкой, стилем съемки, посылом, необычным финалом.
    Некоторые из них язык не повернется назвать иначе как шедевром короткого метра. Смотрим, наслаждаемся, делаем заметки, учимся творить рекламу правильно.
    Если Вы хотите выложить видеоролик о своей продукции на Sec.Ru, пишите о своем желании на adv@sec.ru!

    Картинка: Jpg, 100x150, 16,47 Кбайт

    Мотор!

Отраслевые СМИ

Все права защищены 2002 – 2016
Rambler's Top100 �������@Mail.ru