SHA-3 — конкурс на нову криптографічну геш-функцію, запроваджений Національним інститутутом стандартів і технологій США (), (скорочено 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, його творці: , Joan Daemen, з 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 вибрав п'ять кандидатів, які пройшли в третій (і останній) тур:THIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011 BLAKE

JH Keccak Skein

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

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

NIST випустив звіт, що пояснює оцінку алгоритмівStatus Report on the Second Round of the SHA- 3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011.

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

Blue Midnight Wish (можливі проблеми з безпекою) CubeHash (Bernstein) (проблеми з продуктивністю) ECHO (France Telecom) (проблеми з продуктивністю) Fugue (IBM) (можливі проблеми з безпекою) Hamsi (високі вимоги до ПЗУ, можливі проблеми з безпекою) Luffa(можливі проблеми з безпекою) Shabal (можливі проблеми з безпекою) SHAvite-3 (можливі проблеми з безпекою) SIMD (проблеми з продуктивністю, можливі проблеми з безпекою)

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

ARIRANG (CIST — Korea University) CHI CRUNCH

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 . Вони не брали участі в конкурсі.

Abacus Boole DCH Khichidi-1 MeshHash SHAMATA StreamHash Tangle WaMM Waterfall

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

HASH 2X Maraca NKS 2D Ponic ZK-Crypt

Класифікація кандидатів У таблиці перераховані відомі учасники конкурсу із зазначенням основних атрибутів хеш-функцій і знайдених атак. В ній використовуються наступні абревіатури: FN  — Мережа Фейстеля; WP  — метод побудови криптографічних хеш-функцій, схожих на будову Меркла-Демґарда; KEY  — алгоритм, який одержує ключі для кожного раунду хешування; MDS  — Розмір MDS матриці; OUT  — криптографічна операція, яка здійснюється в останній вихідній ітерації; SBOX  — S-блоки; FSR  — Регістр зсуву з лінійним зворотним зв'язком; ARX  — скадання, циклічний зсув і XOR; BOOL — Булева алгебра; COL  — найкраща з відомих атак на пошук колізій, краща ніж атака «днів народження»; PRE  — друга найкраща атака на пошук колізій, краща ніж ;

Геш-алгоритмFNWPKEYMDSOUTSBOXFSRARXBOOLCOLPREAbacus - X - 4 x 4 X 8 x 8 X - - ARIRANG X X X 4 x 4, 8 x 8 - 8 x 8 - - - - -AURORA - - X 4 x 4 X 8 x 8 - - - BLAKE X - X - - - - X — - - -Blender - X - - - - - X - BMW - X X - - - - X - - -*Boole - - - - X - X - Cheetah - - X 4 x 4, 8 x 8 - 8 x 8 - - - - -Chi X X X - - 4 x 3 - - , - -CRUNCH X - X - - 8 x 1016 - - - - -CubeHash8/1 - - - - - - - X - - *DHC - - X - - 8 x 8 - - - DynamicSHA X - X - - - - - , , -DynamicSHA2 X - X - - - - X , , - -ECHO - X - 4 x 4 - 8 x 8 - - - - -ECOH - - X - - - - - - - -Edon-R - X X - - - - X - - EnRUPT - X - - - - - X - - 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 - - - Keccak - X - - - - - - , - -*Khichidi-1 - - X - - - X - - 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 - - MD6 - X - - - - X - - -*MeshHash - - - - X 8 x 8 - - - - NaSHA X - - - - 8 x 8 X - - -SANDstorm - - X - - 8 x 8 - - , - -Sarmal X - - 8 x 8 - 8 x 8 - - - - Sgail - X X 8 x 8, 16 x 16 - 8 x 8 - X - - -Shabal - - X - - - X - , - -*SHAMATA X X X 4 x 4 - 8 x 8 - - - SHAvite-3 X - X 4 x 4 - 8 x 8 X - - - -SIMD X X X TRSC+ - - - - , , - -Skein X X X - X - - X - - -Spectral Hash - - - - X 8 x 8 - - - - -*StreamHash - - - - - 8 x 8 - - - - SWIFFTX - - - - - 8 x 8 - - - - -*Tangle - X X - - 8 x 8 - X , , -TIB3 U - X - - 3 x 3 - - - - -Twister - X - 8 x 8 X 8 x 8 - - - Vortex - - - 4 x 4 X 8 x 8 - - - *WAMM - X - - X 8 x 8 - - - - -*Waterfall - X - - X 8 x 8 X - - -

Примітки

Посилання NIST website for competition Official list of second round candidates Official list of first round candidates SHA-3 Zoo Classification of the SHA-3 Candidates Hash Function Lounge VHDL source code developed by the Cryptographic Engineering Research Group (CERG) at George Mason University