5.2.3 MD5

MD5 является доработанной версией алгоритма MD4. Аналогично MD4, в алгоритме MD5 размер хэш-кода равен 128 битам.

После ряда начальных действий MD5 разбивает текст на блоки длиной 512 битов, которые, в свою очередь, делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хэш-код.

Сначала текст дополняется таким образом, чтобы длина получаемого текста, выраженная в битах, стала на 64 меньше числа, кратного 512. Дополнение осуществляется приписыванием к концу сообщения единицы и затем необходимого числа нулей (в бинарном представлении). Затем к тексту приписывается 64-битовое представление длины исходного сообщения. Таким образом получается текст, длина которого кратна 512 битам.

Инициализируются 4 переменных размером по 32 бита:

Далее начинает работу основной цикл алгоритма. Основной цикл повторяется столько раз, сколько блоков по 512 битов присутствует в хэшируемом сообщении.

Создаются копии инициализированных переменных: для , для , для , для .

Каждый основной цикл состоит из 4 раундов (в MD4 было всего 3 раунда). В свою очередь, каждый раунд состоит из 16 операторов. Все операторы однотипны и имеют вид: . Здесь:

, , и суть , , и в зависимости от номера раунда и номера оператора в раунде (в оригинале эта подстановка записана в явном виде).

обозначает -тый подблок обрабатываемого блока. В каждом раунде порядок обработки очередным оператором подблоков определяется задаваемой в явном виде подстановкой на множестве всех подблоков (их, также как и операторов, 16).

обозначают зафиксированные случайные константы, зависящие от номера раунда и номера оператора в раунде (Ривест положил для -того () оператора в -том () раунде константу равной целой части от .

обозначает левый циклический сдвиг аргумента на битов. Величины сдвигов также зависят от номера раунда и номера оператора в раунде.

 -- некоторая функция (фиксированная для каждого раунда), действующая покоординатно на биты своих трех аргументов.

В первом раунде действует функция .

Во втором раунде действует функция .

В третьем раунде действует функция .

В четвертом раунде действует функция .

Функции подобраны таким образом, чтобы при равномерном и независимом распределении битов аргументов выходные биты были бы также распределены равномерно и независимо.

Основной цикл алгоритма завершается суммированием полученных , , и и накапливаемых , , и , после чего алгоритм переходит к обработке нового блока данных. Выходом алгоритма является конкатенация получаемых после последнего цикла , , и .

Известные результаты анализа

Ривест внес следующие изменения в MD4 при разработке MD5:

• добавлен четвертый раунд в основной цикл;

• в каждом операторе при суммировании используется уникальная константа;

• изменена функция второго раунда (в MD4 было ). Это сделано для того, чтобы сделать функцию менее симметричной;

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

• изменен порядок считывания слов во втором и третьем раундах для того, чтобы они меньше походили друг на друга;

• величина циклического сдвига в каждом раунде оптимизирована с точки зрения усиления эффекта распространения ошибки. Сдвиги от раунда к раунду различаются.

Берсон [Be] пытался применить метод дифференциального анализа к однораундовым преобразованиям алгоритма MD5. Но его подход не дает эффекта для полной четырехраундовой схемы.

Ден Буру и Босселэру [dBB1] удалось построить коллизию для функции сжатия (т. е. элементарной функции, которая на каждом раунде преобразует промежуточное значение, полученное из предыдущего раунда, и текущий блок сообщения в новое промежуточное значение) алгоритма MD5. Пока это не привело к компрометации MD5 в практических приложениях. Тем не менее этот результат означает, что нарушен один из принципов построения MD5, а именно требование, чтобы функция сжатия была свободна от коллизий.