Коллизии в 512-битных блоках MD5

[Assorium]

У меня дежавю.

[alizar]

Доработал статью немного, сорри за первый ламерский вариант.

[Assorium]

Да почему ламерский? Все есть в статье автора. Хотя предыстория с китайскими взломами немного освежила память)

[mib]

Интересно, существует ли во множестве мд5 хешей такой, от которого хеш мд5 равен самому себе?
(Ну тоесть md5(a) = a)

[msa]

Это легко проверить, всего-то нужно провести 2^¹²⁸ операций)

[kibork]

Если будет не трудно, проверьте пожалуйста сегодня вечерком, а то очень уж интересно

[dom1n1k]

Хэш Мебиуса?

[Paul]

Это называется неподвижная точка.

[azproduction]

Более полезный случай, когда код содержит хэш равный хэшу от этого кода.

[ainu]

О, я видел это правда, не md5.
Согласен, что очень круто.

[Xlab]

Бегает по психушке md5 и кричит «я вас всех тут хеширую»…

[qteb]

Т.к. в md5 хэше 16 байт => 2^(16*8)=3,4*10^38 комбинаций.
Проще говоря, если для вычисления одного хэша по 16 байт требуется одна миллисекунда, то нам потребуется 10790283070806014188970529154,99 лет для расчета всех этих хэшей.

[MrCrock]

Облачные вычисления в помощь.

[qteb]

Числа от этого сильно не изменятся.

[lorc]

Неподвижная точка в мд5 не только существует, но и представляет собой валидную программу на перле (с) не-помню-откуда

[Evengard]

stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x

[MarrySun]

И так хочется верить, что время md5 подошло к концу, но ник автора… эх…

[Ocelot]

Зря вы так на этот раз. Сперва пост был действительно в духе Ализара: «Сенсация! MD5 взломан!», но после пары замечаний он его полностью переписал, добавив технических деталей, и нормально расставив акценты.
А MD5 уже давно признан ненадежным.

[Scratch]

если нашли коллизии первого рода, то почему до сих пор не посчитали md5 который == 0?

[NeverWalkAloner]

Правильно я понимаю что речь идет о коллизиях первого рода?

[Ocelot]

Нет, Марк Стивенс нашел алгоритм поиска коллизий второго рода для сообщений размером в 1 блок. До этого были найдены медленные алгоритмы для коллизий 1-го рода и быстрые — для 2-го, но и те, и другие работали с длинными сообщениями.

[tkf]

А если использовать сразу два быстрых хэш алгоритма(sha1 и md5 например). И хранить соответственно два хэша.
Хоть и там и там есть коллизии, думаю подобрать набор данных который будет выдавать коллизии для обоих алгоритмов будет в разы сложнее.

[ComodoHacker]

Вы знаете, авторы сборок разного софта так и делают.

[tkf]

Да я и сам так делаю :)
Просто на мой взгляд в плане уникальности на одном наборе данных несколько хэш алгоритмов может быть гораздо выгодней чем любой один. Разве только он не имеет коллизий на блоке одного размера, в этом случае вторый параметром для определения уникальности будет размер.
p.s. мне для уникальности файлов пока хватает md5+sha1+file size, но есть предположение что в рамках больших чисел в конце концов эта система все равно может дать сбой, пометив два разных файла как один. ^_^

[lorc]

Ну… весь GIT зиждется на предположении что в одном конкретном репозитории никогда не будет коллизий в SHA1. Потому что там любой обьект однозначно идентифицируется своим SHA1 хешем.
Считается, что вероятность коллизии настолько маленькая, что ей можно пренебречь.