Национальный институт стандартов и технологий США (англ. National Institute of Standards and Technology, сокращённо NIST) создал конкурс на новую хеш-функцию, названную SHA-3, для дополнения и дальнейшей замены старых функций: SHA-1 и SHA-2. Конкурс был анонсирован в журнале Federal Register 2 ноября 2007 года.^[1] NIST инициировал разработку одного или нескольких дополнительных алгоритмов хеширования через открытый конкурс, подобный процесс развития был использован ранее для шифрования Advanced Encryption Standard (сокращённо AES).^[2]

Конкурс завершился 2 октября 2012 года, когда NIST объявил, что Keccak будет новым SHA-3 хеш-алгоритмом.^[3]

Цели конкурса

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

Процесс

Подача заявок была завершена 31 октября 2008 года. Список кандидатов, прошедших в первый раунд, был опубликован 9 декабря 2008 года.^[4]В конце февраля 2009 года NIST провели конференцию, где представили заявленные в конкурс хеш-функции и обсудили критерии прохождения во второй раунд.^[5] Список из 14 кандидатов, прошедших в раунд 2, был опубликован 24 июля 2009 года.^[6]Еще одна конференция состоялась 23 и 24 августа 2010 года в University of California, Santa Barbara, где были рассмотрены кандидаты, прошедшие во второй раунд.^[7] О последнем туре кандидатов было объявлено 10 декабря 2010 года.^[8] И только 2 октября 2012 года NIST объявил победителя - Keccak, его создатели: Guido Bertoni, Joan Daemen, Gilles Van Assche из STMicroelectronics и Michaël Peeters из NXP.^[3]

Критерии оценки

В своих отчетах NIST описывает критерии оценки конкурсантов. Основными критериями оценки были безопасность, производительность и алгоритм хеш-функции^[9][10][11].

Безопасность

Рассматривая безопасность конкурсантов, NIST оценивал применимость хеш-функции, её устойчивость к атакам, соответствие общим для хеш-функций требованиям, а также соответствие требованиям для участников, использующих HMAC, псевдослучайные функции или рандомизированное хеширование. Этот критерий учитывался в первую очередь.

Производительность

Производительность — второй по важности критерий оценки после безопасности. При его проверке смотрели на скорость работы и требования к памяти. Сравнение происходило следующим образом:

• В брэнчмарке ECRYPT Benchmarking of All Submitted Hashes (сокращёенно eBASH) производились замеры скорости вычисления для большого числа 32х и 64х-битных платформ.
• Брэнчмарк eXternal Benchmarking eXtension (сокращённо XBX) предоставил результаты для портативных устройств.
• Дополнительно проверялась производительность и возможность оптимизации на многоядерных архитектурах. Тесты производились на архитектурах Cell Broadband Engine (сокращённо Cell) и the NVIDIA Graphics Processing Units (сокращённо GPUs).^[12]

Также оценивалась скорость работы на конечных устройствах: ПК, мобильных устройствах (точки доступа, роутеры, портативные медиаплееры, мобильные телефоны и терминалы оплаты) и в виртуальных машинах.^[13]

Алгоритм и характеристики реализации

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

Участники

NIST выбрали 51 хеш-функцию в первый тур.^[4] 14 из них прошло во второй раунд,^[6] из которых было выбрано 5 финалистов. Неполный список участников представлен ниже.

Победитель

Победитель был объявлен 2 октября 2012 года, им стал алгоритм Keccak.^[14] Он стал самым производительным на аппаратной реализации среди финалистов, а также в нем был использован нераспространённый метод шифрования - функция Губка. Таким образом, атаки, рассчитанные на SHA-2, не будут работать. Ещё одним существенным преимуществом SHA-3 является возможность его реализации на миниатюрных встраиваемых устройствах (например, USB-флеш-накопитель).

Финалисты

NIST выбрал пять кандидатов, прошедших в третьей (и последний) тур:^[15]

• BLAKE
• Grøstl
• JH
• Keccak
• Skein

NIST описали некоторые критерии, на которых основывался выбор финалистов:^[16]

• Производительность: «Некоторые алгоритмы были уязвимы из-за очень больших требований к производительности.»^[16]
• Безопасность: «Мы предпочли быть консервативными в безопасности и в некоторых случаях не выбрали алгоритмы с исключительной производительностью, потому что они менее безопасны в значительной степени.»^[16]
• Анализ: «NIST устранено несколько алгоритмов из-за неполной проверки или незрелости проекта.»
• Разнообразии: «Хеш-функции, прошедшие в финал, основаны на различных режимах работы, в том числе и на принципе криптографической губки. С разными внутренними структурами, в том числе на основе AES, Bit slicing и на переменных XOR с дополнением.»^[16]

NIST выпустил отчет, поясняющий оценку алгоритмов.^[17][18]

Хеш-функции, не прошедшие в финал

Следующие хеш-функции попали во второй раунд, но не прошли в финал. Также было при объявлении финалистов: «Ни один из этих кандидатов не был явно взломан». В скобках указана причина, по которой хеш-функции не стала финалистом.

Хеш-функция, не прошедшие во второй раунд

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

Заявленные хеш-функции с существенными уязвимостями

Непрошедшие в первый раунд хеш-функции имели существенные криптографические уязвимости.

Отказавшиеся конкурсанты

На протяжении первого раунда некоторые конкурсанты сами отказались от участия в конкурсе, потому что были взломаны на NIST official Round One Candidates web site. Они не принимали участия в конкурсе.

Отклоненные участники

Некоторые хеш-функции не были приняты в качестве кандидатов, после внутреннего обзора NIST.^[4] NIST не сообщил подробностей относительно того, почему эти кандидаты были отклонены. NIST также не дала полный список отклоненных алгоритмов, но 13 из них известны,^[4][71]но только следующие из них были опубликованны.

• HASH 2X^[72][73]
• Maraca^[74][75]
• NKS 2D^[76][77][78]
• Ponic^[79][80]
• ZK-Crypt^[81]

Классификация кандидатов

В таблице перечислены известные участники конкурса с указанием основных атрибутов хеш-функций и найденных атак.^[82] В ней используются следующие аббревиатуры:

• FN англ. A Feistel network - Сеть Фейстеля;
• WP англ. Wide Pipe design - метод построения криптографических хеш-функций, похожей на Структура Меркла — Дамгарда;
• KEY англ. en:Key schedule - алгоритм, получающий ключи для каждого раунда хеширования;
• MDS англ. MDS Matrix - Размер MDS матрицы;
• OUT англ. Output Transformation - криптографическая операция, осуществляемая в последней выходной итерации;
• SBOX англ. S-box - S-блоки;
• FSR англ. Feedback Shift Register - Регистр сдвига с линейной обратной связью;
• ARX англ. Addition Rotation XOR - сложение, циклический сдвиг и XOR;
• BOOLангл. Boolean operations - Булева алгебра;
• COL англ. Collision Attack - самая лучшая из известных атак на поиск коллизий, лучше чем атаке «дней рождения»;
• PRE англ. Preimage Attack - вторая лучшая атака на поиск коллизий, лучше чем en:Length extension attack;

Ссылки