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

Шаг 1. Выравнивание потока

Сначала к концу потока дописывают единичный бит.

Затем добавляют некоторое число нулевых бит такое, чтобы новая длина потока ${\displaystyle L'}$ стала сравнима с 448 по модулю 512, (${\displaystyle L'=512\times N+448}$ ). Выравнивание происходит в любом случае, даже если длина исходного потока уже сравнима с 448.

Шаг 2. Добавление длины сообщения

В конец сообщения дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записывают младшие 4 байта, затем старшие. Если длина превосходит ${\displaystyle 2^{64}-1}$ , то дописывают только младшие биты (эквивалентно взятию по модулю ${\displaystyle 2^{64}}$ ). После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.

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

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами (порядок байтов little-endian, сначала младший байт):

А = 01 23 45 67; // 67452301h
В = 89 AB CD EF; // EFCDAB89h
С = FE DC BA 98; // 98BADCFEh
D = 76 54 32 10. // 10325476h

В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.

Шаг 4. Вычисление в цикле

Определим функции и константы, которые понадобятся нам для вычислений.

• Для каждого раунда потребуется своя функция. Введём функции от трёх параметров — слов, результатом также будет слово:

1-й раунд: ${\displaystyle \operatorname {FunF} (X,Y,Z)=(X\wedge Y)\vee (\neg X\wedge Z)}$ ,

2-й раунд: ${\displaystyle \operatorname {FunG} (X,Y,Z)=(X\wedge Z)\vee (\neg Z\wedge Y)}$ ,

3-й раунд: ${\displaystyle \operatorname {FunH} (X,Y,Z)=X\oplus Y\oplus Z}$ ,

4-й раунд: ${\displaystyle \operatorname {FunI} (X,Y,Z)=Y\oplus (\neg {Z}\vee X)}$ ,

где ${\displaystyle \oplus ,\wedge ,\vee ,\neg }$ побитовые логические операции XOR, AND, OR и NOT соответственно.

• Определим таблицу констант ${\displaystyle T[1\ldots 64]}$  — 64-элементная таблица данных, построенная следующим образом: ${\displaystyle T[n]=\operatorname {int} (2^{32}\cdot |\sin n|)}$ .^[11]
• Каждый 512-битный блок проходит 4 этапа вычислений по 16 раундов. Для этого блок представляется в виде массива X из 16 слов по 32 бита. Все раунды однотипны и имеют вид: [abcd k s i], определяемый как ${\displaystyle a=b+((a+\operatorname {Fun} (b,c,d)+X[k]+T[i])\lll s)}$ , где k — номер 32-битного слова из текущего 512-битного блока сообщения, и ${\displaystyle \ldots \lll s}$  — циклический сдвиг влево на s бит полученного 32-битного аргумента. Число s задается отдельно для каждого раунда.

Заносим в блок данных элемент n из массива 512-битных блоков. Сохраняются значения A, B, C и D, оставшиеся после операций над предыдущими блоками (или их начальные значения, если блок первый).

AA = A

BB = B

CC = C

DD = D

Этап 1

/* [abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 7  1][DABC  1 12  2][CDAB  2 17  3][BCDA  3 22  4]
[ABCD  4 7  5][DABC  5 12  6][CDAB  6 17  7][BCDA  7 22  8]
[ABCD  8 7  9][DABC  9 12 10][CDAB 10 17 11][BCDA 11 22 12]
[ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]

Этап 2

/* [abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  1 5 17][DABC  6 9 18][CDAB 11 14 19][BCDA  0 20 20]
[ABCD  5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA  4 20 24]
[ABCD  9 5 25][DABC 14 9 26][CDAB  3 14 27][BCDA  8 20 28]
[ABCD 13 5 29][DABC  2 9 30][CDAB  7 14 31][BCDA 12 20 32]

Этап 3

/* [abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  5 4 33][DABC  8 11 34][CDAB 11 16 35][BCDA 14 23 36]
[ABCD  1 4 37][DABC  4 11 38][CDAB  7 16 39][BCDA 10 23 40]
[ABCD 13 4 41][DABC  0 11 42][CDAB  3 16 43][BCDA  6 23 44]
[ABCD  9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA  2 23 48]

Этап 4

/* [abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 6 49][DABC  7 10 50][CDAB 14 15 51][BCDA  5 21 52]
[ABCD 12 6 53][DABC  3 10 54][CDAB 10 15 55][BCDA  1 21 56]
[ABCD  8 6 57][DABC 15 10 58][CDAB  6 15 59][BCDA 13 21 60]
[ABCD  4 6 61][DABC 11 10 62][CDAB  2 15 63][BCDA  9 21 64]

Суммируем с результатом предыдущего цикла:

A = AA + A
B = BB + B
C = CC + C
D = DD + D

После окончания цикла необходимо проверить, есть ли ещё блоки для вычислений. Если да, то переходим к следующему элементу массива (n + 1) и повторяем цикл.

Шаг 5. Результат вычислений

Результат вычислений находится в буфере ABCD, это и есть хеш. Если выводить побайтово, начиная с младшего байта A и закончив старшим байтом D, то мы получим MD5-хеш. 1, 0, 15, 34, 17, 18…

Сравнение MD5 и MD4

Алгоритм MD5 происходит от MD4. В новый алгоритм добавили ещё один раунд, теперь их стало 4 вместо 3 в MD4. Добавили новую константу для того, чтобы свести к минимуму влияние входного сообщения, в каждом раунде на каждом шаге и каждый раз константа разная, она суммируется с результатом F и блоком данных. Изменилась функция ${\displaystyle G=XZ\vee (Y\neg Z)}$ вместо ${\displaystyle XY\vee XZ\vee YZ}$ . Результат каждого шага складывается с результатом предыдущего шага, из-за этого происходит более быстрое изменение результата. Для этой же цели оптимизирована величина сдвига на каждом круге. Изменился порядок работы с входными словами в раундах 2 и 3^[2].

Атаки переборного типа

Для полного перебора или перебора по словарю можно использовать программы PasswordsPro^[15], MD5BFCPF^[16], John the Ripper. Для перебора по словарю существуют готовые словари^[17]. Основным недостатком такого типа атак является высокая вычислительная сложность.

RainbowCrack — ещё один метод нахождения прообраза хеша из заданного множества. Он основан на генерации цепочек хешей, чтобы по получившейся базе вести поиск заданного хеша. Хотя создание радужных таблиц занимает много времени и памяти, последующий взлом производится очень быстро. Основная идея данного метода — достижение компромисса между временем поиска по таблице и занимаемой памятью.

Коллизии MD5

Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений и идентичного начального буфера. В отличие от коллизий, псевдоколлизии определяются как равные значения хеша для разных значений начального буфера, причём сами сообщения могут совпадать или отличаться. В MD5 вопрос коллизий не решается^[14].

В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённые инициализирующие векторы, отличные от стандартных. Оказалось, что можно для известного сообщения построить второе, такое, что оно будет иметь такой же хеш, как и исходное. C точки зрения математики это означает: MD5(IV,L1) = MD5(IV,L2), где IV — начальное значение буфера, а L1 и L2 — различные сообщения. Например, если взять начальное значение буфера^[4]:

A = 0x12AC2375
В = 0x3B341042
C = 0x5F62B97C
D = 0x4BA763E 

и задать входное сообщение

то, добавляя число ${\displaystyle 2^{9}}$ к определённому 32-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хешем. Ханс Доббертин представил такую формулу:

${\displaystyle L2_{i}={\begin{cases}L1_{i},&i\neq 14;\\L1_{i}+2^{9},&i=14.\end{cases}}}$

Тогда MD5(IV, L1) = MD5(IV, L2) = BF90E670752AF92B9CE4E3E1B12CF8DE.

В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фэн Дэнго (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии^[5][18].

В 2005 году Ван Сяоюнь и Юй Хунбо из университета Шаньдуна в Китае опубликовали алгоритм, который может найти две различные последовательности в 128 байт, которые дают одинаковый MD5-хеш. Одна из таких пар (отличающиеся разряды выделены):

и

Каждый из этих блоков даёт MD5-хеш, равный 79054025255fb1a26e4bc422aef54eb4^[19].

В 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование»^[7][20].

Алгоритм MD5 использует итерационный метод Меркла — Дамгора, поэтому становится возможным построение коллизий с одинаковым, заранее выбранным префиксом. Аналогично, коллизии получаются при добавлении одинакового суффикса к двум различным префиксам, имеющим одинаковый хеш. В 2009 году было показано, что для любых двух заранее выбранных префиксов можно найти специальные суффиксы, с которыми сообщения будут иметь одинаковое значение хеша. Сложность такой атаки составляет всего 2³⁹ операций подсчета хеша^[21].