17.12 // Анонс пяти финалистов конкурса хэш-функции SHS/SHA-3 от НИСТ


В качестве оценки состояния дел в ситуации с созданием стойких симметричных алгоритмов можно привести цитату группы известных исследователей из недавней публикации "Малозатратные атаки на AES"[link1]:

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


В такой непростой ситуации проходит конкурс на создание нового стандарта (SHS) для хэш-функции SHA-3.

В начале декабря НИСТ (Национальный Институт Стандартов и Технологий США) провёл голосование, в ходе которого были определены пять финалистов, из которых кто-то один станет стандартом хэширования. Вероятно даже те, которые стандартом не станут, также получат некоторое распространение. Выборы хэш-функции SHA-3 и оглашение стандарта намечено на середину 2012 года.

Заявление о результатах голосования по раунду финалистов НИСТ отправил в рассылку 9 декабря, а 13 декабря выложил в открытый доступ на своём сайте.

Ниже приведён перевод этого письма.



НИСТ выбрал пять кандидатов на алгоритм SHA-3, которые прошли в третий (и финальный) раунд:


Выбор был сложным, поскольку у нас был серьёзный набор из четырнадцати хэш-алгоритмов, представленных на конкурс SHA-3, которые были очень сильными соперниками на место стандарта хэш-функции. Самое большое беспокойство у нас вызывала их безопасность, и мы отнеслись к этому очень серьёзно, но ни один из кандидатов не был явным образом взломан. Однако, нет смысла говорить о стойкости хэш-функции в отрыве от производительности, так что на самом деле НИСТ хотел бы, чтобы алгоритмы с высочайшим уровнем стойкости также были и достаточно производительными. Мы предпочли быть консервативными в плане стойкости и в некоторых случаях не выбрали алгоритмы с выдающейся производительностью, главным образом потому, что они заставили нас "понервничать", даже если мы знали, что никакой явной атаки на полный алгоритм нет.

Производительность многомерна: никакой алгоритм не является лучшим в каждом из измерений. Каждый кандидат второго раунда достиг по крайней мере приемлемого уровня производительности на лидирующих десктопных и серверных системах, хотя уровни производительности значительно отличаются. Ещё больше разницы на ограниченных платформах и в аппаратном исполнении, в такой области, где наиболее важным фактором производительности является скорость. Множество алгоритмов ухудшило свою привлекательность или было отвергнуто за счёт очень больших требований к объёму — стало заметно, что требуемый ими объём не позволяет использовать их в достаточно большом числе потенциальных приложений. Некоторые алгоритмы позволяли очень высокий уровень тонко спланированного параллелизма, который мог бы быть реализован в аппаратном исполнении, некоторые использовали параллелизм векторных устройств, другие выглядели способными полностью эксплуатировать значительный параллелизм конвенциональных суперскалярных арифметико-логических устройств (АЛУ), которые могут одновременно запускать множество инструкций за один вычислительный шаг. Многие алгоритмы также использовали мощь 64-битных АЛУ.

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

Некоторые команды анонсировали изменения, которые они согласились бы сделать, если бы их избрали в финальный раунд. НИСТ изучал заявки второго раунда, но не предполагаемые изменения. Однако мы согласились бы, если бы лучшие атаки против некоторых из алгоритмов-кандидатов требовали бы простой модификации.

НИСТ также рассматривал сохранение различий при выборе финалистов. Выбранные пять финалистов включают в себя некоторое количество новых идей проектирования, которые возникли в последние годы, такие как конструкции HAIFA и sponge. Финалисты включают в себя дизайн, основанный на нелинейности S-блоков AES или меньших (4 и 5-битных), эффективно выполняемых в виде последовательности базовых логических инструкций, или как взаимодействие операций сложения и XOR.

НИСТ выражает благодарность всем заявителям всех четырнадцати кандидатов второго раунда. Каждый кандидат второго раунда представлял собой высокопрофессиональную попытку и каждый кандидат имел сильные стороны для того, чтобы его было можно рекомендовать. Мы также благодарим множество частных лиц и организаций, которые помогали в криптоанализе кандидатов или предоставляли данные по производительности их собственного исполнения алгоритмов-кандидатов. Эти выборы были бы невозможны без их помощи.

НИСТ опубликует отчёт о выборах финалистов SHA-3 в ближайшем будущем, который раскроет обоснования выборов на базе сравнительного анализа алгоритмов.

Если будут рассматриваться изменения к третьему раунду, то следует подавать заявления до 16 января 2011 года. Специфические требования к заявлениям будут предоставлены разработчикам пяти финалистов SHA-3.

Билл (Уильям) Бёр, менеджер группы криптографических технологий НИСТ.

Источник: NIST cryptographic hash Algorithm Competition[link2]

Ссылки
[link1] http://eprint.iacr.org/2010/633

[link2] http://csrc.nist.gov/groups/ST/hash/sha-3/index.html