17.12 // Анонс пяти финалистов конкурса хэш-функции SHS/SHA-3 от НИСТ
В качестве оценки состояния дел в ситуации с созданием стойких симметричных алгоритмов можно привести цитату группы известных исследователей из недавней публикации "Малозатратные атаки на AES":
... практические атаки на блочные шифры стали невероятно редкими и даже "сертификационные атаки" (такие, которые не являются практичными, но всё ещё быстрее простого перебора ключей для полной версии шифра) не являются рядовым событием. При этом следует отметить, что в области потоковых шифров и хэш-функций ситуация отличается драматическим образом. Множество обычно использовавшихся хэш-функций взломано в последние годы путём практического криптоанализа, а практические атаки на потоковые шифры случаются каждые несколько месяцев.
В такой непростой ситуации проходит конкурс на создание нового стандарта (SHS) для хэш-функции SHA-3.
В начале декабря НИСТ (Национальный Институт Стандартов и Технологий США) провёл голосование, в ходе которого были определены пять финалистов, из которых кто-то один станет стандартом хэширования. Вероятно даже те, которые стандартом не станут, также получат некоторое распространение. Выборы хэш-функции SHA-3 и оглашение стандарта намечено на середину 2012 года.
Заявление о результатах голосования по раунду финалистов НИСТ отправил в рассылку 9 декабря, а 13 декабря выложил в открытый доступ на своём сайте.
Ниже приведён перевод этого письма.
НИСТ выбрал пять кандидатов на алгоритм SHA-3, которые прошли в третий (и финальный) раунд:
- BLAKE
- Grostl
- JH
- Keccak
- Skein
Выбор был сложным, поскольку у нас был серьёзный набор из четырнадцати хэш-алгоритмов, представленных на конкурс SHA-3, которые были очень сильными соперниками на место стандарта хэш-функции. Самое большое беспокойство у нас вызывала их безопасность, и мы отнеслись к этому очень серьёзно, но ни один из кандидатов не был явным образом взломан. Однако, нет смысла говорить о стойкости хэш-функции в отрыве от производительности, так что на самом деле НИСТ хотел бы, чтобы алгоритмы с высочайшим уровнем стойкости также были и достаточно производительными. Мы предпочли быть консервативными в плане стойкости и в некоторых случаях не выбрали алгоритмы с выдающейся производительностью, главным образом потому, что они заставили нас "понервничать", даже если мы знали, что никакой явной атаки на полный алгоритм нет.
Производительность многомерна: никакой алгоритм не является лучшим в каждом из измерений. Каждый кандидат второго раунда достиг по крайней мере приемлемого уровня производительности на лидирующих десктопных и серверных системах, хотя уровни производительности значительно отличаются. Ещё больше разницы на ограниченных платформах и в аппаратном исполнении, в такой области, где наиболее важным фактором производительности является скорость. Множество алгоритмов ухудшило свою привлекательность или было отвергнуто за счёт очень больших требований к объёму — стало заметно, что требуемый ими объём не позволяет использовать их в достаточно большом числе потенциальных приложений. Некоторые алгоритмы позволяли очень высокий уровень тонко спланированного параллелизма, который мог бы быть реализован в аппаратном исполнении, некоторые использовали параллелизм векторных устройств, другие выглядели способными полностью эксплуатировать значительный параллелизм конвенциональных суперскалярных арифметико-логических устройств (АЛУ), которые могут одновременно запускать множество инструкций за один вычислительный шаг. Многие алгоритмы также использовали мощь 64-битных АЛУ.
Никакой из алгоритмов, дошедших до этапа финалистов, не позволяет легко подстраивать ясную структуру раунда в обмен безопасности на производительность. НИСТ отклонил множество алгоритмов, поскольку их авторы продолжали допускать изменения на протяжении второго раунда или по причине относительной нехватки криптоанализа, который бы подтвердил полную протестированность и зрелость дизайна. НИСТ главным образом допускал мелкие изменения, касающиеся числа раундов или связанные с константами, но был более подозрителен к изменениям, которые выглядели затрагивающими структуру функции сжатия.
Некоторые команды анонсировали изменения, которые они согласились бы сделать, если бы их избрали в финальный раунд. НИСТ изучал заявки второго раунда, но не предполагаемые изменения. Однако мы согласились бы, если бы лучшие атаки против некоторых из алгоритмов-кандидатов требовали бы простой модификации.
НИСТ также рассматривал сохранение различий при выборе финалистов. Выбранные пять финалистов включают в себя некоторое количество новых идей проектирования, которые возникли в последние годы, такие как конструкции HAIFA и sponge. Финалисты включают в себя дизайн, основанный на нелинейности S-блоков AES или меньших (4 и 5-битных), эффективно выполняемых в виде последовательности базовых логических инструкций, или как взаимодействие операций сложения и XOR.
НИСТ выражает благодарность всем заявителям всех четырнадцати кандидатов второго раунда. Каждый кандидат второго раунда представлял собой высокопрофессиональную попытку и каждый кандидат имел сильные стороны для того, чтобы его было можно рекомендовать. Мы также благодарим множество частных лиц и организаций, которые помогали в криптоанализе кандидатов или предоставляли данные по производительности их собственного исполнения алгоритмов-кандидатов. Эти выборы были бы невозможны без их помощи.
НИСТ опубликует отчёт о выборах финалистов SHA-3 в ближайшем будущем, который раскроет обоснования выборов на базе сравнительного анализа алгоритмов.
Если будут рассматриваться изменения к третьему раунду, то следует подавать заявления до 16 января 2011 года. Специфические требования к заявлениям будут предоставлены разработчикам пяти финалистов SHA-3.
Билл (Уильям) Бёр, менеджер группы криптографических технологий НИСТ.
Источник: NIST cryptographic hash Algorithm Competition
комментариев: 9796 документов: 488 редакций: 5664
Ну где же ещё ;-). Вот ещё последние требования НИСТ перед началом конкурса, но там оракул не упоминается.
Несмотря на скептицизм ортодоксальных криптографов, даже непрактичные атаки в ROM учитывались. Это означает, что одних только требований отсутствия коллизий, нахождения второго прообраза и неинвертируемости на малом множестве недостаточно. Любой, самый надуманный и искусственный различитель от RO принимался во внимание при оценке стойкости на всех этапах конкурса.
Даже авторам Keccak, который всё-таки прошёл в финалисты, пришлось отдуваться за атаки с нулевой суммой.
Это когда подбирается масса сообщений, в которых сумма всех битов равна нулю, а функция от этих битов по сумме тоже близка к нулю. Нашли способ такой "атаки" аж за 21369 шагов. И ещё какие-то частичные суммы.
Придумайте любую, самую "надуманную" формулу, описывающую неслучайность. А затем доказательство, что в хэш-алгоритме такую неслучайность найти проще, чем в идеальной случайной функции. Вот и повод для подозрений в нестойкости в ROM.
комментариев: 9796 документов: 488 редакций: 5664
Поменялось, действительно сильно. Но не все с этим согласны. Например, криптографы израильской школы (и не только они конечно) эту модель критикуют по нескольким направлениям:
Вообще, в статье, которая приведена во введении к новости, авторы признают пользу теоретических атак. Потому что практические атаки на профессионально разработанные блочные шифры давно стали почти невозможными (в отличие от хешей и тем более потоковых шифров), а абстрактно-теоретические построения позволяют, по их словам, "расширить границы криптоанализа".
Там как раз стараются от него по возможности избавиться. И с гордостью пишут в работах — "доказательство стойкости протокола X в стандартной модели без RO". Но поскольку асимметричные протоколы смешанные (с симметричными примитивами), то без RO обойтись трудно.
Доказуемая стойкость <не равно> ROM, она включает в себя и стандартную модель безопасности. Но для блочных шифров это фактически RO- или PRP-неразличимость (ROM и ICM). Pseudo Random Function, Pseudo Random Permutation, Random Oracle Model, Ideal Cipher Model — для тех кто хочет запомнить.
Удивительно, что ROM стали использовать не только для построения протоколов (для чего его изначально и приспособили), но и для анализа внутренней структуры криптопримитивов
Строго это не доказано, но мнение большинства криптографов-теоретиков склоняется к "принципу тревожного звонка". Ну может кто-то выпустит большую работу с обоснованием критериев полноты моделей стойкости, так-же как с теорией PRF и PRP функций в 80-хх. Тогда можно это будет окончательно в учебники вписать. Но де-факто этот принцип уже используется.
Опять же, верно подмечено, что любая практичная атака может начаться с поиска различителя. Ну вот представьте, есть два криптопримитива, оба практически пока одинаково стойкие, "серьёзных" атак неизвестно. Но для одного уже известны различители от идеальной модели. Может и для второго когда-то что-то найдут, но для первого уже нашли. А для второго доказали, что именно эти различители не работают. Какой криптоалгоритм лучше отбросить в конкурсе?
комментариев: 9796 документов: 488 редакций: 5664
Объяснения, которые даны здесь и в FAQ составлены в максимально популярной форме, совсем на пальцах. Они разумеется в общем верны, но на строгость, академичность и формальную полноту не претендуют.
комментариев: 9796 документов: 488 редакций: 5664
2 SATtva: а чем не понравился вариант написания, близкий к оригинальному: Grøstl?
комментариев: 9796 документов: 488 редакций: 5664
Кажется понятно, после редактирования движок съедает такие символы. Например, если отредактировать сообщение с этим знаком, то он превратится в "щ" и ещё неизвестно как отображается в разных браузерах :(
комментариев: 11558 документов: 1036 редакций: 4118
которые на печати дают, соответственно, Gr∅stl и Gr⊘stl. Несколько странно, что
комментариев: 9796 документов: 488 редакций: 5664
У авторов в заявке в НИСТ написано некий другой HTML-код:
При вставке этого кода, он и у нас в поле редактирования превращается в этот символ — при предпросмотре, при постинге в теге кода нормально, а при повторном редактировании — опять 'щ'.
Из-за таких проблем НИСТ его глядишь не примет! :)
P.S. Лично мне было бы интереснее всего увидеть стандартом Keccac, на втором месте — Skein, остальные тоже хороши (кроме JH). Интересно будет почитать сравнительный отчёт НИСТ.
комментариев: 11558 документов: 1036 редакций: 4118
Ничего, Вы неплохо справляетесь. :)