Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 5.4 Типичные атаки на хэш-функции
- 5.4.1 Атака «дней рождения» для нахождения коллизий
| ТЕОРЕМА 5.8 Предположим, что tts , как определено в Уравнении (5.4)
является псевдослучайным генератором любых s, MAC, определенный в Урав- нении (5.2) - это MAC фиксированной длины для сообщений длиной n, и (GenH, H) является слабо стойкой к коллизиям. В таком случае HMAC является защи- щенным MAC (для сообщений произвольной длины). HMAC на практике . HMAC - это промышленный стандарт, и он ш ироко при- меняется на практике. Он высокоэффективен и прост для внедрения, а также под- креплен доказательством защиты, основанным на предположениях, которые счита- ются верными для практических хэш-функций. Своей важностью HMAC частично обязан своевременности своего появления. Перед представлением HMAC многие практикующие специалисты отказывались использовать CBC-MAC (с претензией, что он был «слишком медленный») и вместо него использовали конструкции, кото- рые были незащищены. HMAC предоставил стандартизированный, защищенный способ создания аутентификации сообщений, основанный на хэш-функциях. 5.4 Типичные атаки на хэш-функции На какую наилучшую защиту для хэш-функции H мы можем рассчитывать? Мы изучили вопрос при помощи демонстрации двух атак, которые являлись ти- пичными в том смысле, что они применялись к произвольным хэш-функциям. Существование этих атак подразумевает, что нижние границы выходной дли- ны H нуждались в достижении некоторого желательного уровня защиты, и, таким образом, имеют важные практические последствия. 5.4.1 Атака «дней рождения» для нахождения коллизий Пусть h : {0, 1}* → {0, 1}A будет хэш-функцией. (Здесь и в сотавшейся части главы мы опустим явное упоминание хэш-ключа s , так как это не совсем отно- сится к делу. Можно рассматривать s как такой, что был сгенерирован и зафик- сирован перед тем, как эти алгоритмы применялись.) Имеет место тривиальная атака нахождения коллизии, запущенная во время O(2A ): просто определите H на 2A + 1 различных входящих элемента; по принципу Дирихле два выходных элемента должны быть равны. Можем ли мы сделать еще лучше? Обобщая вышеописанный алгоритм, скажем, мы выберем q различных вход- ных элементов x1, . . . , xq , вычислим yi := H(xi) и проверим, равны ли какие-ли- бо из двух значений yi . Какова вероятность того, что данный алгоритм найдет коллизию? Как только что было сказано, если q > 2A , тогда коллизия случается с вероятностью 1. Какова вероятность коллизии, если q меньше? Это довольно тяжело анализировать, и поэтому мы лучше проанализируем идеализирован- ный случай, в котором H расценивается как случайная функция. 1 То есть для 181 каждой i мы предположим, что значение yi = H(xi) равномерно аспределено в {0, 1}A и независимо от любых предыдущих выходных значений {yj }j уменьшили нашу проблему до следующей: если мы выберем значения y1, . . . , yq ∈ {0, 1}A единообразно по случайному принципу, какова будет вероятность, что имеют место различные i, j при yi = yj ? Данная проблема была внимательно изучена и отнесена к так называемой про- блеме «дней рождения», подробно описанной в Дополнении A.4. По этой причине алгоритм нахождения коллизий, который мы описали, часто зовется атакой «дней рождений». Проблема «дней рождений» заключается в следующем: если в комнате находится q людей, какова вероятность того, что у двоих из них день рождения в один и тот же день (Предположим, что дни рождения равномерно распределены по периоду в 365 дней невисокосного года.) Это аналогично нашей проблеме: если yi представляет день рождения человека i, тогда мы имеем y1, . . . , yq ∈ {1, . . . , 365}, выбранные единообразно, и совпадающие дни рождения соответствуют различ- ным i, j при yi = yj (то есть совпадающие дни рождения соответствуют коллизиям). В Дополнении A.4 мы показываем, что для y1, . . . , yq, выбранных единоо- бразно в {1, . . . , N }, вероятность коллизиии приблизительно 1/2, если q = Θ(N 1/2). В случае с дням и рождения, если имеется всего 23 человека, вероятность того, что у двоих из них день рождение выпадет на одну и ту же дату больше, чем 1/2. В нашем условии это означает, что если хэш-функция имеет выходную длину A (и поэтому диапазон будет размером 2A), то принимая q = Θ(2A/2), вы- даст коллизию с вероятностью примерно 1/2. С точки зрения конкретной защиты вышеописанное означает, что для хэш- функции, чтобы противостоять атакам нахождения коллизии, которые действу- ют в течение времени T (где мы берем время, чтобы определить H в качестве нашей единицы времени), выходная длина хэш-функции должна быть как ми- нимум 2 log T бит (так как 2(2 log T )/2 = T). Принимая специфические параме- тры, это означает, что если мы хотим, что нахождение коллизий было настолько же трудным, насколько истощающим является поиск по 128-битным ключам, тогда нам необходимо, чтобы выходная длина хэш-функции была как минимум 256 бит. Мы подчеркиваем, что выходные данные такой длины - это единствен- ное необходимое условие, но не достаточное. Мы также отмечаем, что атаки «дней рождения» работают только для нахождения коллизий. Не существует типичных атак __________________________________________________________ 1Можно увидеть, что это (в значительной степени) наихудший случай, и коллизии случаются с более высокой вероятностью, если H отколняется от случайного, и {xi} выбираются единоо- бразно. 182 для стойкости второго прообраза или стойкости прообраза хэш-функций H, ко- торые требуют менее чем 2A оценок H (впрочем см. Раздел 5.4.3). Нахождение значимых коллизий . Атака «дней рождения», описанная выше, дает коллизию, которая не обязательно очень полезная. Но та же идея может быть использована, чтобы найти и «значимые» коллизии. Предположим, Али- са желает найти два сообщения x и xr так, чтобы H(x) = H(xr), и, более того, x должно быть письмом от ее работодателя, объясняющего, почему она была уволена с работы, тогда как xr должно быть преувеличенное рекомендательное письмо. (Это должно позволить Алисе подделать соответствующий тег на реко- мендательное письмо, если ее работодатель использует подход хэш-и-MAC для аутентификации сообщений.) Очевидно, что атака «дней рождения» потребует только, чтобы входные данные хэша x1, . . . , xq были различные; им не обяза- тельно быть случайными. Алиса может выполнить атаку по типу «дней рожде- ния» путем генерирования q = Θ(2A/2) сообщение первого типа и q сообщений второго типа и затем поиска коллизий между сообщениями двух типов. Неболь- шое изменение анализа из Дополнения A.4 показывает, что это дает коллизию между сообщениями различных типов с вероятностью приблизительно 1/2. Не- много размышлений, и очевидно, что легко написать одно и то же сообщение многими различными способами. Например, рассмотрите следующее: Это тяжело/трудно/затруднительно/невозможно представить/вооб- разить, что мы найдем/пригласим/наймем другого работника/сотруд- ника, который обладает теми же качествами/навыками/способностя- ми, что и Алиса. Она сделала прекрасную/превосходную работу. Любая комбинация слов, выделенных курсивом, возможна и выражает одну и ту же точку зрения. Таким образом, предложение может быть написано 4 • 2 • 3 • 2 • 3 • 2 = 288 различными способами. Это всего лишь одно предложение, и поэтому на самом деле легко сгенерировать сообщение, которое может быть переписано 264 различными способами, все, что нужно - это 64 слова с одим синонимом для каждого. Алиса может приготовить 2A/2 письма, объясняющие, почему она была уволена и еще 2A/2 реко мендательных письма; с высокой вероятностью между двумя типами писем будет найдена коллизия. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|