Stupid Compiler

… and discuss how best to attack SHA.

I was talking with a math guy here about the requirement for SHA-384 in a product we are developing. I had heard that MD5 was “insecure” and not to be trusted for collision resistance, but I hadn’t heard anything about SHA-1. Despite hearing these claims around the internet, I’ve never investigated further. My co-worker mentioned that SHA-1 was also on the way out and NIST will probably issue something declaring the larger members of the SHA family (SHA-384 and SHA-512) to be the new standards (I’ve since learned that NIST has a call for proposals for new hash functions — in the same way they picked AES). Never having implemented a secure hash function, I was curious what was involved and where the “one-wayed-ness” came from. This investigation led me from doing a fast implementation of SHA-512 (and, almost by default, SHA-384) to the original paper on differential attacks on DES to a bunch of work by three groups hitting the SHA functions pretty hard. I feel like I should try and explain some of the attacks I’ve learned (along with source code) — they’re clever and not difficult to understand once digested.

Before I begin, here are some references for those following along at home. I’m sorry for the crappy links; I know Springer and ACM are useless for anyone outside of academia. I’ll have to upload local copies — these papers are surprisingly hard to find.

• F. Chabaud, A. Joux. Differential Collisions in SHA-0.
• E. Biham, R. Chen. Near collisions of SHA-0.
• X. Wang, H. Yu, Y.L. Yin. Efficient collision search attacks on SHA0.
• X. Wang, H. Yu. How to Break MD5 and Other Hash Functions.
• X. Wang, Y.L. Yin, H. Yu. Finding Collisions in the Full SHA-1.
• E. Biham, A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems.
• The FIPS documents for SHA and DES and AES