КулЛиб - Классная библиотека! Скачать книги бесплатно 

Алгоритм построения цифрового дайджеста MD4 [Ло Шу] (pdf) читать онлайн

Книга в формате pdf! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]
Алгоритм построения цифрового дайджеста
MD4
Данная статья предлагает детальный анализ алгоритма построения цифрового
дайджеста сообщения MD4. Теория, рассматриваемая в деталях, подкреплена
весьма качественными примерами, реализованными на языках Си и Форт.

1. Введение
Язык программирования Си наиболее распространенный из языков на сегодняшний
день. Но, как оказалось, в процессе написания статьи мне необходимо было выполнять
некие вычисления. Язык Форт оказался здесь незаменимым помощником, он дал
возможность создавать код, глубже вникать в алгоритм во время его реализации и
выполнять этот алгоритм по шагам в интерактивном режиме. Лучше инструмента найти
я не смог. Я использовал WinForth32, который можно бесплатно загрузить с адреса
FTP://FTP.Taygeta.COM/pub/Forth/Compilers/Native/windows/Win32For/W32for42.exe
Для тех, кто хочет познакомиться с Фортом поближе, я рекомендую посетить сайты
HTTP://www.Forth.ORG и HTTP://www.Forth.ORG.RU.
Алгоритм MD4 это один из алгоритмов целого семейства, в этом семействе существует
еще два алгоритма – MD2 и MD5. Но MD2 довольно старый алгоритм и сейчас
практически не используется, а MD5 это следующий шаг после MD4, и в его основе
лежит все тот же MD4. Поэтому я принял решение начать с более простого алгоритма,
чтобы построить фундамент для понимания современных алгоритмов построения
цифровых дайджестов.

2. Цифровой дайджест
Я прелагаю начать знакомство с цифровыми дайджестами с его определения, взятого
из компьютерного словаря. Одно из определений звучит следующим образом:
"Цифровой дайджест – это представление текста в виде строки цифр, построенной с
использованием формулы, называемой односторонней хэш функцией. Шифрование
цифрового дайджеста с помощью закрытого ключа создает цифровую подпись, которая
представляет собой электронный вид аутентификации." И, наверное, будет неплохо
привести пример. Вот цифровой дайджест строки "MD4" и файла WinWord.EXE
построенный с помощью программы, взятой из документа RFC 1320:
MD4(MD4) = 9af4a3d5f2dfb4b6851b265b46fbeff3
MD4(WinWord.EXE) = 595452c1c9c3008273d83ad32cc8de16
Прошу заметить, что цифровой дайджест для файла WinWord.EXE будет отличаться
для различных версий этого файла. Я строил дайджест для WinWord.EXE с
характеристиками, представленными на Рисунке 1.

Рисунок 1. Диалоговое окно со свойствами фала WinWord.EXE.
Для начала освежим в памяти, что такое хэш. Хэш - это численная величина,
полученная из текстовой строки. Эта величина существенно меньше, чем сама
текстовая строка. Хэш строится с помощью одностороннего преобразования, или
односторонней функции. Особенность этого преобразования заключается в том, что
вероятность генерации одинакового хеш-значения для двух различных строк крайне
низка. Процесс получения такой числовой величины из текстовой строки называется
хэшированием. Хэширование играет большую роль в системах безопасности, где оно
используется для того, чтобы удостовериться, что переданное сообщение не было
подделано. Отправитель строит хэш сообщение, шифрует его и отправляет вместе с
сообщением (также зашифрованным). Получатель дешифрует сообщение и хэш,
строит новый хэш для дешифрованного сообщения и сравнивает его с полученным.
Если они одинаковы, то вероятность того, что сообщение пришло без изменений очень
высока. "Односторонняя" обозначает, что практически невозможно воспроизвести
исходную текстовую строку на основании ее хэш значения. "Практически невозможно" в
свою очередь обозначает, что для нахождения такой строки потребуется
вычислительный ресурс недостижимой на данный момент мощности из-за
ограниченности современных технологий, а также то, что время нахождения такой
строки с использованием современных вычислительных ресурсов настолько велико
(может измеряться годами), что даже если такая строка будет найдена, то ее
информационный смысл уже утратит свою значимость.

3. Немного истории
Немного истории, конечно же, не помешает. Алгоритм MD4 был спроектирован
профессором Ривестом из Массачусетского Технологического Института Соединенных
Штатов Америки в 1990 году и является последователем алгоритма MD2. Этот
алгоритм оптимизирован для быстрого построения цифрового дайджеста сообщения на
32-разрядных машинах. Описание алгоритма и пример реализации может быть найден
в документе RFC 1320, перевод которого приведен в Приложении к этой статье. На
сегодняшний день алгоритм 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 ." | " 8 U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-BC ( b c -- x )
?PRINT IF 2DUP CR ." X & Y = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-vBC ( x1 bc -- x2 )
?PRINT IF 2DUP CR ." . | XY = " SWAP 8 U.R SPACE ." | " 8 U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG ( b-addr c-addr d-addr -- g )
@ ROT @ ROT @ ROT
3DUP
(bcdbcd)
D-FG-CD ( b c d b xi )
-ROT
( b c xi d b )
D-FG-BD ( b c xi xii )

D-FG-CDvBD ( b c xiii )
-ROT
( xiii b c )
D-FG-BC ( xiii xiv )
D-FG-vBC ( g )
;

Приведенный код может показаться достаточно длинным и запутанным, но он
производит вывод большого количества информации. Кроме того, его можно
существенно упростить (оставим это в качестве упражнения для читателя). А также
хочу обратить внимание читателя на то, что все слова в этом коде начинаются с
префикса "D-", то есть "DEBUG" – ОТЛАДОЧНЫЙ. Вот для сравнения код, из которого
были удалены все операторы отладочной печати:

: FF ( b-addr c-addr d-addr -- f ) @ ROT @ ROT @ OVER AND SWAP INVERT ROT AND OR ;
: FG ( b-addr c-addr d-addr -- g ) @ ROT @ ROT @ ROT 3DUP AND -ROT AND OR -ROT AND OR ;
: FH ( b-addr c-addr d-addr -- h ) @ ROT @ ROT @ XOR XOR ;

Не правда ли, гораздо проще!
Процессор также выполняет три базовые операции преобразования. Эти операции
используют определенные выше функции F, G и H и выражаются следующими
формулами:
a = (a + F(b,c,d) + X[k]) >2;
/* слов для копирования */
ec=len&0x03;
for (; ew; ew--,p++)
{

HOST_c2l(data,l); *p=l;
}
HOST_c2l_p(data,l,ec);
*p=l;
}
}

- обработка последнего блока и получение цифрового дайджеста

void MD4_Final(unsigned char *md, MD4_CTX *c)
{
register HASH_LONG *p;
register unsigned long l;
register int i,j;
static const unsigned char end[4]={0x80,0x00,0x00,0x00};
const unsigned char *cp=end;

/* c->num определенно должен иметь место по крайней мере
* еще для одного байта. */
p=c->data;
i=c->num>>2;
j=c->num&0x03;
l = (j==0) ? 0 : p[i];
HOST_p_c2l(cp,l,j); p[i++]=l;
/* i это следующее 'неопределенное слово' */
if (i>(HASH_LBLOCK-2)) /* оставить место для Nl и Nh */
{
if (iNl;
#elif defined(DATA_ORDER_IS_LITTLE_ENDIAN)
p[HASH_LBLOCK-2]=c->Nl;
p[HASH_LBLOCK-1]=c->Nh;
#endif
HASH_BLOCK_HOST_ORDER (c,p,1);
#ifndef HASH_MAKE_STRING
#error "HASH_MAKE_STRING must be defined!"
#else
HASH_MAKE_STRING(c,md);
#endif
c->num=0;
/* очистить все, HASH_BLOCK может оставить некоторую информацию
* на стеке, но меня это не беспокоит
memset((void *)c,0,sizeof(HASH_CTX));
*/
}

На мой критический взгляд, очень длинно и очень запутано. Я постараюсь объяснить
это тем, что библиотека OpenSSL создавалась как переносимая многоплатформенная
библиотека, но... Пример реализации этих же самых примитивов приведенный в
документе RFC 1320 намного проще, но не эффективнее.

Теперь мы готовы привести код для построения цифрового дайджеста строки:

MD4_CTX context;
unsigned char digest[16];
unsigned char string = "abc";
unsigned int len = strlen (string);
MD4_Init(&context);
MD4_Update(&context, string, len);
MD4_Final(digest, &context);

Просто, правда? Зато теперь мы знаем как это все работает внутри!
Ну и конечно же пример:
MD4("abc") = a448017aaf21d8525fc10ae87aa6729d

8. Построение цифрового дайджеста файла
Для того, чтобы построить цифровой дайджест любого файла, мы тоже можем
использовать приведенные выше примитивы. Единственное отличие при обработке
файла от обработки строки состоит в том, что большой файл мы не сможем
представить в виде одной строки байт (символов) и поэтому его нужно будет
обрабатывать частями, например вот так:

FILE *file;
MD4_CTX context;
int len;
unsigned char buffer[1024], digest[16];
file = fopen(filename, "rb");

MD4_Init(&context);
while (len = fread (buffer, 1, 1024, file))
{
MD4_Update(&context, buffer, len);
}
MD4_Final(digest, &context);
fclose(file);

С помощью вот такого кусочка кода и был построен цифровой дайджест для файла
WinWord.EXE, приведенный в начале статьи.
В связи с операцией построения цифрового дайджеста для файла возник один
интересный вопрос, который я исследовал. Вопрос такой: а как влияет размер буфера
данных на скорость работы алгоритма? Есть ли разница в том, какого размера буфер
лучше использовать – размером в 1 байт или размером в 1000 байт?
Для этого я написал маленькую программку, которая измеряет скорость работы
алгоритма для буфера различных размеров, начиная от размера в 1 байт и заканчивая
размером в 128 байт. Результат работы программы я свел в следующие два графика –
график скорости работы реализации и график пропускной способности реализации
алгоритма. В измерениях я использовал две реализации алгоритма построения

цифрового дайджеста MD4 – реализацию, предложенную в документе RFC 1320 и
реализацию из библиотеки OpenSSL.

Время работы алгоритма в зависимоати от
размера буфера
16
14

Время, сек

12
10
RFC

8

OpenSSL

6
4
2

Размер буфера, байт

Рисунок 9. Скорость работы реализаций алгоритма MD4

127

118

109

100

91

82

73

64

55

46

37

28

19

10

1

0

Скорость работы в зависимости от размера буфера
140000
120000
100000
80000

RFC
OpenSSL

60000
40000
20000
0

Размер буфера, байт
Рисунок 10. Пропускная способность реализаций алгоритма MD4
Измерения производились на компьютере с процессором Intel Pentium III, работающем
на частоте 750 МГц. Оценка производилась на основании построения цифрового
дайджеста 10000 раз для сообщения размером 10000 байт.
На основании этих двух графиков можно сделать следующие выводы:
- реализация алгоритма в библиотеке OpenSSL более эффективна;
- оптимальными для использования являются буферы с размерами кратными 64,
то есть размеру внутреннего БЛОЧНОГО БУФЕРА;
- существуют некие другие размеры буфера, дающие увеличение пропускной
способности;
- время работы реализации OpenSSL для буфера размером 64 байта составляет
0.891 секунды, для буфера размером 128 байт – 0.781 секунды;
- пропускная способность реализации OpenSSL для буфера размером 64 байта
составляет 109602 килобайта в секунду (= 107 МБ/сек), для буфера размером
128 байт – 125040 килобайта в секунду (= 122 МБ/сек).
При использовании библиотеки OpenSSL выбирайте размер буфера кратный 64!

9. Резюме
Мы рассмотрели работу алгоритма построения цифрового дайджеста MD4. Этот
алгоритм лежит в основе большинства основных методов построения цифровых
дайджестов и теперь читателю будет несложно понять их работу. В следующей статье
мы рассмотрим алгоритм построения цифрового дайджеста MD5, который широко
используется сегодня. Мы коснемся математических вопросов для более глубокого
понимания того, как и почему строится дайджест и почему его сложно "сломать". Также
я постараюсь осветить вопросы криптоанализа и криптографических атак. До
следующей встречи.

Редакция 3 от 24 сентября 2002 года
Ло Шу (LoShu_LoShu@Yahoo.COM, LoShu_LoShu@HotMail.COM).

Приложение А. RFC 1320

Network Working Group
Request for Comments: 1320
Obsoletes: RFC 1186

R. Rivest
MIT Laboratory for Computer Science
and RSA Data Security, Inc.
April 1992

Алгоритм построения цифрового дайджеста
сообщения MD4
Статус данного документа
Данный документ предлагает информацию для рассмотрения сообществом Интернет.
Документ не определяет стандарт Интернет. Распространение данного документа не
ограничено.

Благодарности
Мы хотели бы выразить благодарность Дону Копперсмиту (Don Coppersmith), Бурту
Калиски (Burt Kaliski), Ральфу Мерклу (Ralph Merkle) и Ноаму Нисану (Noam Nisan) за их
многочисленные важные комментарии, замечания и предложения.

1. Краткое содержание
Этот документ описывает алгоритм построения цифрового дайджеста MD4 [1].
Алгоритм получает в качестве исходных данных сообщение произвольной длины и в
результате своей работы формирует 128-битовый "отпечаток" или "цифровой
дайджест" входного сообщения. Предполагается, что вычислительными средствами
невозможно построить два сообщения, которые имеют одинаковые цифровые
дайджесты, или построить сообщение с заданным цифровым дайджестом. Алгоритм
MD4 предназначается для приложений, требующих использования цифровых
подписей, в которых большие файлы должны быть "сжаты" безопасным способом
перед тем как они будут зашифрованы приватным (секретным) ключом с
использованием таких общественных криптосистем, как, например, RSA.
Алгоритм MD4 спроектирован таким образом, чтобы быть достаточно быстрым на 32разрядных машинах. В дополнение к этому, алгоритм MD4 не требует никаких больших
таблиц подстановки; алгоритм может быть достаточно компактно закодирован.
Алгоритм MD4 предложен для обзора общественности и возможной адаптации его в
качестве стандарта.
Этот документ замещает RFC 1186 от октября 1990 года. Основное различие состоит в
том, что реализация алгоритма MD4, приведенная в Приложении В, является более
переносимой.

Для приложений, поддерживающих стандарт OSI, идентификатор объекта MD4 имеет
вид
md4 OBJECT IDENTIFIER ::=
{iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 4}
В типе AlgorithmIdentifier [3] из X.509, параметры для MD4 должны иметь тип NULL.

2. Терминология и нотация
В этом документе "слово" обозначает 32-разрядная величина, а "байт" это 8-разрядная
величина. Последовательность бит может быть интерпретирована естественным
образом как последовательность байт, где каждая последующая группа из восьми бит
интерпретируется как байт, в котором старший (наиболее значимый) бит каждого байта
стоит первым. Аналогично, последовательность байт может быть интерпретирована как
последовательность 32-разрядных слов, где каждая последующая группа из четырех
байт интерпретируется как слово, в котором младший (менее значимый) байт стоит
первым.
Пусть x_I обозначает "x sub i". Если нижний индекс является выражением, то мы
помещаем его в фигурные скобки, как, например, в x_{i+1}. Аналогично, мы используем
^ для верхних индексов (возведение в степень), таким образом, x^I обозначает x в
степени i.
Пусть символ "+" обозначает сложение слов (то есть сложение по модулю 2^32). Пусть
X