EndCryptor 's  Davies-Meyer hash function construction from Rijndael
Home

A hash function's mainly usage is when a checksum of the file for digital signature is computed.

The cryptographic hash function is a Davies-Meyer construction with Merkle-Damgård strengthening from the block cipher Rijndael (AES) with 192-bit key and block size.

This construction is a block cipher based method. The used Davies-Meyer construction itself has been shown to be secure under the black-box model^1,2. The black-box model assumes that the used block cipher is secure.

A block cipher based construction is usually slower than a specific dedicated hash algorithm. On the other hand the construction's security is that of the used cipher's - which in the case of the industry standard AES is being carefully studied and monitored by the crypto community.

One place that keeps track of the cryptographic attacks against AES is the AES Lounge.

The possibility that Rijndael (AES) is being used as a hash function has been considered already during the cipher's design phase³. Recently, a cryptanalytic achievement in analyzing AES (256-bit key and 128 bit block size) as a hash function was reached¹⁵. The attack is not applicable to a 192-bit key and block size construction¹⁶ like ours.

The widely known hash functions MD5, SHA-1 and SHA-2 also use the Davies-Meyer construction and Merkle-Damgård strengthening – but in the place of a full block cipher - like AES in EndCryptor - they have a less “mature” solution which is faster but in the case of MD5 has been badly broken in practice and in the case of SHA-1 is now on the edge of being broken in practice.

Here is a list of several dedicated hash functions that have recently been cryptographically attacked more or less successfully: MD4 ^4,5,7, MD5 ^6,7,11,12 HAVAL-128 ⁷, RIPEMD ⁷ and SHA-1 ^8,9,14. Researchers say that in SHA-1 “Practical collisions are within resources of a well funded organization.” ¹⁴. A collision in SHA-1 can now be found using about 2⁵² steps¹⁴.

Due to the advances in attacking SHA-1 the National Institute of Standards and Technology (NIST) of USA is “initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES) ¹⁰.” This competition was started on November 2, 2007 when a collision for SHA-1 could be found using about 2⁶³ steps. The new dedicated hash algorithm named SHA-3 should be chosen at the end of the year 2011.

The attacks on MD5 have developed so much that on December 30, 2008 researchers published a report¹³ on how they succeeded in forging a valid Certificate Authority certificate from a commercial company because the company allowed the use of MD5 as hash function. The researchers say that: “This certificate allows us to impersonate any website on the Internet, including banking and e-commerce sites secured using the HTTPS protocol.” This is because web browsers also accept certificates that use MD5. After learning about the attack the company in question removed MD5 from the list of accepted hash functions – the forged certificate is still accepted by those browsers that accept MD5.

References

1. R. Winternitz. A secure one-way hash function built from DES. In Proceedings of the IEEE Symposium on Information Security and Privacy, p. 88-90. IEEE Press, 1984.

2. J. Black, P. Rogaway, T. Shrimpton. Black-Box Analysis of the  Block-Cipher-Based Hash-Function Construction from PGV. In Advances in Cryptology - CRYPTO '02, volume 2442 of Lecture Notes in Computer Science. Springer-Verlag, 2002.

3. Joan Daemen, Vincent Rijmen. AES proposal: Rijndael, pages 41, 43.

4. B. den Boer and A. Bosselaers, An attack on the last two rounds of MD4, Advances in Cryptology, Proceedings Crypto'91, LNCS 576, J. Feigenbaum, Ed., Springer-Verlag, 1992, pp. 194-203.

5. H. Dobbertin, Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, D. , Springer-Verlag, 1996.

6. B. den Boer and A. Bosselaers, Collisions for the compression function of MD5, Advances in Cryptology, Proceedings Eurocrypt'93, LNCS 765, T. Helleseth, Ed., Springer-Verlag, 1994, pp. 293-304.

7. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Crypto'04 Rump Session, Cryptology ePrint Archive http://eprint.iacr.org/2004/199 .

8. Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Finding Collisions in the Full SHA-1, Crypto'05.

9. The April 25, 2006 statement of National Institute of Standards and Technology (NIST) of USA regarding the attack by Wang can be found on this page.

10. See cryptographic hash competition.

11. Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, In: Ronald Cramer (editor), "Advances in Cryptology - EUROCRYPT 2005", volume 3494 of Lecture Notes in Computer Science, pages 19-35, Springer Verlag, Berlin, 2005.

12. Marc Stevens, On collisions for MD5, MSc Thesis, Eindhoven University of Technology, June 2007.

13. Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, MD5 considered harmful today: Creating a rogue CA Certificate. In 25C3: Nothing to hide, 25th Chaos Communication Congress, December 27th to 30th, 2008, bcc Berliner Congress Center, Berlin, Germany. See http://www.win.tue.nl/hashclash/rogue-ca/ .

14. Cameron McDonald, Josef Pieprzyk, Phil Hawkes. Automatic Differential Path Searching for SHA-1, Eurocrypt 2009 rump session, see http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf on page http://eurocrypt2009rump.cr.yp.to/ , paper available now as Differential Path for SHA-1 with complexity O(2⁵²) on Cryptology ePrint Archive http://eprint.iacr.org/2009/259.pdf .

15. Alex Biryukov, Dmitry Khovratovich, Ivica Nikolic. Distinguisher and Related-Key Attack on the Full AES-256. Cryptology ePrint Archive http://eprint.iacr.org/2009/241.pdf .

16. The attack uses specific properties of the key schedule which occur when the key size is double of the block size (256-bit key, 128 bit block), see page 6 of the paper¹⁵. Note that the classical way to construct a hash function from a block cipher is to use same size for the key and block – this situation the attack cannot utilize.

Home