13 августа 2012

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

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

Алгоритм MD5 был предложен в 1992 г., т. е. всего через два года после опубликования алгоритма MD4. Предпосылки разработки MD5 были таковы [1]:

при разработке алгоритма MD4 основным критерием было быстродействие данного алгоритма, его криптостойкость была несколько менее важна; в результате, уже в 1991 г. была опубликована первая атака на усеченный алгоритм MD4 (см. обзор криптоаналитических атак на MD4 в [2]);
поскольку алгоритм MD4 получился исключительно быстрым, особенно на 32-битных платформах, предполагалось, что именно поэтому он будет в центре внимания криптоаналитиков, что, рано или поздно, приведет к обнаружению уязвимостей и к успешным криптоаналитическим атакам на данный алгоритм.

В результате Рональд Ривест разработал алгоритм MD5 – несколько более медленный, чем MD4, но обладающий более консервативным дизайном и учитывающий текущие результаты и тенденции в криптоанализе, что предопределило несколько более высокую, по сравнению с MD4, криптостойкость данного алгоритма (обзор результатов криптоанализа алгоритма MD5 будет дан в последующих статьях).

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

добавляется единичный бит;
затем – нулевые биты до размера 448 битов; нулевые биты не добавляются, если после добавления единичного бита блок имеет 448-битовый размер;
к последовательности добавляется 64-битовое значение, равное размеру в битах исходной последовательности входных данных до дополнения; если размер сообщения превышает 2⁶⁴ - 1, то записывается значение размера по модулю 2⁶⁴.

Аналогично алгоритму MD4, для хранения промежуточных значений после обработки каждого блока сообщения используются 32-битные регистры A, B, C и D. Вектор инициализации алгоритма MD5 эквивалентен таковому в MD4 (указаны шестнадцатеричные значения):

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

512-битовые блоки дополненного сообщения M_i поочередно обрабатывается следующим образом:

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

width=
Рис. 1. Итерация алгоритма MD5.

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

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

j – номер итерации, j = 1…64 (каждые 16 итераций формируют один из четырех раундов алгоритма);
t – временная 32-битовая переменная;
f_j() – одна из следующих раундовых функций:

Номер итерации j	f_j()
1…16	f_j(x, y, z) = (x & y) \| (~x & z)
17…32	f_j(x, y, z) = (x & z) \| (y & ~z)
33…48	f_j(x, y, z) = x ⊕ y ⊕ z
49…64	f_j(x, y, z) = y ⊕ (x \| ~z)

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

Номер итерации j	x_j
1, 20, 42, 49	0
2, 17, 37, 56	1
3, 30, 48, 63	2
4, 27, 43, 54	3
5, 24, 38, 61	4
6, 21, 33, 52	5
7, 18, 44, 59	6
8, 31, 39, 50	7
9, 28, 34, 57	8
10, 25, 45, 64	9
11, 22, 40, 55	10
12, 19, 35, 62	11
13, 32, 46, 53	12
14, 29, 41, 60	13
15, 26, 36, 51	14
16, 23, 47, 58	15

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

Номер итерации j	T_j
1	d76aa478
2	e8c7b756
3	242070db
4	c1bdceee
5	f57c0faf
6	4787c62a
7	a8304613
8	fd469501
9	698098d8
10	8b44f7af
11	ffff5bb1
12	895cd7be
13	6b901122
14	fd987193
15	a679438e
16	49b40821
17	f61e2562
18	c040b340
19	265e5a51
20	e9b6c7aa
21	d62f105d
22	02441453
23	d8a1e681
24	e7d3fbc8
25	21e1cde6
26	c33707d6
27	f4d50d87
28	455a14ed
29	a9e3e905
30	fcefa3f8
31	676f02d9
32	8d2a4c8a
33	fffa3942
34	8771f681
35	6d9d6122
36	fde5380c
37	a4beea44
38	4bdecfa9
39	f6bb4b60
40	bebfbc70
41	289b7ec6
42	eaa127fa
43	d4ef3085
44	04881d05
45	d9d4d039
46	e6db99e5
47	1fa27cf8
48	c4ac5665
49	f4292244
50	432aff97
51	ab9423a7
52	fc93a039
53	655b59c3
54	8f0ccc92
55	ffeff47d
56	85845dd1
57	6fa87e4f
58	fe2ce6e0
59	a3014314
60	4e0811a1
61	f7537e82
62	bd3af235
63	2ad7d2bb
64	eb86d391

Происхождение псевдослучайных констант K_j согласно [1] таково:
K_j = trunc(abs(sin(j)) * 2³²),
где j берется в радианах.

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

Номер итерации j	s_j
33, 37, 41, 45	4
17, 21, 25, 29	5
49, 53, 57, 61	6
1, 5, 9, 13	7
18, 22, 26, 30	9
50, 54, 58, 62	10
34, 38, 42, 46	11
2, 6, 10, 14	12
19, 23, 27, 31	14
51, 55, 59, 63	15
35, 39, 43, 47	16
3, 7, 11, 15	17
20, 24, 28, 32	20
52, 56, 60, 64	21
4, 8, 12, 16	22
36, 40, 44, 48	23

Последняя итерация при обработке каждого блока сообщения отличается от остальных тем, что в ней выполняется только следующая операция:
a = b + ((a + f_j(b, c, d) + M[x_j] + T_j mod 2³²) <<< s_j) mod 2³².

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

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

Основные отличия алгоритма MD5 от MD4 таковы [1]:

в алгоритме выполняется 4 раунда вместо трех;
изменены раундовые функции f_j(); в частности, больше не используется функция f_j(x, y, z) = (x & y) | (x & z) | (y & z), свойства которой вызвали сомнения у криптологов еще в 1990 г. (см. [2]);
в каждую итерацию добавлена дополнительная операция сложения с переменной b (отметим, что именно переменная b модифицируется в каждой предыдущей итерации, за исключением первой) по модулю 2³², ускоряющая влияние значений битов входных данных на биты выходного значения;
в каждом раунде теперь используются уникальные модифицирующие константы;
изменен (на менее упорядоченный) порядок обработки входных слов блока сообщения, а также оптимизированы величины s_j.

Алгоритм MD5 не выглядит более сложным в реализации, чем алгоритм MD4. Все изменения в алгоритме являются достаточно локальными, но в совокупности автору алгоритма удалось решить задачу его усиления за счет некоторого ухудшения скоростных качеств алгоритма (согласно [3], MD4 примерно в 1,5 раза быстрее, чем MD5).

Литература

Rivest R. RFC 1321. The MD5 Message-Digest Algorithm. // http://www.ietf.org – April 1992.
Панасенко С. Алгоритм хэширования MD4: обзор криптоаналитических исследований. // http://daily.sec.ru – 2012.
Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996.

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