SHA-1 Broken


Увидел в Ru.Crypt:

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

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


Комментарии
— unknown (16/02/2005 13:44)   
"Ожидаемые события последних дней в криптоанализе хэш-функций"

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

Пока единственно стойкой и имеющей репутацию может считаться хэш-функция WHIRLPOOL, использующая "wide-trail" – дизайн (такой же как у AES-RIJNDAEL). Хотя все равно надо бы разрабатывать что-то новое, с учетом последних работ.
— SATtva (16/02/2005 13:53)   
Дождались. Правда, 2^69 — это всё-таки даже больше, чем нужно для обычной коллизии в MD5, но сам факт атаки в нынешней ситуации, когда консенсуса по альтернативам алгоритму нет, вызывает серьёзное беспокойство.

Как известно, атаки всегда улучшаются, но никогда не становятся хуже, так что можно быть уверенным, что исследователи доведут результат до большей практической пригодности. Действительно, прошло лишь полгода после Crypto'2004, а мы уже оказываемся в ситуации, когда использование любых старых алгоритмов — риск.
— unknown (16/02/2005 14:52)   
В некоторых вполне серьезных работах было написано, что MD5 была взломана в 1996 г. и от нее надо было отказаться уже тогда. Под взломом авторы понимали всего лишь недостаточные свойства функции сжатия, когда не было еще даже никаких хотя бы теоретических атак и хотя бы на несколько раундов.

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

Странно только то, что и оригинальная работа по взлому MD5 с подробным описанием алгоритма получения результатов не опубликована. Возможно работа по SHA1 будет приведена в таком же урезанном виде. Темнят что-то китайцы ;-)
— SATtva (16/02/2005 15:31)   
Ну, криптографические исследования столь же "открыты" в Китае, как были в СССР. Может быть Ван и её команда ещё не согласовали со своим правительством, как, и возможно ли, предавать работы гласности.
— unknown (16/02/2005 17:02)   
Ну, криптографические исследования столь же "открыты" в Китае, как были в СССР. Может быть Ван и её команда ещё не согласовали со своим правительством, как, и возможно ли, предавать работы гласности.

И атака на хэш-функции так и не будет названа Wang-Yin-Yu. Пожелаем им удачного побега и надежного политического убежища. Может тогда мы все узнаем из первоисточников.
— unknown (16/02/2005 21:01)   
such
as HMAC where collisions aren't important

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

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

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

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


На базе их работы по MD5 уже вовсю стругают вполне практические вещи. Например здесь: 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)   
Вдруг владельцы сети забудут поменять ключ и так и не вспомнят про это через 100000 лет?

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

Тут в дискуссионном листе на gnupg.org ещё вот такой комментарий появился:
On Wed, 16 Feb 2005, David Shaw wrote:
======
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)   
На базе их работы по 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)   
Коротенькие комментарии (цитаты), которые дали Шамир, Райвест, Диффи и другие участники при обсуждении новости на RSA-conference:

http://www.commsdesign.com/new.....l? ArticleID=60401254[link2]
— SATtva (17/02/2005 11:19)   
Кстати, когда злободневность новости поутихнет, может приклеим ее обсуждение в тему "Неожиданные события...в криптоанализе хэш-функций ".

Я бы посоветовал в "Неожиданных событиях..." разместить ссылку на данный топик. Просто если две дискуссии объединять, придётся в разделе новостей ссылки править.
— Stas_S (17/02/2005 12:01)   
Сейчас я думаю сильно возрастет интерес к функции WHIRLPOOL, которая до этого никому не была нужна из-за своей медлительности.

А что можно сказать про функции семейства RIPEMD? 128-битная, как говорилось, ненадёжна, а остальные?
— unknown (17/02/2005 12:27)   
Ripemd-160 имеет сдвоенную (внутри несбалансированной сети Файстеля) структуру функции сжатия. В остальном она похожа на другие. Она базируется на тех же принципах. Думаю, до ее взлома примерно столько же работы, как от sha0 до sha1 или от md5 до sha1. Просто для этого нужно много однообразной работы, может из-за небольшой ее популярности в ближайшее время за нее не возьмутся и результаты будут когда-нибудь позже.

Есть еще TIGER – авторы Ross Anderson, Eli Biham. Ее специально создавали непожей на MDx. В ней есть большие 8x64 S-блоки. Но создавали ее в свете последних событий давно и много тогда возможно не знали.
— SATtva (17/02/2005 16:36)   
Что интересно, за последние часы получил из двух независимых источников информацию, что Шнайер опустил (или забыл упомянуть) в своей публикации одну немаловажную деталь из доклада команды Ван: дополнение входных данных до 512-разрядной кратности в алгоритме SHA-1 в данной атаке не применялось. Т.е. всё-таки усечённый алгоритм?
— unknown (17/02/2005 17:12)   
Новости уже попали в желтую прессу. 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%-й достоверности их результатов пока нельзя.


— Николай (17/02/2005 17:34)   
Читал и плакал ;)
— SATtva (17/02/2005 17:46)   
В шифре, говорите, слабину нашли? Да уж... Николай, Вы, поди, шифр SHA- оплакивали, который пал жертвой изощрённого ума китайских коммунистов? :) Вначале даже не поверил, что значения степеней снесли на строчку, пришлось оригинал смотреть.
— unknown (17/02/2005 17:57)   
Где-то в новостях еще Шнайера со Шнайдером перепутали... а собственно даже в этом же тексте абзацом ниже. Опечатка. Роми Шнайдер икнулось наверное.
— Николай (17/02/2005 17:57)   
У сайта utro.ru явная проблема с тех.редакторами. Видимо редакторы были целиком поглощены тем, как правильно транслитерировать китайские фамилии ;)
— unknown (18/02/2005 09:04)   
http://www.securityLab.ru/52767.html
Вот тут еще пока не пофиксили. Вроде сайт не совсем развлекательный.

То же что в утро.ру. Слово в слово. С потерянными степенями. Автопереводчики их наверно теряют при копировании.

Если доживем до взлома RSA или до решения P=NP, то наверное сможем почитать много развлекательных материалов в СМИ на эти темы. Журналисты будут догадываться, что происходит что-то важное, но не смогут понять что именно.
— unknown (18/02/2005 12:21)   
... А самое смешное во всей этой истории, что даже доказательства все еще не опубликованы.
— SATtva (18/02/2005 13:18)   
SecurityLab исправились, хоть на том спасибо. А если кто настоящую телегу хочет, читайте Lenta.ru. Цитат приводить не буду, наслаждайтесь.
http://www.lenta.ru/internet/2005/02/17/hash/
— unknown (18/02/2005 15:06)   
Да. Это все весело. Но где доказательства от китайцев? Хочу увидеть два разных файла с одинаковой SHA-1 суммой. Нет ни файлов (ну по числу операций это понятно), ни самой работы.
А то вдруг их там ихний ЦК КПК передумает и скажет, что ничего не было взломано.
— Николай (18/02/2005 15:22)   
Всё, что китайцы опубликовали на сегодняшний день, это http://theory.csail.mit.edu/~yiqun/shanote.pdf
От этой ссылки растут все ноги.

Больше от китайцев вестей не было. Я написал Yiqun Lisa Yin письмо, но на ответ не очень расчитываю ;)
— SATtva (19/02/2005 12:33)   
Technical details will be provided in a forthcoming paper.

Как всегда... Самое вкусное оставляют на десерт.
— unknown (21/02/2005 08:51)   
Актуальное

  1. 02:

Мир OpenPGP // Приложения OpenPGP переходят на более стойкие алгоритмы хэширования

Интересно, а как будет выглядеть ID нового ключа и как его отличить от старого?


Кстати в рассылке ietf-openPGP обсуждается еще одно интересное предложение: добавлять к подписываемому документу (файлу) случайные данные. Это простой и обоснованный протокол, позволяющий избежать воздействия специально сгенерированных третьей стороной коллизий в подписях. (Что теоретически может привести даже к раскрытию секретного ключа – оснований для паники, как всегда никаких нет – это к сегодняшним слабостям SHA вообще не имеет отношения, но момент важный).


А с другой стороны – любые случайные данные – это скрытый канал, что многим пользователям не нравится.
— SATtva (21/02/2005 13:24)   
ID, отпечаток, S2K будут по-прежнему вычисляться по SHA-1. На SHA-2 пока переводят только электронную подпись. Формат ключей v4 к таким изменениям просто не приспособлен.

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

Кстати в рассылке ietf-openPGP обсуждается еще одно интересное предложение: добавлять к подписываемому документу (файлу) случайные данные.

Уже забраковали. :) Тут я с разработчиками солидарен — любое усложнение не на пользу стандарту. Такие вещи должны быть оставлены на усмотрение авторов программных реализаций. Вообще простой способ, как не пасть жертвой злоумышленника, — это всегда вносить незначительные изменения в начало предложенного к подписанию документа. Так, если оппонент и изготовил пару, производящую коллизию, хэш-значение подписанного файла будет уже другим.
— unknown (21/02/2005 13:44)   
Вообще простой способ, как не пасть жертвой злоумышленника, — это всегда вносить незначительные изменения в начало предложенного к подписанию документа.

А если мы подписываем архив или бинарник?

А если должны подписать много людей (отделенными подписями)?

Каждый должен к своей подписи приложить patch "для незначительных изменений" что-ли?

Или прикладывать эту строку тоже в отделенном виде?

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

Кстати, тема голосования на главной странице, где упомянута возможность внесения ГОСТ-хэша как приложения к стандарту приобрела еще один ироничный подтекст. ;-)
— unknown (22/02/2005 09:22)   
А что можно сказать про функции семейства RIPEMD? 128-битная, как говорилось, ненадёжна, а остальные?

Вот еще первоисточники про RIPEMD.

Авторы RIPEMD утверждают, что их алгоритм предпочтительнее, чем SHA (было бы странно, если бы было наоборот).

http://www.esat.kuleuven.ac.be.....ripemd160.html#SHA-1[link3]

Хотя в дизайне RIPEMD есть некоторые решения, увеличивающие его стойкость, в целом он похож и на SHA и на MD5.
— unknown (22/02/2005 13:25)   
Что сейчас есть из хэшей – сводная таблица:

http://planeta.terra.com.br/in.....arreto/hflounge.html[link4]
— SATtva (22/02/2005 23:22)   
[quote:550d7553cb="Yiqun Lisa Yin 21.02.05"]We have submitted the paper to a conference for peer review, and we should receive a notification of the review results by early May. We plan to publish the paper after incorporating the comments from the review, and will let you know around that time.
]>
Короче, опубликуют работу в мае, когда отредактируют в соответствии с комментариями рецензентов.
— Николай (23/02/2005 02:29)   

Короче, опубликуют работу в мае, когда отредактируют в соответствии с комментариями рецензентов.


Хорошо хоть ориентировочно со сроками определились. Когда я ей писал, она мне кроме "in the process" ничего толком сказать не могла ;)

Кстати, я-таки собрал все маразмы СМИ по поводу SHA-1: http://www.livejournal.com/users/denish_labs/
— Николай (23/02/2005 11:45)   
SATtva, спасибо за комментарий в блоге ;)
Не возражаете, если я, сославшись на вас, напишу о том, что результаты китайцы планируют опубликовать в мае?
— SATtva (23/02/2005 13:02)   
Be my guest, как говорят бледнолицые братья. Не имею ничего против.
— Николай (23/02/2005 13:21)   

Не имею ничего против.


Спасибо ;)
Гость (16/03/2005 10:38)   
Какова все таки безопасность практического применения SHA1 в свете описанных событий и в составе старых версий PGP? Версия 9 предлагает замену "ослабленной" функции на новую?
— unknown (16/03/2005 17:08)   
Какова все таки безопасность практического применения SHA1 в свете описанных событий и в составе старых версий PGP?

Практически это еще безопасно, но "под ней уже земля горит".

Версия 9 предлагает замену "ослабленной" функции на новую?

Новую еще не придумали. Есть кандидаты на звание коллизионно-стойкой функции (Whirlpool и др. совсем уж малоизвестные), но никто об этом на уровне стандарта еще не договорился.
— SATtva (25/07/2005 19:22)   
Опубликован полный документ китайцев по криптоанализу SHA-1: "Finding Collisions in the Full SHA-1"[link5]. Представили ещё до августовского CRYPTO'2005.
— unknown (31/08/2005 17:09)   
... А это были наши новости:
http://www.pgpru.com/news/crypto/200507.shtml#1708
Гость (16/10/2005 12:42)   
Уважаемые. Есть вопрос про частные случаи MD5.
Читал про прогу, которая генерит самораспаковывающие архивы с одинаковых хэшем. А насколько реально сущестование (написание) программы, которая генерировала бы быстро и много (секунды) небольшие (200-500 байт) файлы с одинаковым хэшем, с одинаковой длиной, но с разным содержанием однако во всех файлах обязательно должна быть часть, которая ни в одном из файлов не должна меняться?

Спасибо.
— unknown (16/10/2005 14:55)   
http://www.darksideprogramming.....ptography/index.html[link6]

У автора есть ссылки на готовые коды и работы по этим вопросам.

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

Эта ссылка сейчас не работает, ищите в гуглях и нет-архивах:
http://www.codeproject.com/useritems/HackingMd5.asp



А насколько реально сущестование (написание) программы, которая генерировала бы быстро и много (секунды) небольшие (200-500 байт) файлы с одинаковым хэшем, с одинаковой длиной, но с разным содержанием

Вполне реально. Читайте работы Властимила Климы.

Это может угрожать некоторым системам, где такая ситуация предусмотрена не была и флуд такими файлами или сертификатами на основе их хэшей может вызвать сбой.
Гость (19/10/2005 10:50)   
И ещё вопрос к специалистам по MD5
допустим есть строка А причем А = Б+С
допустим к строке Б уже найдены коллизии, следует из этого что найти коллизию к строке A будет значительно легче и быстрее.
Как изменится скорость нахождения коллизии к строке A – если коллизии будут уже найдены не к Б, а к С
— SATtva (19/10/2005 14:33)   
Если Б — это коллизирующий блок прообраза, то А будет коллизировать независимо от того, с чем конкатенирована Б. То есть А может быть равно Б+С, Б+В, Б+Д, но если Б дают коллизию, то и А во всех случаях будет давать коллизию. На этом свойстве, вытекающем из особенностей MD4-подобных алгоритмов хэширования, основаны все нынешние демонстрационные атаки. В большинстве случаев коллизирующий блок вообще взят из первой работы китайцев.
Гость (19/10/2005 14:53)   
в таком случае... если на поиск коллизии (коллизирующего блока) уходит всего до 8 часов, то вполне возможно существование целой постоянно пополняемой базы этих коллизионных блоков. То есть если мы имеем целью иметь большое число строк с одинаковыми подписями, то нам лишь надо чтобы они "начинались" с известных нам блоков ?
Гость (20/10/2005 06:47)   
И сразу тогда вопрос – может эта база коллизирующих блоков продается где-нибудь? И насколько реально например выполнения пожелания, чтобы коллизирующие блоки состояли из ограниченного набора символов, например только цифр(десятичных) и пробелов ?
— unknown (20/10/2005 21:40)   


И ещё вопрос к специалистам по 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)   
Очень похоже на то, что Вы говорите, при соблюдении некоторых условий (размер блоков и т. д.)

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

http://www.pgpru.com/forum/viewtopic.php?p=5913#5913
— unknown (21/10/2005 23:40)   
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)   
Keccak интересен своей структурой Sponge:



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

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

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

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

Это краткий анонс работы, которая не была готова к конференции. Он прозвучал в коротком докладе на 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бит) находящейся в ключе?

СПАСИБО.
— unknown (07/02/2012 16:34)   
Что-то типа этого?
H1 = SHA1 ( D1 || x ), ..., H_10 = SHA1 ( D_10 || x )

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

Где Di || x — 448 бит данных и 64 бита секрета.

Первое что приходит на ум — сбрутфорсить эти 64 бита, что не так уж сложно. Размер выхода самой хэш-функции и её стойкость при этом значения не имеет и достаточно одной пары {Hi, Di}. Провести 64 битный взлом не так сложно.
Гость (08/02/2012 00:07)   
Гость (08/02/2012 00:15)   
X rjklm n.
Да, при втором верхнем приходится пробел добавлять, как ни крути.
— Гость_ (08/10/2015 17:44)   
New Collision Attack Lowers Cost of Breaking SHA1[link10]
experts estimate that the cost of an SHA1 collision attack is currently between $75,000 and $120,000 using computing power from Amazon’s EC2 cloud over a period of a few months.

Но коллизии у них пока чисто академические, они выбирают константы (IV) вне стандарта.
— pgprubot (08/10/2015 21:20)   

Ничего, скоро от коллизий на 16-ричных keyid'ах[link11] перейдут к коллизиям на полные PGP-отпечатки, а там и до полного прообраза недалеко, благо

Н[link12]ад новой версией стандарта, насколько мне известно, никто не работает.
— SATtva (08/10/2015 23:53)   
На самом деле, последние полгода рабочая группа OpenPGP весьма оживилась: обсуждаются и айдишники под SHA-3, и новый формат отпечатков, и ряд других фич, дорабатывающих стандарт (предполагается именно ревизия, а не написанная с нуля новая спецификация).
— sentaus (24/02/2017 00:35, исправлен 19/03/2017 18:06)   

А SHA-1 таки поломали практически: https://shattered.it/


This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.

Я только пока не понял, есть ли там что-то новое с криптографической точки зрения. Заявленное число вычислений – это в точности 2^63, т.е. соответствует вычислительной сложности теоретической атаки китайцев 2005 года. Похоже, они просто довели её до практического исполнения.


18/02/2005: Хочу увидеть два разных файла с одинаковой SHA-1 суммой.

джвенаднацть лет ждали!!! ;)


Update: https://eprint.iacr.org/2017/190.pdf


Ссылки
[link1] http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

[link2] http://www.commsdesign.com/news/showArticle.jhtml?articleID=60401254

[link3] http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html#SHA-1

[link4] http://planeta.terra.com.br/informatica/paulobarreto/hflounge.html

[link5] http://cryptome.org/wang_sha1_v2.zip

[link6] http://www.darksideprogramming.org/archives/criptography/index.html

[link7] http://allmydata.org/pipermail/tahoe-dev/2009-April/001663.html

[link8] http://forums.devshed.com/security-and-cryptography-17/sha-1-collisions-now-at-2-52t-608000.html

[link9] http://lukenotricks.blogspot.com/2009/05/cost-of-sha-1-collisions-reduced-to-252.html

[link10] http://www.securityweek.com/new-collision-attack-lowers-cost-breaking-sha1

[link11] http://www.pgpru.com/comment94024

[link12] http://www.pgpru.com/comment77311