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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

Примеры[править | править вики-текст]

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

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

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