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

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

${\displaystyle m_0{m}_1\dots m_{b-1}}$

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

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

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

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

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

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

       word${\displaystyle A}$: 01 23 45 67       word${\displaystyle B}$: 89 ab cd ef       word${\displaystyle C}$: fe dc ba 98       word${\displaystyle D}$: 76 54 32 10

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

${\displaystyle F(X,Y,Z)=XY\vee \mathrm{\neg }XZ}$${\displaystyle G(X,Y,Z)=XY\vee XZ\vee YZ}$${\displaystyle H(X,Y,Z)=X\oplus Y\oplus Z}$

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

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

/* Обрабатываем каждый блок из 16-ти слов */fori=0toN/16-1do/* Заносим i-ый блок в переменную X */forj=0to15dosetX[j]toM[i*16+j].end/* конец цикла по j *//* Сохраняем A как AA, B как BB, C как CC, и D как DD */AA=ABB=BCC=CDD=D/* Раунд 1 *//* Пусть [abcd k s] означает следующую операцию:             a = (a + F(b,c,d) + X[k]) <<< s. *//* Производим 16 следующих операций: */[ABCD03][DABC17][CDAB211][BCDA319][ABCD43][DABC57][CDAB611][BCDA719][ABCD83][DABC97][CDAB1011][BCDA1119][ABCD123][DABC137][CDAB1411][BCDA1519]/* Раунд 2 *//* Пусть [abcd k s] означает следующую операцию:             a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. *//* Производим 16 следующих операций: */[ABCD03][DABC45][CDAB89][BCDA1213][ABCD13][DABC55][CDAB99][BCDA1313][ABCD23][DABC65][CDAB109][BCDA1413][ABCD33][DABC75][CDAB119][BCDA1513]/* Раунд 3 *//* Пусть [abcd k s] означает следующую операцию:             a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. *//* Производим 16 следующих операций: */[ABCD03][DABC89][CDAB411][BCDA1215][ABCD23][DABC109][CDAB611][BCDA1415][ABCD13][DABC99][CDAB511][BCDA1315][ABCD33][DABC119][CDAB711][BCDA1515]/* Затем производим следующие операции сложения. (Увеличиваем значение в каждом регистре           на величину, которую он имел перед началом итерации по i */A=A+AAB=B+BBC=C+CCD=D+DDend/* конец цикла по i */

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

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

Реализация алгоритма на языкеC содержится вRFC 1320.

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

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

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

MD4("The quick brown fox jumps over the lazycog")  = b86e130ce7028da59e672d56ad0113df

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

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

• 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

• Improved Collision Attack on MD4

• Хеш-функции
• Криптографические хеш-функции

• Страницы, использующие устаревший тег source
• ПРО:ИТ:Статьи по алфавиту
• ПРО:ИТ:Последняя правка: в позапозапрошлом году
• Страницы, использующие волшебные ссылки RFC