MD4

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

Одна операция MD4. Хеширование с MD4 состоит из 48 таких операций, сгруппированных в 3 раунда по 16 операций. F — нелинейная функция; в каждом раунде функция меняется. M_i означает 32-битный блок входного сообщения, а K_i — 32-битная константа, различная для каждой операции.

Алгоритм MD4

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

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

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

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

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

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

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

На этом этапе мы получаем сообщение длиной кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Каждое 32-битное слово содержит четыре 8-битных, но следуют они не подряд, а наоборот мы получаем два 32-битных слова). Пусть $M$ означает массив слов получившегося сообщения.

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

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

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

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

На каждую битовую позицию F действует как условное выражение: если X, то Y; иначе Z. Функция F могла бы быть определена с использованием $~+$ вместо $\lor$ , поскольку $~XY$ и $\neg XZ$ не могут равняться 1 одновременно. G действует на каждую битовую позицию как функция максимального значения: если по крайней мере в двух словах из X,Y,Z соответствующие биты равны 1, то G выдаст 1 в этом бите, а иначе G выдаст бит, равный 0. Интересно отметить, что если биты X, Y и Z статистически независимы, то биты F и G будут также статистически независимы. Функция H реализует побитовый xor, она обладает таким же свойством, как F и G.

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

      /* Обрабатываем каждый блок из 16-ти слов */
      for i = 0 to N/16-1 do
 
        /* Заносим i-ый блок в переменную X */
        for j = 0 to 15 do
          set X to M.
        end /* конец цикла по j */
 
        /* Сохраняем A как AA, B как BB, C как CC, и D как DD */
        AA = A
        BB = B
        CC = C
        DD = D
 
        /* Раунд 1 */
        /* Пусть означает следующую операцию:
             a = + X) <<< s. */
        /* Производим 16 следующих операций: */
              
              
              
              
 
        /* Раунд 2 */
        /* Пусть означает следующую операцию:
             a = + X + 5A827999) <<< s. */
        /* Производим 16 следующих операций: */
              
              
              
              
 
        /* Раунд 3 */
        /* Пусть означает следующую операцию:
             a = + X + 6ED9EBA1) <<< s. */
        /* Производим 16 следующих операций: */
              
              
              
              
 
        /* Затем производим следующие операции сложения. (Увеличиваем значение в каждом регистре
           на величину, которую он имел перед началом итерации по 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.