SHA-1 Broken
Увидел в Ru.Crypt:
У Шнайера опубликовано.
http://www.schneier.com/blog/a...../02/sha1_broken.html[link1]
Ссылки
[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] https://www.pgpru.com/comment94024
[link12] https://www.pgpru.com/comment77311
"Ожидаемые события последних дней в криптоанализе хэш-функций"
SHA-2(256,512) будут следующими.
Пока единственно стойкой и имеющей репутацию может считаться хэш-функция WHIRLPOOL, использующая "wide-trail" – дизайн (такой же как у AES-RIJNDAEL). Хотя все равно надо бы разрабатывать что-то новое, с учетом последних работ.
Дождались. Правда, 2^69 — это всё-таки даже больше, чем нужно для обычной коллизии в MD5, но сам факт атаки в нынешней ситуации, когда консенсуса по альтернативам алгоритму нет, вызывает серьёзное беспокойство.
Как известно, атаки всегда улучшаются, но никогда не становятся хуже, так что можно быть уверенным, что исследователи доведут результат до большей практической пригодности. Действительно, прошло лишь полгода после Crypto'2004, а мы уже оказываемся в ситуации, когда использование любых старых алгоритмов — риск.
В некоторых вполне серьезных работах было написано, что MD5 была взломана в 1996 г. и от нее надо было отказаться уже тогда. Под взломом авторы понимали всего лишь недостаточные свойства функции сжатия, когда не было еще даже никаких хотя бы теоретических атак и хотя бы на несколько раундов.
Если существование алгоритма взлома доказано, он быстрее чем "Brute force", (не по реальной скорости, а по числу операций – скорость достаточно оценить на уровне порядков) и он направлен на оригинальный (а не упрощенный алгоритм), то взлом можно считать состоявшимся. Неважно сколько времени ждать до его практической реализации. Ждать уже нет смысла.
Странно только то, что и оригинальная работа по взлому MD5 с подробным описанием алгоритма получения результатов не опубликована. Возможно работа по SHA1 будет приведена в таком же урезанном виде. Темнят что-то китайцы ;-)
Ну, криптографические исследования столь же "открыты" в Китае, как были в СССР. Может быть Ван и её команда ещё не согласовали со своим правительством, как, и возможно ли, предавать работы гласности.
И атака на хэш-функции так и не будет названа Wang-Yin-Yu. Пожелаем им удачного побега и надежного политического убежища. Может тогда мы все узнаем из первоисточников.
Я бы перевел как "где коллизии не имеют особого значения". В новости на Главной получилось по-другому –
в принципе верно и то и другое. В HMAC атаку на основе "парадокса дней рождения" применить невозможно (по крайней мере напрямую) – нельзя сгенерировать подобранные пары блоков, порождающие коллизию.
С другой стороны если противник може сотни тысяч лет перехватывать гигабайты данных в секунду, то он может дождаться случайных коллизий и на их основе построить атаку вычисления ключа. (Вдруг владельцы сети забудут поменять ключ и так и не вспомнят про это через 100000 лет?).
На базе их работы по 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
Не будем забывать об износе оборудования и старении носителей информации (а чем более дискретно и менее избыточно эта информация будет "носиться", стареть носители будут ой-ёй-ёй!). Через 100000 лет и кремниевые чипы, и магнитные, оптические, голографические и всякие разные другие диски в прах превратятся. ;)
Тут в дискуссионном листе на gnupg.org ещё вот такой комментарий появился:
А в IETF OpenPGP ещё неделю назад только обсуждали, уходить с SHA-1 как обязательного алгоритма или нет. В итоге пришли к заключению, что 3DES, конечно, заменим, ну, а SHA-1 оставим, как есть. С интересом ожидаю, чем продолжится дискуссия и что скажут вечные скептики из GnuPG. :)
2 Николай: я читал что-то подобное в 2004 году. Это была просто концептуальная демка, основанная на том, что если найдена коллизия в первом ВХОДНОМ блоке (а он равен 512 бит, а не 128 или 160 (ВЫХОДНОЙ блок) – если мне память не изменяет – сейчас под рукой документации нет), то к этому блоку можно добавить какие-угодно ОДИНАКОВЫЕ данные, тогда получаться два разных (но ТОЛЬКО в ПЕРВЫХ БЛОКАХ) файла. На основе этого можно создавать и самораспаковывающиеся архивы в том числе. Интересно, но не слишком практично. Пока еще.
А про китайцев забавно. Похоже на "мудрый и миролюбивый советский народ". Т.е. на россиян и их соседей по СССР в недалеком прошлом. Поэтому наверное такое умиление и вызывают.
А атака называется в честь Chabaud-Joux, которые разбирали и дополняли исследование, а не по именам китайцев. Ну наподобие того, как радио изобрел не Попов, а Маркони и т.д. Плата за закрытость, обособленность, "свой особый путь" и т.д..
Странно, но я приводил массу ссылок на работы, где ненадежность SHA1 убедительно предсказывалась еще сразу после взлома MD5. Если принцип Дамгарда-Меркла себя не оправдал, если несбалансированные сети Файстеля с регистрами сдвига тоже показали себя не лучшим образом (по крайней мере в данном дизайне для хэш-функций), нет смысла цепляться и за SHA-2.
Сейчас я думаю сильно возрастет интерес к функции WHIRLPOOL, которая до этого никому не была нужна из-за своей медлительности.
Кстати, когда злободневность новости поутихнет, может приклеим ее обсуждение в тему "Неожиданные события...в криптоанализе хэш-функций ". Просто там хронология вопроса хорошо отразилась и проще ссылаться на то, что уже обсуждалось. Может, кому из новых участников форума будет интересно, тогда можно читать по порядку с момента начала обсуждения.
Коротенькие комментарии (цитаты), которые дали Шамир, Райвест, Диффи и другие участники при обсуждении новости на RSA-conference:
http://www.commsdesign.com/new.....l? ArticleID=60401254[link2]
Я бы посоветовал в "Неожиданных событиях..." разместить ссылку на данный топик. Просто если две дискуссии объединять, придётся в разделе новостей ссылки править.
А что можно сказать про функции семейства RIPEMD? 128-битная, как говорилось, ненадёжна, а остальные?
Ripemd-160 имеет сдвоенную (внутри несбалансированной сети Файстеля) структуру функции сжатия. В остальном она похожа на другие. Она базируется на тех же принципах. Думаю, до ее взлома примерно столько же работы, как от sha0 до sha1 или от md5 до sha1. Просто для этого нужно много однообразной работы, может из-за небольшой ее популярности в ближайшее время за нее не возьмутся и результаты будут когда-нибудь позже.
Есть еще TIGER – авторы Ross Anderson, Eli Biham. Ее специально создавали непожей на MDx. В ней есть большие 8x64 S-блоки. Но создавали ее в свете последних событий давно и много тогда возможно не знали.
Что интересно, за последние часы получил из двух независимых источников информацию, что Шнайер опустил (или забыл упомянуть) в своей публикации одну немаловажную деталь из доклада команды Ван: дополнение входных данных до 512-разрядной кратности в алгоритме SHA-1 в данной атаке не применялось. Т.е. всё-таки усечённый алгоритм?
Новости уже попали в желтую прессу. http://www.utro.ru/news/2005/02/16/408905.shtml
Шедевр! Привожу полностью. Без смеха читать невозможно.
Читал и плакал ;)
В шифре, говорите, слабину нашли? Да уж... Николай, Вы, поди, шифр SHA- оплакивали, который пал жертвой изощрённого ума китайских коммунистов? :) Вначале даже не поверил, что значения степеней снесли на строчку, пришлось оригинал смотреть.
Где-то в новостях еще Шнайера со Шнайдером перепутали... а собственно даже в этом же тексте абзацом ниже. Опечатка. Роми Шнайдер икнулось наверное.
У сайта utro.ru явная проблема с тех.редакторами. Видимо редакторы были целиком поглощены тем, как правильно транслитерировать китайские фамилии ;)
http://www.securityLab.ru/52767.html
Вот тут еще пока не пофиксили. Вроде сайт не совсем развлекательный.
То же что в утро.ру. Слово в слово. С потерянными степенями. Автопереводчики их наверно теряют при копировании.
Если доживем до взлома RSA или до решения P=NP, то наверное сможем почитать много развлекательных материалов в СМИ на эти темы. Журналисты будут догадываться, что происходит что-то важное, но не смогут понять что именно.
... А самое смешное во всей этой истории, что даже доказательства все еще не опубликованы.
SecurityLab исправились, хоть на том спасибо. А если кто настоящую телегу хочет, читайте Lenta.ru. Цитат приводить не буду, наслаждайтесь.
http://www.lenta.ru/internet/2005/02/17/hash/
Да. Это все весело. Но где доказательства от китайцев? Хочу увидеть два разных файла с одинаковой SHA-1 суммой. Нет ни файлов (ну по числу операций это понятно), ни самой работы.
А то вдруг их там ихний ЦК КПК передумает и скажет, что ничего не было взломано.
Всё, что китайцы опубликовали на сегодняшний день, это http://theory.csail.mit.edu/~yiqun/shanote.pdf
От этой ссылки растут все ноги.
Больше от китайцев вестей не было. Я написал Yiqun Lisa Yin письмо, но на ответ не очень расчитываю ;)
Как всегда... Самое вкусное оставляют на десерт.
Интересно, а как будет выглядеть ID нового ключа и как его отличить от старого?
Кстати в рассылке ietf-openPGP обсуждается еще одно интересное предложение: добавлять к подписываемому документу (файлу) случайные данные. Это простой и обоснованный протокол, позволяющий избежать воздействия специально сгенерированных третьей стороной коллизий в подписях. (Что теоретически может привести даже к раскрытию секретного ключа – оснований для паники, как всегда никаких нет – это к сегодняшним слабостям SHA вообще не имеет отношения, но момент важный).
А с другой стороны – любые случайные данные – это скрытый канал, что многим пользователям не нравится.
ID, отпечаток, S2K будут по-прежнему вычисляться по SHA-1. На SHA-2 пока переводят только электронную подпись. Формат ключей v4 к таким изменениям просто не приспособлен.
Пару лет назад, когда только планировали будущий переход на формат v5, ожидалось, что в нём для всех этих протокольных целей будет применяться SHA-2. Сейчас, учитывая, что SHA-2 тоже в один прекрасный день может стать горячей сковородкой, сомневаюсь, что на роль обязательного хэша возьмут именно его.
Уже забраковали. :) Тут я с разработчиками солидарен — любое усложнение не на пользу стандарту. Такие вещи должны быть оставлены на усмотрение авторов программных реализаций. Вообще простой способ, как не пасть жертвой злоумышленника, — это всегда вносить незначительные изменения в начало предложенного к подписанию документа. Так, если оппонент и изготовил пару, производящую коллизию, хэш-значение подписанного файла будет уже другим.
А если мы подписываем архив или бинарник?
А если должны подписать много людей (отделенными подписями)?
Каждый должен к своей подписи приложить patch "для незначительных изменений" что-ли?
Или прикладывать эту строку тоже в отделенном виде?
В том то и дело, что "рандомизация" документов должна быть автоматизирована, а подписи с рандомизированными строками должны иметь устоявшийся формат.
Кстати, тема голосования на главной странице, где упомянута возможность внесения ГОСТ-хэша как приложения к стандарту приобрела еще один ироничный подтекст. ;-)
Вот еще первоисточники про RIPEMD.
Авторы RIPEMD утверждают, что их алгоритм предпочтительнее, чем SHA (было бы странно, если бы было наоборот).
http://www.esat.kuleuven.ac.be.....ripemd160.html#SHA-1[link3]
Хотя в дизайне RIPEMD есть некоторые решения, увеличивающие его стойкость, в целом он похож и на SHA и на MD5.
Что сейчас есть из хэшей – сводная таблица:
http://planeta.terra.com.br/in.....arreto/hflounge.html[link4]
[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.
]>
Короче, опубликуют работу в мае, когда отредактируют в соответствии с комментариями рецензентов.
Хорошо хоть ориентировочно со сроками определились. Когда я ей писал, она мне кроме "in the process" ничего толком сказать не могла ;)
Кстати, я-таки собрал все маразмы СМИ по поводу SHA-1: http://www.livejournal.com/users/denish_labs/
SATtva, спасибо за комментарий в блоге ;)
Не возражаете, если я, сославшись на вас, напишу о том, что результаты китайцы планируют опубликовать в мае?
Be my guest, как говорят бледнолицые братья. Не имею ничего против.
Спасибо ;)
Какова все таки безопасность практического применения SHA1 в свете описанных событий и в составе старых версий PGP? Версия 9 предлагает замену "ослабленной" функции на новую?
Практически это еще безопасно, но "под ней уже земля горит".
Новую еще не придумали. Есть кандидаты на звание коллизионно-стойкой функции (Whirlpool и др. совсем уж малоизвестные), но никто об этом на уровне стандарта еще не договорился.
Опубликован полный документ китайцев по криптоанализу SHA-1: "Finding Collisions in the Full SHA-1"[link5]. Представили ещё до августовского CRYPTO'2005.
... А это были наши новости:
http://www.pgpru.com/news/crypto/200507.shtml#1708
Уважаемые. Есть вопрос про частные случаи MD5.
Читал про прогу, которая генерит самораспаковывающие архивы с одинаковых хэшем. А насколько реально сущестование (написание) программы, которая генерировала бы быстро и много (секунды) небольшие (200-500 байт) файлы с одинаковым хэшем, с одинаковой длиной, но с разным содержанием однако во всех файлах обязательно должна быть часть, которая ни в одном из файлов не должна меняться?
Спасибо.
http://www.darksideprogramming.....ptography/index.html[link6]
У автора есть ссылки на готовые коды и работы по этим вопросам.
Реально можно сгенерировать "хороший" исходник или пакет, дать его на подпись дистрибьютеру, а затем подменить троянской версией. Это может сделать автор программы и это разновидность скорее "социальной" атаки. Обе программы ("хорошая" и "плохая" должны быть созданы заранее до подписания). И уже после подписания можно их подменять. Что-то вроде вытаскивания лишнего козырного туза из рукава в карточной игре.
Эта ссылка сейчас не работает, ищите в гуглях и нет-архивах:
http://www.codeproject.com/useritems/HackingMd5.asp
Вполне реально. Читайте работы Властимила Климы.
Это может угрожать некоторым системам, где такая ситуация предусмотрена не была и флуд такими файлами или сертификатами на основе их хэшей может вызвать сбой.
И ещё вопрос к специалистам по MD5
допустим есть строка А причем А = Б+С
допустим к строке Б уже найдены коллизии, следует из этого что найти коллизию к строке A будет значительно легче и быстрее.
Как изменится скорость нахождения коллизии к строке A – если коллизии будут уже найдены не к Б, а к С
Если Б — это коллизирующий блок прообраза, то А будет коллизировать независимо от того, с чем конкатенирована Б. То есть А может быть равно Б+С, Б+В, Б+Д, но если Б дают коллизию, то и А во всех случаях будет давать коллизию. На этом свойстве, вытекающем из особенностей MD4-подобных алгоритмов хэширования, основаны все нынешние демонстрационные атаки. В большинстве случаев коллизирующий блок вообще взят из первой работы китайцев.
в таком случае... если на поиск коллизии (коллизирующего блока) уходит всего до 8 часов, то вполне возможно существование целой постоянно пополняемой базы этих коллизионных блоков. То есть если мы имеем целью иметь большое число строк с одинаковыми подписями, то нам лишь надо чтобы они "начинались" с известных нам блоков ?
И сразу тогда вопрос – может эта база коллизирующих блоков продается где-нибудь? И насколько реально например выполнения пожелания, чтобы коллизирующие блоки состояли из ограниченного набора символов, например только цифр(десятичных) и пробелов ?
А о чем собственно речь? Если 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:
Да, если у казино просчитано заранее куча таких блоков < 512 бит, то игроку добавлять свой пароль бесполезно.
Да, казалось бы лучше добавлять пароль игрока в начало, потому что тогда 128-битный буфер между блоками будет непредсказуемым для казино и тогда они не смогут воспользоваться заранее сгенерированными базами, в которых первый буфер заполняется вектором константы (конструкция Дамгарда-Меркла).
Но если "спины" будут во втором 512-битном блоке (а пароль в первом), то они могут найти правдоподобную коллизию и в нем, используя 128-битный буфер пароля, вычисленный из предыдущего блока. Если у них есть для этого время, то они могут создать базу под индивидуальный пароль игрока (это конечно гораздо дороже по ресурсам, но может пароль игрока предсказуем или не меняется от игры к игре и есть запас времени на такую подтасовку)?
Также были работы по нахождению коллизий в нескольких блоках одновременно, что тоже не внушает оптимизма.
Если почитать "Практическую криптографию" Шнайера-Фергюссона и главы про дефекты хэш-функций, то становится совсем грустно (и эти пророчества были написаны еще до событий 2004 года!)
Поскольку в случаях наподобие казино для хэширования небольших сообщений не нужно использовать потоковые вычисления, то можно использовать предложенный Шнайером-Фергюссоном исправленный вариант функций хэширования (хотя он пока не получил признания).
... Не прошло и года, как прогресс появился и в точности так, как и было предсказано.
Новости?
Хорошо, а что вы думаете относительно новых хэш-функций? С EnRupt, вродебы бы, более-менее ясно – найдены коллизи, однако на больших константах это уже не применимо. Шнайерская Skein заточена под x64, где имеет отличную производительность, может быть использована для генерации хэшей произвольной длины, втч. значительно больше чем внутреннее состояние. То же и с Keccak. Какие функции, на Ваш взгяд будут выбраны как SHA-3? И, самое интересное, как к примеру Skein и Keccak обеспечивает безопасноть, скаже, при генерации хэша длиной 2048-16384 бит? Ведь размер внутреннего состояния у них 1024/1024 бит?
Keccak интересен своей структурой Sponge:
Где как раз придуман очень простой и изящный способ, как из стойкой функции f получать выход любой длины из входа любой разумной длины. Можно хоть вместо потокового шифра использовать. При этом дано самое аккуратное доказательство, что такая структура максимально близка к случайному оракулу. Даже если сам хэш будет неудачен из-за предложенной авторами функции f, то изобретение структуры Sponge вместо Дамгарда-Меркла – очень интересно и перспективно. Keccac – вполне хороший кандидат на финал.
Из чисто академического интереса, любопытными показались Edon и NaSHA, но только потому, что в серьёзной криптографии наконец-то стали рассматривать квазигруппы, по которым накапливается много теоретических работ. хотя Edon неуниверсален, NaSHA тоже и ещё запутана и громоздка и сами по себе они могут быть нестойкими, скорее всего их не выберут.
Пишут тут[link7] что-то новенькое, дескать, сложность поиска коллизий в SHA-1 удалось свести до 252 операций. unknown, Вы держите руку на пульсе, можно это прокомментировать?
интересно, посмотрим, когда она там появится и прокомментируем
http://www.youtube.com/watch?v=4WtF_O7XLMQ
Дурдом. Но весело.
http://forums.devshed.com/secu.....at-2-52t-608000.html[link8]
Вот заметка руководителя одного из авторов:
http://lukenotricks.blogspot.c.....-reduced-to-252.html[link9]
Это краткий анонс работы, которая не была готова к конференции. Он прозвучал в коротком докладе на Rump Session. Поскольку авторы известные, то можно доверять этому результату и считать, что sha1 действительно имеет стойкость уже в пределах возможности практического взлома 252. ну кто-то может скопировать дифференциальные пути со слайдов и по ним восстановить, кто-то возможно видел черновики работы, большинство же ждёт её официальной публикации.
Кстати, в случае со взломом md5 от китайцев было похоже – сначала был объявлен результат без доказательств, затем представлены доказательства в виде файлов с коллизиями, затем метод вкратце и затем полная работа, а дальше все кто-мог это анализировали и развивали дальше.
Никогда не знал, что конференции по криптографии проходят в таком формате :))
Вопрос для специалистов:
Есть контроллер электромагнитного замка работает на алгоритме SHA-1 с ключами DS1961S.
Здесь в основном обсуждаются колизии для электронных подписей, что в данном примере для DS1961S не имеет практического значения.
Вопрос – если есть например 10 исходных(512бит но без пароля) данных и 10 дайджестов(160бит – результат после обработки хеш функции ) к ним соответственно, можно ли в обозримом будущем вычислить пароль(64бит) находящейся в ключе?
СПАСИБО.
Что-то типа этого?
H1 = SHA1 ( D1 || x ), ..., H_10 = SHA1 ( D_10 || x )
Опять я чего-то туплю с разметкой нижних индексов. Не помогают двойные кавычки во второй части.
Где Di || x — 448 бит данных и 64 бита секрета.
Первое что приходит на ум — сбрутфорсить эти 64 бита, что не так уж сложно. Размер выхода самой хэш-функции и её стойкость при этом значения не имеет и достаточно одной пары {Hi, Di}. Провести 64 битный взлом не так сложно.
Расставляйте пробелы — в одном неразделённом пробелом инстэнсе может быть не более одной нераздельной группы нижних и не более одной нераздельней группы верхних индексов, максимум — это что-то типа XYZxyzXYZxyz. Контравариантные и ковариантные индексы будут коряво получаться, но, пожалуй, пока без них можно обойтись.
X rjklm n.
Да, при втором верхнем приходится пробел добавлять, как ни крути.
New Collision Attack Lowers Cost of Breaking SHA1[link10]
Но коллизии у них пока чисто академические, они выбирают константы (IV) вне стандарта.
Ничего, скоро от коллизий на 16-ричных keyid'ах[link11] перейдут к коллизиям на полные PGP-отпечатки, а там и до полного прообраза недалеко, благо
На самом деле, последние полгода рабочая группа OpenPGP весьма оживилась: обсуждаются и айдишники под SHA-3, и новый формат отпечатков, и ряд других фич, дорабатывающих стандарт (предполагается именно ревизия, а не написанная с нуля новая спецификация).
А SHA-1 таки поломали практически: https://shattered.it/
Я только пока не понял, есть ли там что-то новое с криптографической точки зрения. Заявленное число вычислений – это в точности 2^63, т.е. соответствует вычислительной сложности теоретической атаки китайцев 2005 года. Похоже, они просто довели её до практического исполнения.
джвенаднацть лет ждали!!! ;)
Update: https://eprint.iacr.org/2017/190.pdf