Введение в современную криптографию



Pdf көрінісі
бет133/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   129   130   131   132   133   134   135   136   ...   249
Криптография Катц

ТЕОРЕМА 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(вспомним, как мы предполагали, что все {xi} различны). Таким образом, мы 
уменьшили нашу проблему до следующей: если мы выберем значения 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 реко мендательных письма; с высокой 
вероятностью между двумя типами писем будет найдена коллизия.


Достарыңызбен бөлісу:
1   ...   129   130   131   132   133   134   135   136   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет