Опубликован алгоритм поиска коллизий для MD4/MD5

Ну уже давно известно что md4 слаб, а md5 тоже далёк от совершенства. там где есть возможность выбрать, выбирайте sha-1 или ripe-md160

пора переходить на blowfish.

blowfish - это алгоритм шифрования, а MDX/SHXXX - алгоритмы хэширования. Вы что-то не туда загнули.

> там где есть возможность выбрать, выбирайте sha-1 или ripe-md160

Ни в коем случае не слушайте таких горе-советчиков!
Эти алгоритмы слишком похожи на md5 по дизайну. Любой професиональный криптоаналитик порекомендует sha256 или даже sha512 в качестве замены md5, но уж не как не sha1

> blowfish - это алгоритм шифрования, а MDX/SHXXX - алгоритмы хэширования. Вы что-то не туда загнули.

Товарищ просто не совсем точно выразился. Если зафиксировать в качестве ключа blowfish некую последовательность и прогнать данные через CFB режим например, то последний полученный блок вполне можно использовать в качестве хеш-значения.

хм.

значит перепутал.

что сейчас самое безопасное?

Аааа!!!
Ссылка не открывается!
Это происки NSA! Они уже рядом, они следят за мной, я это чувствую!

> что сейчас самое безопасное?

SHA256

/bin/login патчить надо?

> /bin/login патчить надо?

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

у меня слакварь.

все давным-давно настроено и в общем меня устраивает.

пам стоит, но пересобирать все пока еще руки не дошли :)

> выбирайте sha-1 или ripe-md160

Такой же алгоритм для SHA1 был опубликован еще в феврале:

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

А информация по RIPEMD проходила еще в 2004 году:

http://eprint.iacr.org/2004/199.pdf

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

тока бы кто-нибудь тупому втолковал, что за 4 параметра этой программе передаются и, вообще, как в эту игрушку играть :)

> тока бы кто-нибудь тупому втолковал, что за 4 параметра этой программе передаются и, вообще, как в эту игрушку играть :)

Дай линк и я честно попробую все понять и растолковать, а то ссылка из новости упорно не желает открываться.

>> там где есть возможность выбрать, выбирайте sha-1 или ripe-md160 >Ни в коем случае не слушайте таких горе-советчиков! ... >>порекомендует sha256 или даже sha512 в качестве замены md5

А таких советчиков надо слушать? sha2 - это не совсем замена md5. Хотя бы потому, что у нее выходной размер больше, а это бывает неприемлимо. Не говоря уже о том, что как раз по дизайну все семейство sha похоже, и sha2 - обеспечивает стойкость "в лоб", а не своим дизайном (просто коллизии искать во много много раз дольше, но ведь к sha1 уже подбираются...). Если нужна замена md5 советую использовать один из способов превращения стойкого блочного шифра в хэш нужной длины и скорости подсчета (описаны у Шнайера, например) или посмотреть в сторону готовых хешей отличных по дизайну (whirpool, например). Еще вариант, использовать схемы усиления хеширования, если, например, совсем отказаться от алгоритма md5 нельзя по каким-то причинам.

дайте нормальный линк! похоже на у них серваке уже произошла коллизия :)

http://www.stachliu.com/collisions.html

> Не говоря уже о том, что как раз по дизайну все семейство sha похоже...

А кто утверждал обратное?!

Похоже на компоненты md5 хеша. 4 числа по 4 байта. Не уверен. Сейчас запустил нахождение коллизии к хэшу от '123123' :) Посмотрим, что получится.

А сделать 1000 хэша хэшей что мешает?

Victor Gr.

А смысл ?

в юнихах(линуксах) применяются около 1000 итераций мд5 поэтому найти коллизию невозможно! md5 sha1 sha2 sha512 это все блочные шифры и принцип у них похож а вообще все эти разговоры про коллизии бред - идут уже скока лет находят в искуственных случаях а на практике 0

> Опубликован алгоритм поиска коллизий для MD4/MD5

Разве это означает, что можно расшифровать заданный хэш быстрее чем брутфорсом? Если нет, то в принципе паролям ничего не угрожает..

> самое время задуматься о смене дистрибутива - по хорошему

> достаточно переключить одну опцию в конфиге PAM и

Скажите это пользователям и админам СлАкИ :-) :-)

>На совсем не суперкомпьютере с Pentium4 1.6GHz коллизии в MD4 находятся за 5 секунд, в MD5 -- за 45 минут.

Данная программа позволяет создать 2 сообщения с одинаковыми хешами. НИКАКОГО отношеня к взлому хешей она не имеет, так что волноваться не надо.

4 параметра стартовые значения MD5, а не части хеша.

> в юнихах(линуксах) применяются около 1000 итераций мд5
1) ты вообще о чем говоришь ?
2) достаточно сделать коллизию для первого hashирования, и далее будет одно и тоже хэшироватся

Ну не знаю как у вас, а у меня в федоре пакеты подписываются gpg. А на хешированные пароли эта атака не направлена.

Срочно перехожу на совмещенный rot13+rot5 алгоритм.

% cat =rot13
tr A-Za-z N-ZA-Mn-za-m "$@"
% cat =rot5
tr 0-9 5-90-4 "$@"

> что сейчас самое безопасное?

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

Лучше всего, наверное, подписывать документы несколькими хэшами, MD5, SHA1 и т.д. Тогда, если поломают MD5, то будет время еще пока не поломают SHA1 перейти на MD6 и подобное. Невероятно трудно найти 2 разных документа одной длины (да еще и осмысленные), дающие те же самые MD5 и SHA1 суммы (хотя всегда бывают исключения для частных случаев).

нет, не означает. Это означает, что за 45 минут на p4-1.6 можно найти две разных строки, которые дают одинаковый хэш. Задача нахождения искомого текста по данному хешу на несколько порядков сложнее и до сих пор не решена. Равно как и задача поиска второй строки дающей заданный хеш. На самом деле куда опаснее то, что вдруг найдется какой-нибудь умник, который создат алгоритм обратный md5. Ведь математически строго не доказано, что обратной функции нет.

> Ведь математически строго не доказано, что обратной функции нет.

только потому, что это любому матетматику очевидно

"На самом деле куда опаснее то, что вдруг найдется какой-нибудь умник, который создат алгоритм обратный md5. Ведь математически строго не доказано, что обратной функции нет."

Ага и изобретет универсальный архиватор... это из разряда вечных двигателей

> там где есть возможность выбрать, выбирайте sha-1 или ripe-md160

не-е, выбирайте ГОСТ

> Разве это означает, что можно расшифровать заданный хэш быстрее чем брутфорсом? Если нет, то в принципе паролям ничего не угрожает..

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

нет, не позволяет. Позволяет только найти две строки которые дадут одинаковый хеш. Это совсем другое.

да кстати я тоже подумал если будет придуман алгоритм обратный мд5 это же супер архиватор шифруем к примеру 200мб получаем нексолько байт но тока исходных сообщений бесконечное множество а мд5 хешей 2^128

а вот по сабжу

[root@localhost qwer]# ./md4coll 182be0c5cdcd5072bb1864cdee4d3d6e unsigned int m0[16] = { 0x8def6806, 0x3e400132, 0xf30950ec, 0xcd7f5f6a, 0x2139213f, 0x8158629e, 0xd89aef95, 0xa1c1de39, 0xf2605ee3, 0xb1b926f6, 0xe05b1951, 0x9d270906, 0xfd5b5a5a, 0x256c1d4b, 0xed6a2293, 0x1021d965 };

unsigned int m1[16] = { 0x8def6806, 0xbe400132, 0x630950ec, 0xcd7f5f6a, 0x2139213f, 0x8158629e, 0xd89aef95, 0xa1c1de39, 0xf2605ee3, 0xb1b926f6, 0xe05b1951, 0x9d270906, 0xfd5a5a5a, 0x256c1d4b, 0xed6a2293, 0x1021d965 };

ктонить обьяснит как работает сабж? ну да сделал быстро результат несколько секунд по мд4 а где коллизия? куда применять эти хексы?

> Ведь математически строго не доказано, что обратной функции нет. поржал, спасибо

хэш - это отображение бесконечного множества возможных входных данных на конечное множество значений. оно не может быть обратимым.

Правильно. Но существует множество вариантов входных данных которые дают один и тот же хеш. Если обратная функция найдёт хотябы один из них, то задача решена! И при этом не играет никакой роли то что этот вариант отличается от того по которому делали хеш. Если они дают одинаковый хеш, то их "права и возможности" полностью одинаковые.

http://www.cits.rub.de/MD5Collisions/ красиво написанно, читаем, впитываем :)

именно. их видимо смущает слово "обратная":)

MD4, MD5, SHA-1, SHA-256, SHA-384, SHA-512... Это ж все поделки NSA! Почему бы не пользовать, скажем, Tiger (Автор его, Eli Biham, очень респектный чел, создатель алгоритма шифрования Serpent, который считают самым секьюрным из всех AES-кандидатов), или Whirlpool (тоже очень сильный хэш, правда медленный) ?

Медленные хеши рулят для паролей, конечно (затрудняют словарную или переборную атаку на стыренный хеш). Но нифига не рулят для проверки целостности - даже md5 от образа DVD считается, скажем так, не моментально. А более стойкие хеши - соотвественно еще дольше.

А хочется иметь один универсальный.

> Еще вариант, использовать схемы усиления хеширования, если, например, совсем отказаться от алгоритма md5 нельзя по каким-то причинам.

а где можно почитать об этих схемах усиления?

>Медленные хеши рулят для паролей, конечно (затрудняют словарную или переборную атаку на стыренный хеш). Но нифига не рулят для проверки целостности - даже md5 от образа DVD считается, скажем так, не моментально. А более стойкие хеши - соотвественно еще дольше.

Это у тебя образ DVD читается не моментально. Медленные хэши требуют больше вычислений, а не не скорость считывания с диска замедляют.

Tiger при своей скорости как раз подходит для хэширования образов CD/DVD. В некоторых P2P-сетях (скажем, Gnutella) его и юзают. И никаких проблем.

>Невероятно трудно найти 2 разных документа одной длины (да еще и осмысленные), дающие те же самые MD5 и SHA1 суммы (хотя всегда бывают исключения для частных случаев).

Недавно показывали два file1.ps и file2.ps, которые имеют осмысленный текст, одинаковый размер, одинаковый md5, но отличаются по смыслу конкретно на несколько предложений, я скачал и проверил. :)

Ты невнимательно читаешь. Я сказал, документ имеющий одинаковые MD5 и SHA1 суммы одновременно.