Как высоко мне нужно сосчитать, прежде чем я попаду в хэш-коллизию MD5?

Question

Не берите в голову, почему я делаю это - это в основном теоретическое.

Если бы я был MD5 хэширующими строковыми представлениями целых чисел, как высоко я должен был бы сосчитать, прежде чем два хеша столкнутся?

Answer 1

Эта проблема (в общем случае) известна как парадокс дня рождения

Вероятность столкновения в общем случае может быть легко вычислена. Тем не менее, в вашем конкретном случае вы должны вычислить (и сохранить!) Каждый MD5.

РЕДАКТИРОВАТЬ @ Скотт: не совсем. Принцип Пигонхола (являющийся лишь частным случаем проблемы Дня рождения) сказал бы, что имея 2 ^ 128 возможных значений MD5, мы, несомненно, столкнемся после 1 + 2 ^ 128 попыток. Парадокс дня рождения говорит о том, что вероятность столкновения будет больше 0,5 примерно для 2 ^ 70 значений MD5.

С этими оценками требований к хранилищу вы сами решаете, стоит ли проблема того. По мне это не так.

Answer 2

Вот научный способ узнать, как высоко вы должны считать.

Создайте хеш MD5, который будет сокращен до 4 бит.Вычислите это (убедитесь, что вы рассчитываете, пока не достигнете, скажем, 100 коллизий, чтобы вы получили хорошее среднее значение)

Затем сделайте то же самое с 8 битами (опять же, подождите много коллизий, чтобы вы могли вычислить среднее).

Делайте это снова и снова, пока не получите средние значения для 4, 8, 12, 16 бит, а затем посмотрите, сможете ли вы найти тренд.Следуйте этой тенденции до 128 бит

Возможно, вы захотите скорректировать все 128 бит, чтобы получить более короткую версию.Взятие первой или последней части может быть не лучшим тестом.

Answer 3

В идеальном мире, до 1 + 2^128. Но я сомневаюсь, что md5 идеален, я не могу дать вам номер, но гарантированно будет <= 1+ 2^128

Answer 4

Очевидно, можно основать тезис на этой самой вещи (или, во всяком случае, на подобных проблемах).Я этого не читал, но, возможно, что-то из тезиса Стивенса поможет вам (по-видимому, это связано со статьей в Википедии).