ФЭНДОМ


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

Поиск коллизий хеш-функций Править

При заданной функции f, целью атаки является поиск коллизии второго рода. Для этого просто вычисляется значение функции f, для случайно (или псевдослучайно) выбранных блоков входных данных, до тех пор пока не будут найдены два блока, имеющие один и тот же хеш. Таким образом, если f может иметь N различных равновероятных выходных значений, и N является достаточно большим, то из парадокса о днях рождениях следует, что, в среднем, после перебора 1.25 \cdot \sqrt H различных входных значений, будет найдена искомая коллизия.

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

Примеры Править

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

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

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


de:Geburtstagsangriff

en:Birthday attack es:Ataque de cumpleaños it:Attacco del compleanno pl:Atak urodzinowy sv:Födelsedagsattack

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Также на ФЭНДОМЕ

Случайная вики