SHA-3 (конкурс)

«SHA-3» — конкурс Национального института стандартов и технологий (NIST) на новую криптографическую хеш-функцию, предназначенную для дополнения и замены SHA-1 и SHA-2. Проводился в течение в 2007—2012 годов, в результате был избран алгоритм для реализации SHA-3.

NITS Competition.jpg

Официально объявлен в журнале 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[en], Joan Daemen, Gilles Van Assche[en] из STMicroelectronics и Michaël Peeters[en] из 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 (Friday, November 2, 2007). Дата обращения: 6 ноября 2008.
  2. cryptographic hash project - Background Information. Computer Security Resource Center. National Institute of Standards and Technology (November 2, 2007). Дата обращения: 6 ноября 2008.
  3. 1 2 NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST (October 2, 2012). Дата обращения: 2 октября 2012.
  4. Shneier on Security: SHA-3 to Be Announced
  5. 1 2 3 4 5 6 7 8 9 10 11 Round 1 (9 декабря 2008). Дата обращения: 10 декабря 2008.
  6. National Institute of Standards and Technology. The First SHA-3 Candidate Conference (December 9, 2008). Дата обращения: 23 декабря 2008.
  7. 1 2 Second Round Candidates. National Institute for Standards and Technology (July 24, 2009). Дата обращения: 24 июля 2009.
  8. National Institute of Standards and Technology. The Second SHA-3 Candidate Conference (June 30, 2010).
  9. Tentative Timeline of the Development of New Hash Functions. NIST (December 10, 2008). Дата обращения: 15 сентября 2009.
  10. Hash Functions | CSRC
  11. http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf
  12. Hash Functions | CSRC
  13. Performance Analysis of the SHA-3 Candidates on Exotic Multi-core Architectures — Springer
  14. Hash Functions | CSRC
  15. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
  16. THIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011
  17. 1 2 3 4 SHA-3 Finalists Announced by NIST. National Institute for Standards and Technology (December 10, 2010).
  18. Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition
  19. Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (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 (November 4, 2008). Дата обращения: 10 ноября 2008.
  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) (October 29, 2008). Дата обращения: 11 декабря 2008.
  23. Özgül Kücük. The Hash Function Hamsi (PDF) (31 October 2008). Дата обращения: 11 декабря 2008.
  24. Dai Watanabe; Christophe De Canniere, Hisayoshi Sato. Hash Function Luffa: Specification (PDF) (31 October 2008). Дата обращения: 11 декабря 2008.
  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) (October 28, 2008). Дата обращения: 11 декабря 2008.
  26. Eli Biham; Orr Dunkelman. The SHAvite-3 Hash Function (PDF). Дата обращения: 11 декабря 2008.
  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) (October 29, 2008). Дата обращения: 11 декабря 2008.
  28. Philip Hawkes; Cameron McDonald. Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms (October 30, 2008). Дата обращения: 11 ноября 2008.
  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 October 2008). Дата обращения: 11 декабря 2008.
  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) (October 31, 2008). Дата обращения: 11 декабря 2008.
  34. Attacks on AURORA-512 and the Double-Mix Merkle-Damgaard Transform (PDF) (2009). Дата обращения: 10 июля 2009.
  35. Colin Bradbury. BLENDER: A Proposed New Family of Cryptographic Hash Algorithms (PDF) (25 October 2008). Дата обращения: 11 декабря 2008.
  36. Craig Newbold. Observations and Attacks On The SHA-3 Candidate Blender (PDF). Дата обращения: 23 декабря 2008.
  37. Florian Mendel. Preimage Attack on Blender (PDF). Дата обращения: 23 декабря 2008.
  38. Dmitry Khovratovich; Alex Biryukov, Ivica Nikolić. The Hash Function Cheetah: Specification and Supporting Documentation (PDF) (October 30, 2008). Дата обращения: 11 декабря 2008.
  39. Danilo Gligoroski. Danilo Gligoroski - Cheetah hash function is not resistant against length-extension attack (12 декабря 2008). Дата обращения: 21 декабря 2008.
  40. Zijie Xu. Dynamic SHA (PDF). Дата обращения: 11 декабря 2008.
  41. Vlastimil Klima. Dynamic SHA is vulnerable to generic attacks (14 декабря 2008). Дата обращения: 21 декабря 2008.
  42. Zijie Xu. Dynamic SHA2 (PDF). NIST. Дата обращения: 11 декабря 2008.
  43. Vlastimil Klima. Dynamic SHA2 is vulnerable to generic attacks (14 декабря 2008). Дата обращения: 21 декабря 2008.
  44. Danilo Gligoroski; Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal. edon-r (November 4, 2008). Дата обращения: 10 ноября 2008.
  45. Cryptanalysis of Edon-R (2008). Дата обращения: 10 июля 2009.
  46. Sean O'Neil; Karsten Nohl, Luca Henzen. EnRUPT - The Simpler The Better (October 31, 2008). Дата обращения: 10 ноября 2008.
  47. Sebastiaan Indesteege. Collisions for EnRUPT (недоступная ссылка) (November 6, 2008). Дата обращения: 7 ноября 2008. Архивировано 18 февраля 2009 года.
  48. Jason Worth Martin. ESSENCE: A Candidate Hashing Algorithm for the NIST Competition (PDF) (недоступная ссылка) (October 21, 2008). Дата обращения: 8 ноября 2008. Архивировано 12 июня 2010 года.
  49. Cryptanalysis of ESSENCE (PDF).
  50. Ivica Nikolić; Alex Biryukov, Dmitry Khovratovich. Hash family LUX - Algorithm Specifications and Supporting Documentation (PDF). Дата обращения: 11 декабря 2008.
  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) (недоступная ссылка) (September 2008). Дата обращения: 9 11 2008. Архивировано 12 ноября 2013 года.
  54. Peter Maxwell. Aww, p*sh! (недоступная ссылка) (November 5, 2008). Дата обращения: 6 ноября 2008. Архивировано 9 ноября 2008 года.
  55. Michael Gorski; Ewan Fleischmann, Christian Forler. The Twister Hash Function Family (PDF) (October 28, 2008). Дата обращения: 11 декабря 2008.
  56. Florian Mendel, Christian Rechberger, Martin Schläffer. Cryptanalysis of Twister (PDF) (2008). Дата обращения: 19 мая 2009.
  57. Michael Kounavis; Shay Gueron. Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication (November 3, 2008). Дата обращения: 11 ноября 2008.
  58. Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen. Cryptanalysis of Vortex (PDF) (2009). Дата обращения: 19 мая 2009.
  59. Hash Functions | CSRC
  60. Neil Sholer. Abacus: A Candidate for SHA-3 (PDF) (October 29, 2008). Дата обращения: 11 декабря 2008.
  61. Gregory G. Rose. Design and Primitive Specification for Boole (PDF). Дата обращения: 8 ноября 2008.
  62. Gregory G. Rose. OFFICIAL COMMENT: BOOLE (PDF) (10 Dec 2008). Дата обращения: 23 декабря 2008.
  63. David A. Wilson. The DCH Hash Function (PDF) (October 23, 2008). Дата обращения: 23 ноября 2008.
  64. Natarajan Vijayarangan. A NEW HASH ALGORITHM: Khichidi-1 (PDF). Дата обращения: 11 декабря 2008.
  65. Björn Fay. MeshHash (PDF). Дата обращения: 30 ноября 2008.
  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) (October 14, 2008). Дата обращения: 15 декабря 2008.
  68. Rafael Alvarez; Gary McGuire and Antonio Zamora. The Tangle Hash Function (PDF). Дата обращения: 11 декабря 2008.
  69. John Washburn. WAMM: A CANDIDATE ALGORITHM FOR THE SHA-3 COMPETITION (PDF) (недоступная ссылка). Дата обращения: 9 11 2008. Архивировано 19 ноября 2008 года.
  70. OFFICIAL COMMENT: WaMM is Withdrawn (PDFauthor=John Washburn) (20 Dec 2008). Дата обращения: 23 декабря 2008.
  71. Bob Hattersly. Waterfall Hash - Algorithm Specification and Analysis (PDF) (October 15, 2008). Дата обращения: 9 11 2008.
  72. Bob Hattersley. OFFICIAL COMMENT: Waterfall is broken (PDF) (20 Dec 2008). Дата обращения: 23 декабря 2008.
  73. Bruce Schneier. Skein and SHA-3 News (November 19, 2008). Дата обращения: 23 декабря 2008.
  74. Jason Lee. HASH 2X. TI BASIC Developer (November 6, 2008). Дата обращения: 6 ноября 2008.
  75. HASH 2X. TI BASIC Developer (November 6, 2008). Дата обращения: 6 ноября 2008.
  76. Robert J. Jenkins Jr. Algorithm Specification. Дата обращения: 15 декабря 2008.
  77. Internal collision attack on Maraca (PDF). Дата обращения: 15 декабря 2008.
  78. Geoffrey Park. NKS 2D Cellular Automata Hash (PDF). Дата обращения: 9 11 2008.
  79. Cristophe De Cannière. Collisions for NKS2D-224 (November 13, 2008). Дата обращения: 14 ноября 2008.
  80. Brandon Enright. Collisions for NKS2D-512 (November 14, 2008). Дата обращения: 14 ноября 2008.
  81. Peter Schmidt-Nielsen. Ponic (PDF). Дата обращения: 9 11 2008.
  82. María Naya-Plasencia. Second preimage attack on Ponic (PDF). Дата обращения: 30 ноября 2008.
  83. ZK-Crypt Homepage (недоступная ссылка). Дата обращения: 1 марта 2009. Архивировано 9 февраля 2009 года.
  84. http://eprint.iacr.org/2008/511.pdf

СсылкиПравить