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

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

1331, 1336]. Само по себе это вскрытие невозможно для вскрытия MD5 в практических приложениях, оно не влияет и на использование MD5 в алгоритмах шифрования, подобных Luby-Rackoff (см. раздел 14.11). Успех этого вскрытия означает только, что одна из основных целей проектирования MD5- создать устойчивую к столкновениям функцию сжатия - не была достигнута . Хотя справедливо, что "кажется, что у функции сжатия есть слабое место, но это практически не влияет на безопасность хэш-функции " [1336], я отношусь к использо- ванию MD5 очень осторожно.
18.6 MD2
MD2 - это другая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом [801, 1335].
Она, вместе с MD5, используется в протоколах PEM (см. раздел 24.10). Безопасность MD2 опирается на слу- чайную перестановку байтов. Эта перестановка фиксирована и зависит от разрядов ?. S
0
, S
1
, S
2
, . . . , S
255
и яв- ляются перестановкой. Чтобы выполнить хэширование сообщения M:
(1)
Дополните сообщение i байтами, значение i должно быть таким, чтобы длина полученного сообщения б ы- ла кратна 16 байтам.
(2)
Добавьте к сообщению 16 байтов контрольной суммы .
(3)
Проинициализируйте 48-байтовый блок: X
0
, X
1
, X
2
, . . ., X
47
. Заполните первые 16 байтов X нулями, во вторые 16 байтов X скопируйте первые 16 байтов сообщения, а третьи 16 байтов X должны быть равны
XOR первых и вторых 16 байтов X.
(4)
Вот как выглядит функция сжатия:
t = 0
For j = 0 to 17
For k = 0 to 47
t = X
t
XOR S
t
X
k
= t t = (t + j) mod 256
(5)
Скопируйте во вторые 16 байтов X вторые 16 байтов сообщения, а третьи 16 байтов X должны быть равны
XOR первых и вторых 16 байтов X. Выполните этап (4). Повторяйте этапы (5) и (4) по очереди для ка ж- дых 16 байтов сообщения.
(6)
Выходом являются первые 16 байтов X.
Хотя в MD2 пока не было найдено слабых мест (см. [1262]), она работает медленнее большинства других предлагаемых хэш-функций.
18.7 Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA)
NIST, вместе с NSA, для Стандарта цифровой подписи (Digital Signature Standard, см. Раздел 20.2) разрабо- тал Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA) [1154 (Digital Signature Standard]. (Сам стандарт называется Стандарт безопасного хэширования ( Secure Hash Standard, SHS), а SHA - это алгоритм,
используемый в стандарте.) В соответствии с Federal Register [539]:
Предлагается Федеральный стандарт обработки информации (Federal Information Processing Standard, FIPS) для Стандарта безопасного хэширования (Secure Hash Standard, SHS). Этот предложение определяет Алгоритм безопасного хэширования
(Secure Hash Algorithm, SHA) для использования вместе со Стандартом цифровой подписи ( Digital Signature Standard) . . ..

Кроме того, для приложений, в которых не требуется цифровая подпись , SHA должен использоваться во всех Федеральных приложениях, в которых понадобится алгоритм без опасного хэширования.
И
Этот Стандарт определяет Алгоритм безопасного хэширования ( Secure Hash Algorithm, SHA), необходимый для обеспе- чения безопасности Алгоритма цифровой подписи ( Digital Signature Algorithm, DSA). Для любого входного сообщения дли- ной меньше 2 64
битов SHA выдает 160-битовый результат, называемый кратким содержанием сообщения . Далее, краткое со- держание сообщения становится входом DSA, который вычисляет подпись для сообщения . Подписывание краткого содержа- ния вместо всего сообщения часто повышает эффективность процесса, так как краткое содержание сообщения намного меньше, чем само сообщение. То же краткое содержание сообщения должно быть получено тем, кто проверяет подпись, если принятая им версия сообщения используется в качестве входа SHA. SHA называется безопасным, так как он разработан так,
чтобы было вычислительно невозможно найти сообщение, соответствующее данному краткому содержанию сообщения или найти два различных сообщения с одинаковым кратким содержанием сообщения . Любые изменения, произошедшие при п е- редаче сообщения, с очень высокой вероятностью приведут к изменению краткого содержания сообщения, и подпись не пройдет проверку. Принципы, лежащие в основе SHA, аналогичны использованным профессором Рональдом Л. Ривестом из
MIT при проектировании алгоритма краткого содержания сообщения MD4 [1319]. SHA разработан по образцу упомянутого алгоритма.
SHA выдает 160-битовое хэш-значение, более длинное, чем у MD5.
Описание SHA
Во первых, сообщение дополняется, чтобы его длина была кратной 512 битам . Используется то же дополне- ние, что и в MD5: сначала добавляется 1, а затем нули так, чтобы длина полученного сообщения была на 64
бита меньше числа, кратного 512, а затем добавляется 64-битовое представление длины оригинального сообщ е- ния.
Инициализируются пять 32-битовых переменных (в MD5 используется четыре переменных, но рассматр и- ваемый алгоритм должен выдавать 160-битовое хэш-значение ):
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
E = 0xc3d2e1fO
Затем начинается главный цикл алгоритма . Он обрабатывает сообщение 512-битовыми блоками и продо л- жается, пока не исчерпаются все блоки сообщения .
Сначала пять переменных копируются в другие переменные : A в a, B в b, C в c, D в d и E в e.
Главный цикл состоит из четырех этапов по 20 операций в каждом (в MD5 четыре этапа по 16 операций в каждом). Каждая операция представляет собой нелинейную функцию над тремя из a, b, c, d и e, а затем выпол- няет сдвиг и сложение аналогично MD5. В SHA используется следующий набор нелинейных функций :
f t
(X,Y,Z) = (X ? Y) ? ((¬X) ? Z) , для t=0 до 19
f t
(X,Y,Z) = X ? Y ? Z , для t=20 до 39
f t
(X,Y,Z) = (X ? Y) ?(X ? Z) ? (Y ? Z) , для t=40 до 59
f t
(X,Y,Z) = X ? Y ? Z , для t=60 до 79
в алгоритме используются следующие четыре константы:
K
t
= 0x5a827999, для t=0 до 19
K
t
= 0x6ed9eba1 , для t=20 до 39
K
t
= 0x8flbbcdc, для t=40 до 59
K
t
= 0xca62c1d6, для t=60 до 79
(Если интересно, как получены эти числа, то :0x5a827999 = 2 1/2
/4, 0x6ed9eba1 = 3 1/2
/4, 0x8flbbcdc = 5 1/2
/4,
0xca62c1d6 = 10 1/2
/4.)
Блок сообщения превращается из 16 32-битовых слов (M
0
по M
15
) в 80 32-битовых слов (W
0
по W
79
) с помо- щью следующего алгоритма:
W
t
= M
t
, для t = 0 по 15
W
t
= (W
t-3
? W
t-8
? W
t-14
? W
t-16
) <<< 1, для t = 16 по 79
(В качестве интересного замечания, в первоначальной спецификации SHA не было циклического сдвига вле-

во. Изменение "исправляет технический изъян, который делал стандарт менее безопасным, чем предполагалось "
1543]. NSA отказалось уточнить истинную причину изъяна.)
Если t - это номер операции (от 1 до 80), W
t представляет собой t-ый подблок расширенного сообщения, а
<<FOR t = 0 to 79
TEMP = (a <<< 5) + f t
(b,c,d) + e + W
t
+ K
t e = d d = c c = b <<< 30
b = a a = TEMP
На 11-й показана одна операция. Сдвиг переменных выполняет ту же функцию, которую в MD5 выполняет использование в различных местах различных переменных .
Нелинейная функция
<<<30
=
E
>
E
?
E
@
E
A
E
=
E-1
>
E-1
?
E-1
@
E-1
A
E-1
K
t
W
j
<<<5
Рис. 18-7. Одна операция SHA.
После всего этого a, b, c, d и e добавляются к A, B, C D и E, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C D и E.
Безопасность SHA
SHA очень похожа на MD4, но выдает 160-битовое хэш-значение. Главным изменением является введение расширяющего преобразования и добавление выхода предыдущего шага в следующий с целью получения более быстрого лавинного эффекта. Рон Ривест опубликовал цели, преследуемые им при проектировании MD5, но разработчики SHA этого не сделали. Вот улучшения, внесенные Ривестом в MD5 относительно MD4, и их срав- нение с SHA:
1. "Добавился четвертый этап." В SHA тоже. Однако в SHA на четвертом этапе используется та же функция f, что и на втором этапе.
2. "Теперь в каждом действии используется уникальная прибавляемая константа ." SHA придерживается схемы MD4, повторно используя константы для каждой группы их 20 этапов.
3. "Функция G на этапе 2 с ((X?Y)?(X?Z)?(Y?Z)) была изменена на (X?Z)?(Y?(¬Z)), чтобы сделать G
менее симметричной." В SHA используется версия функции из MD4: (X ? Y) ?(X ? Z) ? (Y ? Z).
4. "Теперь каждое действие добавляется к результату предыдущего этапа . Это обеспечивает более быст- рый лавинный эффект." Это изменение было внесено и в SHA. Отличие состоит в том, что в SHA до- бавлена пятая переменная к b, c и d, которые уже используются в f t
. Это незначительное изменение делает применения вскрытия MD5 ден Боером и Босселаерсом невозможным по отношению к SHA.
5. "Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3 , чтобы сделать

шаблоны менее похожими." SHA в этом месте совершенно отличается, так как использует циклич е- ский код исправления ошибок.
6. "Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для уск о- рения лавинного эффекта. Четыре сдвига, используемые на каждом этапе, отличаются от значений,
используемых на других этапах." SHA на каждом этапе использует постоянное значение сдвига. Это значение - взаимно простое число с размером слова, как и в MD4.
Это приводит к следующему заключению : SHA - это MD4 с добавлением расширяющего преобразования,
дополнительного этапа и улучшенным лавинным эффектом. MD5 - это MD4 с улучшенным битовым хэширова- нием, дополнительным этапом и улучшенным лавинным эффектом .
Сведения об успешных криптографических вскрытиях SHA отсутствуют. Так как эта однонаправленная хэш- функция выдает 160-хэш-значение, она устойчивее к вскрытию грубой силой (включая вскрытие методом дня рождения), чем 128-битовые хэш-функции, рассматриваемые в этой главе .
18.8 RIPE-MD
RIPE-MD была разработана для проекта RIPE Европейского сообщества [1305] (см. раздел 25.7). Этот алго- ритм представляет собой вариант MD4, разработанный так, чтобы противостоять известным методам крипт о- графического вскрытия, и выдает 128-битовое хэш-значение . Внесены изменения в циклические сдвиги и пор я- док слов сообщения. Кроме того, параллельно работают две копии алгоритма, отличающиеся константами . По- сле каждого блока результат обоих копий добавляется к переменным сцепления . По видимому, это повышает устойчивость алгоритма к криптоанализу .
18.9 HAVAL
HAVAL - это однонаправленная хэш-функция переменной длины [1646]. Она является модификацией MD5.
HAVAL обрабатывает сообщение блоками по 1024 бита, в два раза большими, чем в MD5. Используется восемь
32-битовых переменных сцепления, в два раза больше, чем в MD5, и переменное число этапов, от трех до пяти
(в каждом 16 действий). Функция может выдавать хэш-значения длиной 128, 160, 192, 224 или 256 битов.
HAVAL заменяет простые нелинейные функции MD5 на сильно нелинейные функции 7 переменных , каждая из которых удовлетворяет строгому лавинному критерию . На каждом этапе используется одна функция, но при каждом действии входные переменные переставляются различным образом . Используется новый порядок со- общения, и при каждом этапе (кроме первого этапа) используется своя прибавляемая константа . В алгоритме также используется два циклических сдвига .
Ядром алгоритма являются следующие действия:
TEMP = (f(j,A,B,C,D,E,F,G) <<<7) + (H <<<11) + M[i][r(j)+K(j)]
H = G; G = F; F = E; E = D; D = C; C = B; B = A; A = TEMP
Переменное количество этапов и переменная длина выдаваемого значения означают, что существует 15 ве р- сий алгоритма. Вскрытие MD5, выполненное ден Боером и Босселаерсом [203], неприменимо к HAVAL из-за циклического сдвига H.
18.10 Другие однонаправленные хэш-функции
MD3 является еще одной хэш-функцией, предложенной Роном Ривестом . Она имела ряд недостатков и нико- гда не выходила за пределы лаборатории, хотя ее описание недавно было опубликовано в [1335].
Группа исследователей из Университета Ватерлоо предложила однонаправленную хэш-функцию на базе итеративного возведения в степень в GF(2 593
) [22]. По этой схеме сообщение разбивается на 593-битовые блоки.
Начиная с первого блока блоки последовательно возводятся в степень . Показатель степени - это результат вы- числений для предыдущего блока, первый показатель задается с помощью IV.
Айвэн Дамгард (Ivan Damgеrd) разработал однонаправленную хэш-функцию, основанную на проблеме рю к- зака (см. раздел 19.2) [414], она может быть взломана примерно за 2 32
операций [290, 1232, 787].
В качестве основы для однонаправленных хэш-функций предлагался и клеточный автомат Стива Вольфрама
[1608]. Ранняя реализация [414] небезопасна [1052,404]. Другая однонаправленная хэш-функция, Cellhash [384,
404], и улучшенная версия, Subbash [384,402, 405], также основаны на клеточных автоматах и предназначены для аппаратной реализации. Boognish объединил принципы Cellhash и MD4 [402, 407]. StepRightUp также мо- жет быть реализована как хэш-функция [402].
Летом 1991 года Клаус Шнорр (Claus Schnorr) предложил однонаправленную хэш-функцию на базе дис-

кретного преобразования Фурье, названную FFT-Hash [1399]. Через несколько месяцев она была взломана дв у- мя независимыми группами [403, 84]. Шнорр предложил новую версию, FFT-Hash II (предыдущая была пере- именована в FFT-Hash I) [1400], которая была взломана через несколько недель [1567]. Шнорр предложил дальнейшие модификации [1402, 1403] но, при данных обстоятельствах, они намного медленнее, чем другие алгоритмы этой главы. Еще одна хэш-функция, SL
2
[1526], небезопасна [315].
Дополнительную информацию по теории проектирования однонаправленных хэш-функций из однонапра в- ленных функций и однонаправленных перестановок можно найти в [412, 1138, 1342].
18.11 Однонаправленные хэш-функции, использующие симметричные блоч- ные алгоритмы
В качестве однонаправленных хэш-функций можно использовать симметричные блочные алгоритмы ши ф- рования. Идея в том, что если безопасен блочный алгоритм, то и однонаправленная хэш-функция будет без о- пасной.
Самым очевидным способом является шифрование сообщения в режиме CBC или CFB с помощью фиксиро- ванного ключа и IV, хэш-значением будет последний блок шифротекста . Эти методы описаны в различных стандартах, использующих DES: оба режима в [1143], CBC в [1145], CFB в [55, 56, 54]. Этот способ не слиш- ком подходит для однонаправленных хэш-функций , хотя он будет работать для MAC (см. раздел 18.14) [29].
Способ поумнее использует в качестве ключа блок сообщения , предыдущее хэш-значение в качестве входа, а текущее хэш-значение служит выходом.
Действительные хэш-функции даже еще сложнее. Размер блока обычно совпадает с длиной ключа, и разм е- ром хэш-значения будет длина блока. Так как большинство блочных алгоритмов 64-битовые , спроектирован ряд схем, дающих хэш-значение в два раза большее длины блока .
При условии, что хэш-функция правильна , безопасность этой схемы основана на безопасности используемой блочной функции. Однако есть и исключения. Дифференциальный криптоанализ лучше работает против бло ч- ных функций в хэш-функциях, чем против блочных функций, используемых для шифрования : ключ известен,
поэтому можно использовать различные приемы. Для успеха нужна только одна правильная пара, и можно г е- нерировать столько выбранного открытого текста, сколько нужно . Это направление освещается в [1263, 858,
1313].
Ниже приведен обзор различных хэш-функций, описанных в литературе [925, 1465, 1262]. Выводы о воз- можности вскрытия предполагают, что используемый блочный алгоритм безопасен, и лучшим вскрытием явл я- ется вскрытие грубой силой.
Полезной мерой для хэш-функций, основанных на блочных шифрах, является скорость хэширования, или количество n-битовых блоков сообщения (n - это размер блока алгоритма), обрабатываемых при шифровании .
Чем выше скорость хэширования, тем быстрее алгоритм . (Другое определение этого параметра дается в [1262],
но определение, приведенное мной, более интуитивно и шире используется . Это может запутать.)
Схемы, в которых длина хэш-значения равна длине блока
Вот общая схема (см. 10-й):
H
0
= I
H
, , где I
H
- случайное начальное значение
H
i
= E
A
(B) ? C
где A, B и C могут быть либо M
i
, H
i-1
, (M
i
? H
i-1
), либо константы (возможно равные 0). H
0
- это некоторое случайное начальное число I
H
. Сообщение разбивается на части в соответствии с размером блока , M
i
, обрабаты- ваемые отдельно. Кроме того, используется вариант MD-усиления, возможно та же процедура дополнения, что и в MD5 и SHA.
Ключ
Шифрование
A
B
C
Рис. 18-8. Обобщенная хэш-функция, у которой длина хэш-значения равна длине блока.
Табл. 18-1.
Безопасные хэш-функции, у которых

длина хэш-значения равна длине блока
H
E
M
M
i
H
i i
i
=
?
?1
(
)
H
E
M
H
M
H
i
H
i i
i i
i
=
?
?
?
?
?
?
1 1
1
(
)
H
E
M
H
M
i
H
i i
i i
=
?
?
?
?
1 1
(
)
H
E
M
H
M
i
H
i i
i i
=
?
?
?
?
1 1
(
)
H
E
H
H
i
M
i i
i
=
?
?
?
(
)
1 1
H
E
M
H
M
H
i
M
i i
i i
i
=
?
?
?
?
?
(
)
1 1
H
E
H
M
H
i
M
i i
i i
=
?
?
?
?
(
)
1 1
H
E
M
H
H
i
M
i i
i i
=
?
?
?
?
(
)
1 1
H
E
M
M
i
M
H
i i
i i
=
?
?
?1
(
)
H
E
H
H
i
M
H
i i
i i
=
?
?
?
?
?1 1
1
(
)
H
E
M
H
i
M
H
i i
i i
=
?
?
?
?1 1
(
)
H
E
H
M
i
M
H
i i
i i
=
?
?
?
?1 1
(
)
Три различные переменные могут принимать одно из четырех возможных значений, поэтому всего сущес т- вует 64 варианта схем этого типа. Они все были изучены Бартом Пренелом ( Bart Preneel) [1262].