Атака на день рождения

Тип криптографической атаки

Атака дня рождения — это атака методом грубой силы , которая использует математику, лежащую в основе проблемы дня рождения в теории вероятностей . Эта атака может быть использована для злоупотребления связью между двумя или более сторонами. Атака зависит от более высокой вероятности столкновений, обнаруженных между случайными попытками атаки и фиксированной степенью перестановок ( pigeonholes ). Пусть будет числом возможных значений хэш-функции, при этом . С атакой дня рождения можно найти столкновение хэш-функции с вероятностью в , где — длина бита выходного хэш-кода, ^{[1] [2]} и при том же значении классического сопротивления прообразу с той же вероятностью. ^[2] Существует общий (хотя и спорный ^[3] ) результат , что квантовые компьютеры могут выполнять атаки дня рождения, тем самым нарушая сопротивление коллизии, в . ^[4] ${\textstyle H}$ ${\textstyle H=2^{l}}$ ${\textstyle 50\%}$ ${\textstyle {\sqrt {2^{l}}}=2^{l/2},}$ ${\textstyle l}$ ${\textstyle 2^{l-1}}$ ${\textstyle {\sqrt[{3}]{2^{l}}}=2^{l/3}}$

Хотя существуют некоторые уязвимости цифровой подписи, связанные с атакой по дням рождения, ее нельзя использовать для взлома схемы шифрования быстрее, чем при атаке методом полного перебора . ^{[5] : 36}

Понимание проблемы

Сравнение проблемы дня рождения (1) и атаки дня рождения (2):

В (1) столкновения обнаружены в пределах одного набора, в данном случае 3 из 276 пар 24 лунных астронавтов.

В (2) коллизии обнаружены между двумя наборами, в данном случае 1 из 256 пар только первых байтов хэшей SHA-256 по 16 вариантов каждого из доброкачественных и вредоносных контрактов.

В качестве примера рассмотрим сценарий, в котором учитель с классом из 30 учеников (n = 30) спрашивает день рождения каждого (для простоты проигнорируйте високосные годы ), чтобы определить, совпадают ли дни рождения любых двух учеников (что соответствует коллизии хэшей, описанной далее). Интуитивно этот шанс может показаться небольшим. Вопреки интуиции, вероятность того, что по крайней мере у одного ученика день рождения совпадает с днем ​​рождения любого другого ученика в любой день, составляет около 70% (для n = 30) по формуле . ^[6] ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$

Если учитель выбрал конкретный день (например, 16 сентября), то вероятность того, что хотя бы один ученик родился в этот день , составляет около 7,9%. ${\displaystyle 1-(364/365)^{30}}$

В атаке дня рождения злоумышленник подготавливает много различных вариантов доброкачественных и вредоносных контрактов, каждый из которых имеет цифровую подпись . Ищете пару доброкачественных и вредоносных контрактов с одинаковой подписью. В этом вымышленном примере предположим, что цифровая подпись строки — это первый байт ее хэша SHA-256 . Найденная пара обозначена зеленым цветом — обратите внимание, что поиск пары доброкачественных контрактов (синий) или пары вредоносных контрактов (красный) бесполезен. После того, как жертва принимает доброкачественный контракт, злоумышленник заменяет его вредоносным и утверждает, что жертва его подписала, что подтверждается цифровой подписью.

Терминология

В контексте атаки по дням рождения ключевые переменные связаны с известной проблемой шаров и корзин в теории вероятностей следующим образом.

н: Количество входов (или шаров)

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

ЧАС: Количество хэш-значений (или ячеек)

Переменная H представляет собой общее количество возможных выходов хэш-функции. Это количество уникальных «корзин», в которые могут попасть шарики. Общее количество выходов хэша часто выражается как , где l — длина бита выходного хэша. В аналогии с шариками и корзинами H представляет собой количество корзин, каждая из которых соответствует уникальному значению хэша. ${\displaystyle H=2^{l}}$

л: Длина бит выходного сигнала хэш-функции

Переменная l относится к длине бит выходных данных хэш-функции. Поскольку хэш-функция с длиной бит l может создавать уникальные выходные данные, число возможных значений хэш-функции (или ячеек) равно . ${\displaystyle 2^{l}}$ ${\displaystyle H=2^{l}}$

п: Вероятность столкновения

Переменная p представляет вероятность того, что произойдет столкновение, то есть вероятность того, что двум или более входам (шарам) будет назначен один и тот же выход (корзина). В атаке дня рождения p часто устанавливается равным 0,5 (50%), чтобы оценить, сколько входов необходимо, чтобы иметь 50%-ную вероятность столкновения.

Краткое изложение отношения к проблеме шаров и контейнеров

Атаку на день рождения можно смоделировать как вариант задачи о шарах и контейнерах . В этой задаче:

• Шарики представляют собой входные данные для хэш-функции.
• Ячейки представляют собой возможные выходные данные хэш-функции (значения хэш-функции).
• Столкновение происходит, когда два или более шаров попадают в одну и ту же корзину (т. е . два входа создают одинаковый хэш-выход).

Математика

При наличии функции цель атаки — найти два разных входа, таких что . Такая пара называется коллизией. Метод, используемый для поиска коллизии, заключается в простой оценке функции для разных входных значений, которые могут быть выбраны случайным образом или псевдослучайно, пока один и тот же результат не будет найден более одного раза. Из-за проблемы дней рождения этот метод может быть довольно эффективным. В частности, если функция выдает любой из разных выходов с равной вероятностью и достаточно велика, то мы ожидаем получить пару разных аргументов и с после оценки функции для примерно разных аргументов в среднем. ${\displaystyle f}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle f(x_{1})=f(x_{2})}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle f}$ ${\displaystyle f(x)}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle f(x_{1})=f(x_{2})}$ ${\displaystyle 1.25{\sqrt {H}}}$

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

${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}}$^[7]

где — количество выбранных значений (входов), а — количество возможных результатов (возможных выходов хэша). ${\displaystyle n}$ ${\displaystyle H}$

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

${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}$

и присваивая вероятность столкновения 0,5, мы получаем

${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}$

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

${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}$

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

Таблица показывает количество хешей n ( p ), необходимых для достижения заданной вероятности успеха, предполагая, что все хеши равновероятны. Для сравнения,10 ⁻¹⁸ в10 ⁻¹⁵ — это неисправимая частота ошибок битов типичного жесткого диска. ^[11] Теоретически хэши MD5 или UUID , составляющие примерно 128 бит, должны оставаться в этом диапазоне до тех пор, пока не будет обработано около 820 миллиардов документов, даже если возможные результаты будут намного больше.

Легко видеть, что если выходные данные функции распределены неравномерно, то коллизия может быть найдена еще быстрее. Понятие «баланса» хэш-функции количественно определяет устойчивость функции к атакам по дням рождения (использующим неравномерное распределение ключей). Однако определение баланса хэш-функции обычно требует вычисления всех возможных входных данных и, таким образом, неосуществимо для популярных хэш-функций, таких как семейства MD и SHA. ^[12] Подвыражение в уравнении для не вычисляется точно для small при прямом переводе на распространенные языки программирования из- за потери значимости . Когда доступно (как в C99 ), например, вместо этого следует использовать эквивалентное выражение . ^[13] Если этого не сделать, первый столбец приведенной выше таблицы вычисляется как ноль, а несколько элементов во втором столбце не имеют даже одной правильной значащей цифры. ${\displaystyle \ln {\frac {1}{1-p}}}$ ${\displaystyle n(p;H)}$ ${\displaystyle p}$log(1/(1-p))log1p-log1p(-p)

Простая аппроксимация

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

${\displaystyle p(n)\approx {n^{2} \over 2H}}$

что также можно записать как

${\displaystyle H\approx {n^{2} \over 2p(n)}}$.

или

${\displaystyle n\approx {\sqrt {2H\times p(n)}}}$.

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

Эта схема аппроксимации особенно проста в использовании при работе с экспонентами. Например, предположим, что вы создаете 32-битные хэши ( ) и хотите, чтобы вероятность коллизии была не более одного на миллион ( ), сколько документов у нас может быть максимум? ${\displaystyle H=2^{32}}$ ${\displaystyle p\approx 2^{-20}}$

${\displaystyle n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5}$

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

Доказательства

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

Атака на день рождения - Верхняя граница

Атаку дня рождения можно смоделировать как бросание n шаров (входов) в H ячеек (возможные выходы хэша). Вероятность столкновения ограничена следующим уравнением:

${\displaystyle p\leq {\frac {n^{2}}{2H}}}$

Это уравнение следует из границы объединения, которая дает верхнюю границу вероятности того, что произойдет хотя бы одно столкновение. Мы обозначаем событие, когда i-й шар сталкивается с одним из предыдущих шаров, как . Вероятность столкновения для i-го шара равна: ${\displaystyle C_{i}}$

${\displaystyle \Pr[C_{i}]\leq {\frac {i-1}{H}}}$

Таким образом, общая вероятность столкновения после бросания всех n шаров ограничена:

${\displaystyle p=\Pr[C_{1}\cup C_{2}\cup \cdots \cup C_{n}]\leq {\frac {0}{H}}+{\frac {1}{H}}+\cdots +{\frac {n-1}{H}}={\frac {n(n-1)}{2H}}}$

Это дает верхнюю границу вероятности коллизии в хеш-функции.

Атака на день рождения - нижняя граница

Нижнюю границу вероятности столкновения можно получить, предположив, что столкновения не произойдет после бросания i шаров, которые должны занимать разные ячейки. Вероятность отсутствия столкновения после бросания (i+1)-го шара равна:

${\displaystyle \Pr[D_{i+1}|D_{i}]={\frac {H-i}{H}}=1-{\frac {i}{H}}}$

Общая вероятность отсутствия столкновения после бросания всех n шаров равна произведению следующих членов:

${\displaystyle \Pr[D_{n}]=\prod _{i=1}^{n-1}\left(1-{\frac {i}{H}}\right)}$

Используя неравенство , мы можем аппроксимировать это как: ${\displaystyle 1-x\leq e^{-x}}$

${\displaystyle \Pr[D_{n}]\leq \prod _{i=1}^{n-1}e^{-{\frac {i}{H}}}=e^{-{\frac {n(n-1)}{2H}}}}$

Таким образом, вероятность хотя бы одного столкновения ограничена снизу:

${\displaystyle p\geq 1-e^{-{\frac {n(n-1)}{2H}}}}$

Это дает нижнюю границу вероятности столкновения.

Атака на день рождения и проблема с мячами и корзинами

Из приведенного выше рассуждения следует, что вероятность хотя бы одного столкновения ограничена:

${\displaystyle {\frac {n(n-1)}{4H}}\leq p\leq {\frac {n^{2}}{2H}}}$

Допустим , что почти наверняка столкновение произойдет, когда число попыток n будет равно: ${\displaystyle p\approx 1}$

${\displaystyle n=\Theta ({\sqrt {H}})=\Theta (2^{l/2})}$

Это иллюстрирует, как количество входов, необходимых для коллизии, растет в зависимости от длины бит выходного хэша.

Подверженность цифровой подписи

Цифровые подписи могут быть подвержены атаке дня рождения или, точнее, атаке коллизии выбранного префикса. Сообщение обычно подписывается сначала вычислением , где — криптографическая хэш-функция , а затем использованием некоторого секретного ключа для подписи . Предположим, Мэллори хочет обманом заставить Боба подписать мошеннический контракт. Мэллори готовит честный контракт и мошеннический . Затем она находит ряд позиций, в которых можно изменить , не меняя смысла, например, вставляя запятые, пустые строки, один пробел после предложения вместо двух, заменяя синонимы и т. д. Объединяя эти изменения, она может создать огромное количество вариаций, все из которых являются честными контрактами. ${\displaystyle m}$ ${\displaystyle f(m)}$ ${\displaystyle f}$ ${\displaystyle f(m)}$ ${\displaystyle m}$ ${\displaystyle m'}$ ${\displaystyle m}$ ${\displaystyle m}$

Аналогичным образом Мэллори также создает огромное количество вариаций мошеннического контракта . Затем она применяет хэш-функцию ко всем этим вариациям, пока не найдет версию честного контракта и версию мошеннического контракта, которые имеют одинаковое значение хэш-функции, . Она представляет честную версию Бобу для подписания. После того, как Боб подписал, Мэллори берет подпись и прикрепляет ее к мошенническому контракту. Эта подпись затем «доказывает», что Боб подписал мошеннический контракт. ${\displaystyle m'}$ ${\displaystyle f(m)=f(m')}$

Вероятности немного отличаются от исходной задачи о днях рождения, так как Мэллори ничего не выигрывает, находя два честных или два мошеннических контракта с одинаковым хешем. Стратегия Мэллори заключается в генерации пар из одного честного и одного мошеннического контракта. Для заданной хеш-функции есть количество возможных хешей, где — длина бита выходного хеша. Уравнения задачи о днях рождения здесь не совсем применимы. Для 50% вероятности коллизии Мэллори нужно было бы сгенерировать приблизительно хеши, что в два раза больше, чем требуется для простой коллизии в классической задаче о днях рождения. ${\displaystyle 2^{l}}$ ${\displaystyle l}$ ${\displaystyle 2^{(l/2)+1}}$

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

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

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

Обратная атака

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

Вот дополнительные подробности:

1. Первоначальное предложение по контракту: Боб предлагает Мэллори справедливый контракт, ожидая, что она его подпишет.

2. Измененные и мошеннические контракты Мэллори: вместо того, чтобы подписать контракт Боба напрямую, Мэллори создает две версии контракта.

• Один из них представляет собой слегка измененную версию контракта Боба, которая кажется Бобу безвредной или «безобидной».

• Другой — мошеннический контракт, выгодный Мэллори, но, что самое важное, имеющий ту же цифровую подпись, что и измененная версия.

3. Мэллори предоставляет измененный контракт: Мэллори подписывает измененную версию и передает ее Бобу. Подпись на этой версии та же самая, что и на мошенническом контракте.

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

5. Результаты:

• Если у Боба нет измененной версии, мошеннический контракт Мэллори неотличим от подписанного документа, что делает возможным идеальное мошенничество.
• Если Боб сохранит измененную версию, Мэллори все равно может заявить, что Боб подменил контракты, что создаст сомнения относительно того, кто несет ответственность за мошенничество.

Смотрите также

• Атака столкновением
• Атака «встреча посередине»
• Алгоритм BHT

Примечания

1. "Избегание коллизий, Криптографические хэш-функции" (PDF) . Основы криптографии, Кафедра компьютерных наук, Колледж Уэллсли .
2. Dang, QH (2012). Рекомендация для приложений, использующих одобренные алгоритмы хэширования (Отчет). Гейтерсберг, Мэриленд: Национальный институт стандартов и технологий.
3. Дэниел Дж. Бернстайн. «Анализ стоимости коллизий хэшей: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Cr.yp.to . Получено 29 октября 2017 г. .
4. Brassard, Gilles; HØyer, Peter; Tapp, Alain (20 апреля 1998 г.). "Quantum cryptanalysis of hash and claw-free functions". LATIN'98: Theoretical Informatics . Lecture Notes in Computer Science. Vol. 1380. Springer, Berlin, Heidelberg. pp. 163–169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID  118940551.
5. Р. Ширей (август 2007 г.). Глоссарий безопасности Интернета, версия 2. Сетевая рабочая группа. doi : 10.17487/RFC4949 . RFC 4949. Информационный.
6. "Birthday Problem". Brilliant.org . Brilliant_(веб-сайт) . Получено 28 июля 2023 г. .
7. Белларе, Михир; Рогауэй, Филлип (2005). «Проблема дня рождения». Введение в современную криптографию (PDF) . стр. 273–274 . Получено 31.03.2023 .
8. Флажоле, Филипп; Одлизко, Андрей М. (1990). «Статистика случайного картирования». В Кискатере — Жан-Жак; Вандевалле, Йоос (ред.). Достижения в криптологии — EUROCRYPT '89 . Конспекты лекций по информатике. Том. 434. Берлин, Гейдельберг: Шпрингер. стр. 329–354. дои : 10.1007/3-540-46885-4_34. ISBN 978-3-540-46885-1.
9. См . верхние и нижние границы .
10. Жак Патарен, Одри Монтрей (2005). «Повторный взгляд на схемы Бенеша и бабочки» ( PostScript , PDF ) . Версальский университет . Получено 15.03.2007 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
11. Грей, Джим; ван Инген, Кэтрин (25 января 2007 г.). «Эмпирические измерения частоты отказов дисков и частоты ошибок». arXiv : cs/0701166 .
12. "CiteSeerX". Архивировано из оригинала 2008-02-23 . Получено 2006-05-02 .
13. "Вычислите log(1+x) точно для малых значений x". Mathworks.com . Получено 29 октября 2017 г. .

Ссылки

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

Внешние ссылки

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