 | Эта статья требует дополнительных ссылок для проверки . ( декабрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В криптографии , сопротивление столкновений является свойством криптографических хэш - функции : хэш - функция H является коллизия устойчивостью , если трудно найти два входа , что хэш - тот же результат; то есть два входа a и b, где a ≠ b, но H ( a ) = H ( b ). [1] : 136 Принцип « ящика» означает, что любая хеш-функция с большим количеством входов, чем выходов, обязательно будет иметь такие коллизии; [1] : 136 чем сложнее их найти, тем более криптографически безопасна хеш-функция.
« Парадокс дня рождения » устанавливает верхнюю границу сопротивления столкновениям: если хеш-функция производит N битов вывода, злоумышленник, который вычисляет только 2 N / 2 (или ) хэш-операций на случайном входе, скорее всего, найдет два совпадающих выхода. Если есть более простой метод, чем эта атака полным перебором , это обычно считается недостатком хеш-функции. [2]
Криптографические хеш-функции обычно предназначены для защиты от коллизий. Однако многие хеш-функции, которые когда-то считались устойчивыми к столкновениям, позже были сломаны. В частности, MD5 и SHA-1 опубликовали методы, более эффективные, чем грубая сила для обнаружения коллизий. [3] [4] Однако у некоторых хэш-функций есть доказательство того, что обнаружение коллизий по крайней мере так же сложно, как и некоторые сложные математические задачи (например, целочисленная факторизация или дискретный логарифм ). Эти функции называются доказуемо безопасными . [2]
Определение [ править ]
Семейство функций { h k : {0, 1} m ( k ) → {0, 1} l ( k ) }, порожденное некоторым алгоритмом G, является семейством устойчивых к коллизиям хэш-функций, если | м ( к ) | > | л ( к ) | для любого k , т. е. h k сжимает входную строку, и каждое h k может быть вычислено за полиномиальное время, заданное k , но для любого вероятностного полиномиального алгоритма A мы имеем
- Pr [ k ← G (1 n ), ( x 1 , x 2 ) ← A ( k , 1 n ) st x 1 ≠ x 2, но h k ( x 1 ) = h k ( x 2 )] <negl ( n ), ( стекло )
где пренебрежение (·) обозначает некоторую незначительную функцию, а n - параметр безопасности. [5]
Обоснование [ править ]
Устойчивость к столкновениям желательна по нескольким причинам.
- В некоторых системах цифровой подписи сторона подтверждает документ, публикуя подпись с открытым ключом на хеш-коде документа. Если возможно создать два документа с одним и тем же хешем, злоумышленник может заставить одну сторону подтвердить один, а затем заявить, что сторона подтвердила другой.
- В некоторых системах с распределенным контентом стороны сравнивают криптографические хэши файлов, чтобы убедиться, что у них одна и та же версия. Злоумышленник, который может создать два файла с одним и тем же хешем, может обманом заставить пользователей поверить, что у них одна и та же версия файла, хотя на самом деле это не так.
См. Также [ править ]
- Атака столкновения
- Атака на прообраз
- Конкурс хеш-функций NIST
- Доказуемо безопасная криптографическая хеш-функция
- Обнаружение и исправление ошибок
Ссылки [ править ]
- ^ a b Голдвассер, С. и Белларе, М. «Лекционные заметки по криптографии» . Летний курс по криптографии, Массачусетский технологический институт, 1996-2001 гг.
- ^ a b Pass, R. «Лекция 21: Устойчивые к коллизиям хеш-функции и общая схема цифровой подписи» . Курс криптографии, Корнельский университет, 2009 г.
- ^ Сяоюнь Ван; Хунбо Ю. «Как взломать MD5 и другие хеш-функции» (PDF) . Архивировано из оригинального (PDF) 21 мая 2009 года . Проверено 21 декабря 2009 . CS1 maint: discouraged parameter (link)
- ^ Сяоюнь Ван; Ицюнь Лиза Инь ; Хонгобо Ю. «Поиск коллизий в полном SHA-1» (PDF) . Cite journal requires
|journal=(help) - ^ Додис, Евгений. «Лекция 12« Введение в криптографию » (PDF) . Проверено 3 января +2016 . CS1 maint: discouraged parameter (link), по умолчанию 1.
