Русская Википедия:SHA-3 (конкурс)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:NITS Competition.jpg

«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, его создатели: Шаблон:Iw, Joan Daemen, Шаблон:Iw из STMicroelectronics и Шаблон:Iw из NXP.

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

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

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

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

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

• В тесте ECRYPT Benchmarking of All Submitted Hashes (сокращённо Шаблон:Lang-en2) производились замеры скорости вычисления для большого числа 32- и 64-битных платформ.
• Тест eXternal Benchmarking eXtension (сокращённо Шаблон:Lang-en2) предоставил результаты для портативных устройств.
• Дополнительно проверялась производительность и возможность оптимизации на многоядерных архитектурах. Тесты производились на архитектурах 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 Шаблон:Lang-en — сеть Фейстеля;
• WP Шаблон:Lang-en — метод построения криптографических хеш-функций, похожий на структуру Меркла — Дамгора;
• KEY Шаблон:Lang-en — Шаблон:Iw, получающий ключи для каждого раунда хеширования;
• MDS Шаблон:Lang-en — размер Шаблон:Iw-матрицы;
• OUT Шаблон:Lang-en — криптографическая операция, осуществляемая в последней выходной итерации;
• SBOX Шаблон:Lang-en — S-блоки;
• FSR Шаблон:Lang-en — регистр сдвига с линейной обратной связью;
• ARX Шаблон:Lang-en — сложение, циклический сдвиг и XOR;
• BOOLШаблон:Lang-en — булева алгебра;
• COL Шаблон:Lang-en — самая лучшая из известных атак на поиск коллизий, лучше чем атаке «дней рождения»;
• PRE Шаблон:Lang-en — вторая лучшая атака на поиск коллизий, лучше чем атака удлинением сообщения;

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

Ссылки

• NIST website for competition Шаблон:Wayback
• Official list of second round candidates Шаблон:Архивировано
• Official list of first round candidates Шаблон:Wayback
• SHA-3 Zoo Шаблон:Wayback
• Classification of the SHA-3 Candidates Шаблон:Wayback
• Hash Function Lounge
• VHDL source code developed by the Cryptographic Engineering Research Group (CERG) at George Mason University Шаблон:Wayback