8.2. MD5
Одна из наиболее популярных в прошлом, но криптографически нестойкая в настоящий момент хеш-функция MD5 (от англ. message digest 5) разработана Рональдом Ривестом (англ. Ronald Linn Rivest) в 1991 году как развитие хеш-функии MD4 и представлена как RFC 1321 в апреле 1992 года ([90]).
MD5 разрабатывалась как криптографически-стойкая хеш-функция с длиной выходного блока 128 бит. Исходный текст сначала дополняется до целого числа обрабатываемых блоков по 512 бит (рис. 8.2).
- Дополнение (паддинг). Исходное сообщение рассматривается как последовательность бит и дополняется сначала единичным битом 1, а далее нулевыми битами 000
000 - Добавление длины сообщения. Длина исходного сообщения в битах (до дополнения) добавляется в виде 64-битового значения к обрабатываемому тексту. Если текст имеет длину больше, чем $2^{64}$ бита, используется остаток от деления длины на $2^{64}$.
Далее обрабатываемый текст разбивается на целое число 512-битовых блоков $M_i$ и выполняется последовательное вычисление хеш-функции по итеративной формуле:
В качестве начального значения $H_0 = \text{IV}$ выступает конкатенация заданных в стандарте 16-ричных последовательностей:
Каждый из раундов вычисления $H_i = f ( H_{i-1}, M_i )$ состоит из 16 итераций (рис. 8.3), в которых выполняется преобразование четырёх 8-битовых блоков $A, B, C, D$. Основное преобразование выполняется с первым из блоков $A$ (который в конце итерации становится блоком $B$, и далее по кругу, что делает процедуру чем-то похожей на схему Фейстеля). К значению $A_{x-1}$ из результата предыдущей итерации (или предыдущего раунда, если это первая итерация) прибавляется значение нелинейной функции $F(B, C, D)$, числовое значение некоторого байта из $M_i$ (индекс байта определяется константой $g_x$), значение «ключа» итерации $K_x$. Полученное значение сдвигается влево на количество бит, определяемое ещё одной константой итерации $s_x$, арифметически складывается со значением блока $B_{x-1}$ и считается новым значением блока $B_x$. Остальные блоки циклически сдвигаются без изменений ($B_{x-1} \to C_x$, $C_{x-1} \to D_x$, $D_{x-1} \to A_x$).
Вид нелинейной функции $F$ и значения констант $g_x$, $K_x$, $s_x$ отличаются для каждой из 16 итераций и заданы в описании на хеш-функции.
Значения $A, B, C, D$ результата обработки самого последнего блока $M_i$ конкатенируются и считаются результатом вычисления хеш-функции.
Уже на примере хеш-функции, предложенной в 1991 году, можно увидеть общие свойства, которые присущи большей части современных хеш-функций.
- Во-первых, разбиение исходного текста на блоки равной длины и дополнение последнего блока дополнительными значениями (для финального преобразования), возможно включая длину исходного открытого текста или какую-либо простую функцию от всех блоков сообщения.
- Во-вторых, наличие некоторой функции преобразования $H_i = f ( H_{i-1}, M_i )$, которую можно рассматривать как фактически функцию шифрования некоторого блочного шифра. Но при этом в качестве шифруемого текста выступает результат хеширования предыдущего блока $H_{i-1}$, а блок исходного хешируемого сообщения $M_i$ выступает в качестве ключа шифрования. От стойкости данного шифра зависит возможность (при известных $H_{i-1}$ и $H_{i}$) восстановить «ключ шифрования», то есть часть исходного сообщения, особенно если оно короткое (меньше одного блока, то есть фактически осуществить атаку на восстановление прообраза.
В 1996 году Ханс Доббертин нашёл коллизии в модификации MD5, которая отличалась от оригинальной только изменением инициализирующих значений $A, B, C, D$, что явно показало наличие уязвимости в дизайне хеш-функции. В 2004 году было объявлено о существовании алгоритма нахождения коллизий к оригинальной хеш-функции с помощью суперкомпьютера, в 2005 году был опубликован подобный алгоритм с примером коллизии, а в 2006 году исследователь из Чехии Властимил Клима представил алгоритм для обычного персонального компьютера с возможностью использования любых начальных значений $A, B, C, D$ ([25, 56, 106]).
В настоящий момент данная хеш-функция считается криптографически нестойкой, но ранее она широко использовалась для обеспечения защиты информации, например для хеширования паролей в некоторых версиях Linux и FreeBSD, для генерации имитовставки HMAC-MD5, для проверки целостности файлов и прочих целей. Большое количество стандартных библиотек времени исполнения, систем управления базами данных и даже программ обработки электронных таблиц содержат встроенные функции для вычисления значений хеш-функции MD5.