id: Гость   вход   регистрация
текущее время 13:09 28/03/2024
Владелец: unknown (создано 17/12/2010 14:26), редакция от 22/12/2010 13:03 (автор: sentaus) Печать
Категории: криптография, алгоритмы, хэширование, стандарты, разное, события
https://www.pgpru.com/Новости/2010/АнонсПятиФиналистовКонкурсаХэш-функцииSHSSHA-3ОтНИСТ
создать
просмотр
редакции
ссылки

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


 
На страницу: 1, 2 След.
Комментарии [скрыть комментарии/форму]
— Гость (17/12/2010 19:18)   <#>
Где то, кажется даже на здешнем форуме читал что при выборе функции в качестве стандарта большой уклон будет делаться в сторону модели случайного оракула. Не могли бы пояснить что это значит. В смысле что бубуд выбирать хеш-функцию наиболее похожую на оракул? И как если это так в таком случае определяется какая похожа больше а какая меньше?
— unknown (17/12/2010 21:45, исправлен 17/12/2010 21:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Ну где же ещё ;-). Вот ещё последние требования НИСТ перед началом конкурса, но там оракул не упоминается.


Несмотря на скептицизм ортодоксальных криптографов, даже непрактичные атаки в ROM учитывались. Это означает, что одних только требований отсутствия коллизий, нахождения второго прообраза и неинвертируемости на малом множестве недостаточно. Любой, самый надуманный и искусственный различитель от RO принимался во внимание при оценке стойкости на всех этапах конкурса.


Даже авторам Keccak, который всё-таки прошёл в финалисты, пришлось отдуваться за атаки с нулевой суммой.


Это когда подбирается масса сообщений, в которых сумма всех битов равна нулю, а функция от этих битов по сумме тоже близка к нулю. Нашли способ такой "атаки" аж за 21369 шагов. И ещё какие-то частичные суммы.


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

— Гость (18/12/2010 18:53)   <#>
Вот же удивительно. Как поменялось то все в мире криптографии с этой моделью случайного оракула. Я еще понимаю когда доказательство в ROM принимают для асимметричной криптографии, там изначально вся стойкость на предположениях основывается, но когда доказуемую стойкость распространяют на блочные шифры, этого я не могу понять, есть же вполне зарекомендовавшие себя методы криптоанализа, к чему все усложнять всеми этими эвфимерными различителями. Вот скажем нашли они различитель для AES, тоже у вас на сайте об этом писали. Так и что, он от этого менее безопасен же не стал с практической точки зрения. Хотя возможно я просто не понимаю преимуществ, которые дает модель случайного оракула.
— Гость (18/12/2010 22:40)   <#>
Так и что, он от этого менее безопасен же не стал с практической точки зрения.
Может и стал, может и нет, но при прочих равных — это тревожный звонок, потому и. Есть примеры когда различители потом дорабатывались до практичных атак.
— unknown (19/12/2010 13:27, исправлен 19/12/2010 13:39)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Вот же удивительно. Как поменялось то все в мире криптографии с этой моделью случайного оракула.

Поменялось, действительно сильно. Но не все с этим согласны. Например, криптографы израильской школы (и не только они конечно) эту модель критикуют по нескольким направлениям:


  1. "Постмодернизм". Заманчивая возможность собрать любой протокол, не задумываясь о свойствах уже готовых криптопримитивов-кирпичиков. При этом примитивы считаются идеальными и их свойства не учитываются. Чему были приведены контрпримеры, правда не слишком убедительные.
  2. Распыление сил на надуманные атаки и пустое, якобы, теоретизирование. В качестве контрмер в одной из статей предлагалось измерять атаки даже не в затратах выч. ресурсов, а в деньгах. В статье, которая вынесена в эпиграф к данной новости, авторы предлагают атаки на AES за несколько пар текстов. Якобы такие атаки — это заведомо практичное направление. Но всё, что они пока доказали, что с увеличением числа раундов эти атаки также непрактичны, как и "теоретически-надуманные".
  3. Недоказанность возможности построения криптопримитива без различителей. Невыясненность их числа. Если доказано, что против n различителей алгоритм стоек, не появится ли n+1-ый различитель (заведомая неполнота моделей стойкости, как бы их не совершенствовали)? Впрочем это же касается и вариантов практичных атак, но там достаточно найти хотя бы одну. А по различителям — если их больше, то алгоритм хуже? Или просто так искали?

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


Я еще понимаю когда доказательство в ROM принимают для асимметричной криптографии

Там как раз стараются от него по возможности избавиться. И с гордостью пишут в работах — "доказательство стойкости протокола X в стандартной модели без RO". Но поскольку асимметричные протоколы смешанные (с симметричными примитивами), то без RO обойтись трудно.


когда доказуемую стойкость распространяют на блочные шифры, этого я не могу понять, есть же вполне зарекомендовавшие себя методы криптоанализа

Доказуемая стойкость <не равно> ROM, она включает в себя и стандартную модель безопасности. Но для блочных шифров это фактически RO- или PRP-неразличимость (ROM и ICM). Pseudo Random Function, Pseudo Random Permutation, Random Oracle Model, Ideal Cipher Model — для тех кто хочет запомнить.


Удивительно, что ROM стали использовать не только для построения протоколов (для чего его изначально и приспособили), но и для анализа внутренней структуры криптопримитивов


Вот скажем нашли они различитель для AES <...>Так и что, он от этого менее безопасен же не стал с практической точки зрения.

Может и стал, может и нет, но при прочих равных — это тревожный звонок, потому и. Есть примеры когда различители потом дорабатывались до практичных атак.

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


Опять же, верно подмечено, что любая практичная атака может начаться с поиска различителя. Ну вот представьте, есть два криптопримитива, оба практически пока одинаково стойкие, "серьёзных" атак неизвестно. Но для одного уже известны различители от идеальной модели. Может и для второго когда-то что-то найдут, но для первого уже нашли. А для второго доказали, что именно эти различители не работают. Какой криптоалгоритм лучше отбросить в конкурсе?

— Гость (19/12/2010 16:46)   <#>
Спасибо за развернутое пояснение. Прям краткое изложение теории случайного оракула для чайников:)
— unknown (19/12/2010 16:59)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Когда есть возможность — всегда пожалуйста :) Эта тема часто обсуждалась в форуме и вероятно будет возникать и дальше, когда возникают вопросы о фундаментальных принципах современной криптографии.

Объяснения, которые даны здесь и в FAQ составлены в максимально популярной форме, совсем на пальцах. Они разумеется в общем верны, но на строгость, академичность и формальную полноту не претендуют.
— unknown (22/12/2010 13:17, исправлен 22/12/2010 13:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

2 SATtva: а чем не понравился вариант написания, близкий к оригинальному: Grøstl?


Grøstl is an Austrian dish, usually made of leftover potatoes and pork, cut into slices. These are roasted on a pan together with onions and butterfat. The dish is often seasoned with salt, pepper, marjoram, cumin, and parsley, and served with a fried egg or kraut (cabbage). Hence, grsøtl is somewhat similar to the American dish called hash.
The letter `o' was replaced by `ø', which is a letter in the Danish alphabet that is pronounced in the same way as `o'. This way, the name, like the hash function itself, contains a mix of Austrian and Danish influences.
— unknown (22/12/2010 13:21, исправлен 22/12/2010 13:23)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Кажется понятно, после редактирования движок съедает такие символы. Например, если отредактировать сообщение с этим знаком, то он превратится в "щ" и ещё неизвестно как отображается в разных браузерах :(

— SATtva (22/12/2010 13:29)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Да, именно. Вообще, если ввести такой символ как html-entity, он сохранится и будет отображаться корректно. Но после правки действительно преобразуется в кириллицу. Причина в том, что движок работает не на utf-8.
— Гость (22/12/2010 16:28)   <#>
Grøstl
Я предлагаю писать через математические html-коды: есть симолы
которые на печати дают, соответственно, Gr∅stl и Gr⊘stl. Несколько странно, что
  • выделение двойными кавычками не работает при квотинге таких символов (чтобы передать их как коды).
  • при повторном редактировании html-код превращается в символ (за исключением заключённого в двойные проценты).
— Гость (22/12/2010 16:28)   <#>
за исключением заключённого в двойные проценты
А вот это когда как. Часто и в них тоже.
— unknown (22/12/2010 17:18, исправлен 22/12/2010 17:21)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

У авторов в заявке в НИСТ написано некий другой HTML-код:


При вставке этого кода, он и у нас в поле редактирования превращается в этот символ — при предпросмотре, при постинге в теге кода нормально, а при повторном редактировании — опять 'щ'.
Из-за таких проблем НИСТ его глядишь не примет! :)


P.S. Лично мне было бы интереснее всего увидеть стандартом Keccac, на втором месте — Skein, остальные тоже хороши (кроме JH). Интересно будет почитать сравнительный отчёт НИСТ.

— Гость (22/12/2010 17:29)   <#>
движок работает не на utf-8.
⨌ы! Κ⊘н∈чн⊘, ∍τ⊘ ∏⊘∍⊘ρъ :〈 ∋α ταк≬∈ нα∂⊘ ⊺, ⊂α≉ατь нα Ψ, нα ⊥ υ⋏υ в ⊞, α н∈ ∏∞ψρяτь — ⋔ατ∈⋔ατυч∈⊂кυ∈ кρυ∩τ⊚∩αнкυ ταк⊘∫⊘ н∈ ∩ρ⊘⊂τяτъ :〉 ∪∩k∩⊘ψ∩ ⋔∈ня ∩∅∂∂∈ρ≉υτъ.∎
— SATtva (22/12/2010 17:32)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Κ⊘н∈чн⊘, ∍τ⊘ ∏⊘∍⊘ρъ :〈

Ничего, Вы неплохо справляетесь. :)
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3