Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

On the surface, SHA1 and MD5 look pretty similar. Their diagrams include chunks of bits, bit rotation, xor and special functions. Their implementations are roughly the same length (at least the ones I've seen). Yet it's widely known that MD5 is broken, but currently SHA1 isn't.

Is the security difference from the increased rounds? SHA1 has 80 compared to MD5's 64. Or is it the greater digest size? SHA1 seems to be described as "more conservative", but I'm not sure what that means.

share|improve this question
2  
Actually, SHA-1 is on the verge of being considered broken. The best attacks against it find collisions in $O(2^{61})$ operations, rather than the $O(2^{80})$ expected by its output length. –  Stephen Touset Aug 13 at 0:46
    
SHA1 is considered conservative because of the limited quantity of round constants compared to MD5 (which it was based on) and the use of fixed rotations vs round dependent rotations –  Richie Frame Aug 13 at 1:37
    
I don't understand your question - every hash function can be described as having "chunks of bits, bit rotation, xor, and special functions". –  pg1989 Aug 13 at 1:41
    
@pg1989 I meant in particular the Merkle-Damgard construction. In contrast, SHA-3 operates differently. –  qwr Aug 13 at 3:18

1 Answer 1

up vote 11 down vote accepted

MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992).

The main structural differences are the following:

  • SHA-1 has a larger state: 160 bits vs 128 bits.
  • SHA-1 has more rounds: 80 vs 64.
  • SHA-1 rounds have an extra bit rotation and the mixing of state words is slightly different (mostly to account for the fifth word).
  • Bitwise combination functions and round constants are different.
  • Bit rotation counts in SHA-1 are the same for all rounds, while in MD5 each round has its own rotation count.
  • The message words are pre-processed in SHA-0 and SHA-1. In MD5, each round uses one of the 16 message words "as is"; in SHA-0, the 16 message words are expanded into 80 derived words with a sort of word-wise linear feedback shift register. SHA-1 furthermore adds a bit rotation to these word derivation.

The extra bit rotation is what makes SHA-1 distinct from SHA-0; it also makes SHA-1 much stronger against collision attacks, and, indeed, SHA-0 collisions have been found (with effort $2^{39}$, thus highly doable) while SHA-1 collisions still remain theoretical.

We don't have a true theory of what makes a hash function strong. However, we can still have some "gut feelings", and my own intestine tells me that in the case of MD-like functions (MD4, MD5, SHA-0, SHA-1, and the SHA-2 functions), the two important points are:

  • Rotating bits a lot. Collision attacks based on differential paths try to induce small differences and keep them from propagating non-linearly everywhere; a useful tool for that is the lack of carry beyond the upper bits in word-wise additions (a difference in the upper bit in one of the operands of an addition modulo $2^{32}$ propagates to the output with probability $1$; two such differences cancel each other reliably). The 1-bit rotation added in SHA-1 is effective at making differential paths harder to find.

  • Doing "enough work". If you count the number of elementary operations per input byte (which more or less translates to code size or speed, especially on GPU), you will see that SHA-1 is about 30% heavier than MD5, while SHA-256 is close to twice heavier than SHA-1. SHA-3 candidates were also, as a rule, "heavier" than SHA-1 (some could get faster by leveraging SIMD opcodes in CPU, but still had more operations per input byte).

share|improve this answer
    
With regard to your last statement, what about BLAKE2b? It claims to be faster even than MD5. Is this only due to taking special advantage of modern hardware, or the result of "working smarter, not harder"? –  Stephen Touset Aug 26 at 18:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.