NIST 해시함수 경연대회

NIST hash function competition

NIST 해시함수 경연대회는 미국 국립표준기술원(NIST)이 구형 SHA-1과 SHA-2를 보완하기 위해 SHA-3라는 새로운 해시함수를 개발하기 위해 개최한 공개 대회였다. 이 대회는 2007년 11월 2일 연방관보에 정식으로 발표되었다.[1] "NIST는 고급암호화표준(AES)의 개발 과정과 유사하게 공개경쟁을 통해 하나 이상의 추가 해시 알고리즘을 개발하려는 노력을 개시하고 있다."[2] 이 대회는 2012년 10월 2일 NIST가 케카크가 새로운 SHA-3 해시 알고리즘이 될 것이라고 발표하면서 막을 내렸다.[3]

우승 해시함수는 FIPS 180-4, Secure Hash Standard를 보완하기 위해 NIST FIPS 202 "SHA-3 Standard"로 발행되었다.

NIST 경기는 암호 해싱 경기와 같은 다른 경기에 영감을 주었다.

과정

제출 기한은 2008년 10월 31일로 1차 합격자 명단은 2008년 12월 9일에 발표되었다.[4] NIST는 2009년 2월 말 컨퍼런스를 개최하여 제출자가 알고리즘을 제시하고 NIST 관계자가 2라운드 후보 범위를 좁히는 기준을 논의하였다.[5] 2009년 7월 24일 2라운드에 합격된 14명의 후보자 명단이 발표되었다.[6] 2010년 8월 23~24일(CRYPLO 2010년 이후)에 또 다른 컨퍼런스가 산타바바라 주 캘리포니아 대학교에서 개최되어 2차 후보자들이 논의되었다.[7] 결선 후보자 발표는 2010년 12월 10일에 있었다.[8] 2012년 10월 2일, NIST는 우승자를 발표하여, STMicroelectronics의 귀도 베르토니, 조안 대멘, 그리고 질스 반 앗쉬와 NXP의 Michael Peeters가 만든 케카크를 선정하였다.[3]

진입자

이것은 알려진 제출물의 불완전한 목록이다. NIST는 1라운드에 51개의 출품작을 선정했다.[4] 이 중 14개 출품작을 2라운드로 진출시켰고,[6] 이 중 5개의 최종 후보작을 선정했다.

위너

우승자는 2012년 10월 2일 케차크라고 발표되었다.[9]

결승전

NIST는 세 번째(및 최종) 라운드에 진출하기 위해 5개의 SHA-3 후보 알고리즘을 선택했다.[10]

NIST는 최종 결승 진출자를 발표하면서 선정 과정에서 고려된 몇 가지 요인에 주목했다.[11]

  • 성능: "아주 큰 [하드웨어 게이트] 영역 요구 사항으로 인해 알고리즘 몇 개가 손상되거나 제거되었으며, 필요한 영역이 잠재적인 애플리케이션 공간의 너무 많은 부분에서 사용을 방해하는 것으로 보였다."
  • 보안: "우리는 보안에 대해 보수적인 것을 선호했고, 어떤 경우에는 예외적인 성능을 가진 알고리즘을 선택하지 않았는데, 그들에 대한 무언가가 우리를 '신경쓰게' 했기 때문인데, 전체 알고리즘에 대한 명확한 공격을 알지 못했기 때문이지요."
  • 분석: "NIST는 2차 수정의 정도나 보고된 암호 분석이 상대적으로 부족하기 때문에 여러 알고리즘을 제거했는데, 이는 설계가 아직 완전히 테스트되지 않고 성숙되지 않을 수 있다는 의심을 불러일으키는 경향이 있다."
  • 다양성: 최종 후보에는 HAIFA 및 스펀지 기능 구성 등 다양한 작동 모드와 AES 기반 해시, 비트라이징, XOR 교대 등 내부 구조가 서로 다른 해시가 포함되었다.

NIST는 알고리즘별 평가 알고리즘을 설명하는 보고서를 발표했다.[12][13][14]

결승전에 통과하지 못함

다음과 같은 해시함수 제출이 2라운드에서 받아들여졌지만 최종 라운드에는 오르지 못했다. 결선 진출자 발표에서 지적했듯이, "이들 중 어느 후보도 명백히 깨지지 않았다".

2라운드에 통과하지 못함

다음과 같은 해시함수 제출이 라운드 1에 받아들여졌으나 라운드 2에 통과하지 못했다. 그들은 제출자들로부터 인정받지도 않았고 실질적인 암호 약점도 없었다. 그러나 이들 중 대부분은 설계 구성요소 또는 성능 문제에서 일부 약점이 있다.

상당한 약점이 있는 등록자

다음과 같은 비컨디드 라운드 원 참가자는 실질적인 암호 약점이 발표되었다.

허가된 진입자

다음 라운드 원 참가자는 제출자에 의해 경기에서 공식적으로 철회되었다. NIST 공식 라운드 원 후보 웹사이트에 따르면, 그들은 깨진 것으로 간주된다.[54] 그러다 보니 이들은 경쟁에서 밀려난다.

거부된 진입자

NIST가 받은 여러 개의 출품작들은 NIST의 내부 검토에 따라 1라운드 후보로 받아들여지지 않았다.[4] 일반적으로 NIST는 각자가 거부된 이유에 대해 자세한 내용을 밝히지 않았다. NIST는 또한 거부된 알고리즘의 포괄적인 목록을 제공하지 않았다. 13개가 있는 것으로 알려져 있지만,[4][68] 다음 사항만 공개된다.

참고 항목

참조

  1. ^ "Federal Register / Vol. 72, No. 212" (PDF). Federal Register. Government Printing Office. November 2, 2007. Retrieved November 6, 2008.
  2. ^ "cryptographic hash project – Background Information". Computer Security Resource Center. National Institute of Standards and Technology. November 2, 2007. Retrieved November 6, 2008.
  3. ^ a b "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST. October 2, 2012. Retrieved October 2, 2012.
  4. ^ a b c d e f g h i j k "Round 1". December 9, 2008. Retrieved December 10, 2008.
  5. ^ National Institute of Standards and Technology (December 9, 2008). "The First SHA-3 Candidate Conference". Retrieved December 23, 2008.
  6. ^ a b "Second Round Candidates". National Institute for Standards and Technology. July 24, 2009. Retrieved July 24, 2009.
  7. ^ National Institute of Standards and Technology (June 30, 2010). "The Second SHA-3 Candidate Conference".
  8. ^ "Tentative Timeline of the Development of New Hash Functions". NIST. December 10, 2008. Retrieved September 15, 2009.
  9. ^ NIST, Secure Hash Algorithm (SHA-3) 경기 우승자 선정
  10. ^ 2011년 11월 9일 회수된 세 번째(최종) 라운드 후보
  11. ^ NIST가 2011년 7월 9일 웨이백 머신(Wayback Machine)에서 발표한 SHA-3 결승전 진출자는 NIST의 발표를 인용한 블로그 게시물.
  12. ^ SHA-3 암호해시 알고리즘 경진대회 1라운드 현황보고서(PDF)
  13. ^ SHA-3 암호해시 알고리즘 경진대회 2라운드 현황보고서(PDF) 2011년 3월 2일 검색됨
  14. ^ SHA-3 암호해시 알고리즘 경연대회 3라운드 보고서(PDF).
  15. ^ Svein Johan Knapskog; Danilo Gligoroski; Vlastimil Klima; Mohamed El-Hadedy; Jørn Amundsen; Stig Frode Mjølsnes (November 4, 2008). "blue_midnight_wish". Retrieved November 10, 2008.
  16. ^ Søren S. Thomsen (2009). "Pseudo-cryptanalysis of Blue Midnight Wish" (PDF). Archived from the original (PDF) on September 2, 2009. Retrieved May 19, 2009.
  17. ^ Henri Gilbert; Ryad Benadjila; Olivier Billet; Gilles Macario-Rat; Thomas Peyrin; Matt Robshaw; Yannick Seurin (October 29, 2008). "SHA-3 Proposal: ECHO" (PDF). Retrieved December 11, 2008.
  18. ^ Özgül Kücük (October 31, 2008). "The Hash Function Hamsi" (PDF). Retrieved December 11, 2008.
  19. ^ Dai Watanabe; Christophe De Canniere; Hisayoshi Sato (October 31, 2008). "Hash Function Luffa: Specification" (PDF). Retrieved December 11, 2008.
  20. ^ 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 (October 28, 2008). "Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition" (PDF). Retrieved December 11, 2008.
  21. ^ Eli Biham; Orr Dunkelman. "The SHAvite-3 Hash Function" (PDF). Retrieved December 11, 2008.
  22. ^ Jongin Lim; Donghoon Chang; Seokhie Hong; Changheon Kang; Jinkeon Kang; Jongsung Kim; Changhoon Lee; Jesang Lee; Jongtae Lee; Sangjin Lee; Yuseop Lee; Jaechul Sung (October 29, 2008). "ARIRANG" (PDF). Retrieved December 11, 2008.
  23. ^ Philip Hawkes; Cameron McDonald (October 30, 2008). "Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms" (PDF). Retrieved November 11, 2008.
  24. ^ Jacques Patarin; Louis Goubin; Mickael Ivascot; William Jalby; Olivier Ly; Valerie Nachef; Joana Treger; Emmanuel Volte. "CRUNCH". Archived from the original on January 29, 2009. Retrieved November 14, 2008.
  25. ^ Hirotaka Yoshida; Shoichi Hirose; Hidenori Kuwakado (October 30, 2008). "SHA-3 Proposal: Lesamnta" (PDF). Retrieved December 11, 2008.
  26. ^ Kerem Varıcı; Onur Özen; Çelebi Kocair. "The Sarmal Hash Function". Archived from the original on June 11, 2011. Retrieved October 12, 2010.
  27. ^ Daniel Penazzi; Miguel Montes. "The TIB3 Hash" (PDF). Retrieved November 29, 2008.[영구적 데드링크]
  28. ^ Tetsu Iwata; Kyoji Shibutani; Taizo Shirai; Shiho Moriai; Toru Akishita (October 31, 2008). "AURORA: A Cryptographic Hash Algorithm Family" (PDF). Retrieved December 11, 2008.
  29. ^ Niels Ferguson; Stefan Lucks (2009). "Attacks on AURORA-512 and the Double-MIX Merkle–Damgård Transform" (PDF). Retrieved July 10, 2009.
  30. ^ Colin Bradbury (October 25, 2008). "BLENDER: A Proposed New Family of Cryptographic Hash Algorithms" (PDF). Retrieved December 11, 2008.
  31. ^ Craig Newbold. "Observations and Attacks On The SHA-3 Candidate Blender" (PDF). Retrieved December 23, 2008.
  32. ^ Florian Mendel. "Preimage Attack on Blender" (PDF). Retrieved December 23, 2008.
  33. ^ Dmitry Khovratovich; Alex Biryukov; Ivica Nikolić (October 30, 2008). "The Hash Function Cheetah: Specification and Supporting Documentation" (PDF). Retrieved December 11, 2008.
  34. ^ Danilo Gligoroski (December 12, 2008). "Danilo Gligoroski – Cheetah hash function is not resistant against length-extension attack". Retrieved December 21, 2008.
  35. ^ Zijie Xu. "Dynamic SHA" (PDF). Retrieved December 11, 2008.
  36. ^ Vlastimil Klima (December 14, 2008). "Dynamic SHA is vulnerable to generic attacks". Retrieved December 21, 2008.
  37. ^ Zijie Xu. "Dynamic SHA2" (PDF). NIST. Retrieved December 11, 2008.
  38. ^ Vlastimil Klima (December 14, 2008). "Dynamic SHA2 is vulnerable to generic attacks". Retrieved December 21, 2008.
  39. ^ Danilo Gligoroski; Rune Steinsmo Ødegård; Marija Mihova; Svein Johan Knapskog; Ljupco Kocarev; Aleš Drápal (November 4, 2008). "edon-r". Retrieved November 10, 2008.
  40. ^ Dmitry Khovratovich; Ivica Nikolić; Ralf-Philipp Weinmann (2008). "Cryptanalysis of Edon-R" (PDF). Retrieved July 10, 2009.
  41. ^ Sean O'Neil; Karsten Nohl; Luca Henzen (October 31, 2008). "EnRUPT – The Simpler The Better". Retrieved November 10, 2008.
  42. ^ Sebastiaan Indesteege (November 6, 2008). "Collisions for EnRUPT". Archived from the original on February 18, 2009. Retrieved November 7, 2008.
  43. ^ Jason Worth Martin (October 21, 2008). "ESSENCE: A Candidate Hashing Algorithm for the NIST Competition" (PDF). Archived from the original (PDF) on June 12, 2010. Retrieved November 8, 2008.
  44. ^ "Cryptanalysis of ESSENCE" (PDF).
  45. ^ Ivica Nikolić; Alex Biryukov; Dmitry Khovratovich. "Hash family LUX – Algorithm Specifications and Supporting Documentation" (PDF). Retrieved December 11, 2008.
  46. ^ Mikhail Maslennikov. "MCSSHA-3 hash algorithm". Archived from the original on May 2, 2009. Retrieved November 8, 2008.
  47. ^ Jean-Philippe Aumasson; María Naya-Plasencia. "Second preimages on MCSSHA-3" (PDF). Retrieved November 14, 2008.[영구적 데드링크]
  48. ^ Peter Maxwell (September 2008). "The Sgàil Cryptographic Hash Function" (PDF). Archived from the original (PDF) on November 12, 2013. Retrieved November 9, 2008.
  49. ^ Peter Maxwell (November 5, 2008). "Aww, p*sh!". Archived from the original on November 9, 2008. Retrieved November 6, 2008.
  50. ^ Michael Gorski; Ewan Fleischmann; Christian Forler (October 28, 2008). "The Twister Hash Function Family" (PDF). Retrieved December 11, 2008.
  51. ^ Florian Mendel; Christian Rechberger; Martin Schläffer (2008). "Cryptanalysis of Twister" (PDF). Retrieved May 19, 2009.
  52. ^ Michael Kounavis; Shay Gueron (November 3, 2008). "Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication". Retrieved November 11, 2008.
  53. ^ Jean-Philippe Aumasson; Orr Dunkelman; Florian Mendel; Christian Rechberger; Søren S. Thomsen (2009). "Cryptanalysis of Vortex" (PDF). Retrieved May 19, 2009.
  54. ^ Computer Security Division, Information Technology Laboratory (January 4, 2017). "SHA-3 Project – Hash Functions". CSRC: NIST. Retrieved April 26, 2019.
  55. ^ Neil Sholer (October 29, 2008). "Abacus: A Candidate for SHA-3" (PDF). Retrieved December 11, 2008.
  56. ^ Gregory G. Rose. "Design and Primitive Specification for Boole" (PDF). Retrieved November 8, 2008.
  57. ^ Gregory G. Rose (December 10, 2008). "Official Comment: Boole" (PDF). Retrieved December 23, 2008.
  58. ^ David A. Wilson (October 23, 2008). "The DCH Hash Function" (PDF). Retrieved November 23, 2008.
  59. ^ Natarajan Vijayarangan. "A New Hash Algorithm: Khichidi-1" (PDF). Retrieved December 11, 2008.
  60. ^ Björn Fay. "MeshHash" (PDF). Retrieved November 30, 2008.
  61. ^ Orhun Kara; Adem Atalay; Ferhat Karakoc; Cevat Manap. "SHAMATA hash function: A candidate algorithm for NIST competition". Archived from the original on February 1, 2009. Retrieved November 10, 2008.
  62. ^ Michal Trojnara (October 14, 2008). "StreamHash Algorithm Specifications and Supporting Documentation" (PDF). Retrieved December 15, 2008.
  63. ^ Rafael Alvarez; Gary McGuire; Antonio Zamora. "The Tangle Hash Function" (PDF). Retrieved December 11, 2008.
  64. ^ John Washburn. "WaMM: A Candidate Algorithm for the SHA-3 Competition" (PDF). Archived from the original (PDF) on November 19, 2008. Retrieved November 9, 2008.
  65. ^ "Official Comment: WaMM is Withdrawn" (PDFauthor=John Washburn). December 20, 2008. Retrieved December 23, 2008.
  66. ^ Bob Hattersly (October 15, 2008). "Waterfall Hash – Algorithm Specification and Analysis" (PDF). Retrieved November 9, 2008.
  67. ^ Bob Hattersley (December 20, 2008). "Official Comment: Waterfall is broken" (PDF). Retrieved December 23, 2008.
  68. ^ Bruce Schneier (November 19, 2008). "Skein and SHA-3 News". Retrieved December 23, 2008.
  69. ^ Robert J. Jenkins Jr. "Algorithm Specification". Retrieved December 15, 2008.
  70. ^ Anne Canteaut & María Naya-Plasencia. "Internal collision attack on Maraca" (PDF). Retrieved December 15, 2008.
  71. ^ Michael P. Frank. "Algorithm Specification for MIXIT: a SHA-3 Candidate Cryptographic Hash Algorithm" (PDF). Archived from the original (PDF) on March 4, 2016. Retrieved January 12, 2014.
  72. ^ Geoffrey Park. "NKS 2D Cellular Automata Hash" (PDF). Retrieved November 9, 2008.
  73. ^ Cristophe De Cannière (November 13, 2008). "Collisions for NKS2D-224". Retrieved November 14, 2008.
  74. ^ Brandon Enright (November 14, 2008). "Collisions for NKS2D-512". Retrieved November 14, 2008.
  75. ^ Peter Schmidt-Nielsen. "Ponic" (PDF). Retrieved November 9, 2008.
  76. ^ María Naya-Plasencia. "Second preimage attack on Ponic" (PDF). Retrieved November 30, 2008.
  77. ^ Nicolas T. Courtois; Carmi Gressel; Avi Hecht; Gregory V. Bard; Ran Granot. "ZK-Crypt Homepage". Archived from the original on February 9, 2009. Retrieved March 1, 2009.

외부 링크