Ты только что узнал, что бывают коллизии хэшей?

Только задумался об этом. Давно слышал такое слово, но не придавал значения.

Не «могут быть», а есть.

Т.е. утверждение md5(«password») == md5(1111....1111) верно?

Даже в википедии кратенько написано о коллизиях хеш-функций и md5 в частности.

Да.

Предположим, для хэша длины 128 бит мы сгенерировали 2^128 хэшей по заданному шаблону без коллизий. Тогда каждый следующий хэш по этому же шаблону будет коллизией к одному из предыдущих. Для меньшего объёма сгенерированныъ хэшей можете посчитать сами, это просто. Это свойство напрямую вытекает из ограничения на длину выходных данных хэш-функции: таблица возможных значений хэша не бесконечна.

а если функция MD5() так устроена, что значение от 1 никогда не будет равно значению от большего количества единиц?

блин, это суровый матан какой-то, тут доказательства нужны

#cast dikiy

а если функция MD5() так устроена, что значение от 1 никогда не будет равно значению от большего количества единиц?

Тогда функция перемешивания отстойная. Я ведь не сказал, что найдётся именно коллизия от «1». Какая-то точно найдётся. Просто потому, что рано или поздно будет исчерпано всё множество значений функции. Да, можно построить функцию перемешивания вида y(1) = 0 , y(x!=1) = 1, тогда никаких коллизий к x=1 не будет.

а если функция MD5() так устроена, что значение от 1 никогда не будет равно значению от большего количества единиц?

такое тоже вероятно. надо достаточно хорошо разобраться в алгоритме. С наскоку не возьмешь.

Могут. Называется коллизия.

Просто потому, что рано или поздно будет исчерпано всё множество значений функции.

Шахматное число знаешь? Так вот, 128-ми битный хэш имеет значений - квадрат шахматного числа.

И что? Это гораздо меньше бесконечности.

И что? Это гораздо меньше бесконечности.

Зато это гораздо больше числа элементарных частиц в известной нам части вселенной.

т.е. во вселенной меньше 2^128 частиц? да это гон имхо.

И? Для математики нет никаких «элементарных частиц» и «известной части вселенной».

Чем лучше хеш функция тем меньше вероятность коллизии. sha1 лучше чем md5, sha512 лучше sha1, а сейчас уже и sha3 должны стандартизировать которая лучше их всех. В Git например вшита sha1, интересно через сколько лет и как он будет переходить на что нибудь другое, наверно будет какой нибудь git hashupgrade.

эх

А вот если бы люди сотрудничали и могли спокойно доверять другдругу даже свои жизни может быть этого вопроса и небыло бы.