Парадокс дня рождения (криптография)

Парадокс дня рождения (криптография)

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

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

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

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

Примеры

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

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

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



Wikimedia Foundation. 2010.

Нужно решить контрольную?

Полезное


Смотреть что такое "Парадокс дня рождения (криптография)" в других словарях:


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»