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

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

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

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

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

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

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

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

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

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

p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}

^[7]

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

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

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

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

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

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

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

Биты	Возможные результаты (H)	Желаемая вероятность случайного столкновения (2 сф) (п)
Биты	Возможные результаты (H)	10 ⁻¹⁸	10 ⁻¹⁵	10 ⁻¹²	10 ⁻⁹	10 ⁻⁶	0.1%	1%	25%	50%	75%
16	2 ¹⁶ (~6,5 х 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	6,100,000	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 ⁷⁷

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

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

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

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

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

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

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

.

или

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

.

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

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

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.

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

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

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

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

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

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

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

Обратная атака [ править ]

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

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

Примечания [ править ]

^ «Избежание коллизий, Криптографические хеш-функции» (PDF) . Основы криптографии, факультет компьютерных наук, колледж Уэлсли .
^ Перейти обратно: ^а ^б Данг, QH (2012). Рекомендации для приложений, использующих утвержденные алгоритмы хеширования (Отчет). Гейтерсбург, Мэриленд: Национальный институт стандартов и технологий.
^ Дэниел Дж. Бернштейн. «Анализ затрат на коллизии хэшей: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Cr.yp.to. Проверено 29 октября 2017 г.
^ Брассар, Жиль; Хойер, Питер; Тапп, Ален (20 апреля 1998 г.). «Квантовый криптоанализ хэш-функций и функций без когтей». LATIN'98: Теоретическая информатика . Конспекты лекций по информатике. Том. 1380. Шпрингер, Берлин, Гейдельберг. стр. 163–169. arXiv : Quant-ph/9705002 . дои : 10.1007/BFb0054319 . ISBN 978-3-540-64275-6 . S2CID 118940551 .
^ Р. Ширей (август 2007 г.). Глоссарий по интернет-безопасности, версия 2 . Сетевая рабочая группа. дои : 10.17487/RFC4949 . РФК 4949 . Информационный.
^ «Проблема дня рождения» . Бриллиант.орг . Бриллиант_(веб-сайт) . Проверено 28 июля 2023 г.
^ Белларе, Михир; Рогауэй, Филипп (2005). «Проблема дня рождения». Введение в современную криптографию (PDF) . стр. 273–274 . Проверено 31 марта 2023 г.
^ Флажоле, Филипп; Одлызко, Андрей М. (1990). «Статистика случайного картирования» . В Кискатере — Жан-Жак; Вандевалле, Йоос (ред.). Достижения в криптологии — EUROCRYPT '89 . Конспекты лекций по информатике. Том. 434. Берлин, Гейдельберг: Шпрингер. стр. 329–354. дои : 10.1007/3-540-46885-4_34 . ISBN 978-3-540-46885-1 .
^ См. верхнюю и нижнюю границы .
^ Жак Патарен, Одри Монтрей (2005). «Возвращение к схемам Бенеша и Баттерфляя» ( PostScript , PDF ) . Университет Версаля . Проверено 15 марта 2007 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Грей, Джим; ван Инген, Катарина (25 января 2007 г.). «Эмпирические измерения частоты отказов дисков и частоты ошибок». arXiv : cs/0701166 .
^ «CiteSeerX» . Архивировано из оригинала 23 февраля 2008 г. Проверено 2 мая 2006 г.
^ «Вычислить log(1+x) точно для малых значений x» . Mathworks.com . Проверено 29 октября 2017 г.

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

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

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

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

[1] «Избежание коллизий, Криптографические хеш-функции» (PDF) . Основы криптографии, факультет компьютерных наук, колледж Уэлсли .

[:0-2] Перейти обратно: ^а ^б Данг, QH (2012). Рекомендации для приложений, использующих утвержденные алгоритмы хеширования (Отчет). Гейтерсбург, Мэриленд: Национальный институт стандартов и технологий.

[3] Дэниел Дж. Бернштейн. «Анализ затрат на коллизии хэшей: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Cr.yp.to. Проверено 29 октября 2017 г.

[4] Брассар, Жиль; Хойер, Питер; Тапп, Ален (20 апреля 1998 г.). «Квантовый криптоанализ хэш-функций и функций без когтей». LATIN'98: Теоретическая информатика . Конспекты лекций по информатике. Том. 1380. Шпрингер, Берлин, Гейдельберг. стр. 163–169. arXiv : Quant-ph/9705002 . дои : 10.1007/BFb0054319 . ISBN 978-3-540-64275-6 . S2CID 118940551 .

[rfc4949-5] Р. Ширей (август 2007 г.). Глоссарий по интернет-безопасности, версия 2 . Сетевая рабочая группа. дои : 10.17487/RFC4949 . РФК 4949 . Информационный.

[6] «Проблема дня рождения» . Бриллиант.орг . Бриллиант_(веб-сайт) . Проверено 28 июля 2023 г.

[7] Белларе, Михир; Рогауэй, Филипп (2005). «Проблема дня рождения». Введение в современную криптографию (PDF) . стр. 273–274 . Проверено 31 марта 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 марта 2007 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[11] Грей, Джим; ван Инген, Катарина (25 января 2007 г.). «Эмпирические измерения частоты отказов дисков и частоты ошибок». arXiv : cs/0701166 .

[12] «CiteSeerX» . Архивировано из оригинала 23 февраля 2008 г. Проверено 2 мая 2006 г.

[13] «Вычислить log(1+x) точно для малых значений x» . Mathworks.com . Проверено 29 октября 2017 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]