Атака «дней рождения»

Атака «дней рождения» — используемое в криптоанализе название для метода взлома шифров или поиска коллизий хеш-функций на основе парадокса дней рождения.

Поиск коллизий хеш-функций

Для заданной хеш-функции <math>f</math> целью атаки является поиск коллизии второго рода. Для этого вычисляются значения <math>f</math> для случайно выбранных блоков входных данных до тех пор, пока не будут найдены два блока, имеющие один и тот же хеш. Таким образом, если <math>f</math> имеет <math>N</math> различных равновероятных выходных значений и <math>N</math> является достаточно большим, то из парадокса дней рождения следует, что в среднем после перебора <math>1{,}25 \cdot \sqrt{N}</math> различных входных значений будет найдена искомая коллизия.

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

В частности, требуется в два раза большая длина хеша, чтобы обеспечить вычислительную сложность, сравнимую со сложностью полного перебора. Другими словами, если с помощью полного перебора злоумышленник может вычислить <math>2^n</math> хэш-значений, то он начнёт находить хэш-коллизии для всех хэшей длиной менее <math>2n</math> бит.

Примеры

Предположим, что для атаки на 64-битный блочный шифр злоумышленнику нужно получить две пары открытого/шифрованного текста, которые отличаются только в наименее значимом бите. Интерпретация этой задачи в терминах парадокса дней рождения приводит к выводу, что пространство из всего лишь <math>2^{32}</math> известных открытых текстов с высокой вероятностью будет содержать необходимую пару.

В качестве другого примера рассмотрим цикл 64-битового Фейстелева шифра. Предположим, что в шифре использована случайная функция F (32 в 32 бита). Нападающий может захотеть узнать, как много ему необходимо получить открытых текстов для получения коллизии функции F. Согласно парадоксу дней рождения, для этого придётся перебрать около <math>2^{16}</math> открытых текстов.

Одним из следствий парадокса дней рождения является то, что для n-битового блочного шифра повторяемые появления блока шифротекста могут ожидаться с вероятностью около 0,63 при наличии лишь <math>2^{n/2}</math> случайных открытых текстов, зашифрованных на одном ключе (независимо от размера ключа). Для ECB режима при совпадении двух блоков шифротекста соответствующие открытые тексты обязаны также совпадать. Это означает, что в атаке с известным шифротекстом информация об открытых текстах может раскрываться из шифротекстовых блоков.

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Атака «дней рождения»

– Гей, Г'ишка, т'убку! – крикнул хриплый голос Васьки Денисова. – Ростов, вставай!
Ростов, протирая слипавшиеся глаза, поднял спутанную голову с жаркой подушки.
– А что поздно? – Поздно, 10 й час, – отвечал Наташин голос, и в соседней комнате послышалось шуршанье крахмаленных платьев, шопот и смех девичьих голосов, и в чуть растворенную дверь мелькнуло что то голубое, ленты, черные волоса и веселые лица. Это была Наташа с Соней и Петей, которые пришли наведаться, не встал ли.
– Николенька, вставай! – опять послышался голос Наташи у двери.
– Сейчас!
В это время Петя, в первой комнате, увидав и схватив сабли, и испытывая тот восторг, который испытывают мальчики, при виде воинственного старшего брата, и забыв, что сестрам неприлично видеть раздетых мужчин, отворил дверь.
– Это твоя сабля? – кричал он. Девочки отскочили. Денисов с испуганными глазами спрятал свои мохнатые ноги в одеяло, оглядываясь за помощью на товарища. Дверь пропустила Петю и опять затворилась. За дверью послышался смех.
– Николенька, выходи в халате, – проговорил голос Наташи.
– Это твоя сабля? – спросил Петя, – или это ваша? – с подобострастным уважением обратился он к усатому, черному Денисову.
Ростов поспешно обулся, надел халат и вышел. Наташа надела один сапог с шпорой и влезала в другой. Соня кружилась и только что хотела раздуть платье и присесть, когда он вышел. Обе были в одинаковых, новеньких, голубых платьях – свежие, румяные, веселые. Соня убежала, а Наташа, взяв брата под руку, повела его в диванную, и у них начался разговор. Они не успевали спрашивать друг друга и отвечать на вопросы о тысячах мелочей, которые могли интересовать только их одних. Наташа смеялась при всяком слове, которое он говорил и которое она говорила, не потому, чтобы было смешно то, что они говорили, но потому, что ей было весело и она не в силах была удерживать своей радости, выражавшейся смехом.
– Ах, как хорошо, отлично! – приговаривала она ко всему. Ростов почувствовал, как под влиянием жарких лучей любви, в первый раз через полтора года, на душе его и на лице распускалась та детская улыбка, которою он ни разу не улыбался с тех пор, как выехал из дома.
– Нет, послушай, – сказала она, – ты теперь совсем мужчина? Я ужасно рада, что ты мой брат. – Она тронула его усы. – Мне хочется знать, какие вы мужчины? Такие ли, как мы? Нет?
– Отчего Соня убежала? – спрашивал Ростов.
– Да. Это еще целая история! Как ты будешь говорить с Соней? Ты или вы?
– Как случится, – сказал Ростов.
– Говори ей вы, пожалуйста, я тебе после скажу.
– Да что же?
– Ну я теперь скажу. Ты знаешь, что Соня мой друг, такой друг, что я руку сожгу для нее. Вот посмотри. – Она засучила свой кисейный рукав и показала на своей длинной, худой и нежной ручке под плечом, гораздо выше локтя (в том месте, которое закрыто бывает и бальными платьями) красную метину.
– Это я сожгла, чтобы доказать ей любовь. Просто линейку разожгла на огне, да и прижала.
Сидя в своей прежней классной комнате, на диване с подушечками на ручках, и глядя в эти отчаянно оживленные глаза Наташи, Ростов опять вошел в тот свой семейный, детский мир, который не имел ни для кого никакого смысла, кроме как для него, но который доставлял ему одни из лучших наслаждений в жизни; и сожжение руки линейкой, для показания любви, показалось ему не бесполезно: он понимал и не удивлялся этому.