MD4 (Message Digest 4)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:28, 12 июня 2016.
MD4
General
Designers Ronald Rivest
First published October 1990[1]
Series MD2, MD4, MD5, MD6
Cipher detail
Digest sizes 128 bits
Block sizes 512 bits
Rounds 3
Best public cryptanalysis
A collision attack published in 2007 can find collisions for full MD4 in less than 2 hash operations.[2]

MD4 (Message Digest 4) — хеш-функция, разработанная профессором Массачусетского технологического института Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5.

Алгоритм MD4

Предполагается, что на вход подано сообщение, состоящее из бит, хеш которого нам предстоит вычислить. Здесь — произвольное неотрицательное целое число; оно может быть нулем, не обязано быть кратным восьми, и может быть сколь угодно большим. Запишем сообщение побитово, в виде:

Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.

Шаг 1. Добавление недостающих битов.

Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.

Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512.

Шаг 2. Добавление длины сообщения.

64-битное представление (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда больше, чем , используются только 64 младших бита. Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды.

На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Каждое 32-битное слово содержит четыре 8-битных, но следуют они не подряд, а наоборот (например, из восьми 8-битных слов (a b c d e f g h) мы получаем два 32-битных слова (dcba hgfe)). Пусть означает массив слов получившегося сообщения (здесь кратно 16).

Шаг 3. Инициализация MD-буфера.

Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (32-битных регистров): . Эти регистры инициализируются следующими шестнадцатеричными числами (младшие байты сначала):

       word : 67 45 23 01
       word : ef cd ab 89
       word : 98 ba dc fe
       word : 10 32 54 76

Шаг 4. Обработка сообщения блоками по 16 слов.

Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова, и по ним вычисляет одно 32-битное слово.

      
      
     

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

Алгоритм хеширования на абстрактном языке программирования:

     
     /* Обрабатываем каждый блок из 16-ти слов */
     for i = 0 to N/16-1 do
       /* Заносим i-ый блок в переменную X */
       for j = 0 to 15 do
         set X[j] to M[i*16+j].
       end /* конец цикла по j */
       /* Сохраняем A как AA, B как BB, C как CC, и D как DD */
       AA = A
       BB = B
       CC = C
       DD = D
       /* Раунд 1 */
       /* Пусть [abcd k s] означает следующую операцию:
            a = (a + F(b,c,d) + X[k]) <<< s. */
       /* Производим 16 следующих операций: */
       [ABCD  0  3]  [DABC  1  7]  [CDAB  2 11]  [BCDA  3 19]
       [ABCD  4  3]  [DABC  5  7]  [CDAB  6 11]  [BCDA  7 19]
       [ABCD  8  3]  [DABC  9  7]  [CDAB 10 11]  [BCDA 11 19]
       [ABCD 12  3]  [DABC 13  7]  [CDAB 14 11]  [BCDA 15 19]
       /* Раунд 2 */
       /* Пусть [abcd k s] означает следующую операцию:
            a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */
       /* Производим 16 следующих операций: */
       [ABCD  0  3]  [DABC  4  5]  [CDAB  8  9]  [BCDA 12 13]
       [ABCD  1  3]  [DABC  5  5]  [CDAB  9  9]  [BCDA 13 13]
       [ABCD  2  3]  [DABC  6  5]  [CDAB 10  9]  [BCDA 14 13]
       [ABCD  3  3]  [DABC  7  5]  [CDAB 11  9]  [BCDA 15 13]
       
       /* Раунд 3 */
       /* Пусть [abcd k s] означает следующую операцию:
            a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */
       /* Производим 16 следующих операций: */
       [ABCD  0  3]  [DABC  8  9]  [CDAB  4 11]  [BCDA 12 15]
       [ABCD  2  3]  [DABC 10  9]  [CDAB  6 11]  [BCDA 14 15]
       [ABCD  1  3]  [DABC  9  9]  [CDAB  5 11]  [BCDA 13 15]
       [ABCD  3  3]  [DABC 11  9]  [CDAB  7 11]  [BCDA 15 15]
       /* Затем производим следующие операции сложения. (Увеличиваем значение в каждом регистре
          на величину, которую он имел перед началом итерации по i */
       A = A + AA
       B = B + BB
       C = C + CC
       D = D + DD
     end /* конец цикла по i */
     

Замечание. Величина 5A827999 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 2. Она же в восьмеричном представлении: 013240474631. Величина 6ED9EBA1 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 3. Она же в восьмеричном представлении: 015666365641. Эти данные приведены в книге Кнут, Искусство программирования, издание 1981 года, том 2, стр 660, таблица 2.

Шаг 5. Формирование хеша.

Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D.

Реализация алгоритма на языке C содержится в RFC 1320.
  1. "The MD4 Message Digest Algorithm". Network Working Group. October 1990. Retrieved 2011-04-29. 
  2. Yu Sasaki; et al. (2007). "New message difference for MD4" (PDF).