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].
Основними параметрами оцінки алгоритму були гнучкість і простота дизайну. Гнучкість включає в себе можливість використання геш-функції на великому числі платформ та можливості розширення набору інструкцій процесора і розпаралелювання (для збільшення продуктивності). Простота дизайну оцінювалася за складністю аналізу й розуміння алгоритму, таким чином простота дизайну дає більше впевненості в оцінці безпеки алгоритму.
Учасники
NIST вибрали 51 геш-функцію в перший тур.[5] 14 з них пройшло до другого раунду,[7] з яких було вибрано 5 фіналістів. Неповний список учасників представлений нижче.
Переможець
Переможець був оголошений 2 жовтня 2012 року, ним став алгоритм Keccak[15]. Він став найпродуктивнішим на апаратній реалізації серед фіналістів, а також в ньому був використаний непоширених метод шифрування — функція губки. Таким чином, атаки, розраховані на SHA-2, не працюватимуть. Ще однією істотною перевагою SHA-3 є можливість його реалізації на мініатюрних вбудованих пристроях (наприклад, USB-флеш-накопичувач).
Фіналісти
NIST вибрав п'ять кандидатів, які пройшли в третій (і останній) тур:[16]
NIST описали деякі критерії, на яких ґрунтувався вибір фіналістів:[17]
Продуктивність: «Деякі алгоритми були уразливі через дуже високі вимоги до продуктивності.»[17]
Безпека: «Ми вважали за краще бути консервативними в безпеці й у деяких випадках не вибрали алгоритми з винятковою продуктивністю, тому що вони менш безпечні в значній мірі.»[17]
Аналіз: «NIST усунуто кілька алгоритмів через неповну перевірку або незрілість проекту.»
Різноманітність: «Геш-функції, які пройшли у фінал, засновані на різних режимах роботи, в тому числі і на принципі криптографічного губки. З різними внутрішніми структурами, в тому числі на основі AES, Bit slicing і на змінних XOR з доповненням.»[17]
NIST випустив звіт, що пояснює оцінку алгоритмів[18][19].
Геш-функції, які не пройшли в фінал
Наступні геш-функції потрапили до другого раунду, але не пройшли у фінал. Також було при оголошенно фіналістів: «Жоден з цих кандидатів не був явно зламаний». В дужках вказана причина, по якій геш-функції не стала фіналістом.
SIMD (проблеми з продуктивністю, можливі проблеми з безпекою)
Геш-функції, що не пройшли до другого раунду
Наступні представники геш-функцій були прийняті до першого раунду, але не пройшли до другого. У них не було суттєвих криптографічних вразливостей. Більшість з них мають слабкі місця в дизайні компонентів або у них були помічені проблеми з продуктивністю.
Деякі геш-функції не були прийняті кандидатами, після внутрішнього огляду NIST.[5] NIST не повідомила подробиць щодо того, чому ці кандидати були відхилені. NIST також не дала повний список відхилених алгоритмів, але 13 з них відомі,[5][71].Проте, тільки такі з них були прилюднені:
У таблиці перераховані відомі учасники конкурсу із зазначенням основних атрибутів хеш-функцій і знайдених атак.[82] В ній використовуються наступні абревіатури:
— Ewan Fleischmann, Christian Forler и Michael Gorski. "Classifcation of the SHA-3 Candidates"
Примітки
↑Federal Register / Vol. 72, No. 212(PDF). Federal Register. Government Printing Office. Friday, November 2, 2007. Архів оригіналу(PDF) за 31 березня 2011. Процитовано 6 листопада 2008.
↑ абSecond Round Candidates. National Institute for Standards and Technology. 24 липня 2009. Архів оригіналу за 10 квітня 2012. Процитовано 24 липня 2009.
↑Архівована копія(PDF). Архів оригіналу(PDF) за 14 березня 2011. Процитовано 12 квітня 2018.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑Архівована копія(PDF). Архів оригіналу(PDF) за 24 січня 2014. Процитовано 12 квітня 2018.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑Архівована копія(PDF). Архів оригіналу(PDF) за 29 грудня 2009. Процитовано 12 квітня 2018.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑Архівована копія(PDF). Архів оригіналу(PDF) за 13 грудня 2013. Процитовано 12 квітня 2018.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑Dai Watanabe; Christophe De Canniere, Hisayoshi Sato (31 October 2008). Hash Function Luffa : Specification(PDF). Архів оригіналу(PDF) за 12 листопада 2013. Процитовано 11 December 2008.
↑Jean-François Misarsky; Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau (28 жовтня 2008). Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition(PDF). Архів оригіналу(PDF) за 12 листопада 2013. Процитовано 11 December 2008.
↑Danilo Gligoroski; Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal (4 листопада 2008). edon-r. Архів оригіналу за 12 листопада 2013. Процитовано 10 November 2008.
↑Peter Maxwell (5 листопада 2008). Aww, p*sh!. Архів оригіналу за 9 листопада 2008. Процитовано 6 листопада 2008.
↑Michael Gorski; Ewan Fleischmann, Christian Forler (28 жовтня 2008). The Twister Hash Function Family(PDF). Архів оригіналу(PDF) за 12 листопада 2013. Процитовано 11 грудня 2008.
↑Florian Mendel, Christian Rechberger, Martin Schläffer (2008). Cryptanalysis of Twister(PDF). Архів оригіналу(PDF) за 12 листопада 2013. Процитовано 19 травня 2009.
↑Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen (2009). Cryptanalysis of Vortex(PDF). Архів оригіналу(PDF) за 12 листопада 2013. Процитовано 19 травня 2009.
↑Rafael Alvarez; Gary McGuire and Antonio Zamora. The Tangle Hash Function(PDF). Архів оригіналу(PDF) за 12 листопада 2013. Процитовано 11 грудня 2008.
↑Архівована копія(PDF). Архів оригіналу(PDF) за 10 травня 2012. Процитовано 12 квітня 2018.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)