Введение
Свойство криптографических хеш-функций
В криптографии устойчивость к коллизиям – это свойство криптографических хеш-функций: хеш-функция H устойчива к коллизиям, если сложно найти два различных входных значения, которые дают одинаковый хеш; то есть два входных значения a и b, где a ≠ b, но H(a) = H(b). Принцип Дирихле (или принцип голубиных ящиков) означает, что любая хеш-функция, имеющая больше возможных входных значений, чем выходных, неизбежно будет иметь такие коллизии.
Криптографические хеш-функции обычно разрабатываются с учетом устойчивости к коллизиям. Однако многие хеш-функции, которые ранее считались устойчивыми к коллизиям, впоследствии были взломаны. В частности, для MD5 и SHA 1 опубликованы методы поиска коллизий, более эффективные, чем перебор. Тем не менее, для некоторых хеш-функций существует доказательство того, что поиск коллизий не менее сложен, чем решение определенных трудных математических задач (например, факторизация целых чисел или вычисление дискретного логарифма). Такие функции называются криптографически стойкими.
Слабое и сильное сопротивление столкновению
Существует два различных типа устойчивости к коллизиям. Хеш-функция обладает слабой устойчивостью к коллизиям, если, задав хеш-функцию H и значение x, невозможно найти другое значение x', такое что H(x) = H(x'). Иными словами, имея x, невозможно найти другое x', которое при хешировании с помощью данной функции привело бы к коллизии. Хеш-функция обладает сильной устойчивостью к коллизиям, если, задав хеш-функцию H, невозможно найти любые два значения x и x', такие что H(x) = H(x'). Иными словами, невозможно найти два различных значения x, которые при хешировании с помощью данной функции привели бы к коллизии.
Обоснование
Устойчивость к коллизиям желательна по нескольким причинам. В некоторых системах цифровой подписи сторона подтверждает подлинность документа, публикуя подпись открытым ключом от хэша этого документа. Если возможно создать два документа с одинаковым хэшем, злоумышленник может заставить сторону подтвердить один документ, а затем утверждать, что подтверждение было дано для другого. В некоторых распределенных системах обмена контентом стороны сравнивают криптографические хэши файлов, чтобы убедиться, что у них одинаковые версии. Злоумышленник, способный создать два файла с одинаковым хэшем, может обмануть пользователей, заставив их поверить, что у них одна и та же версия файла, хотя на самом деле это не так.