«SHA-3» — конкурс Национального института стандартов и технологий (NIST) на новую криптографическую хеш-функцию, предназначенную для дополнения и замены SHA-1 и SHA-2. Проводился в течение в 2007—2012 годов, в результате был избран алгоритм для реализации SHA-3.

Официально объявлен в журнале Federal Register 2 ноября 2007 года. Подобный конкурсный процесс алгоритма был использован ранее для шифрования Advanced Encryption Standard («AES»). 2 октября 2012 года объявлены результаты: хеш-алгоритмом под наименованием SHA-3 стал алгоритм Keccak.

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

Процесс Подача заявок была завершена 31 октября 2008 года. Список кандидатов, прошедших в первый раунд, был опубликован 9 декабря 2008 года. В конце февраля 2009 года NIST провели конференцию, где представили заявленные в конкурс хеш-функции и обсудили критерии прохождения во второй раунд. Список из 14 кандидатов, прошедших в раунд 2, был опубликован 24 июля 2009 года. Ещё одна конференция состоялась 23 и 24 августа 2010 года в University of California, Santa Barbara, где были рассмотрены кандидаты, прошедшие во второй раунд. О последнем туре кандидатов было объявлено 10 декабря 2010 года. И только 2 октября 2012 года NIST объявил победителя — Keccak, его создатели: , Joan Daemen, из STMicroelectronics и из NXP.

В отчётах NIST описывались критерии оценки конкурсантов; основными критериями оценки были безопасность, производительность и алгоритм хеш-функции.

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

Производительность Производительность — второй по важности критерий оценки после безопасности. При его проверке смотрели на скорость работы и требования к памяти. Сравнение происходило следующим образом: В тесте ECRYPT Benchmarking of All Submitted Hashes (сокращённо ) производились замеры скорости вычисления для большого числа 32- и 64-битных платформ. Тест eXternal Benchmarking eXtension (сокращённо ) предоставил результаты для портативных устройств. Дополнительно проверялась производительность и возможность оптимизации на многоядерных архитектурах. Тесты производились на архитектурах Cell Broadband Engine (сокращённо Cell) и NVIDIA Graphics Processing Units (сокращённо GPU).

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

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

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

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

Финалисты NIST выбрал пять кандидатов, прошедших в третий (и последний) турTHIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011: BLAKE Grøstl JH Keccak Skein

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

Также был выпущен отчёт, поясняющий оценку алгоритмовStatus Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011.

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

Blue Midnight Wish (возможны проблемы с безопасностью) CubeHash (Bernstein) (проблемы с производительностью) ECHO (France Telecom) (проблемы с производительностью) Fugue (IBM) (возможны проблемы с безопасностью) Hamsi (высокие требования к ПЗУ, возможны проблемы с безопасностью) Luffa (возможны проблемы с безопасностью) Shabal (возможны проблемы с безопасностью) SHAvite-3 (возможны проблемы с безопасностью) SIMD (проблемы с производительностью, возможны проблемы с безопасностью)

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

ARIRANG (CIST — Korea University) CHI CRUNCH FSB Lane Lesamnta MD6 (Rivest et al.) SANDstorm (Sandia National Laboratories) Sarmal SWIFFTX TIB3

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

AURORA (Sony и Нагойский университет) Blender Cheetah Dynamic SHA Dynamic SHA2 ECOH Edon-R EnRUPT ESSENCE LUX MCSSHA-3 NaSHA Sgàil Spectral Hash Twister Vortex

Отказавшиеся конкурсанты На протяжении первого раунда некоторые конкурсанты сами отказались от участия в конкурсе, потому что были взломаны на веб-сайте первого раунда конкурса:

Abacus Boole DCH Khichidi-1 MeshHash SHAMATA StreamHash Tangle WaMM Waterfall

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

HASH 2X Maraca NKS 2D Ponic ZK-Crypt

Классификация кандидатов В таблице перечислены известные участники конкурса с указанием основных атрибутов хеш-функций и найденных атак. В ней используются следующие аббревиатуры: FN  — сеть Фейстеля; WP  — метод построения криптографических хеш-функций, похожий на структуру Меркла — Дамгора; KEY  — , получающий ключи для каждого раунда хеширования; MDS  — размер -матрицы; OUT  — криптографическая операция, осуществляемая в последней выходной итерации; SBOX  — S-блоки; FSR  — регистр сдвига с линейной обратной связью; ARX  — сложение, циклический сдвиг и XOR; BOOL — булева алгебра; COL  — самая лучшая из известных атак на поиск коллизий, лучше чем атаке «дней рождения»; PRE  — вторая лучшая атака на поиск коллизий, лучше чем атака удлинением сообщения;

Хеш-алгоритмFNWPKEYMDSOUTSBOXFSRARXBOOLCOLPREAbacus - X - 4 x 4 X 8 x 8 X - - ARIRANG X X X 4 x 4, 8 x 8 - 8 x 8 - - - - -AURORA - - X 4 x 4 X 8 x 8 - - - BLAKE X - X - - - - X — - - -Blender - X - - - - - X - BMW - X X - - - - X - - -*Boole - - - - X - X - Cheetah - - X 4 x 4, 8 x 8 - 8 x 8 - - - - -Chi X X X - - 4 x 3 - - , - -CRUNCH X - X - - 8 x 1016 - - - - -CubeHash8/1 - - - - - - - X - - *DHC - - X - - 8 x 8 - - - DynamicSHA X - X - - - - - , , -DynamicSHA2 X - X - - - - X , , - -ECHO - X - 4 x 4 - 8 x 8 - - - - -ECOH - - X - - - - - - - -Edon-R - X X - - - - X - - EnRUPT - X - - - - - X - - Essence - - - - - - X - - - -FSB - X - - X - - - - - -Fugue - X - 4 x 4 X 8 x 8 - - - - -Gr0stl - X - 8 x 8 X 8 x 8 - - - - -Hamsi - - X - - 4 x 4 - - - - -JH X X - 1.5 x 1.5 - 4 x 4 - - - Keccak - X - - - - - - , - -*Khichidi-1 - - X - - - X - - LANE - - X 4 x 4 X 8 x 8 - - - - -Lesamnta X - X 2 x 2, 4 x 4 X 8 x 8 - - - - -Luffa - - - - X 4 x 4 - - - - -Lux - X - 4 x 4 , 8 x 8 X 8 x 8 - - - - -MCSSHA-3 - - - - - - X - - MD6 - X - - - - X - - -*MeshHash - - - - X 8 x 8 - - - - NaSHA X - - - - 8 x 8 X - - -SANDstorm - - X - - 8 x 8 - - , - -Sarmal X - - 8 x 8 - 8 x 8 - - - - Sgail - X X 8 x 8, 16 x 16 - 8 x 8 - X - - -Shabal - - X - - - X - , - -*SHAMATA X X X 4 x 4 - 8 x 8 - - - SHAvite-3 X - X 4 x 4 - 8 x 8 X - - - -SIMD X X X TRSC+ - - - - , , - -Skein X X X - X - - X - - -Spectral Hash - - - - X 8 x 8 - - - - -*StreamHash - - - - - 8 x 8 - - - - SWIFFTX - - - - - 8 x 8 - - - - -*Tangle - X X - - 8 x 8 - X , , -TIB3 U - X - - 3 x 3 - - - - -Twister - X - 8 x 8 X 8 x 8 - - - Vortex - - - 4 x 4 X 8 x 8 - - - *WAMM - X - - X 8 x 8 - - - - -*Waterfall - X - - X 8 x 8 X - - -

Примечания

Ссылки NIST website for competition Official list of second round candidates Official list of first round candidates SHA-3 Zoo Classification of the SHA-3 Candidates Hash Function Lounge VHDL source code developed by the Cryptographic Engineering Research Group (CERG) at George Mason University

Категория:Криптографические хеш-функции Категория:Стандарты криптографии

Категория:Криптографические конкурсы