alizar Jan 30 2012 at 23:36

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

2 min

21K

Cryptography*

+36

Comments 25

Assorium Jan 30 2012 at 23:48

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

alizar Jan 30 2012 at 23:50

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

Assorium Jan 30 2012 at 23:52

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

mib Jan 31 2012 at 00:17

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

msa Jan 31 2012 at 00:40

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

kibork Jan 31 2012 at 00:44

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

dom1n1k Jan 31 2012 at 00:40

Хэш Мебиуса?

Paul Jan 31 2012 at 01:02

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

azproduction Jan 31 2012 at 00:47

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

ainu Jan 31 2012 at 13:44

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

Xlab Jan 31 2012 at 00:52

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

qteb Jan 31 2012 at 00:54

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

MrCrock Jan 31 2012 at 03:17

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

qteb Jan 31 2012 at 03:51

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

lorc Jan 31 2012 at 13:12

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

Evengard Jan 31 2012 at 15:57

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

MarrySun Jan 31 2012 at 04:25

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

Ocelot Jan 31 2012 at 11:21

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

Scratch Jan 31 2012 at 06:46

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

NeverWalkAloner Jan 31 2012 at 07:40

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

Ocelot Jan 31 2012 at 11:14

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

tkf Jan 31 2012 at 13:42

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

ComodoHacker Jan 31 2012 at 23:27

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

tkf Feb 1 2012 at 09:47

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

lorc Feb 1 2012 at 15:26

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