Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Пятнадцать из них тривиально слабы, так как результат не зависит от одного из входов . Тридцать семь не- безопасны по более тонким причинам. В 17-й перечислены оставшиеся 12 безопасных схем : первые четыре безопасны против всех вскрытий (см. 9th), а последние 8 безопасны против всех типов вскрытий, кроме вскр ы- тия с фиксированной точкой, о котором в реальных условиях не стоит беспокоиться . Ключ Шифрование M i H i H i-1 Ключ Шифрование M i H i H i-1 Ключ Шифрование H i Ключ Шифрование M i H i H i-1 M i H i-1 Рис. 18-9. Четыре безопасных хэш-функции, у которых длина хэш-значения равна длине блока. Первая схема была описана в [1028]. Третья схема была описана в [1555, 1105, 1106] и предлагалась в каче- стве стандарта ISO [766]. Пятая схема была предложена Карлом Майером (Carl Meyer), но в литературе обычно называется Davies-Meyer [1606, 1607, 434, 1028]. Десятая схема была предложена в качестве режима хэш- функции для LOKI [273]. Скорость хэширования первой, второй, третьей, четвертой, пятой и одиннадцатой схем равна 1 - длина кл ю- ча равна длине блока. Скорость хэширования других схем составляет k/n, где k -длина ключа. Это означает, что если длина ключа короче длины блока, то блок сообщения должен быть по длине равен ключу . Не рекомендует- ся, чтобы блок сообщения был длиннее ключа, даже если длина ключа алгоритма шифрования больше, чем длина блока. Если блочный алгоритм подобно DES обладает свойством комплиментарности и слабыми ключами , для всех 12 схем существует возможность дополнительного вскрытия . Оно не слишком опасно и в действительности не стоит об это м беспокоиться. Однако вы можете обезопасить себя от такого вскрытия , зафиксировав значение второго и третьего битов ключа, равное ''01" или ''10" [1081,1107]. Конечно же это уменьшит длину k с 56 битов до 54 битов (для DES) и уменьшит скорость хэширования. Было показано, что следующие схемы, описанные в литературе, небезопасны . Эта схема [1282] была взломана в [369]: H E H i M i i = ? ( ) 1 Дэвис (Davies) и Прайс (Price) предложили вариант, в котором все сообщение циклически обрабатывается алгоритмом дважды [432, 433]. Вскрытие Копперсмита взламывает такую схему даже при небольшой вычисл и- тельной мощности [369]. В [1606] была показана небезопасность еще одной схемы [432, 458]: H E H i M H i i i = ? ? ?1 1 ( ) В [1028] была показана небезопасность следующей схемы (c - константа): H E M H M H i с i i i i = ? ? ? ? ? ( ) 1 1 Модификация схемы Davies-Meyer Лай (Lai) и Массей (Massey) модифицировали метод Davies-Meyer, чтобы можно было использовать шифр IDEA [930, 925]. IDEA использует 64-битовый блок и 128-битовый ключ . Вот предложенная ими схема: H 0 = I H , , где I H - случайное начальное значение H E H i H M i i i = ? ? 1 1 , ( ) Эта функция хэширует сообщение 64-битовыми блоками и выдает 64-битовое значение (см. 8-й). Более простое вскрытие этой схемы, чем метод грубой силы, неизвестно . Ключ Шифрование M i H i H i-1 Рис. 18-10. Модификация схемы Davies-Meyer. Preneel-Bosselaers-Govaerts-Vandewalle Эта хэш-функция, впервые предложенная в [1266], выдает хэш-значение, в два раза большее длины блока алгоритма шифрования: при 64-битовом алгоритме получается 128-битовое хэш-значение . При 64-битовом блочном алгоритме схема выдает два 64-битовых хэш-значения , G i и H i , объединение кото- рых и дает 128-битовое хэш-значение. У большинства блочных алгоритмов длина блока равна 64 битам . Два соседних блока, L i и R i , размер каждого равен размеру блока, хэшируются вместе. G 0 = I G , где I G - случайное начальное значение H 0 = I H , , где I H - другое случайное начальное значение G E R G R G H i L H i i i i i i i = ? ? ? ? ? ? ? ? ?1 1 1 1 ( ) H E H G L G H i L R i i i i i i i = ? ? ? ? ? ? ? ? ? ( ) 1 1 1 1 Лай приводит вскрытие этой схемы, которое в некоторых случаях делает вскрытие методом дня рождения тривиальным [925, 926]. Пренел (Preneel) [1262] и Копперсмит (Coppersmith0 [372] также успешно взломали эту схему. Не используйте ее. Quisquater-Girault Эта схема, впервые предложенная в [1279], генерирует хэш-значение, в два раза большее длины блока. Ее скорость хэширования равна 1. Она использует два хэш-значения, G i и H i , и хэширует вместе два блока, L i и R i G 0 = I G , где I G - случайное начальное значение H 0 = I H , , где I H - другое случайное начальное значение W E G R R H i L i i i i i = ? ? ? ? ? ( ) 1 1 G E W L G H L i R i i i i i i = ? ? ? ? ? ? ( ) 1 1 H W G i i i = ? ?1 Эта схема появилась в 1989 году в проекте стандарта ISO [764], но была заменена более поздней версией [765]. Проблемы безопасности этой схемы были описаны в [1107, 925, 1262, 372]. (В действительности, версия, описанная в материалах конференции, была после того, как версия, представленная на конференции, была вскрыта.) В ряде случаев сложность вскрытия методом дня рождения имеет равна 2 39 , а не 2 64 , как у вскрытия грубой. Не используйте эту схему. LOKI с удвоенным блоком Этот алгоритм представляет собой модификацию Quisquater-Cirault, специально спроектированную для ра- боты с LOKI [273]. Все параметры - те же, что и в Quisquater-Girault. G 0 = I G , где I G - случайное начальное значение H 0 = I H , , где I H - другое случайное начальное значение W E G R R H i L G i i i i i i = ? ? ? ? ? ? ?1 1 1 ( ) G E W L G H L i R H i i i i i i i = ? ? ? ? ? ? ? ?1 1 1 ( ) H W G i i i = ? ?1 И снова в некоторых случаях вскрытие методом дня рождения оказывается тривиальным [925, 926, 1262, 372, 736]. Не используйте эту схему. Параллельная схема Davies-Meyer Это еще одна попытка создать алгоритм со скоростью хэширования 1, который выдает хэш-значение, в два раза большее длины блока. [736]. G 0 = I G , где I G - случайное начальное значение H 0 = I H , , где I H - другое случайное начальное значение G E G L L H i L R i i i i i i = ? ? ? ? ? ? ( ) 1 1 H E H R R H i L i i i i i = ? ? ? ? ? ( ) 1 1 К сожалению эта схема тоже небезопасна [928, 861]. Оказывается, что хэш-функция удвоенной длины со скоростью хэширования, равной 1, не может быть безопаснее, чем Davies-Meyer [861]. Тандемная (Tandem) и одновременная (Abreast) схемы Davies-Meyer Другой способ обойти ограничения, присущие блочным шифрам с 64-битовым ключом, использует алг о- ритм, подобный IDEA (см. раздел 13.9), с 64-битовым блоком и 128-битовым ключом. Следующие две схемы выдают 128-битовхэш-значение, а их скорость хэширования равна 1 / 2 [930, 925]. Ключ Шифрование G i G i-1 Шифрование Ключ W i M i H i H i-1 Рис. 18-11. Тандемная (Tandem) схема Davies-Meyer. В первой схеме две модифицированные функции Davies-Meyer работают тандемом, конвейерно (см. 7-й). G 0 = I G , где I G - случайное начальное значение H 0 = I H , , где I H - другое случайное начальное значение W E H i G M i i i = ? ? 1 1 , ( ) G G E G i i M W i i i = ? ? ? 1 1 , ( ) H W H i i i = ? ?1 В следующей схеме используются две модифицированные функции, работающие одновременно (см. 6-й). G 0 = I G , где I G - случайное начальное значение H 0 = I H , , где I H - другое случайное начальное значение G G E G i i M H i i i = ? ¬ ? ? ? 1 1 1 , ( ) H H E H i i G M i i i = ? ? ? ? 1 1 1 , ( ) Ключ Шифрование G i G i-1 Шифрование Ключ M i H i H i-1 Рис. 18-12. Одновременная (Abreast) схема Davies-Meyer. В обеих схемах два 64-битовых значения , G i и H i , объединяются, образуя единое 128-битовое хэш-значение . Насколько известно, безопасность 128-битовой хэш-функции этих алгоритмов идеальна : для обнаружения сообщения с заданным хэш-значением требуется 2 128 попыток, а для нахождения двух случайных сообщений с одинаковым хэш-значением - 2 64 попыток, при условии, что лучшим способом вскрытия является применение грубой силы. MDC-2 и MDC-4 MDC-2 и MDC-4 разработаны в IBM [1081, 1079]. В настоящее время изучается вопрос использования MDC-2, иногда называемой Meyer-Schilling, в качестве стандарта ANSI и ISO [61, 765], этот вариант был пред- ложен в [762]. MDC-4 определена для проекта RIPE [1305] (см. раздел 25.7). Спецификация использует DES в качестве блочной функции, хотя теоретически может быть использован любой блочный алгоритм . Скорость хэширования MDC-2 равна 1 / 2 , длина хэш-значения этой функции в два раза больше размера блока.Ее схема показана на 5-й. MDC-4 также выдает хэш-значение в два раза большее размера блока, а ее ск о- рость хэширования равна 1 / 4 (см. 4-й). G i-1 H i-1 Ключ Шифрование Шифрование Ключ M i G i H i Рис. 18-13. MDC-2. G i-1 H i-1 Ключ Шифрование Шифрование Ключ M i G i H i Ключ Шифрование Шифрование Ключ Рис. 18-14. MDC-4. Эти схемы были проанализированы в [925, 1262]. Они безопасны с учетом сегодняшних возможностей в ы- числительной техники, но их надежность не так велика, как хотелось разработчикам . Их устойчивость к диффе- ренциальному криптоанализу при DES в качестве блочного алгоритма была рассмотрена в [1262]. MDC-2 и MDC-4 запатентованы [223]. Хэш-функция AR Хэш-функция AR была разработана Algorithmic Research, Ltd. и затем распространена ISO только для ин- формации [767]. Ее базовая структура является вариантом используемого блочного шифра (DES в упомянутой статье) в режиме CBC. Выполняется XOR последних двух блоков шифротекста, константы и текущего блока сообщения, результат шифруется алгоритмом . Хэш-значением являются последние вычисленные два блока шифротекста. Сообщение обрабатывается дважды, двумя различными ключами, поэтому скорость хэширования равна 1 / 2 . Первым ключом служит 0x0000000000000000, вторым - 0x2a41522f4446502a, а значение константы c равно 0x0123456789abcdef. Результат сжимается до одного 128-битового хэш-значения . Подробности приведе- ны в [750]. H i = E K (M i ? H i-1 ? H i-2 ? c) ? M i Функция выглядит привлекательной, но не является безопасной . После некоторой значительной предобра- ботки становится возможным легко находить сообщения с одинаковым хэш-значением [416]. Хэш-функция ГОСТ Эта хэш-функция появилась в России и определена в стандарте ГОСТ Р 34.11.94 [657]. В ней используется блочный алгоритм ГОСТ (см. раздел 14.1), хотя теоретически может использоваться любой блочный алгоритм с 64-битовым блоком и 256-битовым ключом . Функция выдает 256-битовое хэш-значение . Функция сжатия, H i = f(M i ,H i-1 ) (оба операнда - 256-битовые величины) определяется следующим образом: (1) При помощи линейного смешивания M i , H i-1 и некоторых констант генерируется четыре ключа шифров а- ния ГОСТ. (2) Каждый ключ используется для шифрования отличных 64 битов H i-1 в режиме ECB. Полученные 256 би- тов сохраняются во временной переменной S. (3) H i является сложной, хотя и линейной функцией S, M i и H i-1 Хэш-значение последнего блока сообщения не является его окончательным хэш-значением . На деле исполь- зуется три переменные сцепления: H n - это хэш-значение последнего блока, Z - это XOR всех блоков сообщения, а L - длина сообщения. С использованием этих переменных и дополненного последнего блока M', окончательное хэш-значение равно: H = f(Z ? M',f(L,f(M', H n ))) Документация немного запутана (и на русском языке), но я думаю, что понял все правильно . Во всяком слу- чае эта хэш-функция определена как часть российского Стандарта цифровой подписи (см. раздел 20.3). Другие схемы Ральф Меркл предложил схему, использующую DES, но она медленна - обрабатывает только семь битов с о- общения за итерацию, и каждая итерация состоит из двух шифрований DES [1065, 1069]. Другая схема [1642, 1645] небезопасна [1267], когда-то она предлагалась в качестве стандарта ISO. 18.12 Использование алгоритмов с открытым ключом В качестве однонаправленной хэш-функции можно использовать и алгоритм шифрования с открытым кл ю- чом в режиме сцепления блоков. Если затем выбросить личный ключ, то взломать хэш-функцию будет также трудно, как и прочитать сообщение без личного ключа. Вот пример, использующий RSA. Если M - это хэшируемое сообщение, n - произведение двух простых чисел p и q, а e - другое большое число, взаимно простое с (p - l)(q - 1), то хэш-функция, H(M), будет равна H(M) = M e mod n Еще проще использовать одно сильное простое число в качестве модуля p. Тогда: H(M) = M e mod p Вскрытие этой проблемы возможно не легче, чем поиск дискретного логарифма e. Проблема этого алгорит- ма состоит в том, что он намного медленнее, чем другие обсуждаемые алгоритмы . По этой причине я не сове- тую его. 18.13 Выбор однонаправленной хэш-функции Лучшими кажутся SHA, MD5 и схемы, основанные на блочных шифрах. Другие на самом деле не были и с- следованы в достаточной степени. Я голосую за SHA. У нее более длинное хэш-значение, чем у MD5, она быст- рее, чем многие схемы с блочными шифрами, и разработана NSA. Я верю в криптоаналитические возможности NSA, даже если они не публикуют свои результаты . В 16-й для сравнения приведены временные соотношения для некоторых хэш-функций . They are meant for comparison purposes only. Табл. 18-2. Скорости шифрования некоторых хэш-функций на i486SX/33 МГц Алгоритм Длина хэш-значения Скорость шифрования (Кбайт/с) Одновременная схема Davies-Meyer (с IDEA) 128 22 Davies-Meyer (с DES) 64 9 Хэш-функция ГОСТ 256 11 HAVAL (3 прохода) переменная 168 HAVAL (4 прохода) переменная 118 HAVAL (5 прохода) переменная 95 MD2 128 23 MD4 128 236 MD5 128 174 N-хэш (12 этапов) 128 29 N-хэш (15 этапов) 128 24 RIPE-MD 128 182 SHA 160 75 Snerfu (4 прохода) 128 48 Snerfu (8 проходов) 128 23 18.14 Коды проверки подлинности сообщения Код проверки подлинности сообщения (message authentication code, MAC) - это зависящая от ключа однона- правленная хэш-функция. Коды MAC обладают теми же свойствами, что и рассмотренные ранее хэш-функции, но они, кроме того, включают ключ. (Это не означает, что вы можете опубликовать ключ MAC и использовать MAC как однонаправленную хэш-функцию.) Только владелец идентичного ключа может проверить хэш- значение. Коды MAC очень полезны для обеспечения проверки подлинности без нарушения безопасности . Коды MAC могут быть использованы для проверки подлинности файлов, которыми обмениваются пользов а- тели. Также они могут быть использованы одним пользователем для проверки, не изменились ли его файлы, может быть из-за вируса. Пользователь может вычислить MAC его файлов и сохранить эти значения в таблице . Если пользователь воспользуется вместо MAC однонаправленной хэш-функцией, то вирус может вычислить новые хэш-значения после заражения файлов и заменить элементы таблицы . С MAC вирус не сможет этого добиться, так как ключ вирусу неизвестен . Простым способом преобразовать однонаправленную хэш-функцию в MAC является шифрование хэш- значения симметричным алгоритмом. Любой MAC может быть преобразован в однонаправленную хэш- функцию с помощью раскрытия ключа. CBC-MAC Простейший способ создать зависящую от ключа однонаправленную хэш-функцию - шифрование сообщения блочным алгоритмом в режимах CBC или CFB. Хэш-значением является последний шифрованный блок , за- шифрованный в режимах CBC или CFB. Метод CBC определен в ANSI X9.9 [54], ANSI X9.19 [56], ISO 8731-1 [759], ISO 9797 [763] и австралийском стандарте [1496]. Дифференциальный криптоанализ может вскрыть эту схему, если в качестве блочного алгоритма используется DES с уменьшенным числом этапов или FEAL [1197]. Потенциальная проблема, связанная с безопасностью этого метода, состоит в том, что получатель должен знать ключ, и этот ключ позволяет ему генерировать сообщения с тем же хэш-значением, что и у присланного сообщения, с помощью дешифрирования в обратном направлении . Алгоритм проверки подлинности сообщения (Message Authenticator Algorithm, MAA) Этот алгоритм является стандартом ISO [760]. Он выдает 32-битовое хэш-значение и был спроектирован для мэйнфреймов с быстрыми инструкциями умножения [428]. v = v <<< 1 e = v ? w x = ((((e + y) mod 2 32 ) ? A ? C) * (x ? M i )) mod 2 32 -1 y = ((((e + x) mod 2 32 ) ? B ? D) * (y ? M i )) mod 2 32 -1 Эти действия повторяются для каждого блока сообщения , M i , и результирующее хэш-значение получается с помощью XOR x и y. Переменные v и e зависят от ключа. A, B, C и D являются константами. Возможно, этот алгоритм широко используется , но я не верю, что он достаточно безопасен . Он был разрабо- тан давным давно и не слишком сложен. Двунаправленный MAC Этот MAC выдает хэш-значение, которое в два раза длиннее блока алгоритма [978). Сначала для сообщения вычисляется CBC-MAC. Затем вычисляется CBC-MAC сообщения с обратным порядком блоков. Двунаправ- ленный MAC просто является объединением этих двух значений . К сожалению эта схема небезопасна [1097]. |