Интернет магазин китайских планшетных компьютеров

Компьютеры - Атака дней рождения

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

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

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

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

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