Найдены коллизии в MD5

Мдааа. И что теперь остаётся более-менее безопасного?

А что такое коллизия хэш-функции?

Это значит, что продемонстрированы (теоретически они всегда были) возможности того, что хэши для каких-то РАЗЛИЧНЫХ аргументов могут быть одинаковы. Чем сложнее обнаружить коллизии, тем хэш-функция лучше...

на стойкость паролей в md5 это никак не повлияет

И лялих здесь ни при чем--это особенности алгоритма, а не их реализации...насколько я понимаю.

> Мдааа. И что теперь остаётся более-менее безопасного?

Отечественный ГОСТ-34.11
=)

Немного не так, следует говорить не "чем сложнее обнаружить коллизии", а "чем реже возникают коллизии".

> что хэши для каких-то РАЗЛИЧНЫХ аргументов могут быть одинаковы

Нет, вам однозначно следует подучить алгебру :-)

Функция проекции на множество меньшей размерности (а хэш, фактически, и есть проекция почти бесконечного множества исходных данных на изначально конечное множество возможных значений хэш-функции) всегда обладает свойством порождать коллизии.

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

Фактически это значит следующее: любая хэш-функция порождает коллизии в случае, если разрядность исходных данных больше разрядности значения хэша.

> Отечественный ГОСТ-34.11

Любой хэш порождает коллизии. Для любой хэш-функции с разрядностью результат n бит и разрядностью исходных данных m бит найдется как минимум два значения аргумента (исходных данных), для которых значение хэш-функции будет одинаковым.

Сложности нахождения таких значений - уже другой вопрос :-)

И вообще я уже забыл, ГОСТ-34.11 - это хэш или шифрование? :-)

> Немного не так, следует говорить не "чем сложнее обнаружить коллизии", а "чем реже возникают коллизии".

Правильно предыдущий оратор сказал. Тут важна не частота коллизий, а практическая возможность их нахождения. Скажем, одно дело если коллизию на современных компах можно найти за час, и совсем другое если на это потребуется миллион лет.

Кстати, вот определение криптографической хэш-функции: http://www.rsasecurity.com/rsalabs/node.asp?id=2176
Предъявленные коллизии в данном случае означают, что перечисленные хэш-функции не являются strongly collision-free, но тем не менее он по-прежнему weakly collision-free.

To no-dashi: > Функция проекции на множество меньшей размерности (а хэш, фактически, и есть проекция почти бесконечного множества исходных данных на изначально конечное множество возможных значений хэш-функции) всегда обладает свойством порождать коллизии.

Именно поэтому я написал в своем посте :

> Это значит, что продемонстрированы (ТЕОРЕТИЧЕСКИ ОНИ ВСЕГДА БЫЛИ) возможности того, что хэши для каких-то РАЗЛИЧНЫХ аргументов могут быть одинаковы. Чем сложнее обнаружить коллизии, тем хэш-функция лучше...

Большими буквами в скобках выделено то, что должно было привлечь ваше внимание перед написанием поста о незнании алгебры. :)

> И вообще я уже забыл, ГОСТ-34.11 - это хэш или шифрование? :-)

гугл тебе поможет ;)

С 1995 года ещё слухи ходили что КГБ могли любой MD5 на одном пентиуме-100 за 3 дня подделывать.

http://cryptolib.com/crypto/chaos

Вон засандалил себе hash хоть на 512 бит и спишь спокойно. Там тебе и умножения, и data-dependent rotations, и никакой линейности. Пять лет там уже лежит и не выёьывается. Кому нужен MD5???

И стоило об этом писать? Этот факт представляет интерес только для специалистов-математиков. Хэш-функция _всегда_, _по определению_ обязана содержать коллизии. (Исключение - совершенная хэш-функция, но она, как все понимают, совсем из другой оперы.)

> Хэш-функция _всегда_, _по определению_ обязана содержать коллизии.

Еще раз и медленно:

Дело не в том, что любая хэш-функция имеет коллизии. С этим никто не спорит.

Но криптостойкая хэш-функция должна представлять определенную СЛОЖНОСТЬ (читай: практическую невозможность) для ОТЫСКАНИЯ КОЛЛИЗИЙ. Как только фактическая коллизия найдена, можно считать, что хэш-функция дискедитирована. Потому что, следующим шагом, возможно, будет ее обращение.

И еще раз: для _хорошей_ (криптостойкой) хэш-функции должно быть _практически невозможно_ отыскать коллизию.

> И еще раз: для _хорошей_ (криптостойкой) хэш-функции должно
> быть _практически невозможно_ отыскать коллизию

Почему я и отделил факт наличия коллизий от способов их нахождения
фразой "Сложности нахождения таких значений - уже другой вопрос" :-)

> "Сложности нахождения таких значений - уже другой вопрос" :-)

Surprise! Surprise! Именно этот "другой вопрос" в данном топике и поднят, из-за него и весь сыр-бор.
А что Вы собрались тут обсуждать мне совсем непонятно. ;-)

> Именно этот "другой вопрос" в данном топике и поднят

Нет стойких шифров и хэшей, есть слабые процессоры (шутка :-))

вон чеваки DESCC ломают а вы тут флэйм развели

Вспоминая ситуация с MD4 можно ждать появления в ближайшее время MD6... ;-)

>Потому что, следующим шагом, возможно, будет ее обращение. О как. Обратить хэш... Ясно же сказано что хэш функции не биективные. И как можно ОБРАТИТЬ такую функцию?

>И еще раз: для _хорошей_ (криптостойкой) хэш-функции должно быть _практически невозможно_ отыскать коллизию.

Тогда хороших хэш функций не существует в природе. Мощности компов растут по экспоненте, а стойкость хэш функции - величина постоянная :)

>> "Сложности нахождения таких значений - уже другой вопрос" :-)

>Surprise! Surprise! Именно этот "другой вопрос" в данном топике и >поднят, из-за него и весь сыр-бор. >А что Вы собрались тут обсуждать мне совсем непонятно. ;-)

А, собственно, в приведенных ссылках я нашел оценку сложности--10**51 для SHA. А много это или мало-- зависит от применения. Для проверки платежки -- много. Для защиты документа с грифом "хранить вечно" -- может оказаться мало :))) Правда, мне трудно придумать примение хэша для защиты документа с грифом "хранить вечно" :)

Опечатка вышла с моем предыдущем сообщении. сложность -- 2**51 для SHA-0 (см здесь -- http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.html)

>> Потому что, следующим шагом, возможно, будет ее обращение.
> О как. Обратить хэш... Ясно же сказано что хэш функции не биективные. И как можно ОБРАТИТЬ такую функцию?

Здесь "обратить" значит найти какой-то (любой) праобраз.
Скажем, есть проверка пароля сравнением MD5 хэша от него с хранящимся в базе (как вариант: shadow ;). Взломщику вовсе не нужно знать какой конкретно пароль был использован для получения этого MD5 значения, подойдет любой другой, коль скоро значение от него совпадает с записанным.

>>И еще раз: для _хорошей_ (криптостойкой) хэш-функции должно быть _практически невозможно_ отыскать коллизию.

>Тогда хороших хэш функций не существует в природе. Мощности компов растут по экспоненте, а стойкость хэш функции - величина постоянная :)

Понятно, что стойкость всегда ограничена каким-то периодом времени. Но пара десятков лет - это несерьезно.
А хэш-функции "сломали" вовсе не потому, что компы стали такими быстрыми (хотя это безусловно помогло), а потому, что нашли алгоритмический подход, позволивший сократить объем работ до обозримого.

>Вспоминая ситуация с MD4 можно ждать появления в ближайшее время MD6... ;-)

А также: M17, M5, L85E3, AK04 и AN-2005

> А также: M17, M5, L85E3, AK04 и AN-2005

А мне M45 нравится...

По ссылкам конкретно про SHA-0 говорится
про остальное ничего определенного - про MD5 не подтверждена информация.

открою вам секрет ,
чтобы найти коллизию 2х АБСТРАКТНЫХ samples для hash на n bits достаточно ~ 2^(n/2) переборов, что в пределах возможности суперкомпов для md5. Для реального секьюрити задача по другому стоит - найти коллизию для кокретного данного значения. Так что пугатся рано.

Угу. А мне - ME45 :))))

> про MD5 не подтверждена информация.

Конкретно про MD5: http://www.rtfm.com/movabletype/archives/2004_08.html#001055

> чтобы найти коллизию 2х АБСТРАКТНЫХ samples для hash на n bits достаточно ~ 2^(n/2) переборов

И примерно столько же памяти!

вы хоть смотрели, что там за коллизии нашли, математики фиговы? +)

ясен пень, что число возможных значений хешей меньше, чем число значений возможных аргументов

просто в приведенных примерах бинарники различаются всего на 1 байт, и хэш при этом одинаковый.

> ясен пень, что число возможных значений хешей меньше, чем число значений возможных аргументов

Еще один. Почитал бы хоть дискуссию, прежде чем не относящийся к делу комментарий давать.

Ключевое слово в заголовке НАЙДЕНЫ. В том, что они есть, никто никогда и не сомневался. Но вот найти их предполагалось невозможным еще долго-долго, а тут нате вам - нашли. И не просто нашли, а метод изобрели для относительно быстрого нахождения коллизий. А тем самым дискредитировали перечисленные хэш-функции.

Да ничего не дискредитировали. Пока не найдут способ для любого заданного значения хэш функции подбирать входные данные которое это значение породят. Пока же представлены ДВА специальным образом подобранных входа. А это совсем не то... Так что можно спать спокойно :)

> Так что можно спать спокойно :)

Да как сказать. Китайский медот, похоже, позволяет находить коллизии для любого префикса. Это уже сейчас открывает возможности к мошенничеству с цифровыми подписями.

Скажем, берется два документа: один "хороший", другой "плохой". Каждый дополняется нужными данными так, чтобы их хэши совпадали. После этого "хороший" документ отправляется на подпись кому-следует, получает одобрение и подпись. Но так как хэши совпадают, то та же самая попись будет валидной для "плохого" документа, и можно сделать подмену...

И это называется "ничего не дискредитировали" ?

А как ты сделаешь так что в плохом документе будет то что тебе надо? Чтобы хэши совпадали туда надо будет кучу мусора положить. Кому такая подделка нужна? Понимаешь, нужно чтобы и хеши совпадали и в новом документе что-то осмысленное было. Тут даже "китайский метод" не поможет. А вот с паролями это может сработать. Но не сегодня и не завтра. На сегодняшний день вычислительных мощностей хватает на то чтобы подобрать два варианта данных с одинаковым хешем. Но на то чтобы подобрать нужные данные для заранее выбранного хеша... До этого еще очень и очень далеко. Как пешком до луны :)

> А как ты сделаешь так что в плохом документе будет то что тебе надо? Чтобы хэши совпадали туда надо будет кучу мусора положить.

Не положить, а дописать. То есть, будет осмысленный текст + нечто еще. При этом это "нечто" - маленькое и, возможно, уже скоро можно будет делать его каким-нибудь текстом, подогнать под шаблон и тп.

> Понимаешь, нужно чтобы и хеши совпадали и в новом документе что-то осмысленное было. Тут даже "китайский метод" не поможет.

Будет. Как я уже говорил, китайский метод позволяет находить коллизиции с любыми префиксами. Причем похоже, что им достаточно дописать всего 1024 бита для получения коллизии. Еще интересно, что тексты предъявленной коллизии для MD5 различаются всего в _шести_ битах.

Конечно, _пока_ это все не так уж страшно. Но потенциал у этих вещей большой...

о! отечественная пресса проснулась: http://zdnet.ru/?ID=455410

> И еще раз: для _хорошей_ (криптостойкой) хэш-функции должно быть _практически невозможно_ отыскать коллизию.

На всякий случай, еще раз, на пальцах =)

Разумеется, у хэш-функции всегда будут коллизии. То есть два входных блока A и B дадут одинаковый хэш X. Но _в идеале_, если некто хэшировал свой пароль A в X, то мы сможем подобрать подходящий под этот хэш блок (A или B) только методом тупого перебора. Не должно существовать более простого способа получить для данного хэша блок соответствующих ему исходных данных. А вот в данном случае именно это и произошло - ребята нашли исходный блок под хэш за время значительно меньшее, чем полагалось бы. Т.е. была обнаружена некоторая зависимость между A и X, позволяющая заметно сократить поиск A. И скорее всего, это не предел.

В-общем, раздавать хэши своих паролей явно не стоит =)

> А вот в данном случае именно это и произошло - ребята нашли исходный блок под хэш за время значительно меньшее, чем полагалось бы.

Это, к счастью, не так. Не умеют они по хэшу данные подбирать (пока?).
Они научились:
1) придумывать два "случайных" блока A и B, хэши которых равны;
2) дополнять два произвольных блока A и B специально подобранными данными так, чтобы хэши от дополненных блоков совпадали.