Survey on the candidate algorithms of SHA-3 Hash function family

doi:10.7523/j.issn.2095-6134.2009.5.001

Abstract

Abstract:

In order to develop the new Secure Hash Standard(SHA-3), NIST has announced request for candidate algorithms. Now the 51 first-round candidates are under evaluation worldwide. These algorithms represent the newest design ideas of cryptographic hash function, and SHA-3 will be another milestone like AES. In order to make domestic researchers know these new algorithms and join the work of evaluation, we briefly introduce these secure algorithms and classify them according to the structure. Meanwhile we sum up the design of security and efficiency on these algorithms.

Key words: Hash function, collision, efficient implementation, structure, differential

CLC Number:

TP309

XUE Yu, WU Wen-Ling, WANG Zhang-Yi. Survey on the candidate algorithms of SHA-3 Hash function family[J]. , 2009, 26(5): 577-586.

References

[1] Wang X Y, Lai X J, Feng D G, et al. Cryptanalysis of the hash functions MD4 and RIPEMD // Cramer (ed). EUROCRYPT 2005, LNCS 3494. Berlin: Springer-Verlag, 2005: 1-18.

[2] Wang X Y, Yiqun Lisa Yin, Yu H B. Finding collisions in the full SHA-1 // Shoup (ed). CRYPTO 2005, LNCS 3621. Berlin: Springer-Verlag, 2005:17-36.

[3] Wang X Y, Yu H B. How to break MD5 and other hash functions //Cramer (ed). EUROCRYPT 2005, LNCS 3494. Berlin: Springer-Verlag, 2005:19-35.

[4] Wang X Y, Yu H B, Yiqun Lisa Yin. Efficient collision search attacks on SHA-0 // Shoup (ed). CRYPTO 2005, LNCS 3621. Berlin: Springer-Verlag, 2005:1-16.

[5] Halevi S, Krawczyk H. Strengthening digital signatures via randomzied hashing //Dwork (ed). CRYPTO 2006, LNCS 4117. Berlin: Springer-Verlag, 2006:41-59.

[6] Damgard I. A design principle for hash functions // Brassard (ed). CRYPTO'89, LNCS 435. Berlin: Springer-Verlag, 1989:416-427.

[7] Merkle R C. One way hash functions and DES // Brassard (ed). CRYPTO'89, LNCS 435. Berlin: Springer-Verlag, 1989:428-446.

[8] Joux A. Multicollsions in iterated hash functions, application to cascaded constructions //Franklin (ed). CRYPTO 2004, LNCS 3152. Berlin: Springer-Verlag, 2004:306-316.

[9] Kelsey J, Kohno T. Herding hash functions and the nostradamus attack // Vaudenay (ed). Proc of the EUROCRYPT 2006, LNCS 4004. Berlin:Springer-Verlag, 2006: 183-200.

[10] Kelsy J, Schneier B. Second preimages on n-bit hash functions for much less than 2^<em>n work // Cramer (ed). EUROCRYPT 2005, LNCS 3494. Berlin: Springer-Verlag, 2005: 474-490.

[11] Knudsen L R, Rechberger C, Thomsen S S. The Grindahl hash functions // Biryukov (ed). Fast Software Encryption: 14th International Workshop, FSE 2007, LNCS 4593. Berlin: Springer-Verlag, 2007: 39-57.

[12] Merkle R C. A fast software one-way hash function
[J]. Journal of Cryptology, 1990,3(1): 43-58.

[13] Lyubashevsky V, Miciancio D, Peikert C, et al. SWIFFT: a modest proposal for FFT hashing // Nyberg (ed). Fast Software Encryption:15th International Workshop, FSE 2008, LNCS 5086. Berlin:Springer-Verlag, 2008: 54-72.

[14] Lucks S. A failure-friendly design principle for hash functions // Roy (ed). ASIACRYPT 2005, LNCS 3788. Berlin:Springer-Verlag, 2005: 474-494.

[15] Coron J S, Dodis Y, Malinaud C, et al. Merkle-damgard revisited: how to construct a Hash function // Shoup (ed). CRYPTO 2005, LNCS 3621. Berlin: Springer-Verlag, 2005: 430-448.

[16] Preneel B, Govaerts R, Vandewalle J. Hash functions based on block ciphers: a synthetic approach // Stinson (ed). CRYPTO 1993, LNCS 773. Berlin:Springer-Verlag, 1994: 268-278.

[17] Black J, Rogaway P, Shrimption T. Black-box analysis of the block-cipher-based hash-function constructions from PGV // Yung (ed). CRYPTO 2002, LNCS 2442. Berlin:Springer-Verlag, 2002: 310-335.

[18] Rogaway P, Steinberger J. Security/efficiency tradeoffs for permutation-based hashing // Smart (ed). EUROCRYPT 2008, LNCS 4965. Berlin:Springer-Verlag, 2008: 220-236.

[19] Patarin J, Nachef V, Berbain C. Generic attacks on unbalanced feistel schemes with expanding functions //Kurosawa (ed). ASIACRYPT 2007, LNCS 4833. Berlin:Springer-Verlag, 2008:325-341.

[20] Deamen J, Rijmen V. The design of rijndael:AES - the advanced encryption standard
[M]. Berlin:Springer-Verlag, 2002.

[21] Maurer U, Renner R, Holenstein C. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology // Naor (ed). TCC'04, LNCS 2951. Berlin:Springer-Verlag, 2004: 21-39.