когда то / давненько / была зааннонсина инфа, что у сабжа есть некоторая уязвимость в алгоритме, что позволяет брать хеш примерно в четыри раза быстрее! кто нить в курсе? есть ли у когото подробное описание?
Вот тут описана концепция - . А вот тут вроде как реализация - . Сам я правда не проверял. Еще полезно почитать в багтреке дискуссию с сабжектом "MD5 To Be Considered Harmful Someday". Вышеприведенные ссылки собственно из этой дискуссии и взяты.
В документе много не понял так как там много воды, и непонятный английский.
Вот как я понял эту идею. 1) MD5 блочный, с размером блока данных 16 4-байтных слова = 64 байта. Т.е. алгоритм выглядит так
state = INITIAL
result = MD5o((MD5o(state, block0), block1) .... т.е. результат "пережёвываения" одного блока данных - это новое начальное состояние для следующего "пережёвываения" MD5o - алгоритм "пережёвываения" блока данных
2) Очевидно, что если мы для каких то 2х разных блоков данных, получили одно и тоже знаеничени MD5o то мы может в сообщении заменить эти блоки, без изменнения MD5 этого сообщения.
3) Очевидно, что коллизии хэша есть.
Я всё понял правильно?
Мое мнение по этому поводу: Все это понятно сразу после знакомства с RFC 1321, нового ничего нет.
Автор нашёл (как - это уже др. дело) два блока данных, для которых существует коллизия. Все знаю, что коллизии есть!
Ввиду того, что они отличаются 6 битами, он сделал вывод, что стойкость алгоритма упала до 2 в 45.
IMHO - это частный случай, кто знает может быть существуют блоки, различающиеся только один битом, но какова верятность, что такой блок присутсвует именно в вашем сообщении?
Чтобы найти эту вероятность, нужно определить мощности всех классов блоков. Имея сложности расчёта коллизии на каждом класса мы получим в конечном итоге стойкость алгоритма.
Практически же важно научится выявлять уязвимые классы блоков, возможно Joux, Wang или Kaminsky поделятся с нами
Вот тогда можно будет по сообщению сказать, что его можно изменить без ущерба для MD5 вот в такое сообщение.
Увы, обычно нужно менять сообщение так, чтобы оно удовляворяло опр. условиям, а не просто 6 бит
Так что пока практического применения не вижу. Как и повода для волнений.
Теперь собственно о быстрее: Очевидно, что вычислять MD5o (один блок) всё равно придётся.
Как сделать это быстрее? 1) Если часть входных данных заранее известна, производится сокращение/предварительное вычисление
2) Хвост алгоритма можно размернуть, т.к. там просто 4 сложения с константой.
3) На совр. процах задействовать SIMD 4) Оптимизировать на конкретные процессоры, например с помошью Vtune
Кроме того, можно считать на специализорованных устройствах, это по прикидкам даёт ускорение в 10^6 раз. Но этого не достаточно для полного перебора в течении вашей жизни
