Interested Article - MD2

MD2 (The MD2 Message Digest Algorithm) — криптографическая хеш-функция , разработанная Рональдом Ривестом (RSA Laboratories) в 1989 году, и описанная в . На входе сообщение произвольный длины. Размер хеша — 128 бит. В настоящий момент алгоритм MD2 считается уже устаревшим, а соответствующий ему переведен в исторический статус.

История

Рональд Ривест разработал серию алгоритмов хеширования, названных MDx, где x — порядковый номер алгоритма.

MD1 — закрытый алгоритм, спецификация которого не была опубликована.

MD2 был разработан в 1989 г. для использования в качестве одного из криптографических алгоритмов, входящих в стандарт защищенной электронной почты ; его реализация на языке Си была приведена в . А в 1990 году MD2 был предложен в качестве замены . Впоследствии спецификация и обновленная реализация MD2 были опубликованы в .

MD3 никогда не был опубликован. По всей видимости разработка MD3 была заброшена . После MD2 были разработаны MD4 , MD5 и MD6 в 1990, 1991 и 2008 годах соответственно.

В 2011 году MD2 был официально списан из-за многочисленных успешных криптоатак. Сейчас использовать MD2 рекомендуют только в целях совместимости со старыми программами, которые до сих пор полагаются на него .

Алгоритм MD2

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

m_{0}m_{1}\ldots m_{b-1}

m_0 m_1 \ldots m_{b-1}

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

Шаг 1. Добавление недостающих бит.

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

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

Например, если длина сообщения 28 байт, то оно дополняется до 32 байт дополнительными четырьмя, каждый из которых равен четырём.

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

Шаг 2. Добавление контрольной суммы.

16-байтная контрольная сумма сообщения добавляется к результату предыдущего шага.

Контрольная сумма вычисляется следующим образом: для каждого 16-байтного блока дополненного сообщения 16 раз выполняются следующие действия:

$c=M[i*16+j]$ $c=M[i*16+j]$ ,

$C[j]=S[c\oplus L]\oplus C[j]$ $C[j]=S[c \oplus L] \oplus C[j]$ ,

$L=C[j]$ $L=C[j]$

, где i — номер 16-байтного блока данных;

j — номер текущего шага цикла;

$M[x]$ $M[x]$ — x-й байт сообщения, то есть $M[i*16+j]$ $M[i * 16 + j]$ — это j-й байт текущего блока данных;

с и L — временные переменные, L изначально содержит значение 0;

$C[j]$ $C[j]$ — j-й байт массива контрольной суммы; перед вычислением контрольной суммы массив содержит нулевые байты;

$S[i]$ $S[i]$ — i-й элемент 256-байтной матрицы из «случайно» переставленных цифр числа пи :

41	46	67	201	162	216	124	1	61	54	84	161	236	240	6	19
98	167	5	243	192	199	115	140	152	147	43	217	188	76	130	202
30	155	87	60	253	212	224	22	103	66	111	24	138	23	229	18
190	78	196	214	218	158	222	73	160	251	245	142	187	47	238	122
169	104	121	145	21	178	7	63	148	194	16	137	11	34	95	33
128	127	93	154	90	144	50	39	53	62	204	231	191	247	151	3
255	25	48	179	72	165	181	209	215	94	146	42	172	86	170	198
79	184	56	210	150	164	125	182	118	252	107	226	156	116	4	241
69	157	112	89	100	113	135	32	134	91	207	101	230	45	168	2
27	96	37	173	174	176	185	246	28	70	97	105	52	64	126	15
85	71	163	35	221	81	175	58	195	92	249	206	186	197	234	38
44	83	13	110	133	40	132	9	211	223	205	244	65	129	77	82
106	220	55	200	108	193	171	250	36	225	123	8	12	189	177	74
120	136	149	139	227	99	232	109	233	203	213	254	59	0	29	57
242	239	183	14	102	88	208	228	166	119	114	248	235	117	75	10
49	68	80	180	143	237	31	26	219	153	141	51	159	17	131	20

Данная таблица используется и в функции сжатия алгоритма MD2 на 4-м шаге.

Программная реализация 2-го шага на псевдокоде:

 /* Clear checksum. */ For i = 0 to 15 do: Set C[i] to 0. end /* of loop on i */ Set L to 0. /* Process each 16-word block. */ For i = 0 to N/16-1 do /* Checksum block i. */ For j = 0 to 15 do Set c to M[i*16+j]. Set C[j] to C[j] xor S[c xor L]. Set L to C[j]. end /* of loop on j */ end /* of loop on i */

16-байтная контрольная сумма $C[0\ldots 15]$ $C[0 \ldots 15]$ добавляется к сообщению. Теперь сообщение можно записать в виде $M[0\ldots N_{1}-1]$ $M[0 \ldots N_1-1]$ , где $N_{1}=N+16$ $N_1 = N + 16$ .

Шаг 3. Инициализация MD-буфера.

48-байтный буфер X используется для вычисления хеша. Он инициализируется нулями.

Шаг 4. Обработка сообщения блоками по 16 байт.

На этом шаге используется та же 256-байтная перестановочная матрица S, как и на шаге 2.

Каждый 16-байтный i-й блок дополненного сообщения, включая блок контрольной суммы, накладывается на буфер X следующим образом:

Блок данных копируется в буфер следующим образом:

$X[16+j]=M[i*16+j]$ $X[16 + j] = M[i * 16 + j]$ , j = 0…15,

$X[32+j]=(X[16+j]\oplus X[j])$ $X[32 + j] = (X[16 + j] \oplus X[j])$ , j = 0…15.

Таким образом, если представить буфер X как 3 фрагмента по 16 байт, то после копирования блока данных второй из фрагментов буфера содержит обрабатываемый блок данных, а третий — результат применения побитовой операции «исключающее или» (XOR) к текущему содержимому первого фрагмента и блока данных.
Выполняется обработка буфера, которая состоит из 18 раундов преобразований, в рамках каждого из которых выполняется обновление каждого байта буфера следующим образом:
$X[k]=(X[k]\oplus S[t])$ $X[k] = (X[k] \oplus S[t])$ , $t=X[k]$ $t = X[k]$ ,
где k = 0…47,

t — временная переменная, которая изначально имеет нулевое значение, а после выполнения каждого j-го раунда (j = 0…17) t модифицируется по правилу:

$t=t+j\mod 256$ $t = t + j \mod 256$ .

Реализация 4-го шага на псевдокоде:

 /* Process each 16-word block. */ For i = 0 to N1/16-1 do /* Copy block i into X. */ For j = 0 to 15 do Set X[16+j] to M[i*16+j]. Set X[32+j] to (X[16+j] xor X[j]). end /* of loop on j */ Set t to 0. /* Do 18 rounds. */ For j = 0 to 17 do /* Round j. */ For k = 0 to 47 do Set t and X[k] to (X[k] xor S[t]). end /* of loop on k */ Set t to (t+j) modulo 256. end /* of loop on j */ end /* of loop on i */

Шаг 5. Формирование хеша.

Хеш вычисляется как результат $X[0\ldots 15]$ $X[0 \ldots 15]$ ; в начале идет байт $X[0]$ $X[0]$ , а конце $X[15]$ $X[15]$ .

На этом завершается описание алгоритма MD2. В можно найти реализацию алгоритма на языке C.

Пример

MD2 («123456789012345678901234567890123456789012345678901234567890123456 78901234567890») = 05dbba941443332475b8e3f572f5d148

Быстродействие

MD2 относительно медленный алгоритм хеширования по сравнению с остальными известными алгоритмами. Ниже в таблице приведены скорости вычисления хеш-суммы сообщений разных алгоритмов хеширования на IBM PS/2 (16 MHz 80386) .

Алгоритм	Скорость, Кбит/с	Год
MD2	78	1989
FFT-hash I	212	1991
N-Hash	266	1990
Snefru-8	270	1990
Snefru-6	358	1990
Snefru-4	520	1990
SHA	710	1995
Snefru-2	970	1990
RIPEMD	1334	1996
MD5	1849	1995
MD4	2669	1990

Из таблицы видно, что MD2 по скорости уступает другим широко используемым алгоритмам, как минимум, на порядок.

Безопасность

Автор MD2, Рональд Ривест , предполагал, что:

сложность задачи поиска прообраза по известной хеш-сумме имеет порядок 2 ¹²⁸ операций
сложность задачи поиска коллизии (двух сообщений с одинаковой хеш-суммой ) имеет порядок 2 ⁶⁴ операций

В 1994 году Брюс Шнайер написал про алгоритм MD2, что, хотя он и более медленный, чем другие алгоритмы хеширования, но на тот момент являлся криптографически стойким .

С тех пор криптоаналитики достигли существенных успехов в анализе MD2; сейчас алгоритм считается взломанным .

История криптоанализа MD2

В 1993 году Барт Пренел в своей работе заметил, что, поскольку последние 32 байта буфера алгоритма не используются в выходном хеш-значении, можно пропустить обновление этих байтов в последней итерации обработки буфера для последнего блока входных данных. В той же работе отмечается, что количество раундов алгоритма (18) всего на один раунд превышает минимально возможное для того, чтобы выходное значение алгоритма могло достигать всех возможных из 2 ¹²⁸ вариантов. Следовательно, можно сделать вывод, что запас криптостойкости алгоритма является минимальным и что невозможно без потери стойкости увеличить скорость хеширования путём уменьшения количества раундов. Барт Пренел также предложил методику проведения атак на полнораундовый MD2 с использованием дифференциального криптоанализа , но не описал конкретных атак на алгоритм.

В 1995 году был предложен метод поиска коллизий, но он не был успешным благодаря контрольной сумме добавляемой в конец сообщения . В некоторых работах отмечалось, что из-за оригинального дизайна алгоритма MD2, к данному алгоритму неприменимы известные результаты криптоанализа хеш-функций с классической структурой. Тем не менее ещё в 1996 г. компания RSA порекомендовала не использовать алгоритм MD2 в тех случаях, когда требуется отсутствие коллизий. Но в остальном MD2 оставался безопасным .

Роже и Шаво в 1997 году опубликовали пример коллизий для MD2, хотя и не смогли представить алгоритма нахождения других коллизий.

Первую атаку на MD2 целиком в 2004 году предложил Фредерих Мюллер, позволяющую найти прообраз с трудоёмкостью 2 ¹⁰⁴ операций, что существенно меньше теоретической трудоёмкости поиска прообраза для MD2, которая составляет 2 ¹²⁸ операций. Мюллер заявил: «MD2 не может больше рассматриваться, как криптостойкий алгоритм хеширования» . Хотя трудоёмкость атаки являлась все же слишком большой для возможности осуществления данной атаки на практике.

В 2005 году Ларс Кнудсен и существенно улучшили результаты Мюллера, предложив атаки, которые не только уменьшали трудоёмкость атак, но и позволяли находить искомые сообщения варьированной длины, в то время как атаки Мюллера позволяли находить лишь прообразы длиной в 128 блоков по 16 байт .

Следующий большой шаг в криптоанализе MD2 был сделан в 2008 году. Ему удалось уменьшить трудоёмкость задачи поиска прообраза до 2 ⁷³ операций , что приблизило эту атаку к статусу реализуемой на практике.

Через год, объединив усилия, авторы предыдущих работ (Ларс Кнудсен, Джон Матиассен, Фредерих Мюллер, Сорен Томсен) улучшили результаты атаки на поиск коллизий, достигнув сложности в 2 ^63,3 операций, что чуть ниже теоретической (2 ⁶⁴ ) .

Применение

Благодаря своей надежности и простоте в реализации, MD2 использовался во многих сетевых протоколах , в том числе:

Протокол защищенной электронной почты PEM (Privacy-Enhanced Mail) , в более поздних версиях PEM MD2 использовался наряду с более надежным MD5
Инфраструктура открытых ключей PKI (Public Keys Infrastructure) , однако уже в спецификации 1999 года рекомендуется использовать SHA-1 или MD5
Стандарт асимметричных криптоопераций PKCS #1 (Public Key Cryptography Standard) , разрешал использование шести алгоритмов хеширования: MD2, MD5, SHA-1, SHA-256, SHA-384 и SHA-512, причем первые два рекомендовалось использовать лишь в целях совместимости со старыми приложениями .

См. также

Примечания

↑ Preneel B. Analysis and Design of Cryptographic Hash Functions — February 2003
J. Linn. (англ.) . IETF (август 1989). Архивировано из 2 декабря 2012 года.
J. Linn. (англ.) . IETF (январь 1988). Архивировано из 2 декабря 2012 года.
B. Kaliski. (англ.) . RSA Laboratories (апрель 1992). Архивировано из 2 декабря 2012 года.
↑ S. Turner, L. Chen. (англ.) . IETF (март 2011). Архивировано из 2 декабря 2012 года.
S. Bakhtiari, R. Safavi-naini, J. Pieprzyk, Cryptographic Hash Functions: A Survey (1995)
↑ Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C (1995)
, (англ.) // — , Springer Science+Business Media , 1997. — Vol. 12, Iss. 3. — P. 245–251. — ISSN ; —
↑ (англ.) // : 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings / — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 2004. — P. 214—229. — 548 p. — (; Vol. 3329) — ISBN 978-3-540-23975-8 — ISSN ; —
Robshaw M. J. B. (англ.) (1996).
Knudsen L. R. , (англ.) // : 12th International Workshop, FSE 2005, Paris, France, February 21-23, 2005, Revised Selected Papers / , — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 2005. — P. 255—267. — 443 p. — (; Vol. 3557) — ISBN 978-3-540-26541-2 — ISSN ; —
Thomsen S. S., An improved preimage attack on MD2 (2008)
Knudsen L. R. , , , (англ.) // / — Springer Science+Business Media , International Association for Cryptologic Research , 2010. — Vol. 23, Iss. 1. — P. 72–90. — ISSN ; —
D. Balenson. (англ.) (февраль 1993). Архивировано из 2 декабря 2012 года.
R. Housley, W. Ford, W. Polk, D. Solo. (англ.) (январь 1999). Архивировано из 2 декабря 2012 года.
J. Jonsson, B. Kaliski. (англ.) (февраль 2003). Архивировано из 2 декабря 2012 года.

Ссылки

[phd_preneel-1] Preneel B. Analysis and Design of Cryptographic Hash Functions — February 2003

[rfc1115_faq-2] J. Linn. (англ.) . IETF (август 1989). Архивировано из 2 декабря 2012 года.

[rfc1040_faq-3] J. Linn. (англ.) . IETF (январь 1988). Архивировано из 2 декабря 2012 года.

[rfc1319_faq-4] B. Kaliski. (англ.) . RSA Laboratories (апрель 1992). Архивировано из 2 декабря 2012 года.

[rfc6149_faq-5] S. Turner, L. Chen. (англ.) . IETF (март 2011). Архивировано из 2 декабря 2012 года.

[hash_survey-6] S. Bakhtiari, R. Safavi-naini, J. Pieprzyk, Cryptographic Hash Functions: A Survey (1995)

[schneier-7] Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C (1995)

[autogenerated1-8] , (англ.) // — , Springer Science+Business Media , 1997. — Vol. 12, Iss. 3. — P. 245–251. — ISSN ; —

[muller-9] (англ.) // : 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings / — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 2004. — P. 214—229. — 548 p. — (; Vol. 3329) — ISBN 978-3-540-23975-8 — ISSN ; —

[robshaw-10] Robshaw M. J. B. (англ.) (1996).

[knudsen_mathiassen-11] Knudsen L. R. , (англ.) // : 12th International Workshop, FSE 2005, Paris, France, February 21-23, 2005, Revised Selected Papers / , — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 2005. — P. 255—267. — 443 p. — (; Vol. 3557) — ISBN 978-3-540-26541-2 — ISSN ; —

[thomsen-12] Thomsen S. S., An improved preimage attack on MD2 (2008)

[13] Knudsen L. R. , , , (англ.) // / — Springer Science+Business Media , International Association for Cryptologic Research , 2010. — Vol. 23, Iss. 1. — P. 72–90. — ISSN ; —

[rfc1423_faq-14] D. Balenson. (англ.) (февраль 1993). Архивировано из 2 декабря 2012 года.

[rfc2459_faq-15] R. Housley, W. Ford, W. Polk, D. Solo. (англ.) (январь 1999). Архивировано из 2 декабря 2012 года.

[rfc3447_faq-16] J. Jonsson, B. Kaliski. (англ.) (февраль 2003). Архивировано из 2 декабря 2012 года.

41	46	67	201	162	216	124	1	61	54	84	161	236	240	6	19
98	167	5	243	192	199	115	140	152	147	43	217	188	76	130	202
30	155	87	60	253	212	224	22	103	66	111	24	138	23	229	18
190	78	196	214	218	158	222	73	160	251	245	142	187	47	238	122
169	104	121	145	21	178	7	63	148	194	16	137	11	34	95	33
128	127	93	154	90	144	50	39	53	62	204	231	191	247	151	3
255	25	48	179	72	165	181	209	215	94	146	42	172	86	170	198
79	184	56	210	150	164	125	182	118	252	107	226	156	116	4	241
69	157	112	89	100	113	135	32	134	91	207	101	230	45	168	2
27	96	37	173	174	176	185	246	28	70	97	105	52	64	126	15
85	71	163	35	221	81	175	58	195	92	249	206	186	197	234	38
44	83	13	110	133	40	132	9	211	223	205	244	65	129	77	82
106	220	55	200	108	193	171	250	36	225	123	8	12	189	177	74
120	136	149	139	227	99	232	109	233	203	213	254	59	0	29	57
242	239	183	14	102	88	208	228	166	119	114	248	235	117	75	10
49	68	80	180	143	237	31	26	219	153	141	51	159	17	131	20

41	46	67	201	162	216	124	1	61	54	84	161	236	240	6	19
98	167	5	243	192	199	115	140	152	147	43	217	188	76	130	202
30	155	87	60	253	212	224	22	103	66	111	24	138	23	229	18
190	78	196	214	218	158	222	73	160	251	245	142	187	47	238	122
169	104	121	145	21	178	7	63	148	194	16	137	11	34	95	33
128	127	93	154	90	144	50	39	53	62	204	231	191	247	151	3
255	25	48	179	72	165	181	209	215	94	146	42	172	86	170	198
79	184	56	210	150	164	125	182	118	252	107	226	156	116	4	241
69	157	112	89	100	113	135	32	134	91	207	101	230	45	168	2
27	96	37	173	174	176	185	246	28	70	97	105	52	64	126	15
85	71	163	35	221	81	175	58	195	92	249	206	186	197	234	38
44	83	13	110	133	40	132	9	211	223	205	244	65	129	77	82
106	220	55	200	108	193	171	250	36	225	123	8	12	189	177	74
120	136	149	139	227	99	232	109	233	203	213	254	59	0	29	57
242	239	183	14	102	88	208	228	166	119	114	248	235	117	75	10
49	68	80	180	143	237	31	26	219	153	141	51	159	17	131	20

История

Алгоритм MD2

Шаг 1. Добавление недостающих бит.

Шаг 2. Добавление контрольной суммы.

Шаг 3. Инициализация MD-буфера.

Шаг 4. Обработка сообщения блоками по 16 байт.

Шаг 5. Формирование хеша.

Пример

Быстродействие

Безопасность

История криптоанализа MD2

Применение

См. также

Примечания

Ссылки

Марокканский риал

Сулейман I

Физалис

Same as MD2

Марокканский риал

Сулейман I

Физалис

САУ Дриженко

GW-BASIC

Глубинное экологическое сопротивление

2019 год в экономике

IBM Roadrunner

Киекбаев, Джалиль Гиниятович

Понизовая вольница

Мэтьюс, Дэйв

Ферромагнетизм

Hawker Siddeley Nimrod

Умершие в округе Сакраменто

Восточный Артиллерийский мост

1073 год

Картаполов, Андрей Валериевич

Келли, Нэнси

Назад в будущее 3

Атака Таранто

Деказ, Эли

Портелья

Густера

Шанхайский центр восточного искусства

Handley Page Halifax

Вергун, Наталья Ивановна

V476 Большой Медведицы

Аранци, Юлий Цезарь

Шаг (денежная единица)

Анна Всеволодовна (городенская княжна)

Алёхин, Николай Михайлович (юрист)

Туризм в Бельгии

Марч, Фредрик

Вероника густоцветковая

Броссе, Марий Иванович

Послания Иоанна

Иоанн Бранкович

Поццекко, Джанмарко

Система «Периметр»

Умершие в 680 году

Каргилл, Джейд

Вайнер, Лео

Унесённые ветром

U-1235

Патни (мост)

Тобус, Филип

Флоты США

Фурманов, Рудольф Давыдович

Ллойд-Карри, Андреа

Ламинин

41	46	67	201	162	216	124	1	61	54	84	161	236	240	6	19
98	167	5	243	192	199	115	140	152	147	43	217	188	76	130	202
30	155	87	60	253	212	224	22	103	66	111	24	138	23	229	18
190	78	196	214	218	158	222	73	160	251	245	142	187	47	238	122
169	104	121	145	21	178	7	63	148	194	16	137	11	34	95	33
128	127	93	154	90	144	50	39	53	62	204	231	191	247	151	3
255	25	48	179	72	165	181	209	215	94	146	42	172	86	170	198
79	184	56	210	150	164	125	182	118	252	107	226	156	116	4	241
69	157	112	89	100	113	135	32	134	91	207	101	230	45	168	2
27	96	37	173	174	176	185	246	28	70	97	105	52	64	126	15
85	71	163	35	221	81	175	58	195	92	249	206	186	197	234	38
44	83	13	110	133	40	132	9	211	223	205	244	65	129	77	82
106	220	55	200	108	193	171	250	36	225	123	8	12	189	177	74
120	136	149	139	227	99	232	109	233	203	213	254	59	0	29	57
242	239	183	14	102	88	208	228	166	119	114	248	235	117	75	10
49	68	80	180	143	237	31	26	219	153	141	51	159	17	131	20