Устойчивость к столкновениям

В криптографии устойчива к коллизиям , устойчивость к коллизиям является свойством криптографических хеш-функций : хеш-функция H если трудно найти два входа, которые хешируют один и тот же выход; то есть два входа a и b , где a ≠ b, но H ( a ) = H ( b ). ^[1]^: 136 Принцип «ячейки» означает, что любая хэш-функция с большим количеством входов, чем выходов, обязательно будет иметь такие коллизии; ^[1]^: 136 чем сложнее их найти, тем более криптографически безопасна хэш-функция.

« Парадокс дня рождения » устанавливает верхнюю границу сопротивления коллизиям: если хеш-функция выдает N бит на выходе, злоумышленник, вычисливший только 2 ^{Н /2} (или $\scriptstyle {\sqrt {2^{N}}}$ ) хеш-операции со случайными входными данными, скорее всего, найдут два совпадающих результата. Если есть более простой способ сделать это, чем атака методом перебора , это обычно считается недостатком хэш-функции. ^[2]

Криптографические хэш-функции обычно разрабатываются с учетом устойчивости к коллизиям. Однако многие хеш-функции, которые когда-то считались устойчивыми к коллизиям, позже были сломаны. В частности, MD5 и SHA-1 опубликовали методы, более эффективные, чем грубая сила, для обнаружения коллизий. ^[3]^[4] Однако у некоторых хеш-функций есть доказательство того, что обнаружение коллизий по крайней мере так же сложно, как и какая-либо сложная математическая задача (например, факторизация целых чисел или дискретный логарифм ). Эти функции называются доказуемо безопасными . ^[2]

Определение

Семейство функций { h _k : {0, 1} ^{м ( к )} → {0, 1} ^{л ( к )}}, сгенерированная некоторым алгоритмом G, является семейством устойчивых к коллизиям хеш-функций, если | м ( к )| > | л ( к )| для любого k , т. е. h _k сжимает входную строку, и каждый h _k может быть вычислен за полиномиальное время при заданном k , но для любого вероятностного полиномиального алгоритма A мы имеем

Пр [ k ← G (1 ^н), ( Икс ₁ , Икс ₂ ) ← А ( k , 1 ^н) st Икс ₁ ≠ Икс _2, но час _k ( Икс ₁ ) = час _k ( Икс ₂ )] < negl( n ),

где negl(·) обозначает некоторую незначительную функцию, а n — параметр безопасности. ^[5]

Слабое и сильное сопротивление столкновению

Существует два разных типа устойчивости к столкновению.

Хэш-функция имеет слабую устойчивость к коллизиям, когда при заданной хеш-функции H и x невозможно найти другой x', такой, что H(x)=H(x'). Другими словами, если задан x, невозможно найти другой x', такой, что эта хэш-функция создала бы коллизию.

Хэш-функция имеет высокую устойчивость к коллизиям, когда для данной хеш-функции H невозможно найти произвольные x и x', где H(x)=H(x'). Другими словами, невозможно найти два x, где хеш-функция создала бы коллизию.

Обоснование

Устойчивость к столкновениям желательна по нескольким причинам.

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

См. также

Ссылки

^ Jump up to: ^а ^б Гольдвассер, С. и Белларе, М. «Конспекты лекций по криптографии». Архивировано 21 апреля 2012 г. в Wayback Machine . Летний курс по криптографии, Массачусетский технологический институт, 1996–2001 гг.
^ Jump up to: ^а ^б Пасс, Р. «Лекция 21: Устойчивые к коллизиям хэш-функции и общая схема цифровой подписи» . Курс криптографии, Корнелльский университет, 2009 г.
^ Сяоюнь Ван; Хунбо Ю. «Как взломать MD5 и другие хэш-функции» (PDF) . Архивировано из оригинала (PDF) 21 мая 2009 г. Проверено 21 декабря 2009 г.
^ Сяоюнь Ван; Ицюнь Лиза Инь ; Хонгобо Ю. Поиск коллизий в полном SHA-1 (PDF) . doi : 10.1007/11535218_2 .
^ Додис, Евгений. «Лекция 12 «Введение в криптографию»» (PDF) . Проверено 3 января 2016 г. , защита 1.

[GoldwasserBellare-1] Jump up to: ^а ^б Гольдвассер, С. и Белларе, М. «Конспекты лекций по криптографии». Архивировано 21 апреля 2012 г. в Wayback Machine . Летний курс по криптографии, Массачусетский технологический институт, 1996–2001 гг.

[Lecture21Collision-2] Jump up to: ^а ^б Пасс, Р. «Лекция 21: Устойчивые к коллизиям хэш-функции и общая схема цифровой подписи» . Курс криптографии, Корнелльский университет, 2009 г.

[3] Сяоюнь Ван; Хунбо Ю. «Как взломать MD5 и другие хэш-функции» (PDF) . Архивировано из оригинала (PDF) 21 мая 2009 г. Проверено 21 декабря 2009 г.

[4] Сяоюнь Ван; Ицюнь Лиза Инь ; Хонгобо Ю. Поиск коллизий в полном SHA-1 (PDF) . doi : 10.1007/11535218_2 .

[5] Додис, Евгений. «Лекция 12 «Введение в криптографию»» (PDF) . Проверено 3 января 2016 г. , защита 1.

[1]

[2]

[3]

[4]

[5]