SHA-3 (конкурс)

Эта статья — о конкурсе на создание хеш-функции. О функции, получившей по его результатам это название, см. SHA-3.

«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, его создатели: Guido Bertoni, Joan Daemen, Gilles Van Assche из STMicroelectronics и Michaël Peeters из NXP.

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

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

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

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

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

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

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

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

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

Участники

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

Победитель

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

Финалисты

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

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

Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:

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

Также был выпущен отчёт, поясняющий оценку алгоритмов.

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

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

• 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 англ. A Feistel network — сеть Фейстеля;
• WP англ. Wide Pipe design — метод построения криптографических хеш-функций, похожий на структуру Меркла — Дамгора;
• KEY англ. 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 — вторая лучшая атака на поиск коллизий, лучше чем атака удлинением сообщения;

Таблица классификации

Хеш-алгоритм	FN	WP	KEY	MDS	OUT	SBOX	FSR	ARX	BOOL	COL	PRE
Abacus	-	X	-	4 x 4	X	8 x 8	X	-	-	$2^{172}$	$2^{172}$
ARIRANG	X	X	X	4 x 4, 8 x 8	-	8 x 8	-	-	-	-	-
AURORA	-	-	X	4 x 4	X	8 x 8	-	-	-	$2^{234.61}/2^{229.6}$	$2^{291}/2^{31.6}$
BLAKE	X	-	X	-	-	-	-	X —	-	-	-
Blender	-	X	-	-	-	-	-	X	-	$10*2^{n \over 4}$	$10*2^{n \over 4}$
BMW	-	X	X	-	-	-	-	X	-	-	-
*Boole	-	-	-	-	X	-	X	-	$\land$	$2^{34}$	$2^{9*n \over r}$
Cheetah	-	-	X	4 x 4, 8 x 8	-	8 x 8	-	-	-	-	-
Chi	X	X	X	-	-	4 x 3	-	-	$\lor$, $\lnot$	-	-
CRUNCH	X	-	X	-	-	8 x 1016	-	-	-	-	-
CubeHash8/1	-	-	-	-	-	-	-	X	-	-	$2^{509}$
*DHC	-	-	X	-	-	8 x 8	-	-	-	$2^{9}$	$2^{9}$
DynamicSHA	X	-	X	-	-	-	-	-	$\land$, $\lor$, $\lnot$	$2^{114}$	-
DynamicSHA2	X	-	X	-	-	-	-	X	$\land$, $\lor$, $\lnot$	-	-
ECHO	-	X	-	4 x 4	-	8 x 8	-	-	-	-	-
ECOH	-	-	X	-	-	-	-	-	-	-	-
Edon-R	-	X	X	-	-	-	-	X	-	-	$2^{2*n \over 3}$
EnRUPT	-	X	-	-	-	-	-	X	-	-	$2^{480}/2^{480}$
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	-		-	-	$2^{510.3}/2^{510.3}$
Keccak	-	X	-	-	-	-	-	-	$\land$, $\lnot$	-	-
*Khichidi-1	-	-	X	-	-	-	X	-	-	$1$	$1/2^{33}$
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	-	-	$2^{3n/8}$	$2^{3n/4}$
MD6	-	X	-	-	-	-	X	-	$\land$	-	-
*MeshHash	-	-	-	-	X	8 x 8	-	-	-	-	$2^{323.2}/2^{n \over 2}$
NaSHA	X	-	-	-	-	8 x 8	X	-	-	$2^{128}$	-
SANDstorm	-	-	X	-	-	8 x 8	-	-	$\land$, $\lnot$	-	-
Sarmal	X	-	-	8 x 8	-	8 x 8	-	-	-	-	$2^{384}/2^{128}$
Sgail	-	X	X	8 x 8, 16 x 16	-	8 x 8	-	X	-	-	-
Shabal	-	-	X	-	-	-	X	-	$\land$, $\lnot$	-	-
*SHAMATA	X	X	X	4 x 4	-	8 x 8	-	-	-	$2^{40}/2^{29}$	$2^{461.7}/2^{462.7}$
SHAvite-3	X	-	X	4 x 4	-	8 x 8	X	-	-	-	-
SIMD	X	X	X	TRSC+	-	-	-	-	$\land$, $\lor$, $\lnot$	-	-
Skein	X	X	X	-	X	-	-	X	-	-	-
Spectral Hash	-	-	-	-	X	8 x 8	-	-	-	-	-
*StreamHash	-	-	-	-	-	8 x 8	-	-	-	-	$n*2^{n \over 2}$
SWIFFTX	-	-	-	-	-	8 x 8	-	-	-	-	-
*Tangle	-	X	X	-	-	8 x 8	-	X	$\land$, $\lor$, $\lnot$	$2^{19}$	-
TIB3	U	-	X	-	-	3 x 3	-	-	-	-	-
Twister	-	X	-	8 x 8	X	8 x 8	-	-	-	$2^{252}$	$2^{448/264}$
Vortex	-	-	-	4 x 4	X	8 x 8	-	-	-	$2^{122.5}/2^{122.5}$	$2^{3}/2^{n \over 4}$
*WAMM	-	X	-	-	X	8 x 8	-	-	-	-	-
*Waterfall	-	X	-	-	X	8 x 8	X	-	-	$2$	-

— Ewan Fleischmann, Christian Forler и Michael Gorski. "Classifcation of the SHA-3 Candidates"

Ссылки

• NIST website for competition Архивная копия от 9 июля 2011 на Wayback Machine
• Official list of second round candidates Архивировано 10 апреля 2012 года.
• Official list of first round candidates Архивная копия от 4 июня 2009 на Wayback Machine
• SHA-3 Zoo Архивная копия от 12 ноября 2013 на Wayback Machine
• Classification of the SHA-3 Candidates Архивная копия от 10 мая 2012 на Wayback Machine
• Hash Function Lounge
• VHDL source code developed by the Cryptographic Engineering Research Group (CERG) at George Mason University Архивная копия от 25 апреля 2012 на Wayback Machine