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

From CryptoWiki
Revision as of 14:34, 5 December 2013 by 13-02-KomarovAI (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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

Если же хэш-функция генерирует N - битное значение, то число случайных входных данных, для которых хэш-коды с большой вероятностью дадут коллизию, равно не 2 N, а только около 2 N/2. В светлых ячейках приведено количество входных данных, при котором коллизия будет с заданной вероятностью (проводя аналогию с парадоксом, кол-во различных выходных цепочек равно 365):

N Количество
различных
выходных
цепочек
(2N)
Вероятность хотя бы одной коллизии (p)
10−18 10−15 10−12 10−9 10−6 0,1 % 1 % 25 % 50 % 75 %
32 4,3 × 109 2 2 2 2.9 93 2.9 × 10³ 9.3 × 10³ 5.0 × 104 7.7 × 104 1.1 × 105
64 1,8 × 1019 6.1 1.9 × 10² 6.1 × 10³ 1.9 × 105 6.1 × 106 1.9 × 108 6.1 × 108 3.3 × 109 5.1 × 109 7.2 × 109
128 3,4 × 1038 2.6 × 1010 8.2 × 1011 2.6 × 1013 8.2 × 1014 2.6 × 1016 8.3 × 1017 2.6 × 1018 1.4 × 1019 2.2 × 1019 3.1 × 1019
256 1,2 × 1077 4.8 × 1029 1.5 × 1031 4.8 × 1032 1.5 × 1034 4.8 × 1035 1.5 × 1037 4.8 × 1037 2.6 × 1038 4.0 × 1038 5.7 × 1038
384 3,9 × 10115 8.9 × 1048 2.8 × 1050 8.9 × 1051 2.8 × 1053 8.9 × 1054 2.8 × 1056 8.9 × 1056 4.8 × 1057 7.4 × 1057 1.0 × 1058
512 1,3 × 10154 1.6 × 1068 5.2 × 1069 1.6 × 1071 5.2 × 1072 1.6 × 1074 5.2 × 1075 1.6 × 1076 8.8 × 1076 1.4 × 1077 1.9 × 1077

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

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