LINUX.ORG.RU

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


0

0

На проходящей конференции CRYPTO'04 представлены несколько статей, посвященные нахождению коллизий в криптографических хеш-функциях. В частности, найдены коллизии для хэш-функций MD4, MD5, SHA-0, HAVAL, RIPEMD и предположительно в SHA-1.

Подробности:
http://www.iacr.org/conferences/crypt...
http://www.mail-archive.com/cryptogra...
http://eprint.iacr.org/2004/199/
http://www.rtfm.com/movabletype/archi...
http://www.freedom-to-tinker.com/arch...

Обсуждение на slashdot: http://slashdot.org/article.pl?sid=04...

anonymous

Проверено: l-xoid ()

Ответ на: комментарий от LX

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

far
()

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

anonymous
()
Ответ на: комментарий от far

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

far
()
Ответ на: комментарий от far

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

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

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

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

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

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

no-dashi ★★★★★
()
Ответ на: комментарий от anonymous

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

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

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

no-dashi ★★★★★
()
Ответ на: комментарий от no-dashi

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

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

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

anonymous
()
Ответ на: комментарий от no-dashi

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

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

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

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

far
()
Ответ на: комментарий от no-dashi

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

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

anonymous
()

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

http://cryptolib.com/crypto/chaos

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

anonymous
()

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

no-dashi ★★★★★
()
Ответ на: комментарий от no-dashi

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

no-dashi ★★★★★
()

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

ZLO
()
Ответ на: комментарий от anonymous

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

gns ★★★★★
()
Ответ на: комментарий от anonymous

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

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

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

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

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

anonymous
()

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

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

szh ★★★★
()
Ответ на: комментарий от szh

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

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

x029ah
()
Ответ на: комментарий от x029ah

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

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

int19h ★★★★
()
Ответ на: комментарий от int19h

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

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

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.