MD4

2022-04-05T02:53:34Z

188.162.229.137: Удалена ошибочная строчка, вводящая, в заблуждение пользователей.

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

[[Файл:MD4.svg|right|thumbnail|300px|Одна операция MD4. Хеширование с MD4 состоит из 48 таких операций, сгруппированных в 3 раунда по 16 операций. ''F'' — нелинейная функция; в каждом раунде функция меняется. ''M<sub>i</sub>'' означает 32-битный блок входного сообщения, а ''K<sub>i</sub>'' — 32-битная константа, различная для каждой операции.]]

== Алгоритм MD4 ==
Предполагается, что на вход подано сообщение, состоящее из <math>b</math> бит, хеш которого нам предстоит вычислить. Здесь <math>b</math> — произвольное неотрицательное [[целое число]]; оно может быть нулём, не обязано быть кратным восьми, и может быть сколь угодно большим. Запишем сообщение побитно, в виде:
<math>m_0 m_1 \ldots m_{b-1}</math>

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

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

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

=== Шаг 2. Добавление длины сообщения. ===
64-битное представление <math>b</math> (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда <math>b</math> больше, чем <math>2^{64}</math>, используются только 64 младших бита. Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды.

На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной, кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Пусть <math>M[0 \ldots N-1]</math> означает массив слов получившегося сообщения (здесь <math>N</math> кратно 16).

=== Шаг 3. Инициализация MD-буфера. ===
Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (32-битных регистров): <math>(A,B,C,D)</math>. Эти регистры инициализируются следующими шестнадцатеричными числами (младшие байты сначала):
word <math>A</math>: 01 23 45 67
word <math>B</math>: 89 ab cd ef
word <math>C</math>: fe dc ba 98
word <math>D</math>: 76 54 32 10

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

<math>F(X,Y,Z) = XY \lor \neg X Z</math>
<math>G(X,Y,Z) = XY \lor XZ \lor YZ</math>
<math>H(X,Y,Z) = X \oplus Y \oplus Z</math>

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

Алгоритм хеширования на [[Псевдокод (язык описания алгоритмов)|абстрактном языке программирования]]:

<source lang="c">
/* Обрабатываем каждый блок из 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 */
</source>

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

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

Реализация алгоритма на языке [[Си (язык программирования)|C]] содержится в RFC 1320.

== Примеры хешей ==
128-битные MD4 хеши представляют собой 32-значное число в 16-ричном формате. В следующем примере показан хеш 43-байтной строки [[ASCII]]:

MD4("[[The quick brown fox jumps over the lazy dog]]")
= 1bee69a46ba811185c194762abaeae90

Любое даже самое незначительное изменение хешируемой информации приводит к получению полностью отличного хеша, например, изменение в примере одной буквы с <tt>d</tt> на <tt>c</tt>:

MD4("The quick brown fox jumps over the lazy '''c'''og")
= b86e130ce7028da59e672d56ad0113df

Пример MD4 хеша для «нулевой» строки:

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

== Сравнение с MD5 ==
* MD4 использует три цикла из 16 шагов каждый, в то время как MD5 использует четыре цикла из 16 шагов каждый.

* В MD4 дополнительная константа в первом цикле не применяется. Аналогичная дополнительная константа используется для каждого из шагов во втором цикле. Другая дополнительная константа используется для каждого из шагов в третьем цикле. В MD5 различные дополнительные константы, Т[i], применяются для каждого из 64 шагов.

* MD5 использует четыре элементарные логические функции, по одной на каждом цикле, по сравнению с тремя в MD4, по одной на каждом цикле.

* В MD5 на каждом шаге текущий результат складывается с результатом предыдущего шага. Например, результатом первого шага является измененное слово А. Результат второго шага хранится в D и образуется добавлением А к циклически сдвинутому влево на определенное число бит результату элементарной функции. Аналогично, результат третьего шага хранится в С и образуется добавлением D к циклически сдвинутому влево результату элементарной функции. MD4 это последнее сложение не включает.

== Безопасность ==
Уровень безопасности, закладывавшийся в MD4, был рассчитан на создание достаточно устойчивых гибридных систем [[Электронная подпись|электронной цифровой подписи]], основанных на MD4 и криптосистеме с открытым ключом. [[Рональд Ривест]] считал, что алгоритм хеширования MD4 можно использовать и для систем, нуждающихся в сильной [[Криптографическая стойкость|криптостойкости]]. Но в то же время он отмечал, что MD4 создавался прежде всего как очень быстрый алгоритм хеширования, поэтому он может быть плох в плане криптостойкости. Как показали последовавшие исследования, он был прав, и для приложений, где важна прежде всего криптостойкость, стал использоваться алгоритм [[MD5]].

== Уязвимости ==
Уязвимости в MD4 были продемонстрированы в статье Берта ден Бура и Антона Босселарса в 1991 году. Первая коллизия была найдена Гансом Доббертином в 1996 году.

== См. также ==
* [[MD2]]
* [[MD5]]
* [[HAVAL]]
* [[SHA-1]]

== Ссылки ==
* RFC 1186
* RFC 1320

=== Поиск коллизий ===
* [http://eprint.iacr.org/2005/151.pdf Improved Collision Attack on MD4]

{{Хеш-алгоритмы}}

[[Категория:Криптографические хеш-функции]]

wiki12 - Вклад [ru]

MD4