Русская Википедия:SHA-3 (конкурс)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:О

Файл:NITS Competition.jpg

«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 (проблемы с производительностью, возможны проблемы с безопасностью)

Шаблон:Конец кол

Хеш-функции, не прошедшие во второй раунд

Следующие представители хеш-функций были приняты для первого раунда, но не прошли во второй. У них не было существенных криптографических уязвимостей. Большинство из них имеют слабые места в дизайне компонентов или у них были замечены проблемы с производительностью. Шаблон:Кол

Шаблон:Конец кол

Заявленные хеш-функции с существенными уязвимостями

Не прошедшие в первый раунд хеш-функции имели существенные криптографические уязвимости: Шаблон:Кол

Шаблон:Конец кол

Отказавшиеся конкурсанты

На протяжении первого раунда некоторые конкурсанты сами отказались от участия в конкурсе, потому что были взломаны на веб-сайте первого раунда конкурса[59]: Шаблон:Кол

Шаблон:Конец кол

Отклонённые участники

Некоторые хеш-функции не были приняты в качестве кандидатов после внутреннего обзора NIST[5]. NIST не сообщил подробностей относительно того, почему эти кандидаты были отклонены. NIST также не дал полный список отклонённых алгоритмов, но 13 из них известны[5][73], но только следующие из них были опубликованы.

Шаблон:Кол

Шаблон:Конец кол

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

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

Шаблон:Начало скрытого блока Шаблон:Начало цитаты

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

Шаблон:Конец цитаты Шаблон:Конец скрытого блока

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Хеш-алгоритмы

  1. Шаблон:Cite web
  2. Шаблон:Cite web
  3. 3,0 3,1 Шаблон:Cite web
  4. Шаблон:Cite web
  5. 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 Шаблон:Cite web
  6. Шаблон:Cite web
  7. 7,0 7,1 Шаблон:Cite web
  8. Шаблон:Cite web
  9. Шаблон:Cite web
  10. Шаблон:Cite web
  11. Шаблон:Cite web
  12. Шаблон:Cite web
  13. Шаблон:Cite web
  14. Шаблон:Cite web
  15. Шаблон:Cite web
  16. THIRD (FINAL) ROUND CANDIDATES Шаблон:Wayback Retrieved 9 Nov 2011
  17. 17,0 17,1 17,2 17,3 Шаблон:Cite web
  18. Шаблон:Cite web
  19. Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition Шаблон:Wayback (PDF). Retrieved 2 March 2011
  20. Шаблон:Cite web
  21. Шаблон:Cite web
  22. Шаблон:Cite web
  23. Шаблон:Cite web
  24. Шаблон:Cite web
  25. Шаблон:Cite web
  26. Шаблон:Cite web
  27. Шаблон:Cite web
  28. Шаблон:Cite web
  29. Шаблон:Cite web
  30. Шаблон:Cite web
  31. Шаблон:Cite web
  32. Шаблон:Cite webШаблон:Недоступная ссылка
  33. Шаблон:Cite web
  34. Шаблон:Cite web
  35. Шаблон:Cite web
  36. Шаблон:Cite web
  37. Шаблон:Cite web
  38. Шаблон:Cite web
  39. Шаблон:Cite web
  40. Шаблон:Cite web
  41. Шаблон:Cite web
  42. Шаблон:Cite web
  43. Шаблон:Cite web
  44. Шаблон:Cite web
  45. Шаблон:Cite web
  46. Шаблон:Cite web
  47. Шаблон:Cite web
  48. Шаблон:Cite web
  49. Шаблон:Cite web
  50. Шаблон:Cite web
  51. Шаблон:Cite web
  52. Шаблон:Cite webШаблон:Dead link
  53. Шаблон:Cite web
  54. Шаблон:Cite web
  55. Шаблон:Cite web
  56. Шаблон:Cite web
  57. Шаблон:Cite web
  58. Шаблон:Cite web
  59. Шаблон:Cite web
  60. Шаблон:Cite web
  61. Шаблон:Cite web
  62. Шаблон:Cite web
  63. Шаблон:Cite web
  64. Шаблон:Cite web
  65. Шаблон:Cite web
  66. Шаблон:Cite web
  67. Шаблон:Cite web
  68. Шаблон:Cite web
  69. Шаблон:Cite web
  70. Шаблон:Cite web
  71. Шаблон:Cite web
  72. Шаблон:Cite web
  73. Шаблон:Cite web
  74. Шаблон:Cite web
  75. Шаблон:Cite web
  76. Шаблон:Cite web
  77. Шаблон:Cite web
  78. Шаблон:Cite web
  79. Шаблон:Cite web
  80. Шаблон:Cite web
  81. Шаблон:Cite web
  82. Шаблон:Cite web
  83. Шаблон:Cite web
  84. Шаблон:Cite web