Да, ты прав; это вращается вокруг Проблемы дня рождения. При хешировании вы, по сути, пытаетесь поместить что-то, что может быть теоретически бесконечной длины, в строку фиксированной длины с помощью математического процесса; поэтому столкновение неизбежно.
Проблема дня рождения в основном означает, что предположим, что у вас есть зал, полный людей, и вы спрашиваете у каждого человека дату его рождения. Вероятность найти кого-то с таким же днем рождения, как у другого, увеличивается, поскольку у вас больше дат рождения, которые могут быть у двух людей одинаковыми. И в конце концов вы найдете кого-то, у кого такой же день рождения.
Аарон Топонсе написал об этом в своей статье "Реальность SHA1" где он указал:
SHA1 должен был заменить MD5. MD5 имеет выходное пространство всего 128 бит, тогда как SHA1 имеет выходное пространство 160 бит. SHA1 также разработан иначе, чем MD5, и не должен страдать от тех же слабых мест или атак, с которыми сталкивается MD5. Однако со временем криптографы смогли серьезно атаковать SHA1, и в результате все они предупреждали нас, чтобы мы отказались от SHA1 и перешли на SHA2. Чтобы найти коллизию с SHA1, потребуется 2^160 операций, однако, используя парадокс дня рождения, мы можем иметь вероятность 50% найти коллизию SHA1 примерно за 2^80 операций. Однако криптоаналитики сократили SHA1 до сложности всего 2^61 операции. Даже лучше.
По сути, SHA1 — это математический алгоритм, в алгоритмах можно найти слабые места, которые облегчают их взлом и снижают вероятность коллизии. Это исследование, обычно проводимое учеными-компьютерщиками, криптографами и математиками, затем может быть использовано для уменьшения вероятности обнаружения коллизии за счет использования новых алгоритмов для поиска новых способов обнаружения коллизий.
person
mjsa
schedule
14.10.2015
