Сопротивление столкновению - Collision resistance

В криптография, сопротивление столкновению является собственностью криптографические хеш-функции: хеш-функция ЧАС устойчива к коллизиям, если трудно найти два входа, которые хешируют один и тот же выход; то есть два входа а и б куда а ≠ б но ЧАС(а) = ЧАС(б).[1]:136 В принцип голубятни означает, что любая хеш-функция с большим количеством входов, чем выходов, обязательно будет иметь такие коллизии;[1]:136 чем сложнее их найти, тем более криптографически безопасна хеш-функция.

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

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

Определение

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

Pr [k ← грамм(1п), (Икс1, Икс2) ← А(k, 1п) s.t. Икс1 ≠ Икс2 но часk(Икс1) = часk(Икс2)] <пренебрежение (п), (стекло)

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

Обоснование

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

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

Смотрите также

Рекомендации

  1. ^ а б Гольдвассер, С. и Белларе, М. «Конспект лекций по криптографии». Летний курс по криптографии, Массачусетский технологический институт, 1996-2001 гг.
  2. ^ а б Пасс, Р. «Лекция 21: Устойчивые к коллизиям хеш-функции и общая схема цифровой подписи». Курс криптографии, Корнельский университет, 2009 г.
  3. ^ Сяоюнь Ван; Хунбо Ю. «Как взломать MD5 и другие хеш-функции» (PDF). Архивировано из оригинал (PDF) на 2009-05-21. Получено 2009-12-21.
  4. ^ Сяоюнь Ван; Ицюнь Лиза Инь; Хонгобо Ю. «Обнаружение коллизий в полном SHA-1» (PDF). Цитировать журнал требует | журнал = (помощь)
  5. ^ Додис, Евгений. «Лекция 12« Введение в криптографию » (PDF). Получено 3 января 2016., по умолчанию 1.