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

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

NIST ініціював розробку одного або декількох додаткових алгоритмів гешування через відкритий конкурс, подібний процес розвитку був використаний раніше для шифрування Advanced Encryption Standard (скорочено AES).

Конкурс завершився 12 жовтня 2012 року, коли NIST оголосив, що Keccak буде новим SHA-3 геш-алгоритмом.

Цілі конкурсу

Спочатку організатори конкурсу припускали замінити старі геш-функції переможцем, так як в 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 описали деякі критерії, на яких ґрунтувався вибір фіналістів:

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

NIST випустив звіт, що пояснює оцінку алгоритмів.

Геш-функції, які не пройшли в фінал

Наступні геш-функції потрапили до другого раунду, але не пройшли у фінал. Також було при оголошенно фіналістів: «Жоден з цих кандидатів не був явно зламаний». В дужках вказана причина, по якій геш-функції не стала фіналістом.

• 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
• SWIFFT X
• TIB3

Заявлені геш-функції з істотними уразливостями

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

• AURORA (Sony and Nagoya University)
• Blender
• Cheetah
• Dynamic SHA
• Dynamic SHA2
• ECOH
• Edon-R
• EnRUPT
• ESSENCE
• LUX
• MCSSHA-3
• NaSHA
• Sgàil
• Spectral Hash
• Twister
• Vortex

Конкурсанти, які відмовилися

Протягом першого раунду деякі конкурсанти самі відмовилися від участі в конкурсі, тому що були зламані на NIST official Round One Candidates web site [Архівовано 4 червня 2009 у Wayback Machine.]. Вони не брали участі в конкурсі.

• 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 — друга найкраща атака на пошук колізій, краща ніж Length extension 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 у WebCite]
• 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.]