Криптоанализ N-хэш

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, которые объединяются в единое 128-битовое хэш-значение.

Во первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно. Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два действия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алгоритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Инициализируются четыре переменных:

A = 0x01234567

B = 0x89abcdef

C= 0xfedcba98

D= 0x76543210

Они называются переменными сцепления.

Теперь перейдем к основному циклу алгоритма. Этот цикл продолжается, пока не исчерпаются 512-битовые блоки сообщения.

Четыре переменных копируются в другие переменные: Aв a, B в b, C в c и D в d.

Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тремя из a, b, c и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных a, b, c и d. Наконец результат заменяет одну из переменных a, b, c и d. См. Рис. 18-5 и Рис. 18-6. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).

Рис. 18-5. Главный цикл MD5.

Рис. 18-6. Одна операция MD5.

F(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z)

G(X,Y,Z) = (X Ù Z) Ú (Y Ù (ØZ))

H(X,Y,Z) = XÅ Y Å Z

I(X,Y,Z) = Y Å(X Ú (ØZ))

(Å - это XOR, Ù - AND, Ú - OR, а Ø - NOT.)

Эти функции спроектированы так, чтобы, если соответствующие биты X, Y и Z независимы и несмещены, каждый бит результата также был бы независимым и несмещенным. Функция F - это побитовое условие: если X, то Y, иначе Z. Функция H - побитовая операция четности.

Если M_j обозначает j-ый подблок сообщения (от 0 до 15), а <<<s обозначает циклический сдвиг влево на s битов, то используются следующие четыре операции:

FF(a,b,c,d,M_j,s,t_i) означает a= b+ ((a + F(b,c,d) + M_j + t_i) <<<s)

GG(a,b,c,d,M_j,s,t_i) означает a= b+ ((a + G(b,c,d) + M_j + t_i) <<<s)

HH(a,b,c,d,M_j,s,t_i) означает a= b+ ((a + H(b,c,d) + M_j + t_i) <<<s)

II(a,b,c,d,M_j,s,t_i) означает a= b+ ((a + I(b,c,d) + M_j + t_i) <<<s)

Четыре этапа (64 действия выглядят следующим образом):

Этап 1:

FF(a, b, c, d, M₀, 7, 0xd76aa478)

FF(d, a, b, c, M₁, 12, 0xe8c7b756)

FF(c, d, a, b, M₂, 17, 0x242070db)

FF(b, c, d, a, M₃, 22, 0xc1bdceee)

FF(a, b, c, d, M₄, 7, 0xf57c0faf)

FF(d, a, b, c, M₅, 12, 0x4787c62a)

FF(c, d, a, b, M₆, 17, 0xa8304613)

FF(b, c, d, a, M₇, 22, 0xfd469501)

FF(a, b, c, d, M₈, 7, 0x698098d8)

FF(d, a, b, c, M₉, 12, 0x8b44f7af)

FF(c, d, a, b, M₁₀, 17, 0xffff5bb1)

FF(b, c, d, a, M₁₁, 22, 0x895cd7be)

FF(a, b, c, d, M₁₂, 7, 0x6b901122)

FF(d, a, b, c, M₁₃, 12, 0xfd987193)

FF(c, d, a, b, M₁₄, 17, 0xa679438e)

FF(b, c, d, a, M₁₅, 22, 0x49b40821)

Этап 2:

GG(a, b, c, d, M₁, 5, 0xf61e2562)

GG(d, a, b, c, M₆,9, 0xc040b340)

GG(c, d, a, b, M₁₁, 14, 0x265e5a51)

GG(b, c, d, a, M₀, 20, 0xe9b6c7aa)

GG(a, b, c, d, M₅, 5, 0xd62fl05d)

GG(d, a, b, c, M₁₀,9, 0x02441453)

GG(c, d, a, b, M₁₅, 14, 0xd8ale681)

GG(b, c, d, a, M₄, 20, 0xe7d3fbc8)

GG(a, b, c, d, M₉, 5, 0x2,lelcde6)

GG(d, a, b, c, M₁₄,9, 0xc33707d6)

GG(c, d, a, b, M₃, 14, 0xf4d50d87)

GG(b, c, d, a, M₈, 20, 0x455al4ed)

GG(a, b, c, d, M₁₃, 5, 0xa9e3e905)

GG(d, a, b, c, M₂,9, 0xfcefa3f8)

GG(c, d, a, b, M₇, 14, 0x676f02d9)

GG(b, c, d, a, M₁₂, 20, 0x8d2a4c8a)

Этап 3:

HH(a, b, c, d, M₅, 4, 0xfffa3942)

HH(d, a, b, c, M₈, 11, 0x8771f681)

HH(c, d, a, b, M₁₁, 16, 0x6d9d6122)

HH(b, c, d, a, M₁₄, 23, 0xfde5380c)

HH(a, b, c, d, M₁, 4, 0xa4beea44)

HH(d, a, b, c, M₄, 11, 0x4bdecfa9)

HH(c, d, a, b, M₇, 16, 0xf6bb4b60)

HH(b, c, d, a, M₁₀, 23, 0xbebfbc70)

HH(a, b, c, d, M₁₃, 4, 0x289b7ec6)

HH(d, a, b, c, M₀, 11, 0xeaa127fa)

HH(c, d, a, b, M₃, 16, 0xd4ef3085)

HH(b, c, d, a, M₆, 23, 0x04881d05)

HH(a, b, c, d, M₉, 4, 0xd9d4d039)

HH(d, a, b, c, M₁₂, 11, 0xe6db99e5)

HH(c, d, a, b, M₁₅, 16, 0x1fa27cf8)

HH(b, c, d, a, M₂, 23, 0xc4ac5665)

Этап 4:

II(a, b, c, d, M₀, 6, 0xf4292244)

II(d, a, b, c, M₇, 10, 0x432aff97)

II(c, d, a, b, M₁₄, 15, 0xab9423a7)

II(b, c, d, a, M₅, 21, 0xfc93a039)

II(a, b, c, d, M₁₂, 6, 0x655b59c3)

II(d, a, b, c, M₃, 10, 0x8f0ccc92)

II(c, d, a, b, M₁₀, 15, 0xffeff47d)

II(b, c, d, a, M₁, 21, 0x85845ddl)

II(a, b, c, d, M₈,6, 0x6fa87e4f)

II(d, a, b, c, M₁₅, 10, 0xfe2ce6e0)

II(c, d, a, b, M₆,15, 0xa3014314)

II(b, c, d, a, M₁₃, 21, 0x4e081lal)

II(a, b, c, d, M₄, 6, 0xf7537e82)

II(d, a, b, c, M₁₁, 10, 0xbd3af235)

II(c, d, a, b, M₂, 15, 0x2ad7d2bb)

II(b, c, d, a, M₉, 21, 0xeb86d391)

Эти константы, t_i, выбирались следующим образом:

На i-ом этапе t_iявляется целой частью 2³²*abs(sin(i)), где i измеряется в радианах.

После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.

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