 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Криптоанализ Snefru
|
|
Используя дифференциальный криптоанализ, Бихам и Шамир показали небезопасность двухпроходного Snefru (с 128-битовым хэш-значением) [172]. Их способ вскрытия за несколько минут обнаруживает пару соо б-щений с одинаковым хэш-значением.
Для 128-битового Snefru их вскрытия работают лучше, чем вскрытие грубой силой для четырех и менее пр о-ходов. Вскрытие Snefru методом дня рождения требует 2м операций; дифференциальный криптоанализ может найти пару сообщений с одинаковым хэш-значением за 228'5 операций для трехпроходного Snefru и за 244'5 операций для четырехпроходного Snefru. Нахождение сообщения, хэш-значение которого совпадает с заданным, при использовании грубой силы требует 2128 операций, при дифференциальном криптоанализе для этого нужно 256 операций для трехпроходного и 288 операций для четырехпроходного Snefru.
Хотя Бихам и Шамир не анализировали 256-битовые хэш-значения, они провели анализ вплоть до 224-битовых хэш-значений. В сравнении с вскрытием методом дня рождения, требующим 2 112 операций они могут найти сообщения с одинаковым хэш-значением за 212'5 операций для двухпроходного Snefru, за 233 операций для трехпроходного Snefru и за для 281 операций для четырехпроходного Snefru.
В настоящее время Меркл рекомендует использовать Snefru по крайней мере с восемью проходами [1073]. Однако с таким количеством проходов алгоритм становится намного медленнее, чем MD5 или SHA.
М-хэш
N-хэш - это алгоритм, придуманный в 1990 году исследователями Nippon Telephone and Telegraph, теми же людьми, которые изобрели FEAL [1105, 1106]. Л^-хэш использует 128-битовые блоки сообщения, сложную ран-домизирующую функцию, похожую на FEAL, и выдает 128-битовое хэш-значение.
Хэш-значение каждого 128-битового блока является функцией блока и хэш-значения предыдущего блока.
Я0 = /, где / - случайное начальное значение
Hi = g(M„ Я,ч) © Mi © Я,ч
Хэш-значение всего сообщения представляет собой хэш-значение последнего блока сообщения. Случайное начальное значение /может быть любым числом, определенным пользователем (даже одними нулями).
Функция g достаточно сложна. Схема алгоритма приведена на 16-й. Сначала переставляются левая и правая 64-битовые половины 128-битового хэш-значения предыдущего блока Я„ь а затем выполняется XOR с повторяющимся шаблоном (128-битовым) и XOR с текущим блоком сообщения М„ Далее это значение каскадно преобразуется в N (на рисунках N= 8) стадий обработки. Другим входом стадии обработки является предыдущее хэш-значение, подвергнутое XOR с одной из восьми двоичных констант.
| PS |
| PS |
EXG: перестановка левой и правой частей v. 1010... 1010 (двоичное, 128 битов) PS: стадия обработки (processing stage) Ц-=б||Ау1 6ЦД-2 б||Д3 б||Д4 ||: конкатенация б: 000... 0 (двоичное, 24 бит) д.Л=4*(/-1)+/с(/с=1,2,3,4, А]к - 8 битов в длину) Hi = g(Mi, Hi и)® Mi® Hi и
Лм
128 битов
Mi 128 битов
i— Я
v
EXG
| PS |
Уг
| PS |
| PS |
4 4 4 4
Ve
Ф
-*• hi
128 битов
•0-
v8
PS
PS
PS
Рис. 18-2. Схема iV-хэш.
Одна стадия обработки показана на 15-й. Блок сообщения разбивается на четыре 32-битовых значения. Предыдущее хэш-значение также разбивается на четыре 32-битовых значения. Функция f представлена на 14th. Функции S0 и Si те же самые, что и в FEAL.
S0(a,b) = циклический сдвиг влево на два бита ((а + Ъ) mod 256)
Sx{a,b) = циклический сдвиг влево на два бита((а + Ъ + 1) mod 256)
| 32 бита |
| 32 бита |
X X2
У Уг
Вход:Х=Х1||Х2||Хз||Х4 P= Р1ЦР2ЦР3ЦР4
Выход: У=УУ2||Уз||У4 y=PS(X,P)
X3 X4
Уз У4
Рис. 18-3. Одна стадия обработки iV-хэш.
Выход одной стадии обработки становится входом следующей стадии обработки. После последней стадии обработки выполняется XOR выхода с М, и Я„ь а затем к хэшированию готов следующий блок.
X
,-, 32 бита ^
Р ---------- ►©
8 битов 8 битов
32 бита
8 битов 8 битов
Ю О*
St
So
So
И St
▼____ £
|32 бита
f{x,P)
y=So(X1,X2)=Rot2((X1+X2) mod 256) y=S1(X1,X2)=Rot2((X1+X2+1) mod 256) У: выходные 8 битов, ХЬХ2 (8 битов): входы Rot2(V): циклический сдвиг влево на 2 бита 8-битовых данных У
Рис. 18-4. Функция/.
Криптоанализ N-хэш
Берт ден Боер (Bert den Boer) открыл способ создавать столкновения в функции этапа N-хэш [1262]. Бихам и Шамир применили дифференциальный криптоанализ для вскрытия 6-этапной N-хэш [169, 172]. Конкретное выполненное ими вскрытие (конечно же, могли быть и другие) работает для любого N, делящегося на 3, и эффективнее вскрытия методом дня рождения для любого N, меньшего 15.
То же самое вскрытие может обнаруживать пары сообщений с одинаковым хэш-значением для 12-этапной N-хэш за 256 операций (для вскрытия грубой силой нужно 2м операций). Л^-хэш с 15 этапами безопасна по отношению к дифференциальному криптоанализу: для вскрытия потребуется 272 операций.
Разработчики алгоритма рекомендуют использовать 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-битовое хэш-значение.
Дата публикования: 2014-11-03; Прочитано: 488 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
