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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
NITS Competition.jpg

Национальный институт стандартов и технологий США (англ. National Institute of Standards and Technology, сокращённо NIST) создал конкурс на новую хеш-функцию, названную SHA-3, для дополнения и дальнейшей замены старых функций: SHA-1 и SHA-2. Конкурс был анонсирован в журнале Federal Register 2 ноября 2007 года.[1] NIST инициировал разработку одного или нескольких дополнительных алгоритмов хеширования через открытый конкурс, подобный процесс развития был использован ранее для шифрования Advanced Encryption Standard (сокращённо AES).[2]

Конкурс завершился 2 октября 2012 года, когда NIST объявил, что Keccak будет новым SHA-3 хеш-алгоритмом.[3]

Цели конкурса[править | править вики-текст]

Изначально организаторы конкурса предполагали заменить старые хеш-функции победителем, так как в 2006 году возникло предположение, что в будущем надежность хеш-функции SHA-2 значительно снизится из-за роста мощности и производительности устройств, а также из-за появления новых методов криптоанализа. Но в 2013 году оказалось, что SHA-2 является криптостойкой, поэтому переход на SHA-3 не является необходимым.

Процесс[править | править вики-текст]

Подача заявок была завершена 31 октября 2008 года. Список кандидатов, прошедших в первый раунд, был опубликован 9 декабря 2008 года.[4]В конце февраля 2009 года NIST провели конференцию, где представили заявленные в конкурс хеш-функции и обсудили критерии прохождения во второй раунд.[5] Список из 14 кандидатов, прошедших в раунд 2, был опубликован 24 июля 2009 года.[6]Еще одна конференция состоялась 23 и 24 августа 2010 года в University of California, Santa Barbara, где были рассмотрены кандидаты, прошедшие во второй раунд.[7] О последнем туре кандидатов было объявлено 10 декабря 2010 года.[8] И только 2 октября 2012 года NIST объявил победителя - Keccak, его создатели: Guido Bertoni, Joan Daemen, Gilles Van Assche из STMicroelectronics и Michaël Peeters из NXP.[3]

Критерии оценки[править | править вики-текст]

В своих отчетах NIST описывает критерии оценки конкурсантов. Основными критериями оценки были безопасность, производительность и алгоритм хеш-функции[9][10][11].

Безопасность[править | править вики-текст]

Рассматривая безопасность конкурсантов, NIST оценивал применимость хеш-функции, её устойчивость к атакам, соответствие общим для хеш-функций требованиям, а также соответствие требованиям для участников, использующих HMAC, псевдослучайные функции или рандомизированное хеширование. Этот критерий учитывался в первую очередь.

Производительность[править | править вики-текст]

Производительность — второй по важности критерий оценки после безопасности. При его проверке смотрели на скорость работы и требования к памяти. Сравнение происходило следующим образом:

  • В брэнчмарке ECRYPT Benchmarking of All Submitted Hashes (сокращёенно eBASH) производились замеры скорости вычисления для большого числа 32х и 64х-битных платформ.
  • Брэнчмарк eXternal Benchmarking eXtension (сокращённо XBX) предоставил результаты для портативных устройств.
  • Дополнительно проверялась производительность и возможность оптимизации на многоядерных архитектурах. Тесты производились на архитектурах Cell Broadband Engine (сокращённо Cell) и the NVIDIA Graphics Processing Units (сокращённо GPUs).[12]

Также оценивалась скорость работы на конечных устройствах: ПК, мобильных устройствах (точки доступа, роутеры, портативные медиаплееры, мобильные телефоны и терминалы оплаты) и в виртуальных машинах.[13]

Алгоритм и характеристики реализации[править | править вики-текст]

Основными параметрами оценки алгоритма были гибкость и простота дизайна. Гибкость включает в себя возможность использования хеш-функции на большом числе платформ и возможности расширения набора инструкций процессора и распараллеливания (для увеличения производительности). Простота дизайна оценивалась по сложности анализа и понимания алгоритма, таким образом простота дизайна дает больше уверенности в оценке безопасности алгоритма.

Участники[править | править вики-текст]

NIST выбрали 51 хеш-функцию в первый тур.[4] 14 из них прошло во второй раунд,[6] из которых было выбрано 5 финалистов. Неполный список участников представлен ниже.

Победитель[править | править вики-текст]

Победитель был объявлен 2 октября 2012 года, им стал алгоритм Keccak.[14] Он стал самым производительным на аппаратной реализации среди финалистов, а также в нем был использован нераспространённый метод шифрования - функция Губка. Таким образом, атаки, рассчитанные на SHA-2, не будут работать. Ещё одним существенным преимуществом SHA-3 является возможность его реализации на миниатюрных встраиваемых устройствах (например, USB-флеш-накопитель).

Финалисты[править | править вики-текст]

NIST выбрал пять кандидатов, прошедших в третьей (и последний) тур:[15]

NIST описали некоторые критерии, на которых основывался выбор финалистов:[16]

  • Производительность: «Некоторые алгоритмы были уязвимы из-за очень больших требований к производительности.»[16]
  • Безопасность: «Мы предпочли быть консервативными в безопасности и в некоторых случаях не выбрали алгоритмы с исключительной производительностью, потому что они менее безопасны в значительной степени.»[16]
  • Анализ: «NIST устранено несколько алгоритмов из-за неполной проверки или незрелости проекта.»
  • Разнообразии: «Хеш-функции, прошедшие в финал, основаны на различных режимах работы, в том числе и на принципе криптографической губки. С разными внутренними структурами, в том числе на основе AES, Bit slicing и на переменных XOR с дополнением.»[16]

NIST выпустил отчет, поясняющий оценку алгоритмов.[17][18]

Хеш-функции, не прошедшие в финал[править | править вики-текст]

Следующие хеш-функции попали во второй раунд, но не прошли в финал. Также было при объявлении финалистов: «Ни один из этих кандидатов не был явно взломан». В скобках указана причина, по которой хеш-функции не стала финалистом.

  • Blue Midnight Wish[19][20] (возможны проблемы с безопасностью)
  • CubeHash (Bernstein) (проблемы с производительностью)
  • ECHO (France Telecom)[21] (проблемы с производительностью)
  • Fugue (IBM) (проблемы с безопасностью)
  • Hamsi[22] (высокие требования к ПЗУ)
  • Luffa[23] (возможны проблемы с безопасностью))

Хеш-функция, не прошедшие во второй раунд[править | править вики-текст]

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

Заявленные хеш-функции с существенными уязвимостями[править | править вики-текст]

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

Отказавшиеся конкурсанты[править | править вики-текст]

На протяжении первого раунда некоторые конкурсанты сами отказались от участия в конкурсе, потому что были взломаны на NIST official Round One Candidates web site. Они не принимали участия в конкурсе.

Отклоненные участники[править | править вики-текст]

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

Классификация кандидатов[править | править вики-текст]

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

Ссылки[править | править вики-текст]

  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. 1 2 3 4 5 6 7 8 9 10 11 Round 1 (9 декабря 2008). Проверено 10 декабря 2008.
  5. National Institute of Standards and Technology. The First SHA-3 Candidate Conference (December 9, 2008). Проверено 23 декабря 2008.
  6. 1 2 Second Round Candidates. National Institute for Standards and Technology (July 24, 2009). Проверено 24 июля 2009.
  7. National Institute of Standards and Technology. The Second SHA-3 Candidate Conference (June 30, 2010).
  8. Tentative Timeline of the Development of New Hash Functions. NIST (December 10, 2008). Проверено 15 сентября 2009.
  9. http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Round2_Report_NISTIR_7764.pdf
  10. http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf
  11. http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/sha3_NISTIR7620.pdf
  12. Performance Analysis of the SHA-3 Candidates on Exotic Multi-core Architectures — Springer
  13. http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/Pornin_report-sphlib-tp-final.pdf
  14. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
  15. THIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011
  16. 1 2 3 4 SHA-3 Finalists Announced by NIST. National Institute for Standards and Technology (December 10, 2010).
  17. Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition
  18. Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011
  19. 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.
  20. Søren S. Thomsen. Pseudo-cryptanalysis of Blue Midnight Wish (PDF) (2009). Проверено 19 мая 2009.
  21. 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.
  22. Özgül Kücük. The Hash Function Hamsi (PDF) (31 October 2008). Проверено 11 декабря 2008.
  23. Dai Watanabe; Christophe De Canniere, Hisayoshi Sato. Hash Function Luffa: Specification (PDF) (31 October 2008). Проверено 11 декабря 2008.
  24. 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.
  25. Eli Biham; Orr Dunkelman. The SHAvite-3 Hash Function (PDF). Проверено 11 декабря 2008.
  26. 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.
  27. Philip Hawkes; Cameron McDonald. Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms (October 30, 2008). Проверено 11 ноября 2008.
  28. Jacques Patarin; Louis Goubin, Mickael Ivascot, William Jalby, Olivier Ly, Valerie Nachef, Joana Treger, Emmanuel Volte. CRUNCH. Проверено 14 ноября 2008.
  29. Hirotaka Yoshida; Shoichi Hirose, Hidenori Kuwakado. SHA-3 Proposal: Lesamnta (PDF) (30 October 2008). Проверено 11 декабря 2008.
  30. Kerem Varıcı; Onur Özen and Çelebi Kocair. The Sarmal Hash Function. Проверено 12 октября 2010.
  31. Daniel Penazzi; Miguel Montes. The TIB3 Hash. Проверено 29 ноября 2008.
  32. AURORA: A Cryptographic Hash Algorithm Family (PDF) (October 31, 2008). Проверено 11 декабря 2008.
  33. Attacks on AURORA-512 and the Double-Mix Merkle-Damgaard Transform (PDF) (2009). Проверено 10 июля 2009.
  34. Colin Bradbury. BLENDER: A Proposed New Family of Cryptographic Hash Algorithms (PDF) (25 October 2008). Проверено 11 декабря 2008.
  35. Craig Newbold. Observations and Attacks On The SHA-3 Candidate Blender (PDF). Проверено 23 декабря 2008.
  36. Florian Mendel. Preimage Attack on Blender (PDF). Проверено 23 декабря 2008.
  37. Dmitry Khovratovich; Alex Biryukov, Ivica Nikolić. The Hash Function Cheetah: Specification and Supporting Documentation (PDF) (October 30, 2008). Проверено 11 декабря 2008.
  38. Danilo Gligoroski. Danilo Gligoroski - Cheetah hash function is not resistant against length-extension attack (12 декабря 2008). Проверено 21 декабря 2008.
  39. Zijie Xu. Dynamic SHA (PDF). Проверено 11 декабря 2008.
  40. Vlastimil Klima. Dynamic SHA is vulnerable to generic attacks (14 декабря 2008). Проверено 21 декабря 2008.
  41. Zijie Xu. Dynamic SHA2 (PDF). NIST. Проверено 11 декабря 2008.
  42. Vlastimil Klima. Dynamic SHA2 is vulnerable to generic attacks (14 декабря 2008). Проверено 21 декабря 2008.
  43. Danilo Gligoroski; Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal. edon-r (November 4, 2008). Проверено 10 ноября 2008.
  44. Cryptanalysis of Edon-R (2008). Проверено 10 июля 2009.
  45. Sean O'Neil; Karsten Nohl, Luca Henzen. EnRUPT - The Simpler The Better (October 31, 2008). Проверено 10 ноября 2008.
  46. Sebastiaan Indesteege. Collisions for EnRUPT (November 6, 2008). Проверено 7 ноября 2008.
  47. Jason Worth Martin. ESSENCE: A Candidate Hashing Algorithm for the NIST Competition (PDF) (October 21, 2008). Проверено 8 ноября 2008.
  48. Cryptanalysis of ESSENCE (PDF).
  49. Ivica Nikolić; Alex Biryukov, Dmitry Khovratovich. Hash family LUX - Algorithm Specifications and Supporting Documentation (PDF). Проверено 11 декабря 2008.
  50. Mikhail Maslennikov. MCSSHA-3 hash algorithm. Проверено 8 ноября 2008.
  51. Second preimages on MCSSHA-3 (PDF). Проверено 14 ноября 2008.
  52. Peter Maxwell. The Sgàil Cryptographic Hash Function (PDF) (September 2008). Проверено 9 11 2008.
  53. Peter Maxwell. Aww, p*sh! (November 5, 2008). Проверено 6 ноября 2008.
  54. Michael Gorski; Ewan Fleischmann, Christian Forler. The Twister Hash Function Family (PDF) (October 28, 2008). Проверено 11 декабря 2008.
  55. Florian Mendel, Christian Rechberger, Martin Schläffer. Cryptanalysis of Twister (PDF) (2008). Проверено 19 мая 2009.
  56. 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.
  57. Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen. Cryptanalysis of Vortex (PDF) (2009). Проверено 19 мая 2009.
  58. Neil Sholer. Abacus: A Candidate for SHA-3 (PDF) (October 29, 2008). Проверено 11 декабря 2008.
  59. Gregory G. Rose. Design and Primitive Specification for Boole (PDF). Проверено 8 ноября 2008.
  60. Gregory G. Rose. OFFICIAL COMMENT: BOOLE (PDF) (10 Dec 2008). Проверено 23 декабря 2008.
  61. David A. Wilson. The DCH Hash Function (PDF) (October 23, 2008). Проверено 23 ноября 2008.
  62. Natarajan Vijayarangan. A NEW HASH ALGORITHM: Khichidi-1 (PDF). Проверено 11 декабря 2008.
  63. Björn Fay. MeshHash (PDF). Проверено 30 ноября 2008.
  64. Orhun Kara; Adem Atalay, Ferhat Karakoc and Cevat Manap. SHAMATA hash function: A candidate algorithm for NIST competition. Проверено 10 ноября 2008.
  65. Michal Trojnara. StreamHash Algorithm Specifications and Supporting Documentation (PDF) (October 14, 2008). Проверено 15 декабря 2008.
  66. Rafael Alvarez; Gary McGuire and Antonio Zamora. The Tangle Hash Function (PDF). Проверено 11 декабря 2008.
  67. John Washburn. WAMM: A CANDIDATE ALGORITHM FOR THE SHA-3 COMPETITION (PDF). Проверено 9 11 2008.
  68. OFFICIAL COMMENT: WaMM is Withdrawn (PDFauthor=John Washburn) (20 Dec 2008). Проверено 23 декабря 2008.
  69. Bob Hattersly. Waterfall Hash - Algorithm Specification and Analysis (PDF) (October 15, 2008). Проверено 9 11 2008.
  70. Bob Hattersley. OFFICIAL COMMENT: Waterfall is broken (PDF) (20 Dec 2008). Проверено 23 декабря 2008.
  71. Bruce Schneier. Skein and SHA-3 News (November 19, 2008). Проверено 23 декабря 2008.
  72. Jason Lee. HASH 2X. TI BASIC Developer (November 6, 2008). Проверено 6 ноября 2008.
  73. HASH 2X. TI BASIC Developer (November 6, 2008). Проверено 6 ноября 2008.
  74. Robert J. Jenkins Jr. Algorithm Specification. Проверено 15 декабря 2008.
  75. Internal collision attack on Maraca (PDF). Проверено 15 декабря 2008.
  76. Geoffrey Park. NKS 2D Cellular Automata Hash (PDF). Проверено 9 11 2008.
  77. Cristophe De Cannière. Collisions for NKS2D-224 (November 13, 2008). Проверено 14 ноября 2008.
  78. Brandon Enright. Collisions for NKS2D-512 (November 14, 2008). Проверено 14 ноября 2008.
  79. Peter Schmidt-Nielsen. Ponic (PDF). Проверено 9 11 2008.
  80. María Naya-Plasencia. Second preimage attack on Ponic (PDF). Проверено 30 ноября 2008.
  81. ZK-Crypt Homepage. Проверено 1 марта 2009.
  82. http://eprint.iacr.org/2008/511.pdf

Внешние ссылки[править | править вики-текст]

 Просмотр этого шаблона Хеш-функции
Общего назначения

Adler-32 CRC FNV Murmur2 PJW-32 TTH Jenkins hash

Криптографические

JH HAVAL Keccak (SHA-3) • LM-хеш Luffa MD2 MD4 MD5 MD6 N-Hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 Scrypt SHA-1 SHA-2 Skein Snefru Tiger Whirlpool ГОСТ Р 34.11-94 ГОСТ Р 34.11-2012