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, его создатели: 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]:

Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов[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] В ней используются следующие аббревиатуры:

Примечания

[править | править код]
  1. Federal Register / Vol. 72, No. 212 (PDF). Federal Register. Government Printing Office (2 ноября 2007). Дата обращения: 6 ноября 2008. Архивировано 31 марта 2011 года.
  2. cryptographic hash project - Background Information. Computer Security Resource Center. National Institute of Standards and Technology (2 ноября 2007). Дата обращения: 6 ноября 2008. Архивировано 5 мая 2010 года.
  3. 1 2 NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST (2 октября 2012). Дата обращения: 2 октября 2012. Архивировано 30 апреля 2017 года.
  4. Shneier on Security: SHA-3 to Be Announced. Дата обращения: 9 апреля 2015. Архивировано 15 апреля 2015 года.
  5. 1 2 3 4 5 6 7 8 9 10 11 Round 1 (9 декабря 2008). Дата обращения: 10 декабря 2008. Архивировано 27 мая 2009 года.
  6. National Institute of Standards and Technology. The First SHA-3 Candidate Conference (9 декабря 2008). Дата обращения: 23 декабря 2008. Архивировано 12 ноября 2013 года.
  7. 1 2 Second Round Candidates. National Institute for Standards and Technology (24 июля 2009). Дата обращения: 24 июля 2009. Архивировано 10 апреля 2012 года.
  8. National Institute of Standards and Technology. The Second SHA-3 Candidate Conference (30 июня 2010). Дата обращения: 12 ноября 2013. Архивировано 5 марта 2010 года.
  9. Tentative Timeline of the Development of New Hash Functions. NIST (10 декабря 2008). Дата обращения: 15 сентября 2009. Архивировано 4 июня 2009 года.
  10. Hash Functions | CSRC. Дата обращения: 12 ноября 2013. Архивировано 14 марта 2011 года.
  11. Архивированная копия. Дата обращения: 10 декабря 2013. Архивировано 24 января 2014 года.
  12. Hash Functions | CSRC. Дата обращения: 12 ноября 2013. Архивировано 29 декабря 2009 года.
  13. Performance Analysis of the SHA-3 Candidates on Exotic Multi-core Architectures — Springer. Дата обращения: 3 октября 2017. Архивировано 29 января 2018 года.
  14. Hash Functions | CSRC. Дата обращения: 10 декабря 2013. Архивировано 13 декабря 2013 года.
  15. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. Дата обращения: 28 декабря 2016. Архивировано 30 апреля 2017 года.
  16. THIRD (FINAL) ROUND CANDIDATES Архивная копия от 18 декабря 2010 на Wayback Machine Retrieved 9 Nov 2011
  17. 1 2 3 4 SHA-3 Finalists Announced by NIST. National Institute for Standards and Technology (10 декабря 2010). Дата обращения: 12 ноября 2013. Архивировано 10 апреля 2012 года.
  18. Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition. Дата обращения: 12 ноября 2013. Архивировано 29 декабря 2009 года.
  19. Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition Архивная копия от 14 марта 2011 на Wayback Machine (PDF). Retrieved 2 March 2011
  20. Svein Johan Knapskog; Danilo Gligoroski, Vlastimil Klima, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes.: blue_midnight_wish (4 ноября 2008). Дата обращения: 10 ноября 2008. Архивировано 12 ноября 2013 года.
  21. Søren S. Thomsen. Pseudo-cryptanalysis of Blue Midnight Wish (PDF) (2009). Дата обращения: 19 мая 2009. Архивировано из оригинала 2 сентября 2009 года.
  22. Henri Gilbert; Ryad Benadjila, Olivier Billet, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin.: SHA-3 Proposal: ECHO (PDF) (29 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  23. Özgül Kücük. The Hash Function Hamsi (PDF) (31 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 11 апреля 2012 года.
  24. Dai Watanabe; Christophe De Canniere, Hisayoshi Sato.: Hash Function Luffa: Specification (PDF) (31 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  25. 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.: Shabal, a Submission to NIST’s Cryptographic Hash Algorithm Competition (PDF) (28 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  26. Eli Biham; Orr Dunkelman.: The SHAvite-3 Hash Function (PDF). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  27. Jongin Lim; Donghoon Chang, Seokhie Hong, Changheon Kang, Jinkeon Kang, Jongsung Kim, Changhoon Lee, Jesang Lee, Jongtae Lee, Sangjin Lee, Yuseop Lee, Jaechul Sung.: ARIRANG (PDF) (29 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  28. Philip Hawkes; Cameron McDonald.: Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms (30 октября 2008). Дата обращения: 11 ноября 2008. Архивировано 12 ноября 2013 года.
  29. Jacques Patarin; Louis Goubin, Mickael Ivascot, William Jalby, Olivier Ly, Valerie Nachef, Joana Treger, Emmanuel Volte.: CRUNCH. Дата обращения: 14 ноября 2008. Архивировано из оригинала 29 января 2009 года.
  30. Hirotaka Yoshida; Shoichi Hirose, Hidenori Kuwakado.: SHA-3 Proposal: Lesamnta (PDF) (30 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  31. Kerem Varıcı; Onur Özen and Çelebi Kocair.: The Sarmal Hash Function. Дата обращения: 12 октября 2010. Архивировано из оригинала 11 июня 2011 года.
  32. Daniel Penazzi; Miguel Montes.: The TIB3 Hash. Дата обращения: 29 ноября 2008. (недоступная ссылка)
  33. AURORA: A Cryptographic Hash Algorithm Family (PDF) (31 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  34. Attacks on AURORA-512 and the Double-Mix Merkle-Damgaard Transform (PDF) (2009). Дата обращения: 10 июля 2009. Архивировано 10 мая 2012 года.
  35. Colin Bradbury. BLENDER: A Proposed New Family of Cryptographic Hash Algorithms (PDF) (25 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  36. Craig Newbold. Observations and Attacks On The SHA-3 Candidate Blender (PDF). Дата обращения: 23 декабря 2008. Архивировано 12 ноября 2013 года.
  37. Florian Mendel. Preimage Attack on Blender (PDF). Дата обращения: 23 декабря 2008. Архивировано 12 ноября 2013 года.
  38. Dmitry Khovratovich; Alex Biryukov, Ivica Nikolić.: The Hash Function Cheetah: Specification and Supporting Documentation (PDF) (30 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  39. Danilo Gligoroski. Danilo Gligoroski - Cheetah hash function is not resistant against length-extension attack (12 декабря 2008). Дата обращения: 21 декабря 2008. Архивировано 12 ноября 2013 года.
  40. Zijie Xu. Dynamic SHA (PDF). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  41. Vlastimil Klima. Dynamic SHA is vulnerable to generic attacks (14 декабря 2008). Дата обращения: 21 декабря 2008. Архивировано 12 ноября 2013 года.
  42. Zijie Xu. Dynamic SHA2 (PDF). NIST. Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  43. Vlastimil Klima. Dynamic SHA2 is vulnerable to generic attacks (14 декабря 2008). Дата обращения: 21 декабря 2008. Архивировано 12 ноября 2013 года.
  44. Danilo Gligoroski; Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal.: edon-r (4 ноября 2008). Дата обращения: 10 ноября 2008. Архивировано 12 ноября 2013 года.
  45. Cryptanalysis of Edon-R (2008). Дата обращения: 10 июля 2009. Архивировано 12 ноября 2013 года.
  46. Sean O'Neil; Karsten Nohl, Luca Henzen.: EnRUPT - The Simpler The Better (31 октября 2008). Дата обращения: 10 ноября 2008. Архивировано 9 декабря 2008 года.
  47. Sebastiaan Indesteege. Collisions for EnRUPT (6 ноября 2008). Дата обращения: 7 ноября 2008. Архивировано из оригинала 18 февраля 2009 года.
  48. Jason Worth Martin. ESSENCE: A Candidate Hashing Algorithm for the NIST Competition (PDF) (21 октября 2008). Дата обращения: 8 ноября 2008. Архивировано из оригинала 12 июня 2010 года.
  49. Cryptanalysis of ESSENCE (PDF). Дата обращения: 12 ноября 2013. Архивировано 12 ноября 2013 года.
  50. Ivica Nikolić; Alex Biryukov, Dmitry Khovratovich.: Hash family LUX - Algorithm Specifications and Supporting Documentation (PDF). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  51. Mikhail Maslennikov. MCSSHA-3 hash algorithm. Дата обращения: 8 ноября 2008. Архивировано из оригинала 2 мая 2009 года.
  52. Second preimages on MCSSHA-3 (PDF). Дата обращения: 14 ноября 2008. (недоступная ссылка)
  53. Peter Maxwell. The Sgàil Cryptographic Hash Function (PDF) (сентябрь 2008). Дата обращения: 9 ноября 2008. Архивировано из оригинала 12 ноября 2013 года.
  54. Peter Maxwell. Aww, p*sh! (5 ноября 2008). Дата обращения: 6 ноября 2008. Архивировано из оригинала 9 ноября 2008 года.
  55. Michael Gorski; Ewan Fleischmann, Christian Forler.: The Twister Hash Function Family (PDF) (28 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  56. Florian Mendel, Christian Rechberger, Martin Schläffer. Cryptanalysis of Twister (PDF) (2008). Дата обращения: 19 мая 2009. Архивировано 12 ноября 2013 года.
  57. Michael Kounavis; Shay Gueron.: Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication (3 ноября 2008). Дата обращения: 11 ноября 2008. Архивировано 2 декабря 2013 года.
  58. Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen. Cryptanalysis of Vortex (PDF) (2009). Дата обращения: 19 мая 2009. Архивировано 12 ноября 2013 года.
  59. Hash Functions | CSRC. Дата обращения: 12 ноября 2013. Архивировано 4 июня 2009 года.
  60. Neil Sholer. Abacus: A Candidate for SHA-3 (PDF) (29 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  61. Gregory G. Rose. Design and Primitive Specification for Boole (PDF). Дата обращения: 8 ноября 2008. Архивировано 6 июля 2011 года.
  62. Gregory G. Rose. OFFICIAL COMMENT: BOOLE (PDF) (10 декабря 2008). Дата обращения: 23 декабря 2008. Архивировано 13 июля 2009 года.
  63. David A. Wilson. The DCH Hash Function (PDF) (23 октября 2008). Дата обращения: 23 ноября 2008. Архивировано 12 ноября 2013 года.
  64. Natarajan Vijayarangan. A NEW HASH ALGORITHM: Khichidi-1 (PDF). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  65. Björn Fay. MeshHash (PDF). Дата обращения: 30 ноября 2008. Архивировано 12 ноября 2013 года.
  66. Orhun Kara; Adem Atalay, Ferhat Karakoc and Cevat Manap.: SHAMATA hash function: A candidate algorithm for NIST competition. Дата обращения: 10 ноября 2008. Архивировано из оригинала 1 февраля 2009 года.
  67. Michal Trojnara. StreamHash Algorithm Specifications and Supporting Documentation (PDF) (14 октября 2008). Дата обращения: 15 декабря 2008. Архивировано 12 ноября 2013 года.
  68. Rafael Alvarez; Gary McGuire and Antonio Zamora.: The Tangle Hash Function (PDF). Дата обращения: 11 декабря 2008. Архивировано 12 ноября 2013 года.
  69. John Washburn. WAMM: A CANDIDATE ALGORITHM FOR THE SHA-3 COMPETITION (PDF). Дата обращения: 9 ноября 2008. Архивировано из оригинала 19 ноября 2008 года.
  70. OFFICIAL COMMENT: WaMM is Withdrawn (PDFauthor=John Washburn) (20 декабря 2008). Дата обращения: 23 декабря 2008. Архивировано 13 июля 2009 года.
  71. Bob Hattersly. Waterfall Hash - Algorithm Specification and Analysis (PDF) (15 октября 2008). Дата обращения: 9 ноября 2008. Архивировано 12 ноября 2013 года.
  72. Bob Hattersley. OFFICIAL COMMENT: Waterfall is broken (PDF) (20 декабря 2008). Дата обращения: 23 декабря 2008. Архивировано 13 июля 2009 года.
  73. Bruce Schneier. Skein and SHA-3 News (19 ноября 2008). Дата обращения: 23 декабря 2008. Архивировано 12 ноября 2013 года.
  74. Jason Lee. HASH 2X. TI BASIC Developer (6 ноября 2008). Дата обращения: 6 ноября 2008. Архивировано 2 мая 2009 года.
  75. HASH 2X. TI BASIC Developer (6 ноября 2008). Дата обращения: 6 ноября 2008. Архивировано 2 мая 2009 года.
  76. Robert J. Jenkins Jr. Algorithm Specification. Дата обращения: 15 декабря 2008. Архивировано 22 декабря 2008 года.
  77. Internal collision attack on Maraca (PDF). Дата обращения: 15 декабря 2008. Архивировано 12 ноября 2013 года.
  78. Geoffrey Park. NKS 2D Cellular Automata Hash (PDF) (недоступная ссылка — история). Дата обращения: 9 ноября 2008.
  79. Cristophe De Cannière. Collisions for NKS2D-224 (13 ноября 2008). Дата обращения: 14 ноября 2008. Архивировано 12 ноября 2013 года.
  80. Brandon Enright. Collisions for NKS2D-512 (14 ноября 2008). Дата обращения: 14 ноября 2008. Архивировано 12 ноября 2013 года.
  81. Peter Schmidt-Nielsen. Ponic (PDF). Дата обращения: 9 ноября 2008. Архивировано 12 ноября 2013 года.
  82. María Naya-Plasencia. Second preimage attack on Ponic (PDF). Дата обращения: 30 ноября 2008. Архивировано 22 июля 2011 года.
  83. ZK-Crypt Homepage. Дата обращения: 1 марта 2009. Архивировано из оригинала 9 февраля 2009 года.
  84. Архивированная копия. Дата обращения: 12 ноября 2013. Архивировано 10 мая 2012 года.