В криптографии устойчивость к коллизиям является свойством криптографических хэш-функций : хеш-функция 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 мы имеем
где negl(·) обозначает некоторую незначительную функцию, а n — параметр безопасности. [5]
Существует два разных типа устойчивости к столкновению.
Хэш-функция имеет слабую устойчивость к коллизиям, когда при заданной хеш-функции H и x невозможно найти другой x', такой, что H(x)=H(x'). Другими словами, если задан x, невозможно найти другой x', такой, что эта хэш-функция создала бы коллизию.
Хэш-функция имеет высокую устойчивость к коллизиям, когда для данной хеш-функции H невозможно найти произвольные x и x', где H(x)=H(x'). Другими словами, невозможно найти два x, где хеш-функция создала бы коллизию.
Устойчивость к столкновениям желательна по нескольким причинам.
