A Атака по случаю дня рождения - это тип криптографической атаки, который использует математику, лежащую в основе проблемы дня рождения в теории вероятностей. Эта атака может использоваться для злоупотребления связью между двумя или более сторонами. Атака зависит от более высокой вероятности коллизий, обнаруженных между случайными попытками атаки и фиксированной степенью перестановок (пометок ). При атаке по случаю дня рождения можно найти конфликт хэш-функции в , где является классической ценностью сопротивления прообразу. Существует общий (хотя и оспариваемый) результат, что квантовые компьютеры могут выполнять атаки в день рождения, тем самым нарушая сопротивление столкновениям в .
В качестве примера рассмотрим сценарий, в котором учитель с классом из 30 студентов (n = 30) просит всех день рождения (для простоты игнорируйте високосные годы ), чтобы определить, совпадают ли дни рождения любых двух студентов (что соответствует хэш-конфликту, как описано далее). Интуитивно этот шанс может показаться небольшим. Если учитель выбрал определенный день (скажем, 16 сентября), то вероятность того, что хотя бы один ученик родился в этот конкретный день, составляет , около 7,9%. Однако, как это ни парадоксально, вероятность того, что хотя бы один ученик имеет такой же день рождения, как и любой другой ученик, в любой день составляет около 70% (для n = 30), из формулы .
Дана функция , цель атаки - найти два разных входа таких что . Такая пара называется коллизией. Метод, используемый для поиска коллизии, заключается в простом вычислении функции для различных входных значений, которые могут выбираться случайным образом или псевдослучайно, пока один и тот же результат не будет найден более одного раза. Из-за проблемы с днем рождения этот способ может быть достаточно эффективным. В частности, если функция возвращает любое из разные выходные данные с равной вероятностью и достаточно велик, тогда мы ожидаем получить пару разных аргументов и с после оценки функции в среднем для различных аргументов.
Мы рассматриваем следующий эксперимент. Из набора значений H мы выбираем n значений равномерно и случайным образом, что позволяет повторять их. Пусть p (n; H) - вероятность того, что во время этого эксперимента хотя бы одно значение будет выбрано более одного раза. Эта вероятность может быть приблизительно равна
Пусть n (p; H) - наименьшее количество значений, которые мы должны выбрать, чтобы вероятность обнаружения столкновения была не менее p. Обращая это выражение выше, мы находим следующее приближение
и присвоив вероятность столкновения 0,5, мы приходим к
Пусть Q (H) будет ожидаемым количеством значений, которые мы должны выбрать перед обнаружением первого столкновения. Это число может быть приблизительно равно
В качестве Например, если используется 64-битный хэш, имеется примерно 1,8 × 10 различных выходных данных. Если все они равновероятны (лучший случай), то потребуется «всего» приблизительно 5 миллиардов попыток (5,38 × 10), чтобы сгенерировать столкновение с использованием грубой силы. Это значение называется граница дня рождения, и для n-битных кодов оно может быть вычислено как 2. Другие примеры:
Биты | Возможные выходы (H) | Желаемая вероятность случайного столкновения. (2 sf) (p) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
10 | 10 | 10 | 10 | 10 | 0,1% | 1% | 25% | 50% | 75% | ||
16 | 2 (~ 6,5 x 10) | <2 | <2 | <2 | <2 | <2 | 11 | 36 | 190 | 300 | 430 |
32 | 2 (~ 4,3 × 10) | <2 | <2 | <2 | 3 | 93 | 2900 | 9300 | 50,000 | 77,000 | 110,000 |
64 | 2 (~ 1,8 × 10) | 6 | 190 | 6100 | 190,000 | 6100000 | 1,9 × 10 | 6,1 × 10 | 3,3 × 10 | 5,1 × 10 | 7,2 × 10 |
128 | 2 (~ 3,4 × 10) | 2,6 × 10 | 8,2 × 10 | 2,6 × 10 | 8,2 × 10 | 2,6 × 10 | 8,3 × 10 | 2,6 × 10 | 1,4 × 10 | 2,2 × 10 | 3,1 × 10 |
256 | 2 (~ 1,2 × 10) | 4,8 × 10 | 1,5 × 10 | 4,8 × 10 | 1,5 × 10 | 4,8 × 10 | 1,5 × 10 | 4,8 × 10 | 2,6 × 10 | 4,0 × 10 | 5,7 × 10 |
384 | 2 (~ 3,9 × 10) | 8,9 × 10 | 2,8 × 10 | 8,9 × 10 | 2,8 × 10 | 8,9 × 10 | 2,8 × 10 | 8,9 × 10 | 4,8 × 10 | 7,4 × 10 | 1,0 × 10 |
512 | 2 (~ 1,3 × 10) | 1,6 × 10 | 5,2 × 10 | 1,6 × 10 | 5,2 × 10 | 1,6 × 10 | 5,2 × 10 | 1,6 × 10 | 8,8 × 10 | 1,4 × 10 | 1,9 × 10 |
Это просто чтобы увидеть, что если выходные данные функции распределены неравномерно, то коллизия может быть обнаружена еще быстрее. Понятие «баланс» хэш-функции количественно определяет устойчивость функции к атакам по случаю дня рождения (используя неравномерное распределение ключей). Однако для определения баланса хэш-функции обычно требуется вычислить все возможные входные данные, и поэтому это невозможно для популярных хэш-функции, такие как семейства MD и SHA. Подвыражение в уравнении для не вычисляется точно для малых при прямом переводе на общие языки программирования как log (1 / (1-p))
из-за потери значимости. Например, когда log1p
доступен (как в C99 ), вместо него следует использовать эквивалентное выражение -log1p (-p)
. Если этого не сделать, первый столбец приведенной выше таблицы считается равным нулю, а несколько элементов во втором столбце не имеют ни одной правильной значащей цифры.
Хорошее эмпирическое правило, которое можно использовать для мысленных вычислений, - это соотношение
, которое также можно записать как
или
Это хорошо работает для вероятностей, меньших или равных 0,5.
Эта схема аппроксимации особенно удобна при работе с показателями степени. Например, предположим, что вы строите 32-битные хэши () и хотите, чтобы вероятность столкновения была не более одной миллион (), сколько документов у нас может быть самое большее?
, что близко к правильному ответу 93.
Цифровые подписи могут быть уязвимы для атаки дня рождения. Сообщение обычно подписывается первым вычислением , где - это криптографическая хеш-функция, а затем использование секретного ключа для подписи . Предположим, Мэллори хочет обманом заставить Боба подписать мошеннический контракт. Мэллори готовит честный контракт и мошеннический . Затем она находит несколько позиций, в которых может быть изменено без изменения значения, например, вставка запятых, пустых строк, одного или двух пробелов после предложения, замены синонимов, и т. д. Объединив эти изменения, она может создать огромное количество вариаций для , которые все являются честными контрактами.
Подобным образом Мэллори также создает огромное количество вариантов мошеннического контракта . Затем она применяет хеш-функцию ко всем этим вариантам, пока не найдет версию честного контракта и версию мошеннического контракта, которые имеют одинаковое хеш-значение, . Она представляет Бобу на подпись справедливую версию. После того, как Боб подписал, Мэллори берет подпись и прикрепляет ее к мошенническому контракту. Эта подпись затем «доказывает», что Боб подписал мошеннический контракт.
Вероятности немного отличаются от исходной задачи о дне рождения, поскольку Мэллори ничего не получает, обнаруживая два честных или два мошеннических контракта с одинаковым хешем. Стратегия Мэллори заключается в создании пары из одного честного и одного мошеннического контракта. Применяются уравнения задачи дня рождения, где - количество пар. Фактически генерируемое Мэллори количество хешей составляет .
Чтобы избежать этой атаки, длина вывода хеш-функции, используемой для схемы подписи, может быть выбрана достаточно большой, чтобы атака дня рождения стала вычислительной. недопустимо, т.е. примерно в два раза больше битов, чем необходимо для предотвращения обычной атаки грубой силой.
Помимо использования большей битовой длины, подписывающее лицо (Боб) может защитить себя, внося в документ некоторые случайные, безобидные изменения перед его подписанием и сохраняя копию подписанного им контракта в своем собственном владении, чтобы он мог хотя бы продемонстрировать в суде, что его подпись соответствует этому контракту, а не только фальшивой.
Ро-алгоритм Полларда для логарифмов является примером алгоритма, использующего атаку по случаю дня рождения для вычисления дискретных логарифмов.