Ло Шу - Алгоритм построения цифрового дайджеста MD4

алгоритм MD4 считается взломанным.
В 1994 году Ван Ооршот и Вейнер оценили стоимость машины для поиска двух
сообщений, приводящих к коллизии, то есть таких, которые генерируют одинаковый
цифровой дайджест методом "грязной силы" для алгоритма MD5 – последователя
алгоритма MD4. Эта оценка показала, что стоимость такой машины составляет 10
миллионов долларов (на 1994 год) и для нахождения коллизирующих сообщений в
среднем требуется 24 дня работы.

4. MD4 процессор
В основе работы алгоритма MD4 лежит преобразование блока данных с
использованием определенных формул. Но для начала посмотрим на внутреннюю
структуру алгоритма как на специализированный процессор, который имеет свои
регистры и операции. Начнем с регистров. На Рисунке 2 представлена внутренняя
структура такого процессора.

MESSAGE POINTER

a
61

MESSAGE LENGTH

3

REGISTER A
REGISTER B
REGISTER C
REGISTER D
NUMBER OF BITS

BLOCK BUFFER

DATA LENGTH

MD4 PROCESSOR
Рисунок 2. Структура MD4 процессора.

b
62

c
63

Два регистра "УКАЗАТЕЛЬ ДАННЫХ" и "РАЗМЕР ДАННЫХ" содержат, соответственно,
указатель на буфер, где находится строка, подлежащая обработке и ее размер в
байтах. На рисунке приведена строка, состоящая из трех символов, поэтому регистр
"РАЗМЕР ДАННЫХ" содержит величину 3.
Регистры A, B, C и D содержат текущий дайджест обрабатываемого блока, а в конце
обработки – цифровой дайджест сообщения. Каждый регистр содержит 32-разрядную
беззнаковую величину, поэтому размер цифрового дайджеста будет равен 32*4=128
бит.
Регистр "РАЗМЕР СООБЩЕНИЯ" хранит размер обрабатываемого сообщения в битах.
Эта величина понадобиться нам на последнем этапе работы алгоритма. Регистр хранит
64-разрядную величину.
Регистровая группа "БЛОЧНЫЙ БУФЕР" предназначена для хранения очередного
блока, подлежащего обработке. Эта группа состоит из 16 регистров с номерами от 0 до
15.
Регистр "БАЙТ В БУФЕРЕ" хранит величину указывающую заполнение регистровой
группы "БЛОЧНЫЙ БУФЕР".

4.1 Базовые операции MD4 процессора
Я начну с рассмотрения трех базовых функций, затем мы рассмотрим три базовых
преобразования, которые выполняет процессор. И в конце мы объединим все это в
операцию преобразования блока данных.
MD4 процессор реализует три базовых логических функции:
1

F(x,y,x) = (x AND y) OR (NOT x AND z)
G(x,y,z) = (x AND y) OR (x AND z) OR (y AND z)
H(x,y,z) = x XOR y XOR z
Таблицы истинности этих логических функций выглядят следующим образом:
x
0
0
0
0
1
1
1
1

y
0
0
1
1
0
0
1
1

z
0
1
0
1
0
1
0
1

F
0
1
0
1
0
0
1
1

x
0
0
0
0
1
1
1
1

y
0
0
1
1
0
0
1
1

z
0
1
0
1
0
1
0
1

G
0
0
0
1
0
1
1
1

x
0
0
0
0
1
1
1
1

y
0
0
1
1
0
0
1
1

z
0
1
0
1
0
1
0
1

H
0
1
1
0
1
0
0
1

Каждая из функций получает на вход три 32-разрядные величины и формирует один
32-разрядный результат.
Здесь подошло время обратиться к исходному коду. В качестве иллюстрации мы будем
использовать исходный код библиотеки OpenSSL (HTTP://www.OpenSSL.ORG). Вот как
реализованы эти функции в этой библиотеке:

#define F(b,c,d) (((b) & (c)) | ((~(b)) & (d)))
#define G(b,c,d) (((b) & (c)) | ((b) & (d)) | ((c) & (d)))
#define H(b,c,d) ((b) ^ (c) ^ (d))

С целью изучения работы этих функций ниже приведен код на языке Форт. Его можно
использовать для того, чтобы посмотреть какой результат получится после применения
1

NOT x AND z = (NOT x) AND z

этих функций к каким-либо данным. (Примечание: если хотите увидеть результат в
двоичном виде, то замените слово HEX на слово BINARY.)

: D-FF-BC ( c b -- x )
?PRINT IF 2DUP CR ." X & Y = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-~B ( b -- ~b )
?PRINT IF DUP CR ." ~X = ~" 8 HEX U.R THEN
INVERT
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-~BD ( ~b d -- x )
?PRINT IF 2DUP SWAP CR ." ~X & Z = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-F ( x1 x2 -- x3 )
?PRINT IF 2DUP SWAP CR ." . | .. = " 8 HEX U.R SPACE ." | " 8 HEX U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF ( b-addr c-addr d-addr -- f )
@ ROT @ ROT @ ( d b c )
OVER ( d b c b )
D-FF-BC ( d b xi )
SWAP ( d xi b )
D-FF-~B ( d xi ~b )
ROT
( xi ~b d )
D-FF-~BD ( xi xii )
D-FF-F ( f )
;
: D-FG-CD ( c d -- x )
?PRINT IF 2DUP CR ." Y & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-BD ( d b -- x )
?PRINT IF 2DUP CR ." X & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-CDvBD ( cd bd -- x )
?PRINT IF 2DUP CR ." YZ | XZ = " SWAP 8 U.R SPACE ." --">