WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данная таблица используется и в функции сжатия алгоритма 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-байтная контрольная сумма ${\displaystyle C[0\ldots 15]}$ добавляется к сообщению. Теперь сообщение можно записать в виде ${\displaystyle M[0\ldots N_{1}-1]}$ , где ${\displaystyle N_{1}=N+16}$ .

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

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

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

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

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

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

   ${\displaystyle X[16+j]=M[i*16+j]}$ , j = 0…15,

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

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

2. Выполняется обработка буфера, которая состоит из 18 раундов преобразований, в рамках каждого из которых выполняется обновление каждого байта буфера следующим образом:
   ${\displaystyle X[k]=(X[k]\oplus S[t])}$ , ${\displaystyle t=X[k]}$ ,

   где k = 0…47,

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

   ${\displaystyle 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. Формирование хеша.

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

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

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

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

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

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

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

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

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

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