Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Нападение дня рождения является типом криптографической атаки , которая эксплуатирует математику за проблемами рождения в теории вероятностей . Эта атака может использоваться для злоупотребления связью между двумя или более сторонами. Атака зависит от более высокой вероятности коллизий, обнаруженных между случайными попытками атаки и фиксированной степенью перестановок ( ячеек ). С нападением на день рождения, можно найти соударение функции хэш - ин , с будучи классическим сопротивление прообразом безопасности. Есть генерал (правда, спорный [1]) приводят к тому, что квантовые компьютеры могут выполнять атаки по случаю дня рождения, тем самым нарушая сопротивление столкновениям в . [2]

Понимание проблемы [ править ]

В качестве примера рассмотрим сценарий, в котором учитель с классом из 30 учеников (n = 30) спрашивает у всех день рождения (для простоты игнорируйте високосные годы ), чтобы определить, есть ли у двух учеников одинаковый день рождения (что соответствует хэш-коллизии). как описано далее). Интуитивно этот шанс может показаться небольшим. Как это ни парадоксально, вероятность того, что хотя бы один ученик имеет такой же день рождения, как и любой другой ученик, в любой день составляет около 70% (для n = 30), согласно формуле . [3]

Если учитель выбрал определенный день (скажем, 16 сентября), то вероятность того, что хотя бы один ученик родился в этот конкретный день, составляет около 7,9%.

Математика [ править ]

Для заданной функции цель атаки - найти два разных входа, такие что . Такая пара называется коллизией . Метод, используемый для обнаружения коллизии, заключается в простом вычислении функции для различных входных значений, которые могут быть выбраны случайным образом или псевдослучайно до тех пор, пока один и тот же результат не будет найден более одного раза. Из-за проблемы с днем ​​рождения этот способ может быть достаточно эффективным. В частности, если функция дает любой из разных выходных данных с равной вероятностью и является достаточно большой, то мы ожидаем получить пару разных аргументов и с после оценки функции примерно для разных аргументов в среднем.

Рассмотрим следующий эксперимент. Из набора значений H мы выбираем n значений равномерно и случайным образом, тем самым позволяя повторения. Пусть p ( nH ) - вероятность того, что во время этого эксперимента хотя бы одно значение будет выбрано более одного раза. Эта вероятность может быть аппроксимирована как

[4]

Пусть n ( pH ) будет наименьшим количеством значений, которые мы должны выбрать, так чтобы вероятность обнаружения столкновения была не менее  p . Обращая это выражение выше, мы находим следующее приближение

и присвоив вероятность столкновения 0,5, мы приходим к

Пусть Q ( H ) будет ожидаемым количеством значений, которые мы должны выбрать перед обнаружением первого столкновения. Это число может быть приблизительно равно

Например, если используется 64-битный хэш, имеется примерно 1,8 × 10 19 различных выходов. Если все они равновероятны (лучший случай), то потребуется «всего» приблизительно 5 миллиардов попыток (5,38 × 10 9 ), чтобы сгенерировать коллизию с использованием грубой силы. Это значение называется границей дня рождения [5], и для n- битных кодов оно может быть вычислено как 2 n / 2 . [6] Другие примеры:

В таблице показано количество хешей n ( p ), необходимых для достижения заданной вероятности успеха, при условии, что все хеши равновероятны. Для сравнения, от 10 -18 до 10 -15 - это уровень неисправимых битовых ошибок типичного жесткого диска. [7] Теоретически, хэши MD5 или UUID , составляющие 128 бит, должны оставаться в этом диапазоне примерно до 820 миллиардов документов, даже если их возможных выходов намного больше.

Легко видеть, что если выходы функции распределены неравномерно, то коллизия может быть обнаружена еще быстрее. Понятие «баланса» хэш-функции количественно определяет устойчивость функции к атакам по случаю дня рождения (используя неравномерное распределение ключей). Однако определение баланса хэш-функции обычно требует вычисления всех возможных входных данных и, таким образом, неосуществимо для популярных хэш-функции, такие как семейства MD и SHA. [8] Подвыражение в уравнении для не вычисляется точно для small при прямом переводе на общепринятые языки программирования из-за потери значимости . Когда доступно (как в C99log(1/(1-p))log1p), например, -log1p(-p)следует использовать эквивалентное выражение . [9] Если этого не сделать, первый столбец приведенной выше таблицы считается равным нулю, а несколько элементов во втором столбце не имеют даже одной правильной значащей цифры.

Простое приближение [ править ]

Хорошее практическое правило, которое можно использовать для мысленных вычислений, - это соотношение

который также можно записать как

.

или же

.

Это хорошо работает для вероятностей, меньших или равных 0,5.

Эта схема аппроксимации особенно удобна при работе с показателями степени. Например, предположим, что вы создаете 32-битные хэши ( ) и хотите, чтобы вероятность коллизии составляла не более одного из миллиона ( ), сколько документов у нас может быть не больше?

что близко к правильному ответу 93.

Восприимчивость к цифровой подписи [ править ]

Цифровые подписи могут быть уязвимы для атак по случаю дня рождения. Сообщение обычно подписывается сначала вычислением , где используется криптографическая хеш-функция , а затем использованием некоторого секретного ключа для подписи . Предположим, Мэллори хочет обманом заставить Боба подписать мошеннический контракт. Мэллори готовит честный и мошеннический контракт . Затем она находит ряд позиций, которые можно изменить без изменения значения, например, вставка запятых, пустых строк, одного или двух пробелов после предложения, замены синонимов и т. Д. Комбинируя эти изменения, она может создать огромное количество вариаций. по которым заключаются все честные контракты.

Точно так же Мэллори создает огромное количество вариантов мошеннического контракта . Затем она применяет хэш - функцию для всех этих изменений , пока она не найдет версию договора справедливой и версию мошеннической договора , которые имеют одинаковое значение хеш - функции, . Она представляет Бобу на подпись справедливую версию. После того, как Боб подписал, Мэллори берет подпись и прикрепляет ее к мошенническому контракту. Эта подпись затем «доказывает», что Боб подписал мошеннический контракт.

Вероятности немного отличаются от исходной задачи о дне рождения, поскольку Мэллори ничего не получает, находя два честных или два мошеннических контракта с одним и тем же хешем. Стратегия Мэллори состоит в том, чтобы создать пары из одного честного и одного мошеннического контракта. Применяются уравнения задачи дня рождения, где - количество пар. Фактическое количество хешей, генерируемых Мэллори, равно .

Чтобы избежать этой атаки, длина вывода хэш-функции, используемой для схемы подписи, может быть выбрана достаточно большой, чтобы атака дня рождения стала вычислительно невыполнимой, то есть примерно вдвое больше битов, чем необходимо для предотвращения обычной атаки грубой силы .

Помимо использования большей длины в битах, подписывающий (Боб) может защитить себя, внося в документ некоторые случайные безобидные изменения перед его подписанием и сохраняя копию подписанного им контракта в своем собственном владении, чтобы он мог, по крайней мере, продемонстрировать в суде, что его подпись соответствует этому контракту, а не только фальшивому.

Алгоритм Ро Полларда для логарифмов является примером алгоритма, использующего атаку дня рождения для вычисления дискретных логарифмов .

См. Также [ править ]

  • Атака столкновения
  • Атака по центру

Заметки [ править ]

  1. ^ Дэниел Дж. Бернштейн. «Анализ затрат на хэш-коллизии: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Cr.yp.to . Проверено 29 октября 2017 года .
  2. ^ Брассар, Жиль; Хёйер, Питер; Тэпп, Ален (20 апреля 1998 г.). ЛАТИНЬ'98: Теоретическая информатика . Конспект лекций по информатике. 1380 . Шпрингер, Берлин, Гейдельберг. С. 163–169. arXiv : квант-ph / 9705002 . DOI : 10.1007 / BFb0054319 . ISBN 978-3-540-64275-6. S2CID  118940551 .
  3. ^ "Математический форум: Спросите доктора математики FAQ: Проблема дня рождения" . Mathforum.org . Проверено 29 октября 2017 года .
  4. ^ Гупта, Ганеш (2015). "Что такое атака по случаю дня рождения ??" . DOI : 10.13140 / 2.1.4915.7443 . Cite journal requires |journal= (help)
  5. ^ См. Верхнюю и нижнюю границы .
  6. ^ Жак Патарен, Одри Монтрей (2005). «Переосмысление схем Бенеша и бабочки» ( PostScript , PDF ) . Университет Версаля . Проверено 15 марта 2007 . Cite journal requires |journal= (help)
  7. ^ Грей, Джим; ван Инген, Катарина (25 января 2007 г.). «Эмпирические измерения частоты отказов дисков и ошибок». arXiv : cs / 0701166 .
  8. ^ "CiteSeerX" . Архивировано из оригинала на 2008-02-23 . Проверено 2 мая 2006 .
  9. ^ «Вычислить журнал (1 + x) точно для малых значений x» . Mathworks.com . Проверено 29 октября 2017 года .

Ссылки [ править ]

  • Михир Белларе , Тадаёши Коно: Баланс хеш-функции и его влияние на атаки по случаю дня рождения. EUROCRYPT 2004: стр. 401–418
  • Прикладная криптография, 2-е изд. по Брюс Шнайер

Внешние ссылки [ править ]

  • «Что такое цифровая подпись и что такое аутентификация?» из часто задаваемых вопросов о криптографии RSA Security .
  • "Атака на день рождения" X5 Networks Crypto: вопросы и ответы