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

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

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

Конкурс завершився 12 жовтня 2012 року, коли NIST оголосив, що Keccak буде новим SHA-3 геш-алгоритмом^[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

NIST описали деякі критерії, на яких ґрунтувався вибір фіналістів:^[17]

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

NIST випустив звіт, що пояснює оцінку алгоритмів^[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^[en]
• Lane^[en]
• Lesamnta^[30]
• MD6 (Rivest et al.)
• SANDstorm (Sandia National Laboratories)
• Sarmal^[31]
• SWIFFT X
• TIB3^[32]

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

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

• AURORA (Sony and Nagoya University)^[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]
• LUX^[49]
• MCSSHA-3^[50][51]
• NaSHA
• Sgàil^[52][53]
• Spectral Hash
• Twister^[54][55]
• Vortex^[56][57]

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

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

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

Відхилені учасники

Деякі геш-функції не були прийняті кандидатами, після внутрішнього огляду NIST.^[5] NIST не повідомила подробиць щодо того, чому ці кандидати були відхилені. NIST також не дала повний список відхилених алгоритмів, але 13 з них відомі,^[5][71].Проте, тільки такі з них були прилюднені:

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

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

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

• FN англ. A Feistel network — Мережа Фейстеля;
• WP англ. Wide Pipe design — метод побудови криптографічних хеш-функцій, схожих на будову Меркла-Демґарда;
• KEY англ. Key schedule^[en] — алгоритм, який одержує ключі для кожного раунду хешування;
• 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^[en];

Таблиця класифікації

Геш-алгоритм	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"