19 марта 2012

Алгоритм хэширования MD4

Данная статья является продолжением цикла статей про алгоритмы хэширования семейства MD. Она описывает структуру широко распространенного алгоритма хэширования MD4. Данный алгоритм активно использовался до начала 2000 гг. – до тех пор, когда была предложена эффективная атака на MD4, позволяющая практически мгновенно найти коллизию (обзору результатов криптоанализа MD4 будет посвящена следующая статья цикла).
MD4 интересен не только тем, что он был одним из наиболее широко применяемых алгоритмов хэширования в мире, но и тем, что на основе заложенных в MD4 идей были разработаны многие другие известные алгоритмы хэширования – прежде всего, алгоритмы семейства SHA [1, 2].

Как и другие алгоритмы семейства MD, MD4 разработан Рональдом Ривестом; данный алгоритм был предложен в 1990 г. Алгоритм MD4 подробно описан в документах RFC 1186 [3] и RFC 1320 [4].

Структура алгоритма MD4 полностью соответствует схеме Меркля-Дамгаарда. Данная схема была предложена в 1988-1989 гг. независимо двумя известными криптологами: Ральфом Мерклем (Ralph Merkle) и Айвеном Дамгаардом (Ivan Damgard) [5]. Суть схемы состоит в следующем (см. рис. 1).

Хэшируемое сообщение M разбивается на блоки определенной длины M₀…M_N. Выполняется (по-разному в различных алгоритмах) дополнение сообщения M до размера, кратного данной длине блока (при этом количество блоков может увеличиться).
Каждый i-й блок сообщения обрабатывается функцией fb(), являющейся криптографическим ядром алгоритма хэширования, причем данная функция накладывает результат этой обработки на текущее хэш-значение H_i-1 (т. е. на результат обработки предыдущих блоков сообщения):

H_i = fb(H_i-1, M_i).

Результатом работы алгоритма хэширования hash() (т. е. хэш-значением сообщения M) является значение H_N:

hash(M) = H_N.

Начальное значение H-1 обычно является константным и различным в различных алгоритмах хэширования; оно часто обозначается как IV (от Initialization Vector – вектор инициализации).

Рис. 1 Схема Меркля-Дамгаарда

Алгоритм MD4 вычисляет 128-битовое хэш-значение от входного блока данных переменного и неограниченного размера.
Прежде всего, входное сообщение разбивается на блоки размером по 512 битов. Последний блок всегда дополняется до 512-битового размера следующим образом:

сначала добавляется единичный бит;
затем – нулевые биты до размера 448 битов (т. е. 512 - 64); нулевые биты не добавляются, если после добавления единичного бита блок имеет 448-битовый размер;
к последовательности добавляется 64-битовое значение, равное размеру в битах исходной последовательности входных данных до дополнения.

В [4] Ривест отметил, что если размер сообщения в битах L превышает 2⁶⁴ - 1 (что можно считать крайне маловероятным), то значение размера становится невозможно записать в 64 бита. Поэтому в качестве размера записывается не L, а значение L mod 2⁶⁴.
Если изначально размер последнего блока равен 448 битам (или больше), дополнение выполняется все равно, при этом количество блоков увеличивается на один.
Для хранения промежуточных значений алгоритм использует 4 регистра по 32 бита, которые обозначаются как A, B, C и D. Они инициализируются перед началом вычислений согласно следующей таблице (указаны шестнадцатеричные значения):

Регистр	Исходное значение
A	01234567
B	89ABCDEF
C	FEDCBA98
D	76543210

Согласно описанной выше схеме Меркля-Дамгаарда, совокупность регистров A…D содержит значение H_i после обработки i-го блока сообщения, а указанное в таблице начальное заполнение регистров является вектором инициализации алгоритма.
Каждый из 512-битовых блоков входных данных M_i поочередно обрабатывается следующим образом:

Блок входных данных представляется в виде 16 слов M[0]…M[15], каждое из которых является 32-битовым.
Содержимое регистров A…D копируется во временные переменные a…d.

Рис. 2 Итерация алгоритма MD4

Выполняются 48 итераций преобразований (см. рис. 2), в каждой из которых модифицируются переменные a…d с участием одного из слов блока сообщения M[0]…M[15]:

t = (a + f_j(b, c, d) + M[x_j] + K_j mod 2³²) <<< s_j;
a = d;
d = c;
c = b;
b = t,
где:

j – номер итерации, j = 0…47;
t – временная 32-битовая переменная;
f_j() – одна из следующих раундовых функций (в таблице символами & и | обозначены, соответственно, побитовые логические операции «и» и «или»; ~x обозначает побитовый комплемент к x):

Номер итерации j	f_j()
0…15	f_j(x, y, z) = (x & y) \| (~x & z)
16…31	f_j(x, y, z) = (x & y) \| (x & z) \| (y & z)
32…47	f_j(x, y, z) = x A y A z

индекс используемого слова блока сообщения xj определяется следующим образом:

Номер итерации j	x_j
0, 16, 32	0
1, 20, 40	1
2, 24, 36	2
3, 28, 44	3
4, 17, 34	4
5, 21, 42	5
6, 25, 38	6
7, 29, 46	7
8, 18, 33	8
9, 22, 41	9
10, 26, 37	10
11, 30, 45	11
12, 19, 35	12
13, 23, 43	13
14, 27, 39	14
15, 31, 47	15

Kj – модифицирующие константы (указаны шестнадцатеричные значения):

Номер итерации j	K_j
0…15	0
16…31	5A827999
32…47	6ED9EBA1

Происхождение второй и третьей констант – округленный результат умножения, соответственно, значений и на 2³² [6]. Отметим, что в [4] в качестве источника данных констант ошибочно указаны значения и вместо и .

<<< – операция побитового циклического сдвига влево; количество битов сдвига sj определяется в зависимости от номера итерации согласно следующей таблице:

Номер итерации j	s_j
0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44	3
17, 21, 25, 29	5
1, 5, 9, 13	7
18, 22, 26, 30, 33, 37, 41, 45	9
2, 6, 10, 14, 34, 38, 42, 46	11
19, 23, 27, 31	13
35, 39, 43, 47	15
3, 7, 11, 15	19

Значения регистров A…D складываются по модулю 2³² с полученными значениями переменных a…d соответственно.

Выходное значение алгоритма, т. е. 128-битовое хэш-значение сообщения – результат конкатенации регистров A…D после обработки последнего блока расширенного сообщения.

Алгоритм MD4 выглядит не более сложным в реализации, чем алгоритм MD2. В отличие от MD2, MD4 не содержит таблиц замен и может быть весьма компактно реализован аппаратно [4].

В [3] описан также расширенный вариант алгоритма MD4, который позволяет вычислить 256-битовое хэш-значение. Расширенный вариант основан на параллельном применении двух копий обычного алгоритма MD4. Вычисления выполняются следующим образом:

Первая копия алгоритма выполняется обычным образом, за исключением описанного далее обмена значениями регистров A.
Во второй копии применяются другие начальные значения регистров A…D согласно таблице (в этой и следующей таблицах указаны шестнадцатеричные значения):

Регистр	Исходное значение
A	00112233
B	44556677
C	8899AABB
D	CCDDEEFF

В итерациях 16…47 используются другие значения модифицирующих констант K_j:

Номер итерации j	K_j
16…31	50A28BE6
32…47	5C4DD124

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

Результирующим 256-битовым хэш-значением алгоритма является конкатенация регистров A…D первой копии MD4 и регистров A…D второй копии после обработки всех блоков входных данных. Отметим, что расширенный вариант алгоритма MD4 продолжает соответствовать схеме Меркля-Дамгаарда.
Из более поздней спецификации алгоритма MD4 ([4]) расширенный вариант исключен.

Литература

FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
FIPS PUB 180-2. Secure Hash Standard. // http://www.securitytechnet.com – National Institute of Standards and Technology – 2002 August 1.
Rivest R. RFC 1186: The MD4 Message Digest Algorithm. // http://www.ietf.org – MIT Laboratory for Computer Science – October 1990.
Rivest R. RFC 1320: The MD4 Message Digest Algorithm. // http://www.ietf.org – April 1992.
Merkle-Damgard construction. From Wikipedia, the free encyclopedia // http://en.wikipedia.org.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.

Просмотров: 13138

Мнения экспертов

Рогушин Я.Г.
ОКО+
Главный инженер

Данная статья, как и предыдущие статьи из этой серии, безупречна во всех отношениях. Несложная подача материала. Подробная информация о всех аспектах темы.

Коробанов В.А.
ООО "Альманах"
ведущий специалист

Продолжение цикла статей о криптографических алгоритмах. Читается немного туговато, так как приводится «сухой» алгоритм шифрования. Внести некоторую динамику в статью можно было бы добавив перечень программ и систем, использующих данный алгоритм и историей вскрытия такого шифрования. Хотя обзор криптостойкости обещан в следующей части.