SHA-1 Broken

И ещё вопрос к специалистам по 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), получить осмысленный набор букв пока маловероятно.

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

Но зачем вам база блоков с коллизиями? Я подозреваю, что вы интересуетесь, можно ли что-то провернуть с подписями, программами, протоколами, но в тоже время не хотите ни хотите ни сами разбираться, ни сказать что именно.

Спасибо за внимание к моему вопросу и обстоятельные ответы! Я скажу зачем мне это нужно. Буду признателен, если и дальше оставите свое мнение специалиста. Итак, в чем суть моих вопросов:

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

Большое спасибо.

Очень похоже на то, что Вы говорите, при соблюдении некоторых условий (размер блоков и т. д.)

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

http://www.pgpru.com/forum/viewtopic.php?p=5913#5913

Casino:

Block1=&#40;S1 || S2 || S3 || S4 || S5&#41; Block2=&#40;S1 || S2 || S3 || S4 || S5'&#41; Block3=&#40;S1 || S2' || S3' || S4 || S5''&#41; H &#40;Block1&#41; = H &#40;Block2&#41; =H &#40;Block3&#41; H1 &#40;Block1 || CasinoPass || GamerPass&#41; H2 &#40;Block2 || CasinoPass || GamerPass&#41; H3 &#40;Block3 || CasinoPass || GamerPass&#41; H1=H2=H3

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

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

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

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

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

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

!!(blue)

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

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

!!

... Не прошло и года, как прогресс появился и в точности так, как и было предсказано.

Новости?

Хорошо, а что вы думаете относительно новых хэш-функций? С EnRupt, вродебы бы, более-менее ясно – найдены коллизи, однако на больших константах это уже не применимо. Шнайерская Skein заточена под x64, где имеет отличную производительность, может быть использована для генерации хэшей произвольной длины, втч. значительно больше чем внутреннее состояние. То же и с Keccak. Какие функции, на Ваш взгяд будут выбраны как SHA-3? И, самое интересное, как к примеру Skein и Keccak обеспечивает безопасноть, скаже, при генерации хэша длиной 2048-16384 бит? Ведь размер внутреннего состояния у них 1024/1024 бит?

Keccak интересен своей структурой Sponge:



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

Из чисто академического интереса, любопытными показались Edon и NaSHA, но только потому, что в серьёзной криптографии наконец-то стали рассматривать квазигруппы, по которым накапливается много теоретических работ. хотя Edon неуниверсален, NaSHA тоже и ещё запутана и громоздка и сами по себе они могут быть нестойкими, скорее всего их не выберут.

Пишут тут что-то новенькое, дескать, сложность поиска коллизий в SHA-1 удалось свести до 2⁵² операций. unknown, Вы держите руку на пульсе, можно это прокомментировать?

paper will appear on eprint soon

интересно, посмотрим, когда она там появится и прокомментируем

Дурдом. Но весело.

Вот заметка руководителя одного из авторов:

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

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

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

http://www.youtube.com/watch?v=4WtF_O7XLMQ

Никогда не знал, что конференции по криптографии проходят в таком формате :))

Вопрос для специалистов:
Есть контроллер электромагнитного замка работает на алгоритме SHA-1 с ключами DS1961S.
Здесь в основном обсуждаются колизии для электронных подписей, что в данном примере для DS1961S не имеет практического значения.
Вопрос – если есть например 10 исходных(512бит но без пароля) данных и 10 дайджестов(160бит – результат после обработки хеш функции ) к ним соответственно, можно ли в обозримом будущем вычислить пароль(64бит) находящейся в ключе?

СПАСИБО.