В криптографии устойчивость к коллизиям является свойством криптографических хэш-функций : хэш-функция 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 , является семейством хеш-функций, устойчивых к коллизиям, если | m ( k )| > | l ( k )| для любого 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, где функция хеширования создала бы коллизию.
Устойчивость к столкновениям желательна по нескольким причинам.
