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

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

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

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

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

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

Процесс

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

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

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

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

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

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

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

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

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

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

Участники

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

Победитель

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

Финалисты

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

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

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

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

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

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

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

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

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

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

• ARIRANG^[27] (CIST — Korea University)
• CHI^[28]
• CRUNCH^[29]
• FSB
• Lane
• Lesamnta^[30]
• MD6 (Rivest et al.)
• SANDstorm (Sandia National Laboratories)
• Sarmal^[31]
• SWIFFTX
• TIB3^[32]

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

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

• AURORA (Sony и Нагойский университет)^[33][34]
• Blender^[35][36][37]
• Cheetah^[38][39]
• Dynamic SHA^[40][41]
• Dynamic SHA2^[42][43]
• ECOH
• Edon-R^[44][45]
• EnRUPT^[46][47]
• ESSENCE^[48][49]
• LUX^[50]
• MCSSHA-3^[51][52]
• NaSHA
• Sgàil^[53][54]
• Spectral Hash
• Twister^[55][56]
• Vortex^[57][58]

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

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

• Abacus^[5][60]
• Boole^[61][62]
• DCH^[5][63]
• Khichidi-1^[5][64]
• MeshHash^[5][65]
• SHAMATA^[5][66]
• StreamHash^[5][67]
• Tangle^[5][68]
• WaMM^[69][70]
• Waterfall^[71][72]

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

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

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

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

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

• 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	-	-	${\displaystyle 2^{172}}$	${\displaystyle 2^{172}}$
ARIRANG	X	X	X	4 x 4, 8 x 8	-	8 x 8	-	-	-	-	-
AURORA	-	-	X	4 x 4	X	8 x 8	-	-	-	${\displaystyle 2^{234.61}/2^{229.6}}$	${\displaystyle 2^{291}/2^{31.6}}$
BLAKE	X	-	X	-	-	-	-	X —	-	-	-
Blender	-	X	-	-	-	-	-	X	-	${\displaystyle 10*2^{n \over 4}}$	${\displaystyle 10*2^{n \over 4}}$
BMW	-	X	X	-	-	-	-	X	-	-	-
*Boole	-	-	-	-	X	-	X	-	${\displaystyle \land }$	${\displaystyle 2^{34}}$	${\displaystyle 2^{9*n \over r}}$
Cheetah	-	-	X	4 x 4, 8 x 8	-	8 x 8	-	-	-	-	-
Chi	X	X	X	-	-	4 x 3	-	-	${\displaystyle \lor }$, ${\displaystyle \lnot }$	-	-
CRUNCH	X	-	X	-	-	8 x 1016	-	-	-	-	-
CubeHash8/1	-	-	-	-	-	-	-	X	-	-	${\displaystyle 2^{509}}$
*DHC	-	-	X	-	-	8 x 8	-	-	-	${\displaystyle 2^{9}}$	${\displaystyle 2^{9}}$
DynamicSHA	X	-	X	-	-	-	-	-	${\displaystyle \land }$, ${\displaystyle \lor }$, ${\displaystyle \lnot }$	${\displaystyle 2^{114}}$	-
DynamicSHA2	X	-	X	-	-	-	-	X	${\displaystyle \land }$, ${\displaystyle \lor }$, ${\displaystyle \lnot }$	-	-
ECHO	-	X	-	4 x 4	-	8 x 8	-	-	-	-	-
ECOH	-	-	X	-	-	-	-	-	-	-	-
Edon-R	-	X	X	-	-	-	-	X	-	-	${\displaystyle 2^{2*n \over 3}}$
EnRUPT	-	X	-	-	-	-	-	X	-	-	${\displaystyle 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	-		-	-	${\displaystyle 2^{510.3}/2^{510.3}}$
Keccak	-	X	-	-	-	-	-	-	${\displaystyle \land }$, ${\displaystyle \lnot }$	-	-
*Khichidi-1	-	-	X	-	-	-	X	-	-	${\displaystyle 1}$	${\displaystyle 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	-	-	${\displaystyle 2^{3n/8}}$	${\displaystyle 2^{3n/4}}$
MD6	-	X	-	-	-	-	X	-	${\displaystyle \land }$	-	-
*MeshHash	-	-	-	-	X	8 x 8	-	-	-	-	${\displaystyle 2^{323.2}/2^{n \over 2}}$
NaSHA	X	-	-	-	-	8 x 8	X	-	-	${\displaystyle 2^{128}}$	-
SANDstorm	-	-	X	-	-	8 x 8	-	-	${\displaystyle \land }$, ${\displaystyle \lnot }$	-	-
Sarmal	X	-	-	8 x 8	-	8 x 8	-	-	-	-	${\displaystyle 2^{384}/2^{128}}$
Sgail	-	X	X	8 x 8, 16 x 16	-	8 x 8	-	X	-	-	-
Shabal	-	-	X	-	-	-	X	-	${\displaystyle \land }$, ${\displaystyle \lnot }$	-	-
*SHAMATA	X	X	X	4 x 4	-	8 x 8	-	-	-	${\displaystyle 2^{40}/2^{29}}$	${\displaystyle 2^{461.7}/2^{462.7}}$
SHAvite-3	X	-	X	4 x 4	-	8 x 8	X	-	-	-	-
SIMD	X	X	X	TRSC+	-	-	-	-	${\displaystyle \land }$, ${\displaystyle \lor }$, ${\displaystyle \lnot }$	-	-
Skein	X	X	X	-	X	-	-	X	-	-	-
Spectral Hash	-	-	-	-	X	8 x 8	-	-	-	-	-
*StreamHash	-	-	-	-	-	8 x 8	-	-	-	-	${\displaystyle n*2^{n \over 2}}$
SWIFFTX	-	-	-	-	-	8 x 8	-	-	-	-	-
*Tangle	-	X	X	-	-	8 x 8	-	X	${\displaystyle \land }$, ${\displaystyle \lor }$, ${\displaystyle \lnot }$	${\displaystyle 2^{19}}$	-
TIB3	U	-	X	-	-	3 x 3	-	-	-	-	-
Twister	-	X	-	8 x 8	X	8 x 8	-	-	-	${\displaystyle 2^{252}}$	${\displaystyle 2^{448/264}}$
Vortex	-	-	-	4 x 4	X	8 x 8	-	-	-	${\displaystyle 2^{122.5}/2^{122.5}}$	${\displaystyle 2^{3}/2^{n \over 4}}$
*WAMM	-	X	-	-	X	8 x 8	-	-	-	-	-
*Waterfall	-	X	-	-	X	8 x 8	X	-	-	${\displaystyle 2}$	-

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

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