32
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – Stephen Touset
    Aug 13, 2014 at 0:46
  • $\begingroup$ 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 $\endgroup$
    – Richie Frame
    Aug 13, 2014 at 1:37
  • $\begingroup$ I don't understand your question - every hash function can be described as having "chunks of bits, bit rotation, xor, and special functions". $\endgroup$
    – pg1989
    Aug 13, 2014 at 1:41
  • $\begingroup$ @pg1989 I meant in particular the Merkle-Damgard construction. In contrast, SHA-3 operates differently. $\endgroup$
    – qwr
    Aug 13, 2014 at 3:18

1 Answer 1

Reset to default
29
$\begingroup$

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 are much more difficult.

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).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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"? $\endgroup$
    – Stephen Touset
    Aug 26, 2014 at 18:58
  • $\begingroup$ @StephenTouset You may want to read the BLAKE2 paper. It's surprisingly readable (not nearly as much domain-specific math as some other papers) and gives extensive rational for design decisions that improve performance. $\endgroup$
    – forest ♦
    Feb 18, 2019 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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