SHA-1 Broken

Увидел в Ru. Crypt:

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

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

На страницу: 1, 2, 3, 4, 5 След.

Комментарии

—	unknown (16/02/2005 13:44) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

"Ожидаемые события последних дней в криптоанализе хэш-функций"

SHA-2(256,512) будут следующими.

Пока единственно стойкой и имеющей репутацию может считаться хэш-функция WHIRLPOOL, использующая "wide-trail" – дизайн (такой же как у AES-RIJNDAEL). Хотя все равно надо бы разрабатывать что-то новое, с учетом последних работ.

—	SATtva (16/02/2005 13:53) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Дождались. Правда, 2^69 — это всё-таки даже больше, чем нужно для обычной коллизии в MD5, но сам факт атаки в нынешней ситуации, когда консенсуса по альтернативам алгоритму нет, вызывает серьёзное беспокойство.

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

—	unknown (16/02/2005 14:52) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

В некоторых вполне серьезных работах было написано, что MD5 была взломана в 1996 г. и от нее надо было отказаться уже тогда. Под взломом авторы понимали всего лишь недостаточные свойства функции сжатия, когда не было еще даже никаких хотя бы теоретических атак и хотя бы на несколько раундов.

Если существование алгоритма взлома доказано, он быстрее чем "Brute force", (не по реальной скорости, а по числу операций – скорость достаточно оценить на уровне порядков) и он направлен на оригинальный (а не упрощенный алгоритм), то взлом можно считать состоявшимся. Неважно сколько времени ждать до его практической реализации. Ждать уже нет смысла.

Странно только то, что и оригинальная работа по взлому MD5 с подробным описанием алгоритма получения результатов не опубликована. Возможно работа по SHA1 будет приведена в таком же урезанном виде. Темнят что-то китайцы ;-)

—	SATtva (16/02/2005 15:31) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Ну, криптографические исследования столь же "открыты" в Китае, как были в СССР. Может быть Ван и её команда ещё не согласовали со своим правительством, как, и возможно ли, предавать работы гласности.

—	unknown (16/02/2005 17:02) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Ну, криптографические исследования столь же "открыты" в Китае, как были в СССР. Может быть Ван и её команда ещё не согласовали со своим правительством, как, и возможно ли, предавать работы гласности.

И атака на хэш-функции так и не будет названа Wang-Yin-Yu. Пожелаем им удачного побега и надежного политического убежища. Может тогда мы все узнаем из первоисточников.

—	unknown (16/02/2005 21:01) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

such
as HMAC where collisions aren't important

Я бы перевел как "где коллизии не имеют особого значения". В новости на Главной получилось по-другому –

как HMAC, где коллизии труднее реализуемы

в принципе верно и то и другое. В HMAC атаку на основе "парадокса дней рождения" применить невозможно (по крайней мере напрямую) – нельзя сгенерировать подобранные пары блоков, порождающие коллизию.

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

—	Николай (16/02/2005 21:07) профиль/связь <#> комментариев: 25 документов: 1 редакций: 0

Странно только то, что и оригинальная работа по взлому MD5 с подробным описанием алгоритма получения результатов не опубликована. Возможно работа по SHA1 будет приведена в таком же урезанном виде. Темнят что-то китайцы

На базе их работы по MD5 уже вовсю стругают вполне практические вещи. Например здесь: file

http://cryptography.hyperlink.cz/2004/MD5-POC.pdf
В белой бумажке написано как делать самораспаковывающиеся архивы с одинаковым md5 хешем и кое-что ещё. Более того, у них на сайте есть рабочий вариант с исходникам для генерации таких архивов.

2^69 операций это довольно большое число для повсеместного применения. В том же блоге Шнайера в комментариях кто-то даже посчитал сколько это будет в годах при выполнении кода на среднестатистической тачке — 4000 лет ;)
Другое дело, что алгоритм прилижут и оптимизируют. Да и прогресс вычислительных мощностей ползёт вверх.

А по поводу Китайцев я уже устал прикалываться (на SQL. RU чисто случайно развели бодягу про стойкость MD5, пришлось доказывать — пока два разных файла с одинаковым хешем им не показал, не верили). Кому интересно, подробности этой баталии тут: http://www.livejournal.com/users/denish_labs/788.html

—	SATtva (16/02/2005 21:27) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Вдруг владельцы сети забудут поменять ключ и так и не вспомнят про это через 100000 лет?

Не будем забывать об износе оборудования и старении носителей информации (а чем более дискретно и менее избыточно эта информация будет "носиться", стареть носители будут ой-ёй-ёй!). Через 100000 лет и кремниевые чипы, и магнитные, оптические, голографические и всякие разные другие диски в прах превратятся. ;)

Тут в дискуссионном листе на gnupg.org ещё вот такой комментарий появился:

On Wed, 16 Feb 2005, David Shaw wrote:
>> In terms of GnuPG: it's up to you whether you want to switch hashes or
>> not. GnuPG supports all of the SHA-2 hashes, so they are at least
>> available. Be careful you don't run up against compatibility problems:
>> PGP doesn't support 384 or 512, and only recently started supporting
>> 256. GnuPG before 1.2.2 (2003-05-01), doesn't have any of the new
>> hashes. Finally, if you have a DSA signing key (most people do) you are
>> required to use either SHA-1 or RIPEMD/160. RSA signing keys can use
>> any hash.

======
there's more to it than that. openPGP specifies SHA-1 (and nothing else)
as the hash used to generate key fingerprints, and is what key IDs are
derived from.

a real threat if this can be extended into a practical attack is
substituting a key with a *different* key having the same ID and
fingerprint. it would be difficult for average users (and impossible for
the current openPGP infrastructure) to tell bob's key from mallory's key
that claims to be bob's.

it can also be used (if the attack becomes practical) to forge key
signatures. mallory can create a bogus key and "sign" it with anyone's
real key. this would turn the web of trust into dust.

the openPGP spec seemed to have assumed that SHA-1 just wouldn't fail.
ever. this was the same mistake made in the original version of pgp that
relied on md5. the spec needs to allow a choice of hash algorithms for
fingerprints and key IDs, or else we'll play this game every time someone
breaks a strong hash algorithm.

...atom

А в IETF OpenPGP ещё неделю назад только обсуждали, уходить с SHA-1 как обязательного алгоритма или нет. В итоге пришли к заключению, что 3DES, конечно, заменим, ну, а SHA-1 оставим, как есть. С интересом ожидаю, чем продолжится дискуссия и что скажут вечные скептики из GnuPG. :)

—	unknown (17/02/2005 08:58) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

На базе их работы по MD5 уже вовсю стругают вполне практические вещи. Например здесь: http://cryptography.hyperlink.cz/2004/MD5-POC.pdf
В белой бумажке написано как делать самораспаковывающиеся архивы с одинаковым md5 хешем и кое-что ещё. Более того, у них на сайте есть рабочий вариант с исходникам для генерации таких архивов.

2 Николай: я читал что-то подобное в 2004 году. Это была просто концептуальная демка, основанная на том, что если найдена коллизия в первом ВХОДНОМ блоке (а он равен 512 бит, а не 128 или 160 (ВЫХОДНОЙ блок) – если мне память не изменяет – сейчас под рукой документации нет), то к этому блоку можно добавить какие-угодно ОДИНАКОВЫЕ данные, тогда получаться два разных (но ТОЛЬКО в ПЕРВЫХ БЛОКАХ) файла. На основе этого можно создавать и самораспаковывающиеся архивы в том числе. Интересно, но не слишком практично. Пока еще.

А про китайцев забавно. Похоже на "мудрый и миролюбивый советский народ". Т.е. на россиян и их соседей по СССР в недалеком прошлом. Поэтому наверное такое умиление и вызывают.

А атака называется в честь Chabaud-Joux, которые разбирали и дополняли исследование, а не по именам китайцев. Ну наподобие того, как радио изобрел не Попов, а Маркони и т.д. Плата за закрытость, обособленность, "свой особый путь" и т.д..

А в IETF OpenPGP ещё неделю назад только обсуждали, уходить с SHA-1 как обязательного алгоритма или нет.

Странно, но я приводил массу ссылок на работы, где ненадежность SHA1 убедительно предсказывалась еще сразу после взлома MD5. Если принцип Дамгарда-Меркла себя не оправдал, если несбалансированные сети Файстеля с регистрами сдвига тоже показали себя не лучшим образом (по крайней мере в данном дизайне для хэш-функций), нет смысла цепляться и за SHA-2.

Сейчас я думаю сильно возрастет интерес к функции WHIRLPOOL, которая до этого никому не была нужна из-за своей медлительности.

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

—	unknown (17/02/2005 10:11) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Коротенькие комментарии (цитаты), которые дали Шамир, Райвест, Диффи и другие участники при обсуждении новости на RSA-conference:

http://www.commsdesign.com/new.....l? ArticleID=60401254

—	SATtva (17/02/2005 11:19) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

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

Я бы посоветовал в "Неожиданных событиях..." разместить ссылку на данный топик. Просто если две дискуссии объединять, придётся в разделе новостей ссылки править.

—	Stas_S (17/02/2005 12:01) <#>

Сейчас я думаю сильно возрастет интерес к функции WHIRLPOOL, которая до этого никому не была нужна из-за своей медлительности.

А что можно сказать про функции семейства RIPEMD? 128-битная, как говорилось, ненадёжна, а остальные?

—	unknown (17/02/2005 12:27) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Ripemd-160 имеет сдвоенную (внутри несбалансированной сети Файстеля) структуру функции сжатия. В остальном она похожа на другие. Она базируется на тех же принципах. Думаю, до ее взлома примерно столько же работы, как от sha0 до sha1 или от md5 до sha1. Просто для этого нужно много однообразной работы, может из-за небольшой ее популярности в ближайшее время за нее не возьмутся и результаты будут когда-нибудь позже.

Есть еще TIGER – авторы Ross Anderson, Eli Biham. Ее специально создавали непожей на MDx. В ней есть большие 8x64 S-блоки. Но создавали ее в свете последних событий давно и много тогда возможно не знали.

—	SATtva (17/02/2005 16:36) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Что интересно, за последние часы получил из двух независимых источников информацию, что Шнайер опустил (или забыл упомянуть) в своей публикации одну немаловажную деталь из доклада команды Ван: дополнение входных данных до 512-разрядной кратности в алгоритме SHA-1 в данной атаке не применялось. Т.е. всё-таки усечённый алгоритм?

—	unknown (17/02/2005 17:12) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Новости уже попали в желтую прессу. http://www.utro.ru/news/2005/02/16/408905.shtml
Шедевр! Привожу полностью. Без смеха читать невозможно.

Китайцы нашли слабину в созданном спецслужбами США шифре SHA-

"Компьюлента". 19:52:23

Исследователи-криптоаналитики из Китая нашли слабину в американском криптоалгоритме SHA-1. Этот алгоритм был разработан в Агентстве национальной безопасности США и принят Национальным институтом стандартов США в качестве инструмента для создания электронной подписи. Алгоритм генерирует подпись из 160 бит на основе любого документа длиной до 264 бит. Принципы работы алгоритмов семейства SHA сходны с принципами более старых алгоритмов MD4 и MD5.
Однако, как пишет в своем блоге Брюс Шнайер – известный специалист по компьютерной безопасности и криптографии – алгоритм может оказаться совсем не таким надежным, как предполагалось. Ссылаясь на результаты исследователей Шаньдонского университета (КНР), Шнайдер отмечает, что добиться хэш-коллизии в алгоритме SHA-1 можно за 269 операций, тогда как методом простого перебора алгоритм вскрывается за 280 операций.
Под хэш-коллизией (hash collision) в данном случае подразумевается генерирование хэш-функцией одного и того же значения при двух различных наборах исходных данных. Если получить коллизию достаточно легко, то алгоритм не может использоваться для электронной подписи, поскольку подпись может быть сгенерирована как на основе оригинального документа, так и на базе набора данных, вызывающего коллизию.
Это уже не первый подобный случай с алгоритмами семейства SHA (аббревиатура расшифровывается как Secure Hash Algorithm). Первый алгоритм семейства – SHA-0 был представлен АНБ в 1993 г., но через два года был отозван из-за проблем с безопасностью. Подробностей об этих проблемах не сообщалось, но, по данным китайский исследователей, коллизии в случае SHA-0 можно добиться за 233 операции.
Призванный исправить недочеты SHA-0 алгоритм SHA-1 был выпущен в 1995 году. Однако из-за сообщений о его возможной нестойкости Национальный институт стандартов США планирует к 2010 г. отказаться от SHA-1 в пользу набора алгоритмов SHA-2.
Что касается результатов китайских исследователей, то они не означают, что SHA-1 – совершенно бесполезный алгоритм. Во-первых, 269 операций – это очень большой объем вычислений, и на практике взлом осуществить все равно непросто. Во-вторых, авторы исследования Сяоюнь Ван, Йицунь Лиса Йинь и Хонбо Ю пока нигде не опубликовали деталей своего исследования, так что говорить о 100%-й достоверности их результатов пока нельзя.

На страницу: 1, 2, 3, 4, 5 След.

Ваша оценка документа [показать результаты]