id: Гость   вход   регистрация
текущее время 23:27 28/03/2024
Автор темы: Гость, тема открыта 16/02/2005 12:29 Печать
создать
просмотр
ссылки

SHA-1 Broken


Увидел в Ru. Crypt:


У Шнайера опубликовано.

http://www.schneier.com/blog/a...../02/sha1_broken.html


 
На страницу: 1, 2, 3, 4, 5 След.
Комментарии
— unknown (20/10/2005 21:40)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664


И ещё вопрос к специалистам по MD5
допустим есть строка А причем А = Б+С
допустим к строке Б уже найдены коллизии, следует из этого что найти коллизию к строке A будет значительно легче и быстрее.
Как изменится скорость нахождения коллизии к строке A – если коллизии будут уже найдены не к Б, а к С



А о чем собственно речь? Если B и C < размера блока, то тогда ничего не выйдет.

H (A1) = H ( B1 || C1 ) = H ( B1' || C1 )

B1 и B1' – частичные коллизии?

H (A2) = H ( B1 || C2 ) = H ( B1 || C2' )

C2 и C2' – частичные коллизии?

Но H (A1) != H (A2). (!= – знак неравенства)

Как получить полную коллизию? Если брать полблока, то найти такую полуколлизию легко
2^(64/2)=2^32, но как это поможет найти вторую половину?

Если бы вторую половину было легко зафиксировать и искать коллизии сокращенным способом,
то это был бы "partitioning cryptanalysis", разделение задачи. Любой криптоалгоритм проектируется устойчивым к этому (хотя бы из-за лавинного эффекта). Поиск половины решения не должен давать в данном случае ничего.
Китайцы (и их предшественники и последователи) нашли уязвимость другим способом.


Это мы говорили об отдельном блоке. К существующей паре коллидирующих блоков можно действительно дописать пару одинаковых строк.

Коллидирующие блоки из работ китайцев и их продолжателей сами по себе очень специфичны, они подобраны под константы и функции самой md5 (или sha1), получить осмысленный набор букв пока маловероятно.

Все ссылки на работы я вам привел.

Но зачем вам база блоков с коллизиями? Я подозреваю, что вы интересуетесь, можно ли что-то провернуть с подписями, программами, протоколами, но в тоже время не хотите ни хотите ни сами разбираться, ни сказать что именно.
— Гость (21/10/2005 08:15)   <#>
Спасибо за внимание к моему вопросу и обстоятельные ответы! Я скажу зачем мне это нужно. Буду признателен, если и дальше оставите свое мнение специалиста. Итак, в чем суть моих вопросов:

MD5 используется в ряде онлайн-казин для подписи заранее сгенерированных последовательностей спинов. Эта подпись предоставляется игроку для гарантии того, что в процессе игры последовательность и значения спинов на рулетке не меняются независимо от ставок игрока.
Есть мизерные (но ненулевые) сомнения на тему того, а вдруг уже найдено множество коллидирующих блоков, представляющих из себя последовательности из цифр и пробелов. Тогда говорить об абсолютности предоставляемой гарантии неизменности последовательности в процессе игры – нельзя! Тем более вызывает некоторое сомение-подозрение тот факт, что для бОльшей гарантии игроку разрешают перед игрой добавлять к сгенерированной строке свой пароль и уже на результирующую строку (там кроме спинов и пароля игрока ещё присутствует и пароль казино, для того, чтобы нельзя было найти последние значения спинов простым перебором) напускается MD5.
Так вот небольшое сомнение заключается в том, что все "честные" казины разрешают вставлять пароль игрока в конец строки, уже после последовательности значений спинов. В этом то и вопрос, потенциально может это увеличить вероятность того, что могут быть использованы коллидирующие (найденные зараннее за много часов работы компьютеров) блоки? И уменьшит ли вероятность этого "обмана" если игроки добьются того, чтобы их пароль разрешали вставлять в начало строки, перед последовательностью спинов ?

Большое спасибо.
— unknown (21/10/2005 21:44)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Очень похоже на то, что Вы говорите, при соблюдении некоторых условий (размер блоков и т. д.)

Надо формализовать протокол и можно еще помедитировать над атакой Нострадамуса:

http://www.pgpru.com/forum/viewtopic.php?p=5913#5913
— unknown (21/10/2005 23:40)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Casino:



Да, если у казино просчитано заранее куча таких блоков < 512 бит, то игроку добавлять свой пароль бесполезно.

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

Но если "спины" будут во втором 512-битном блоке (а пароль в первом), то они могут найти правдоподобную коллизию и в нем, используя 128-битный буфер пароля, вычисленный из предыдущего блока. Если у них есть для этого время, то они могут создать базу под индивидуальный пароль игрока (это конечно гораздо дороже по ресурсам, но может пароль игрока предсказуем или не меняется от игры к игре и есть запас времени на такую подтасовку)?

Также были работы по нахождению коллизий в нескольких блоках одновременно, что тоже не внушает оптимизма.

Если почитать "Практическую криптографию" Шнайера-Фергюссона и главы про дефекты хэш-функций, то становится совсем грустно (и эти пророчества были написаны еще до событий 2004 года!)

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


!!(blue)

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

© Б. Шнайер, Н. Фергюссон "Практическая криптография", 2003 год

!!

... Не прошло и года, как прогресс появился и в точности так, как и было предсказано.
— Гость (27/01/2009 21:33)   <#>
Новости?
— Alexander_M (14/03/2009 16:47)   <#>
Хорошо, а что вы думаете относительно новых хэш-функций? С EnRupt, вродебы бы, более-менее ясно – найдены коллизи, однако на больших константах это уже не применимо. Шнайерская Skein заточена под x64, где имеет отличную производительность, может быть использована для генерации хэшей произвольной длины, втч. значительно больше чем внутреннее состояние. То же и с Keccak. Какие функции, на Ваш взгяд будут выбраны как SHA-3? И, самое интересное, как к примеру Skein и Keccak обеспечивает безопасноть, скаже, при генерации хэша длиной 2048-16384 бит? Ведь размер внутреннего состояния у них 1024/1024 бит?
— unknown (03/04/2009 15:07, исправлен 03/04/2009 15:24)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Keccak интересен своей структурой Sponge:



Где как раз придуман очень простой и изящный способ, как из стойкой функции f получать выход любой длины из входа любой разумной длины. Можно хоть вместо потокового шифра использовать. При этом дано самое аккуратное доказательство, что такая структура максимально близка к случайному оракулу. Даже если сам хэш будет неудачен из-за предложенной авторами функции f, то изобретение структуры Sponge вместо Дамгарда-Меркла – очень интересно и перспективно. Keccac – вполне хороший кандидат на финал.

Из чисто академического интереса, любопытными показались Edon и NaSHA, но только потому, что в серьёзной криптографии наконец-то стали рассматривать квазигруппы, по которым накапливается много теоретических работ. хотя Edon неуниверсален, NaSHA тоже и ещё запутана и громоздка и сами по себе они могут быть нестойкими, скорее всего их не выберут.
— SATtva (30/04/2009 16:59)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Пишут тут что-то новенькое, дескать, сложность поиска коллизий в SHA-1 удалось свести до 252 операций. unknown, Вы держите руку на пульсе, можно это прокомментировать?
— unknown (30/04/2009 17:58, исправлен 30/04/2009 17:58)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
paper will appear on eprint soon

интересно, посмотрим, когда она там появится и прокомментируем
— unknown (08/05/2009 15:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
http://www.youtube.com/watch?v=4WtF_O7XLMQ
— SATtva (08/05/2009 15:55)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Дурдом. Но весело.
— Гость (08/05/2009 18:48)   <#>
http://forums.devshed.com/secu.....at-2-52t-608000.html
— unknown (09/05/2009 00:17)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Вот заметка руководителя одного из авторов:

http://lukenotricks.blogspot.c.....-reduced-to-252.html

Это краткий анонс работы, которая не была готова к конференции. Он прозвучал в коротком докладе на Rump Session. Поскольку авторы известные, то можно доверять этому результату и считать, что sha1 действительно имеет стойкость уже в пределах возможности практического взлома 252. ну кто-то может скопировать дифференциальные пути со слайдов и по ним восстановить, кто-то возможно видел черновики работы, большинство же ждёт её официальной публикации.

Кстати, в случае со взломом md5 от китайцев было похоже – сначала был объявлен результат без доказательств, затем представлены доказательства в виде файлов с коллизиями, затем метод вкратце и затем полная работа, а дальше все кто-мог это анализировали и развивали дальше.
— Гость (22/05/2009 00:40, исправлен 22/05/2009 07:17)   <#>
http://www.youtube.com/watch?v=4WtF_O7XLMQ

Никогда не знал, что конференции по криптографии проходят в таком формате :))
— Корнилов_Николай (07/02/2012 14:24)   <#>
Вопрос для специалистов:
Есть контроллер электромагнитного замка работает на алгоритме SHA-1 с ключами DS1961S.
Здесь в основном обсуждаются колизии для электронных подписей, что в данном примере для DS1961S не имеет практического значения.
Вопрос – если есть например 10 исходных(512бит но без пароля) данных и 10 дайджестов(160бит – результат после обработки хеш функции ) к ним соответственно, можно ли в обозримом будущем вычислить пароль(64бит) находящейся в ключе?

СПАСИБО.
На страницу: 1, 2, 3, 4, 5 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3