Рейтинг@Mail.ru

21 ноября 2013

Алгоритм хэширования MD6

Панасенко С. П.

Данная статья продолжает цикл статей, посвященных алгоритмам хэширования семейства MD. Следующий после алгоритма MD5 и наиболее современный из алгоритмов хэширования данного семейства – это алгоритм MD6.
MD6 был разработан большой группой криптологов из Массачусетского Технологического Института (Massachusetts Institute of Technology – MIT) в 2008 г. под руководством Рональда Ривеста.
Данный алгоритм был представлен на конференции Crypto 2008 [1], а также был предложен на конкурс по определению нового стандарта США SHA-3; мы рассматривали данный конкурс ранее в [2] и более подробно рассмотрим участие алгоритма MD6 в конкурсе SHA-3 в последующих статьях, а здесь приведем описание алгоритма MD6 согласно его спецификации [3].
MD6 – алгоритм, имеющий большое количество опциональных параметров, с помощью которых он настраивается под разнообразные возможные реализации и применения. Рассмотрим базовый вариант алгоритма, использующий параметры по умолчанию, а прочим вариантам алгоритма MD6 будет посвящена следующая статья.

Входные и выходные данные алгоритма

Алгоритм MD6 обрабатывает любое сообщение M, размер которого в битах m соответствует следующим ограничениям:

0  ≤ m < 264.

Размер сообщения не обязательно должен быть известен заранее (т. е. до начала хэширования), что позволяет обрабатывать потоковые данные по мере их поступления.
Вырабатываемые алгоритмом MD6 хэш-значения могут быть любого положительного размера d, не превышающего 512 битов. Размер выходного значения алгоритма должен быть известен заранее, поскольку значение d участвует в вычислениях на различных этапах с самого начала обработки входного сообщения.
Варианты алгоритма, использующие значения опциональных параметров по умолчанию, обозначаются как MD6-d. Основными вариантами алгоритма можно считать варианты с размерами хэш-значений, обязательными для участия алгоритма в конкурсе SHA-3 (см., например, [4] и [5]), а именно:

  • MD6-224;
  • MD6-256;
  • MD6-384;
  • MD6-512.

Кроме того, в качестве одного из основных авторы алгоритма MD6 рассматривают вариант MD6-160, поскольку он совместим по размеру со стандартом SHA-1 [6].

Структура алгоритма

Структура алгоритма MD6 принципиально отличается от рассмотренных ранее алгоритмов семейства MD. Базовый вариант алгоритма обрабатывает входные данные, структурированные в виде кватернарного дерева.
Данное дерево представлено на рис. 1. Листьями дерева являются блоки хэшируемого сообщения M и блоки дополнения, которые обозначены на рис. 1 круглыми элементами с различной окраской:

  • черные соответствуют блокам сообщения;
  • серый обозначает последний неполный блок сообщения (если таковой существует), частично дополненный до размера блока;
  • белые – блоки дополнения.

Алгоритм оперирует блоками размером в 16 слов; словом является 64-битовый фрагмент данных, т. е. размер блока составляет 128 байтов или 1024 бита.
Какой-либо вектор инициализации в алгоритме не предусмотрен. Дополнение хэшируемого сообщения также выполняется максимально просто – добавлением нулевых битов до требуемого размера.


Рис. 1 Структура алгоритма MD6

Каждый узел дерева соответствует применению функции сжатия f(). Функция сжатия получает в качестве входного значения 4 блока данных, которые сжимает до одного блока, передаваемого «вверх» следующей функции сжатия, как показано на рис. 1. Последнее применение функции сжатия дает 1024-битовое значение, которое усекается до требуемого размера d, в результате чего получается хэш-значение сообщения M. Функция сжатия будет подробно описана далее.
Данная древовидная структура алгоритма выбрана для достижения максимальной возможности по распараллеливанию хэширования между несколькими процессорными ядрами. Действительно, все экземпляры функции f(), находящиеся на одном уровне дерева, могут быть выполнены параллельно, поскольку они полностью независимы друг от друга.
Отметим, что существуют альтернативные структуры алгоритма, которые не применяются в его базовом варианте; данные структуры, а также обоснование необходимости наличия альтернативных структур алгоритма будут обсуждаться в последующих статьях.

Входная последовательность функции сжатия

Помимо четырех блоков входных данных по 16 слов, функция сжатия получает еще несколько входных параметров, которые вместе с данными формируют 89 слов входной последовательности, обрабатываемой функцией сжатия.

Рис. 2 Входная последовательность функции сжатия

Структура входной последовательности приведена на рис. 2, где размеры фрагментов последовательности указаны в 64-битовых словах и использованы следующие обозначения:

  • Q – константа, сформированная округленным значением дробной части √6; точное значение будет приведено далее;
  • – значение секретного ключа; в базовом варианте алгоритма секретный ключ не используется, поэтому данное поле обнулено;
  • U – уникальный идентификатор конкретного экземпляра функции сжатия, определяется местоположением узла, соответствующего данному экземпляру, в древовидной структуре алгоритма;
  • V – дополнительное слово, содержащее значения остальных параметров функции сжатия.

Рассмотрим фрагменты входной последовательности более подробно.
Структура слова U приведена на рис. 3, где размеры фрагментов приведены в байтах. Значение U формируется следующими переменными:

  • level – номер уровня узла дерева; узлы нумеруются снизу вверх, начиная со значения 0, которое соответствует уровню блоков сообщения M;
  • index – позиция узла в текущем уровне дерева, считается слева направо, начиная с 0.


Рис. 3 Идентификатор экземпляра функции сжатия U

Дополнительное слово V имеет значительно более сложную структуру, но в базовом варианте многие из составляющих V параметров имеют константные значения. Структура V приведена на рис. 4, где размеры фрагментов приведены в битах, а параметры обозначены следующим образом:

  • RFU – зарезервированное поле, заполненное нулями;
  • r – количество раундов функции сжатия (см. далее); в базовом варианте напрямую зависит от d (размер хэш-значения в битах, также представленный в слове V) следующим образом:

r = 40 + ⌊d / 4⌋;

  • L – параметр, определяющий структуру алгоритма; в базовом варианте L = 64;
  • z – параметр, определяющий, является ли данное вычисление функции сжатия финальным (т. е. корнем дерева на рис. 1); в этом случае z = 1, во всех остальных узлах z = 0;
  • p – количество битов дополнения (если таковые существуют) в блоках входных данных;
  • keylen – размер ключа K в байтах; поскольку в базовой версии ключ K не используется, данное поле обнулено.


Рис. 4 Дополнительное слово V

Значение константы Q приведено в следующей таблице (шестнадцатеричные значения):

Слово

Значение

0

7311c2812425cfa0

1

6432286434aac8e7

2

b60450e9ef68b7c1

3

e8fb23908d9f06f1

4

dd2e76cba691e5bf

5

0cd0d63b2c30bc41

6

1f8ccf6823058f8a

7

54e5ed5b88e3775d

8

4ad12aae0a6d6031

9

3e7f16bb88222e0d

10

8af8671d3fb50c2c

11

995ad1178bd25c31

12

c878c1dd04c4b633

13

3b72066c7a1552ac

14

0d6f3522631effcb

Функция сжатия

Функция сжатия выполняет t итераций обработки входной последовательности; количество итераций определяется количеством раундов r: t = 16r.
Обозначим как N входную последовательность (размером в 89 слов), являющуюся результатом конкатенации Q, K, U, V и блоков входных данных, как показано на рис. 2. Обозначим также i-е слово любой последовательности X как Xi.
Перед выполнением первой итерации функции сжатия выполняется инициализация ее внутренних данных следующим образом:

  1. Создается массив A размером t + 89 слов: A0At+88.
  2. Входная последовательность N копируется в первые 89 слов массива A:

Ai = Ni, i = 0…88.

Каждая итерация модифицирует одно слово массива A (а именно, Ai для i = 89…t + 88) следующим образом (см. рис. 5):

x = Si-89 ⊕ Ai-89 ⊕ Ai-t0;

x = x ⊕ (Ai-t1 & Ai-t2) ⊕ (Ai-t3 & Ai-t4);

x = x ⊕ (x >> ri-89);

Ai = x ⊕ (x << li-89),

где:

  • x – временная переменная;
  • Sj – раундовые константы, будут описаны далее;
  • t0…t4 – константы, определяющие позиции обратной связи, в базовом варианте алгоритма определены следующим образом:

t0

t1

t2

t3

t4

17

18

21

31

67

  • rj и lj – константы, определяющие количество битов вращения текущего значения x, соответственно, вправо и влево согласно следующей таблице:

(i – 89) mod 16

ri-89

li-89

0

10

11

1

5

24

2

13

9

3

10

16

4

11

15

5

12

9

6

2

27

7

7

15

8

14

6

9

15

2

10

7

29

11

13

8

12

11

15

13

7

5

14

6

31

15

12

9


Рис. 5 Итерация функции сжатия

Раундовые константы Sj определены на основе двух следующих констант (указаны шестнадцатеричные значения):

S0 = 0123456789abcdef;

S* = 7311c2812425cfa0.

Вычисление раундовых констант выполняется так:

Si-89 = S⌊(i-89)/16⌋,

где Sk+1 = (Sk <<< 1) ⊕ (Sk & S*).

На рис. 5 отчетливо видно, что в данном случае имеет место сдвиговый регистр с нелинейной обратной связью (сдвиг выполняется влево), на основе которого и может быть реализована функция сжатия алгоритма MD6.
Обработка всего массива A на основе его первых 89 слов в [3] очень наглядно представлена в виде сдвигающегося «окна», поочередно захватывающего для обработки 89 элементов массива и формирующего за одну итерацию значение одного следующего элемента. Данное представление функции сжатия приведено на рис. 6.


Рис. 6 Функция сжатия

Результат работы функции сжатия обозначен на рис. 6 символом C. Это массив размером в 16 слов, которые представляют собой последние 16 слов массива A, т. е.:

Ci = At+73+i, i = 0…15.

Резюмируя описание базового варианта алгоритма MD6, можно сказать следующее:

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

 

Литература

  1. Rivest R. L. The MD6 Hash Function (aka “Pumpkin Hash”). // http://groups.csail.mit.edu – MIT – CRYPTO 2008.
  2. Панасенко С. Обзор алгоритмов хэширования – финалистов конкурса SHA-3. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=30852 – 12.12.2011 г.
  3. 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.
  4. Hill J. E. Announcing the Development of New Hash Algorithm(s) for the Revision of Federal Information Processing Standard (FIPS) 180-2, Secure Hash Standard. // http://csrc.nist.gov – National Institute of Standards and Technology – Federal Register, Vol. 72, No. 14, pp. 2861-2863 – January 23, 2007.
  5. Kayser R. F. Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family. // http://csrc.nist.gov – National Institute of Standards and Technology – Federal Register, Vol. 72, No. 212, pp. 62212-62220 – November 2, 2007.
  6. FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.

 

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

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

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

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

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

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

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


Автор

Информация

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

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

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

    Мотор!

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

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