MD2

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
MD2
Создан 1989 г.
Опубликован апрель 1992 г.
Преемник MD4
Размер хеша 128 бит
Число раундов 18
Тип хеш-функция

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

История[править | править код]

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

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

MD2 был разработан в 1989 г. для использования в качестве одного из криптографических алгоритмов, входящих в стандарт защищенной электронной почты PEM (Privacy-Enhanced Mail);[1] его реализация на языке Си была приведена в RFC 1115[2]. А в 1990 году MD2 был предложен в качестве замены BMAC (Bidirectional MAC)[3]. Впоследствии спецификация и обновленная реализация MD2 были опубликованы в RFC 1319[4].

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

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

Алгоритм MD2[править | править код]

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

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

Шаг 1. Добавление недостающих бит.[править | править код]

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

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

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

На этом этапе (после добавления байт) сообщение имеет длину в точности кратную 16 байтам. Пусть означает байты получившегося сообщения (N кратно 16).

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

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

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

,

,

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

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

 — x-й байт сообщения, то есть  — это j-й байт текущего блока данных;

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

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

 — 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-байтная контрольная сумма добавляется к сообщению. Теперь сообщение можно записать в виде , где .

Шаг 3. Инициализация MD-буфера.[править | править код]

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

Шаг 4. Обработка сообщения блоками по 16 байт.[править | править код]

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

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

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

    , j = 0…15,

    , j = 0…15.

    Таким образом, если представить буфер X как 3 фрагмента по 16 байт, то после копирования блока данных второй из фрагментов буфера содержит обрабатываемый блок данных, а третий — результат применения побитовой операции «исключающее или» (XOR) к текущему содержимому первого фрагмента и блока данных.

  2. Выполняется обработка буфера, которая состоит из 18 раундов преобразований, в рамках каждого из которых выполняется обновление каждого байта буфера следующим образом:
    , ,

    где k = 0…47,

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

    .

Реализация 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. Формирование хеша.[править | править код]

Хеш вычисляется как результат ; в начале идет байт , а конце .

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

Пример[править | править код]

MD2 («123456789012345678901234567890123456789012345678901234567890123456 78901234567890») = 05dbba941443332475b8e3f572f5d148

Быстродействие[править | править код]

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

Алгоритм Скорость, Кбит/с Год
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, Рональд Ривест, предполагал, что:

  1. сложность задачи поиска прообраза по известной хеш-сумме имеет порядок 2128 операций
  2. сложность задачи поиска коллизии (двух сообщений с одинаковой хеш-суммой) имеет порядок 264 операций[6]

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

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

История криптоанализа MD2[править | править код]

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

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

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

Первую атаку на MD2 целиком в 2004 году предложил Фредерих Мюллер, позволяющую найти прообраз с трудоёмкостью 2104 операций, что существенно меньше теоретической трудоёмкости поиска прообраза для MD2, которая составляет 2128 операций. Мюллер заявил: «MD2 не может больше рассматриваться, как криптостойкий алгоритм хеширования»[9]. Хотя трудоёмкость атаки являлась все же слишком большой для возможности осуществления данной атаки на практике.

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

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

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

Применение[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

  1. ↑ 1 2 3 4 Preneel B. Analysis and Design of Cryptographic Hash Functions — February 2003
  2. ↑ J. Linn. Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers (англ.). IETF (август 1989). Архивировано из оригинала 2 декабря 2012 года.
  3. ↑ J. Linn. Privacy Enhancement for Internet Electronic Mail: Part I: Message Encipherment and Authentication Procedures (англ.). IETF (январь 1988). Архивировано из оригинала 2 декабря 2012 года.
  4. ↑ B. Kaliski. The MD2 Message-Digest Algorithm (англ.). RSA Laboratories (апрель 1992). Архивировано из оригинала 2 декабря 2012 года.
  5. ↑ 1 2 S. Turner, L. Chen. MD2 to Historic Status (англ.). IETF (март 2011). Архивировано из оригинала 2 декабря 2012 года.
  6. ↑ S. Bakhtiari, R. Safavi-naini, J. Pieprzyk, Cryptographic Hash Functions: A Survey (1995)
  7. ↑ 1 2 Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C (1995)
  8. ↑ Rogier N., Chauvaud P. Md2 is not Secure Without the Checksum Byte (англ.) // Designs, Codes and Cryptography — Springer US, Springer Science+Business Media, 1997. — Vol. 12, Iss. 3. — P. 245–251. — ISSN 0925-1022; 1573-7586 — doi:10.1023/A:1008220711840
  9. ↑ 1 2 Muller F. The MD2 Hash Function Is Not One-Way (англ.) // Advances in Cryptology — ASIACRYPT 2004: 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings / P. J. Lee — Berlin, Heidelberg, New York City, London: Springer Science+Business Media, 2004. — P. 214—229. — 548 p. — (Lecture Notes in Computer Science; Vol. 3329) — ISBN 978-3-540-23975-8 — ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-540-30539-2_16
  10. ↑ Robshaw M. J. B. On Recent Results for MD2, MD4 and MD5 (англ.) (1996).
  11. ↑ Knudsen L. R., Mathiassen J. E. Preimage and Collision Attacks on MD2 (англ.) // Fast Software Encryption: 12th International Workshop, FSE 2005, Paris, France, February 21-23, 2005, Revised Selected Papers / H. Gilbert, H. Handschuh — Berlin, Heidelberg, New York City, London: Springer Science+Business Media, 2005. — P. 255—267. — 443 p. — (Lecture Notes in Computer Science; Vol. 3557) — ISBN 978-3-540-26541-2 — ISSN 0302-9743; 1611-3349 — doi:10.1007/11502760_17
  12. ↑ Thomsen S. S., An improved preimage attack on MD2 (2008)
  13. ↑ Knudsen L. R., Mathiassen J. E., Muller F., Thomsen S. S. Cryptanalysis of MD2 (англ.) // Journal of Cryptology / I. Damgård — Springer Science+Business Media, International Association for Cryptologic Research, 2010. — Vol. 23, Iss. 1. — P. 72–90. — ISSN 0933-2790; 1432-1378 — doi:10.1007/S00145-009-9054-1
  14. ↑ D. Balenson. Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers (англ.) (февраль 1993). Архивировано из оригинала 2 декабря 2012 года.
  15. ↑ R. Housley, W. Ford, W. Polk, D. Solo. Internet X.509 Public Key Infrastructure. Certificate and CRL Profile (англ.) (январь 1999). Архивировано из оригинала 2 декабря 2012 года.
  16. ↑ J. Jonsson, B. Kaliski. Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography (англ.) (февраль 2003). Архивировано из оригинала 2 декабря 2012 года.

Ссылки[править | править код]

Источник — https://wiki4.ru/w/index.php?title=MD2&oldid=134099433