Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 39 из 78

Не легко построить функцию, вход которой имеет произвольный размер, а тем более сделаьть ее однон а- правленной. В реальном мире однонаправленные хэш-функции строятся на идее функции сжатия. Такая одно- направленная функция выдает хэш-значение длины n при заданных входных данных большей длины m [1069,
414]. Входами функции сжатия являются блок сообщения и выход предыдущего блока текста (см. 17-й). Выход представляет собой хэш-значение всех блоков до этого момента . То есть, хэш-значение блока M
i равно h
i
= f(M
i
, h i-1
)
Это хэш-значение вместе со следующим блоком сообщения становится следующим входом функции сжатия .
Хэш-значением всего сообщения является хэш-значение последнего блока .
Однонаправленная функция
Mi hi hi-1
Рис. 18-1. Однонаправленная функция
Хэшируемый вход должен каким-то способом содержать бинарное представление длины всего сообщения .
Таким образом преодолевается потенциальная проблема, вызванная тем, что сообщения различной длины могут давать одно и то же хэш-значение [1069, 414]. Иногда такой метод называется MD-усилением [930].
Различные исследователи выдвигали предположения, что если функция сжатия безопасна, то этот метод х э- ширования исходных данных произвольной длины также безопасен - но ничего не было доказано [1138, 1070,
414].
На тему проектирования однонаправленных хэш-функций написано много. Более подробную математиче- скую информацию можно найти [1028, 793, 791, 1138, 1069, 414, 91, 858, 1264]. Возможно самым толковой интерпретацией однонаправленных хэш-функций являются тезисы Барта Пренела (Bart Preneel) [1262].
18.2 Snefru
Snefru - это однонаправленная хэш-функция, разработанная Ральфом Мерклом [1070]. (Snefru, также как
Khufu и Khafre, был египетским фараоном.) Snefru хэширует сообщения произвольной длины, превращая их в
128-битовые 256-битовые значения.
Сначала собщение разбивается на кусочки длиной по 512-m. (Переменная m является длитной хэш- значения.) Если выход - это 128-битовое значение, то длина кусочков равна 384 битам, а если выход -
128-битовое значение, то длина кусочков - 256 битов.
Сердцем алгоритма служит функция H, хэширующая 512-битовое значение в m-битовое. Первые m битов выхода H являются хэш-значением блока, остальные отбрасываются . Следующий блок добавляется к хэш- значению предыдущего блока и снова хэшируется . (К первоначальному блоку добавляется строка нулей .) После последнего блока (если сообщение состоит не из целого числа блоков, последний блок дополняется нулями )
первые m битов добавляются к бинарному представлению длины сообщения и хэшируются последний раз .
Функция H основывается на E, обратимой функции блочного шифрования, работающей с 512 битовыми

блоками. H - это последние m битов выхода E, объединенные посредством XOR с первыми m битами входа E.
Безопасность Snefru опирается на функцию E, которая рандомизирует данные за несколько проходов . Каж- дый проход состоит из 64 рандомизирующих этапов. В каждом этапе в качестве входа S-блока используется другой байт данных. Выходное слово подвергается операции XOR с двумя соседними словами сообщения. По- строение S-блоков аналогично построению S-блоков в Khafre (см. раздел 13.7). Кроме того, выполняется ряд циклических сдвигов. Оригинальный Snefru состоял из двух проходов.
Криптоанализ Snefru
Используя дифференциальный криптоанализ, Бихам и Шамир показали небезопасность двухпроходного
Snefru (с 128-битовым хэш-значением) [172]. Их способ вскрытия за несколько минут обнаруживает пару соо б- щений с одинаковым хэш-значением.
Для 128-битового Snefru их вскрытия работают лучше, чем вскрытие грубой силой для четырех и менее пр о- ходов. Вскрытие Snefru методом дня рождения требует 2 64
операций; дифференциальный криптоанализ может найти пару сообщений с одинаковым хэш-значением за 2 28.5 операций для трехпроходного Snefru и за 2 44.5 опе- раций для четырехпроходного Snefru. Нахождение сообщения, хэш-значение которого совпадает с заданным,
при использовании грубой силы требует 2 128
операций, при дифференциальном криптоанализе для этого нужно
2 56
операций для трехпроходного и 2 88 операций для четырехпроходного Snefru.
Хотя Бихам и Шамир не анализировали 256-битовые хэш-значения, они провели анализ вплоть до 224- битовых хэш-значений. В сравнении с вскрытием методом дня рождения, требующим 2 112
операций они могут найти сообщения с одинаковым хэш-значением за 2 12.5
операций для двухпроходного Snefru, за 2 33
операций для трехпроходного Snefru и за для 2 81 операций для четырехпроходного Snefru.
В настоящее время Меркл рекомендует использовать Snefru по крайней мере с восемью проходами [1073].
Однако с таким количеством проходов алгоритм становится намного медленнее, чем MD5 или SHA.
18.3 N-хэш
N-хэш - это алгоритм, придуманный в 1990 году исследователями Nippon Telephone and Telegraph, теми же людьми, которые изобрели FEAL [1105, 1106]. N-хэш использует 128-битовые блоки сообщения, сложную ра н- домизирующую функцию, похожую на FEAL, и выдает 128-битовое хэш-значение.
Хэш-значение каждого 128-битового блока является функцией блока и хэш-значения предыдущего блока .
H
0
= I, где I - случайное начальное значение
H
i
= g(M
i
, H
i-1
) ? M
i
? H
i-1
Хэш-значение всего сообщения представляет собой хэш-значение последнего блока сообщения . Случайное начальное значение I может быть любым числом, определенным пользователем (даже одними нулями).
Функция g достаточно сложна. Схема алгоритма приведена на 16-й. Сначала переставляются левая и правая
64-битовые половины 128-битового хэш-значения предыдущего блока H
i-1
, а затем выполняется XOR с повто- ряющимся шаблоном (128-битовым) и XOR с текущим блоком сообщения M
i
. Далее это значение каскадно пре- образуется в N (на рисунках N= 8) стадий обработки. Другим входом стадии обработки является предыдущее хэш-значение, подвергнутое XOR с одной из восьми двоичных констант.

PS
n
128 битов
128 битов
128 битов
||: конкатенация
PS: стадия обработки (processing stage)
n: 1010 ... 1010 (двоичное, 128 битов)
EXG: перестановка левой и правой частей
V
j
=х||A
j1
х||A
j2
х||A
j3
х||A
j4
H
i
= g(M
i
, H
i-1
) ? M
i
? H
i-1
A
jk
=4*(j-1)+k(k=1,2,3,4, A
jk
- 8 битов в длину)
х: 000 ... 0 (двоичное, 24 бит)
V
3
V
2
EXG
h i=1
h i
M
i
V
1
PS
PS
V
4
PS
V
5
PS
V
6
PS
V
7
PS
V
8
PS
g
Рис. 18-2. Схема N-хэш.
Одна стадия обработки показана на 15-й. Блок сообщения разбивается на четыре 32-битовых значения . Пре- дыдущее хэш-значение также разбивается на четыре 32-битовых значения . Функция f представлена на 14th.
Функции S
0
и S
1
те же самые, что и в FEAL.
S
0
(a,b) = циклический сдвиг влево на два бита (( a + b) mod 256)
S
1
(a,b) = циклический сдвиг влево на два бита(( a + b + 1) mod 256)

B
B
32 бита
32 бита
32 бита
32 бита
32 бита
32 бита
32 бита
32 бита
P= P
1
||P
2
||P
3
||P
4
Вход: X= X
1
||X
2
||X
3
||X
4
X
2
P
4
P
3
P
2
P
2
P
1
P
1
X
1
X
4
X
3
B
B
P
4
P
3
Y
2
Y
1
Y
4
Y
3
Y=PS(X,P)
Выход: Y= Y
1
||Y
2
||Y
3
||Y
4
Рис. 18-3. Одна стадия обработки N-хэш.
Выход одной стадии обработки становится входом следующей стадии обработки . После последней стадии обработки выполняется XOR выхода с M
i и H
i-1
, а затем к хэшированию готов следующий блок .
S
1
S
0
S
1
P
S
0 8 битов
8 битов
8 битов
8 битов
32 бита
32 бита
32 бита
N
f (N,2)
Y=S
0
(X
1
,X
2
)=Rot2((X
1
+X
2
) mod 256)
Y=S
1
(X
1
,X
2
)=Rot2((X
1
+X
2
+1) mod 256)
Y: выходные 8 битов, X
1
,X
2
(8 битов): входы
Rot2(Y): циклический сдвиг влево на 2 бита
8-битовых данных Y
Рис. 18-4. Функция f.

Криптоанализ N-хэш
Берт ден Боер (Bert den Boer) открыл способ создавать столкновения в функции этапа N-хэш [1262]. Бихам и
Шамир применили дифференциальный криптоанализ для вскрытия 6-этапной N-хэш [169, 172]. Конкретное выполненное ими вскрытие (конечно же, могли быть и другие) работает для любого N, делящегося на 3, и эф- фективнее вскрытия методом дня рождения для любого N, меньшего 15.
То же самое вскрытие может обнаруживать пары сообщений с одинаковым хэш-значением для 12-этапной
N-хэш за 2 56
операций (для вскрытия грубой силой нужно 2 64
операций). N-хэш с 15 этапами безопасна по от- ношению к дифференциальному криптоанализу : для вскрытия потребуется 2 72
операций.
Разработчики алгоритма рекомендуют использовать N-хэш не меньше, чем с 8 этапами [1106]. С учетом до- казанной небезопасности N-хэш и FEAL (и ее скорости при 8 этапах) я рекомендую полностью отказаться от этого алгоритма.
18.4 MD4
MD4 - это однонаправленная хэш-функция, изобретенная Роном Ривестом [1318, 1319, 1321]. MD обознача- ет Message Digest (краткое изложение сообщения), алгоритм для входного сообщения выдает 128-битовое хэш- значение, или краткое изложение сообщения.
В [1319] Ривест описал цели, преследуемые им при разработке алгоритма :
Безопасность. Вычислительно невозможно найти два сообщения с одинаковым хэш-значением . Вскрытие грубой силой является самым эффективным .
Прямая безопасность. Безопасность MD4 не основывается на каких-либо допущениях, например, предп о- ложении о трудности разложения на множители .
Скорость. MD4 подходит для высокоскоростных программных реализаций . Она основана на простом набо- ре битовых манипуляций с 32-битовыми операндами.
Простота и компактность. MD4 проста, насколько это возможна, и не содержит больших структур данных или сложных программных модулей.
Удачна архитектура. MD4 оптимизирована для микропроцессорной архитектуры (особенно для микропро- цессоров Intel), для более крупных и быстрых компьютеров можно выполнить любые необходимые изменения .
После первого появления алгоритма Берт ден Боер и Антон Босселаерс (Antoon Bosselaers) достигли успеха при криптоанализе последних двух из трех этапов алгоритма [202]. Ральфу Мерклу совершенно независимо удалось вскрыть первые два этапа [202]. Эли Бихам рассмотрел использование дифференциального криптоан а- лиза против первых двух этапов MD4 [159]. Хотя все эти вскрытия не были распространены на полный алг о- ритм, Ривест усилил свою разработку. В результате появилась MD5.
18.5 MD5
MD5 - это улучшенная версия MD4 [1386, 1322]. Хотя она сложнее MD4, их схемы похожи, и результатом
MD5 также является 128-битовое хэш-значение .
Описание MD5
После некоторой первоначальной обработки 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. См. 13-й и 12-й. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая фун кция).
B
A
Этап 2
Этап 1
Этап 3
Этап 4
D
С
B
Блок сообщения
A
D
С
Рис. 18-5. Главный цикл MD5.
<<t i
M
j
Нелинейная функция
=
>
?
@
Рис. 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), а <<

битов, то используются следующие четыре операции :
FF(a,b,c,d,M
j
,s,t i
) означает a = b + ((a + F(b,c,d) + M
j
+ t i
) <<GG(a,b,c,d,M
j
,s,t i
) означает a = b + ((a + G(b,c,d) + M
j
+ t i
) <<HH(a,b,c,d,M
j
,s,t i
) означает a = b + ((a + H(b,c,d) + M
j
+ t i
) <<II(a,b,c,d,M
j
,s,t i
) означает a = b + ((a + I(b,c,d) + M
j
+ t i
) <<Четыре этапа (64 действия выглядят следующим образом) :
Этап 1:
FF(a, b, c, d, M
0
, 7, 0xd76aa478)
FF(d, a, b, c, M
1
, 12, 0xe8c7b756)
FF(c, d, a, b, M
2
, 17, 0x242070db)
FF(b, c, d, a, M
3
, 22, 0xc1bdceee)
FF(a, b, c, d, M
4
, 7, 0xf57c0faf)
FF(d, a, b, c, M
5
, 12, 0x4787c62a)
FF(c, d, a, b, M
6
, 17, 0xa8304613)
FF(b, c, d, a, M
7
, 22, 0xfd469501)
FF(a, b, c, d, M
8
, 7, 0x698098d8)
FF(d, a, b, c, M
9
, 12, 0x8b44f7af)
FF(c, d, a, b, M
10
, 17, 0xffff5bb1)
FF(b, c, d, a, M
11
, 22, 0x895cd7be)
FF(a, b, c, d, M
12
, 7, 0x6b901122)
FF(d, a, b, c, M
13
, 12, 0xfd987193)
FF(c, d, a, b, M
14
, 17, 0xa679438e)
FF(b, c, d, a, M
15
, 22, 0x49b40821)
Этап 2:
GG(a, b, c, d, M
1
, 5, 0xf61e2562)
GG(d, a, b, c, M
6
, 9, 0xc040b340)
GG(c, d, a, b, M
11
, 14, 0x265e5a51)
GG(b, c, d, a, M
0
, 20, 0xe9b6c7aa)
GG(a, b, c, d, M
5
, 5, 0xd62fl05d)
GG(d, a, b, c, M
10
, 9, 0x02441453)
GG(c, d, a, b, M
15
, 14, 0xd8ale681)
GG(b, c, d, a, M
4
, 20, 0xe7d3fbc8)
GG(a, b, c, d, M
9
, 5, 0x2,lelcde6)
GG(d, a, b, c, M
14
, 9, 0xc33707d6)
GG(c, d, a, b, M
3
, 14, 0xf4d50d87)
GG(b, c, d, a, M
8
, 20, 0x455al4ed)
GG(a, b, c, d, M
13
, 5, 0xa9e3e905)
GG(d, a, b, c, M
2
, 9, 0xfcefa3f8)
GG(c, d, a, b, M
7
, 14, 0x676f02d9)
GG(b, c, d, a, M
12
, 20, 0x8d2a4c8a)
Этап 3:

HH(a, b, c, d, M
5
, 4, 0xfffa3942)
HH(d, a, b, c, M
8
, 11, 0x8771f681)
HH(c, d, a, b, M
11
, 16, 0x6d9d6122)
HH(b, c, d, a, M
14
, 23, 0xfde5380c)
HH(a, b, c, d, M
1
, 4, 0xa4beea44)
HH(d, a, b, c, M
4
, 11, 0x4bdecfa9)
HH(c, d, a, b, M
7
, 16, 0xf6bb4b60)
HH(b, c, d, a, M
10
, 23, 0xbebfbc70)
HH(a, b, c, d, M
13
, 4, 0x289b7ec6)
HH(d, a, b, c, M
0
, 11, 0xeaa127fa)
HH(c, d, a, b, M
3
, 16, 0xd4ef3085)
HH(b, c, d, a, M
6
, 23, 0x04881d05)
HH(a, b, c, d, M
9
, 4, 0xd9d4d039)
HH(d, a, b, c, M
12
, 11, 0xe6db99e5)
HH(c, d, a, b, M
15
, 16, 0x1fa27cf8)
HH(b, c, d, a, M
2
, 23, 0xc4ac5665)
Этап 4:
II(a, b, c, d, M
0
, 6, 0xf4292244)
II(d, a, b, c, M
7
, 10, 0x432aff97)
II(c, d, a, b, M
14
, 15, 0xab9423a7)
II(b, c, d, a, M
5
, 21, 0xfc93a039)
II(a, b, c, d, M
12
, 6, 0x655b59c3)
II(d, a, b, c, M
3
, 10, 0x8f0ccc92)
II(c, d, a, b, M
10
, 15, 0xffeff47d)
II(b, c, d, a, M
1
, 21, 0x85845ddl)
II(a, b, c, d, M
8
, 6, 0x6fa87e4f)
II(d, a, b, c, M
15
, 10, 0xfe2ce6e0)
II(c, d, a, b, M
6
, 15, 0xa3014314)
II(b, c, d, a, M
13
, 21, 0x4e081lal)
II(a, b, c, d, M
4
, 6, 0xf7537e82)
II(d, a, b, c, M
11
, 10, 0xbd3af235)
II(c, d, a, b, M
2
, 15, 0x2ad7d2bb)
II(b, c, d, a, M
9
, 21, 0xeb86d391)
Эти константы, t i
, выбирались следующим образом:
На i-ом этапе t i
является целой частью 2 32
*abs(sin(i)), где i измеряется в радианах.
После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для сле- дующего блока данных. Окончательным результатом служит объединение A, B, C и D.
Безопасность MD5
Рон Ривест привел следующие улучшения MD5 в сравнении с MD4 [1322]:
1. Добавился четвертый этап.
2. Теперь в каждом действии используется уникальная прибавляемая константа .

3. Функция G на этапе 2 с ((X?Y)?(X?Z)?(Y?Z)) была изменена на (X?Z)?(Y?(¬Z)), чтобы сделать G
менее симметричной.
4. Теперь каждое действие добавляется к результату предыдущего этапа . Это обеспечивает более быст- рый лавинный эффект.
5. Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3 , чтобы сделать шаблоны менее похожими.
6. Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для уск о- рения лавинного эффекта. Четыре сдвига, используемые на каждом этапе, отличаются от значений,
используемых на других этапах.
Том Берсон (Tom Berson) попытался применить дифференциальный криптоанализ к одному этапу MD5
[144], но его вскрытие не оказалось эффективным ни для одного из четырех этапов . Более успешное вскрытие ден Боера и Босселаерса, использующее функцию сжатия, привело к обнаружению столкновений в MD5 [203,