The Hash Function Lounge 

Welcome!



Hash Functions


Table 1: Features of some selected hash functions

Name Ref. Version Author(s) Block Size Digest Size Rounds Attack(s)
AR AR92 1992 ISO ? ? ? Broken! DK93
Boognish DGV92a 1992 Daemen 32 up to 160 NA Broken! D02
Cellhash DGV91 1991 Daemen, Govaerts, Vandewalle 32 up to 256 NA ?
FFT-Hash I S91 1991 Schnorr 128 128 2 Broken! BGG92, DBGV91
FFT-Hash II S92 1992 Schnorr 128 128 2 Broken! V92
FSB AFS05 2005 Augot, Finiasz, Sendrier 336, 680, 1360 320, 400, 480 () NA ?
GOST R 34.11-94 G94 1990 Government Committee of Russia for Standards 256 256 NA ?
HAS-160 TTA05 2005 Telecommunications Technology Association 512 160 4×20 ?
HAVAL ZPS92 1994 Zheng, Pieprzyk, Seberry 1024 128, 160, 192, 224, 256 3×32, 4×32, 5×32 Broken! WFLY04, RBPV03, KP00, KBPL05
LASH-n
(n = 160, 256, 384, 512)
BPSSS06 2006 Bentahar, Page, Saarinen, Silverman, Smart n n NA ?
MAA () ISO88 1988 ISO 32 32 NA Broken! PRO97
MAELSTROM-0 GBR06 2006 Gazzoni Filho, Barreto, Rijmen 1024 up to 512 10 ?
MD2 K92 1989 Rivest 512 128 18 Broken! M04, RC95
MD4 R90 1990 Rivest 512 128 3×16 Broken! WLFCY05, WFLY04, D98, KBPL05
MD5 R92 1992 Rivest 512 128 4×16 Broken! K06, S06, K05a, K05b, WY05, WFLY04, D96, KBPL05
N-Hash MOI90 1990 Miyaguchi, Ohta, Iwata 128 128 ≥ 8 Broken! BS91
PANAMA DC98 1998 Daemen, Clapp 256 unlimited NA Broken! RRPV01, DV07
Parallel FFT-Hash SV93 1993 Schnorr, Vaudenay 128 128 5 ?
RADIOGATÚN[w]
(default: w = 64)
BDPvA06 2006 Bertoni, Daemen, Peeters, van Assche w unlimited NA ?
RIPEMD RIPE92 1990 The RIPE Consortium 512 128 4×16 Broken! WLFCY05, WFLY04, D97
RIPEMD-128 DBP96 1996 Dobbertin, Bosselaers, Preneel 512 128 4×16 ?
RIPEMD-160 DBP96 1996 Dobbertin, Bosselaers, Preneel 512 160 5×16 ?
SHA-0 NN91 1991 NIST/NSA 512 160 4×20 Broken! WYY05, WFLY04, CJ98
SHA-1 NN02 1993 NIST/NSA 512 160 4×20 Wounded! WYY05, R04, BC04
SHA-1-IME JP05 2005 Jutla, Patthak 512 160 80 ?
SHA-224 NN02 2004 NIST/NSA 512 224 64 Analyzed! HPR04
SHA-256 NN02 2000 NIST/NSA 512 256 64 Analyzed! HPR04
SHA-384 NN02 2000 NIST/NSA 1024 384 80 Analyzed! HPR04
SHA-512 NN02 2000 NIST/NSA 1024 512 80 Analyzed! HPR04
SMASH K05 2005 Knudsen 256 256 NA Broken! PRR05
Snefru-n
(n = 128, 256)
M90 1990 Merkle 512-n n ≥ 8 Broken! BS93
StepRightUp D95 1995 Daemen 256 256 NA Wounded! RRPV01
Subhash DGV92b 1992 Daemen 32 up to 256 NA ?
Tiger AB96 1996 Anderson, Biham 512 192 3×8 Analyzed! KL06, MPRYW06
WHIRLPOOL BR00 2000 Barreto, Rijmen 512 512 10 ?
Name Ref. Version Author(s) Block Size Digest Size Rounds Attack(s)

Table 2: General design strategies, analyses, and attacks

Category Author(s) Ref.
Design
  •  Damgård
  •  Gauravaram, Millan, Dawson, Viswanathan
  •  Lucks
  •  Merkle
  • D89
    GMDV06
    L04
    M89
    Analysis
  •  Black, Rogaway, Shrimpton
  •  Mironov, Zhang
  •  Preneel, Govaerts, Vandewalle
  • BRS02
    MZ06
    PGV93
    Attack
  •  Hoch, Shamir
  •  Joux
  •  Kelsey, Schneier
  •  Kohno, Kelsey
  • HS06
    J04
    KS05
    KK06




    Acknowledgements



    References

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    [AB96]
    R. Anderson, E. Biham, "Tiger: A Fast New Hash Function", Fast Software Encryption -- FSE'96, LNCS 1039, Springer (1996), pp. 89--97.
    [AFS05]
    D. Augot, M. Finiasz, N. Sendrier, "A Family of Fast Syndrome Based Cryptographic Hash Functions", LNCS 3715, Springer (2005), pp. 64--83.
    [AR92]
    ISO N179, "AR Fingerprint Function", working document, ISO-IEC/JTC1/SC27/WG2, International Organization for Standardization, 1992.
    [BC04]
    E. Biham, R. Chen, "Near-Collisions of SHA-0", Advances in Cryptology -- Crypto'2004, LNCS 3152, Springer (2004), pp. 290--305. Updated version.
    [BDPvA06]
    G. Bertoni, J. Daemen, M. Peeters, G. van Assche, "RadioGatún, a belt-and-mill hash function", Second NIST Cryptographic Hash Workshop, Santa Barbara, USA, August 24--25, 2006.
    [BGG92]
    T. Baritaud, H. Gilbert, M. Girault, "F.F.T. hashing is not collision-free", Advances in Cryptology -- Eurocrypt'92, LNCS 658, Springer (1992), pp. 35--44.
    [BPSSS06]
    K. Bentahar, D. Page, J. H. Silverman, M.-J. O. Saarinen, N. P. Smart, "LASH", Second NIST Cryptographic Hash Workshop, Santa Barbara, USA, August 24--25, 2006.
    [BR00]
    P. S. L. M. Barreto, V. Rijmen, "The Whirlpool Hashing Function", First open NESSIE Workshop, Leuven, Belgium, November 13--14, 2000.
    [BRS02]
    J. Black, P. Rogaway, and T. Shrimpton, "Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV", Advances in Cryptology -- CRYPTO'2002, LNCS 2442, Springer (2002), pp. 320--335.
    [BS91]
    E. Biham and A. Shamir, "Differential cryptanalysis of Feal and N-Hash", Advances in Cryptology -- Eurocrypt'91, LNCS 547, Springer (1991), pp. 1-­16.
    [BS93]
    E. Biham and A. Shamir, "Differential Cryptanalysis of the Data Encryption Standard", Springer (1993).
    [CJ98]
    F. Chabaud and A. Joux, "Differential Collisions in SHA-0", Advances in Cryptology -- Crypto'98, LNCS 1462, Springer (1998), pp. 56--71.
    [D95]
    J. Daemen, " Cipher and Hash Function Design, Strategies Based on Linear and Differential Cryptanalysis", Doctoral dissertation, Katholiek Universiteit Leuven, 1995.
    [D89]
    I. B. Damgård, "A Design Principle for Hash Functions," Advances in Cryptology -- Crypto'89, LNCS 435, Springer (1989), pp. 416--427.
    [D96]
    H. Dobbertin, "The Status of MD5 after a Recent Attack", CryptoBytes 2:2 (1996), pp. 1--6.
    [D97]
    H. Dobbertin, "RIPEMD with Two-Round Compress Function is Not Collision-Free", Journal of Cryptology 10:1 (1997), pp. 51--70.
    [D98]
    H. Dobbertin, "Cryptanalysis of MD4", Journal of Cryptology 11:4 (1998), pp. 253--271.
    [D02]
    J. Daemen, personal communication, 2002 (if you are curious, it merely states that Boognish is "certainly weak").
    [DBGV91]
    J. Daemen, A. Bosselaers, R. Govaerts, J. Vandewalle, "Collisions for Schnorr's Hash Function FFT-Hash", Advances in Cryptology -- Asiacrypt'91, LNCS 739, Springer (1993), pp. 447--480.
    [DBP96]
    H. Dobbertin, A. Bosselaers, and B. Preneel, "RIPEMD-160, a strengthened version of RIPEMD", Fast Software Encryption -- FSE'96, LNCS 1039, Springer (1996), pp. 71--82.
    [DC98]
    J. Daemen and C. Clapp, "Fast Hashing and Stream Encryption with PANAMA", Fast Software Encryption -- FSE'98, LNCS 1372, Springer (1998), pp. 60--74.
    [DGV91]
    J. Daemen, R. Govaerts, and J. Vandewalle, "A Framework for the Design of One-Way Hash Functions Including Cryptanalysis of Damgård's One-Way Function Based on Cellular Automata", Advances in Cryptology - Asiacrypt'91, LNCS 739, Springer (1993), pp. 82--96.
    [DGV92a]
    J. Daemen, R. Govaerts, and J. Vandewalle, "Fast Hashing Both in Hard- and Software", ESAT-COSIC Report 92-2, Department of Electrical Engineering, Katholieke Universiteit Leuven, April 1992.
    [DGV92b]
    J. Daemen, R. Govaerts, and J. Vandewalle, "A Hardware Design Model for Cryptographic Algorithms", European Symposium on Research in Computer Security - ESORICS, 1992, pp. 419--434.
    [DK93]
    I. B. Damgård, and L. R. Knudsen, "The breaking of the AR Hash Function", Advances in Cryptology -- EUROCRYPT'93, LNCS 765, Springer (1994), pp. 286--292.
    [DV07]
    J. Daemen, G. van Assche, " Producing Collisions for Panama, Instantaneously, Fast Software Encryption -- FSE'2007, LNCS 4593, Springer (2007), pp. 1--18.
    [G94]
    Government Committee of Russia for Standards, "Information technology. Cryptographic Data Security. Hashing function.", GOST R 34.10-94, Gosudarstvennyi Standard of Russian Federation, 1994. See also " Using the GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94 algorithms with the Internet X.509 Public Key Infrastructure Certificate and CRL Profile, Serguei Leontiev, 2005.02.08.
    [GBR06]
    D. L. Gazzoni Filho, P. S. L. M. Barreto, V. Rijmen, "The Maelstrom-0 Hash Function", VI Brazilian Symposium on Information and Computer Systems Security -- SBSeg'2006.
    [GMDV06]
    P. Gauravaram, W. Millan, E. Dawson, K. Viswanathan, "Constructing Secure Hash Functions by Enhancing Merkle-Damgård Construction", Cryptology ePrint Archive, Report 2006/061.
    [HPR04]
    P. Hawkes, M. Paddon, G. G. Rose, "On Corrective Patterns for the SHA-2 Family", Cryptology ePrint Archive, Report 2004/207.
    [HS06]
    J. J. Hoch, A. Shamir, "Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions", Fast Software Encryption -- FSE'2006, LNCS 4047, Springer (2006), pp 179--194. Preliminary version.
    [ISO88]
    ISO Standard 8731-2, 1988. More information can be found here.
    [J04]
    A. Joux, "Multicollisions in Iterated Hash Functions. Applications to Cascaded Constructions", Advances in Cryptology - Crypto'2004, LNCS 3152, Springer (2004), pp. 306--316.
    [JP05]
    C. S. Jutla and A. C. Patthak, "A Simple and Provably Good code for SHA Message Expansion", First NIST Cryptographic Hash Workshop, Gaithersburg, USA, October 31 -- November 01, 2005. Full version: C. S. Jutla and A. C. Patthak, "Provably Good Codes for Hash Function Design", Selected Areas in Cryptography - SAC'2006, LNCS , Springer (2007), to appear.
    [K92]
    B. Kaliski, "The MD2 Message-Digest Algorithm", RFC 1319 (1992).
    [KS05]
    J. Kelsey, B. Schneier, " Second Preimages on n-Bit Hash Functions for Much Less than 2n Work," Advances in Cryptology - Eurocrypt'2005, LNCS 3494, Springer (2005), pp. 474--490.
    [K05a]
    V. Klima, "Finding MD5 Collisions -- a Toy For a Notebook", Cryptology ePrint Archive, Report 2005/075.
    [K05b]
    V. Klima, "Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications", Cryptology ePrint Archive, Report 2005/102.
    [K06]
    V. Klima, "Tunnels in Hash Functions: MD5 Collisions Within a Minute", Cryptology ePrint Archive, Report 2006/105.
    [K05]
    L. R. Knudsen, "SMASH - A Cryptographic Hash Function", Fast Software Encryption - FSE'2005, LNCS 3557, Springer (2005), pp. 228--242.
    [KBPL05]
    J. Kim, A. Biryukov, B. Preneel, S. Lee, "On the Security of Encryption Modes of MD4, MD5 and HAVAL", Cryptology ePrint Archive, report 2005/327.
    [KK06]
    T. Kohno, J. Kelsey, " Herding Hash Functions and the Nostradamus Attack", First NIST Cryptographic Hash Workshop, Gaithersburg, USA, October 31 -- November 01, 2005. Full version: Advances in Cryptology -- Eurocrypt'2006, LNCS 4004, Springer (2006), pp. 183--200.
    [KL06]
    J. Kelsey, S. Lucks, " Collisions and Near-Collisions for Reduced-Round Tiger", Full version: Fast Software Encryption -- FSE'2006, LNCS 4047, Springer (2006), pp. 111--125.
    [KP00]
    P. Kasselman, W. Penzhorn, "Cryptanalysis of Reduced Version of HAVAL", Electronics letters, Vol. 36, No. 1, January 2000, pp. 30--31.
    [L04]
    S. Lucks, "Design Principles for Iterated Hash Functions", Cryptology ePrint Archive, report 2004/253.
    [M89]
    R. C. Merkle, "One Way Hash Functions and DES", Advances in Cryptology - Crypto'89, LNCS 435, Springer (1989), pp. 428--446.
    [M90]
    R. C. Merkle, "A Fast Software One-Way Hash Function", Journal of Cryptology 3:1 (1990), pp 43--58.
    [M04]
    F. Muller, " The MD2 Hash Function Is Not One-Way," Advances in Cryptology - Asiacrypt'2004, LNCS 3329, Springer (2004), pp. 214--229.
    [MOI90]
    S. Miyaguchi, K. Ohta, and M. Iwata, "128-bit hash function (N-hash)", NTT Review, vol. 2 (no. 6), Nov. 1990, pp. 128--132.
    [MPRYW06]
    F. Mendel, B. Preneel, V. Rijmen, H. Yoshida, D. Watanabe, "Update on Tiger", Progress in Cryptology -- INDOCRYPT'2006, LNCS 4329, Springer (2006), pp. 63--79.
    [MZ06]
    I. Mironov, L. Zhang, "Applications of SAT Solvers to Cryptanalysis of Hash Functions", Theory and Applications of Satisfiability Testing -- SAT 2006, LNCS 4121, Springer (2006), pp. 102--115.
    [NN91]
    NIST/NSA, "FIPS 180" (superseded by FIPS 180-1 and FIPS 180-2). See also NIST's Secure Hashing site.
    [NN02]
    NIST/NSA, "FIPS 180-2: Secure Hash Standard (SHS)", August 2002 (change notice: February 2004). See also NIST's Secure Hashing site.
    [PGV93]
    B. Preneel, R. Govaerts, J. Vandewalle, "Hash Functions Based on Block Ciphers: A Synthetic Approach", Advances in Cryptology - Crypto'93, LNCS 773, Springer (1990), pp. 368--378.
    [PRO97]
    B. Preneel, V. Rijmen, and P. van Oorschot, "Security analysis of the Message Authenticator Algorithm (MAA)", European Transactions on Telecommunications, Vol. 8, No. 5 (Sept./Oct. 1997), pp. 455--470.
    [PRR05]
    N. Pramstaller, C. Rechberger, V. Rijmen, "Smashing SMASH", Cryptology ePrint Archive, report 2005/081.
    [R90]
    R. L. Rivest, "The MD4 Message Digest Algorithm", Advances in Cryptology - Crypto'90, LNCS 537, Springer (1990), pp. 303--311.
    [R92]
    R. L. Rivest, "The MD5 Message Digest Algorithm", RFC 1321 (1992).
    [R04]
    V. Rijmen, "Update on SHA-1", Topics in Cryptography -- CT-RSA'2005, LNCS 3376, Springer (2005), pp. 58--71.
    [RC95]
    N. Rogier, P. Chauvaud, "The compression function of MD2 is not collision free", Selected Areas in Cryptography -- SAC'95, Ottawa, Canada, May 18--19, 1995 (workshop record).
    [RIPE92]
    Research and Development in Advanced Communication Technologies in Europe, "RIPE Integrity Primitives: Final Report of RACE Integriy Primitives Evaluation (R1040)", RACE, June 1992.
    [RRPV01]
    V. Rijmen, B. Van Rompay, B. Preneel, J. Vandewalle, "Producing Collisions for PANAMA", Fast Software Encryption - FSE'2001, LNCS 2355, Springer (2002), pp. 37--51.
    [RBPV03]
    B. Van Rompay, A. Biryukov, B. Preneel, J. Vandewalle, " Cryptanalysis of 3-pass HAVAL", Advances in Cryptology - Asiacrypt'2003, LNCS 2894, Springer (2003), pp. 228--245.
    [S91]
    C. Schnorr, "FFT-Hash, An Efficient Cryptographic Hash Function", Crypto'91 rump session, unpublished manuscript, 1991.
    [S92]
    C. Schnorr, "FFT-Hash II, efficient cryptographic hashing", Advances in Cryptology - Eurocrypt'92, LNCS 658, Springer (1992), pp. 45--54.
    [S06]
    M. Stevens, "Fast Collision Attack on MD5", Cryptology ePrint Archive, report 2006/104.
    [SV93]
    C. Schnorr, S. Vaudenay, "Parallel FFT-Hashing", Fast Software Encryption - FSE'93, LNCS 809, Springer (1994), pp. 149--156.
    [TTA05]
    Telecommunications Technology Association, "TTAS.KO-12.0011/R2: Hash Function Standard - Part 2: Hash Function Algorithm Standard (HAS-160)", December 2005.
    [V92]
    S. Vaudenay, "FFT-Hash-II is not yet Collision-free", Advances in Cryptology - Crypto'92, LNCS 740, Springer (1993), pp. 587--593.
    [WFLY04]
    X. Wang, D. Feng, X. Lai, H. Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", Cryptology ePrint Archive, Report 2004/199.
    [WLFCY05]
    X. Wang, X. Lai, D. Feng, H. Chen, X. Yu, " Cryptanalysis of the Hash Functions MD4 and RIPEMD", Advances in Cryptology -- Eurocrypt'2005, LNCS 3494, Springer (2005), pp. 1--18.
    [WY05]
    X. Wang, H. Yu, " How to Break MD5 and Other Hash Functions", Advances in Cryptology -- Eurocrypt'2005, LNCS 3494, Springer (2005), pp. 19--35.
    [WYY05]
    X. Wang, Y. L. Yin, H. Yu, "Collision Search Attacks on SHA1", research summary, 2005.
    [ZPS92]
    Y. Zheng, J. Pieprzyk, and J. Seberry, "HAVAL - a one-way hashing algorithm with variable length of output", Advances in Cryptology - Auscrypt'92, LNCS 718, Springer (1993), pp. 83--104.



    Back to main page

    Visits between 2000.01.01 and 2008.11.19:

    Visits since 2008.11.19:

    Last update2008.11.28
    Copyright © 2001, 2008 by Paulo S. L. M. Barreto.  All rights reserved.