Столкновения обязательно существуют для данной хэш-функции в математическом смысле: существует больше возможных входов, чем возможных выходов, поэтому должно быть два входа, которые отображаются на один и тот же выход. Теперь доказательство существования столкновения и фактическое его обнаружение - это две разные вещи. Если я урону бриллиант посреди океана, я определенно знаю , что где-то в океане сейчас есть бриллиант, но я совершенно не в себе, если захочу его вернуть.
Для «универсальной» хеш-функции с выходом n битов существуют универсальные методы для нахождения коллизии со средней стоимостью 2 n / 2 оценки функции (см. на этой странице ). В зависимости от n это может варьироваться от простого до абсолютно невозможного. Вывод MD5 составляет 128 бит, а 2 64 «довольно высокий»: вы можете сделать это, но для этого потребуется несколько тысяч машин и месяцев вычислений.
Теперь в MD5 есть известные слабости, то есть некоторая внутренняя структура, которая может быть использована для создания столкновений намного легче. Наилучшая атака на MD5, известная до сих пор, требует немного меньше, чем 2 21 вызовов функций , так что это всего лишь несколько секунд (максимум) на базовый ПК. @ Omri указывает в своем ответе на замечательный пример коллизии MD5, в которой коллизионные сообщения на самом деле являются исполняемыми файлами с совершенно разными поведениями.
Для SHA-1 выход имеет размер 160 бит. Это означает, что общая атака столкновением обошлась примерно в 2 80 , чего нельзя достичь с помощью существующих технологий (ну, Человечество может сделать это, но, конечно, не незаметно : это должно быть выполнимо, скажем, с эквивалентом одного года бюджета для всей армии США). Однако SHA-1, как и MD5, имеет известные недостатки. В настоящее время эти недостатки все еще являются теоретическими, поскольку они приводят к атаке со столкновением стоимостью 2 61 , что слишком дорого для любой отдельной криптографической исследовательской лаборатории и, следовательно, не было полностью проведена (была объявлена атака со стоимостью 2 51 , но, похоже, это была глупость - анализ был ошибочным). Таким образом, фактическое столкновение показывать не нужно (но исследователи почти уверены, что атака 2 61 правильная и сработает, если кто-то найдет бюджет).
В SHA-256 нет известных недостатков, а выходной 256-битный размер подразумевает общую стоимость 2 128 , что далеко отходит от невыполнимых сегодня и завтра технология.