Русская Википедия:SHA-3 (конкурс)
«SHA-3» — конкурс Национального института стандартов и технологий (NIST) на новую криптографическую хеш-функцию, предназначенную для дополнения и замены SHA-1 и SHA-2. Проводился в течение в 2007—2012 годов, в результате был избран алгоритм для реализации SHA-3.
Официально объявлен в журнале Federal Register 2 ноября 2007 года[1]. Подобный конкурсный процесс алгоритма был использован ранее для шифрования Advanced Encryption Standard («AES»)[2]. 2 октября 2012 года объявлены результаты: хеш-алгоритмом под наименованием SHA-3 стал алгоритм Keccak[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, его создатели: Шаблон:Iw, Joan Daemen, Шаблон:Iw из STMicroelectronics и Шаблон:Iw из NXP[3].
В отчётах NIST описывались критерии оценки конкурсантов; основными критериями оценки были безопасность, производительность и алгоритм хеш-функции[10][11][12].
Безопасность
Рассматривая безопасность алгоритмов-конкурсантов, 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)[13].
Также оценивалась скорость работы на конечных устройствах: ПК, мобильных устройствах (точки доступа, роутеры, портативные медиаплееры, мобильные телефоны и терминалы оплаты) и виртуальных машинах[14].
Алгоритм и характеристики реализации
Основными параметрами оценки алгоритма были гибкость и простота дизайна. Гибкость включает в себя возможность использования хеш-функции на большом числе платформ и возможности расширения набора инструкций процессора и распараллеливания (для увеличения производительности). Простота дизайна оценивалась по сложности анализа и понимания алгоритма, таким образом простота дизайна дает больше уверенности в оценке безопасности алгоритма.
Участники
NIST выбрали 51 хеш-функцию в первый тур[5]. 14 из них прошло во второй раунд[7], из которых было выбрано 5 финалистов. Неполный список участников представлен ниже.
Победитель
Победитель был объявлен 2 октября 2012 года, им стал алгоритм Keccak[15]. Он стал самым производительным на аппаратной реализации среди финалистов, а также в нём был использован нераспространённый метод шифрования — функция губки. Таким образом, атаки, рассчитанные на SHA-2, не будут работать. Ещё одним существенным преимуществом SHA-3 является возможность его реализации на миниатюрных встраиваемых устройствах (например, USB-флеш-накопитель).
Финалисты
NIST выбрал пять кандидатов, прошедших в третий (и последний) тур[16]:
Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов[17]:
- Производительность: «Некоторые алгоритмы были уязвимы из-за очень больших требований к производительности.»[17]
- Безопасность: «Мы предпочли быть консервативными в безопасности и в некоторых случаях не выбрали алгоритмы с исключительной производительностью, потому что они менее безопасны в значительной степени.»[17]
- Анализ: «NIST устранено несколько алгоритмов из-за неполной проверки или незрелости проекта.»
- Разнообразие: «Хеш-функции, прошедшие в финал, основаны на различных режимах работы, в том числе и на принципе криптографической губки. С разными внутренними структурами, в том числе на основе AES, Bit slicing и на переменных XOR с дополнением.»[17]
Также был выпущен отчёт, поясняющий оценку алгоритмов[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
- Lane
- Lesamnta[30]
- MD6 (Rivest et al.)
- SANDstorm (Sandia National Laboratories)
- Sarmal[31]
- SWIFFTX
- TIB3[32]
Заявленные хеш-функции с существенными уязвимостями
Не прошедшие в первый раунд хеш-функции имели существенные криптографические уязвимости: Шаблон:Кол
- AURORA (Sony и Нагойский университет)[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][49]
- LUX[50]
- MCSSHA-3[51][52]
- NaSHA
- Sgàil[53][54]
- Spectral Hash
- Twister[55][56]
- Vortex[57][58]
Отказавшиеся конкурсанты
На протяжении первого раунда некоторые конкурсанты сами отказались от участия в конкурсе, потому что были взломаны на веб-сайте первого раунда конкурса[59]: Шаблон:Кол
- Abacus[5][60]
- Boole[61][62]
- DCH[5][63]
- Khichidi-1[5][64]
- MeshHash[5][65]
- SHAMATA[5][66]
- StreamHash[5][67]
- Tangle[5][68]
- WaMM[69][70]
- Waterfall[71][72]
Отклонённые участники
Некоторые хеш-функции не были приняты в качестве кандидатов после внутреннего обзора NIST[5]. NIST не сообщил подробностей относительно того, почему эти кандидаты были отклонены. NIST также не дал полный список отклонённых алгоритмов, но 13 из них известны[5][73], но только следующие из них были опубликованы.
Классификация кандидатов
В таблице перечислены известные участники конкурса с указанием основных атрибутов хеш-функций и найденных атак.[84] В ней используются следующие аббревиатуры:
- 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
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ 3,0 3,1 Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ 7,0 7,1 Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ THIRD (FINAL) ROUND CANDIDATES Шаблон:Wayback Retrieved 9 Nov 2011
- ↑ 17,0 17,1 17,2 17,3 Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition Шаблон:Wayback (PDF). Retrieved 2 March 2011
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite webШаблон:Недоступная ссылка
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite webШаблон:Dead link
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- Русская Википедия
- Страницы с неработающими файловыми ссылками
- Криптографические хеш-функции
- Стандарты криптографии
- NIST hash function competition
- Криптографические конкурсы
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии