Why does SHA-1 have 80 rounds?

Question

Why does SHA-1 algorithm have exactly 80 rounds? Is it to reduce collisions? If yes, then why do SHA-2 and SHA-3 have a lower number of rounds?

Answer 1

Most hashes are built from permutations (either keyed permutations/block-ciphers, as in MD5, SHA-1 and SHA-2, or unkeyed permutations as in Keccak/SHA-3 and CubeHash). A permutation is a shuffling of the inputs. Once you have a good random permutation, you can easily build a hash from it. See Construction of One-way compression functions from block ciphers on wikipedia for details.

As an analogy you can think of shuffling cards by hand (except crypto uses between $2^{128}$ and $2^{512}$ cards).

A common strategy for shuffling is going through the deck several times, performing a bunch simple operation each time. Each time of going through the deck is called a "round".

Why do SHA-2 and SHA-3 have a smaller number of rounds?

For a round you can either choose to do more complex, and thus expensive operations which achieves more or simpler cheaper rounds which do less. SHA-1 has simpler rounds than SHA-2 and thus needs more of them to properly mix the values.

The art of designing a symmetric primitive that achieves as much mixing as possible with as cheap as possible operations. The SHA-2 and SHA-3 are better than SHA-1 in that regard.

Why have many rounds?

More rounds make cryptoanalytic attacks harder but do not help (much) against brute-force. In particular it increases resistance to a technique called differential cryptoanalysis, which is a popular technique for attacking hashes and block-ciphers.

Going back to the card shuffling analogy:

You can define features of a deck, such as two specific cards being placed directly after each other. After going through the deck once, that feature might be preserved with a relatively high probability like 10%. After going through the deck multiple times the probability of a feature surviving all of them drops exponentially. So the probability of a feature being present in the final state will approach the ideal probability quickly.

In cryptoanalysis you can define similar features called "differential characteristic". One round preserves this characteristic with a certain probability. For example if a characteristic survives one round with probability $10^{-3}$, it might survive 80 rounds with probability $10^{-3 \cdot 80}= 10^{-240}$.

If you have characteristics surviving all rounds with high enough probability, that can often be exploited for finding a collision or pre-image faster. A designer aims for enough rounds that exploiting these shuffling flaws is more expensive than doing a brute-force attack while choosing few enough rounds for good performance.

(There are a few inaccuracies in the above description, but I believe the general idea is correct.)

Why does SHA-1 have 80 rounds?

More rounds increase security against cryptoanalysis. But it also decreases performance. So it's necessary to find a compromise between security and performance. The SHA-1 designers chose 80 rounds.

In hindsight, they chose a too low value, since we have since found attacks against SHA-1 that find collisions faster than brute-force.

Answer 2

In hash functions (and similarly block ciphers) each round applies a non-linear function to its input. This function is somewhat difficult to calculate backwards (and it needs a few other properties, but let's leave it at that). This concept is called diffusion.

On the other side, one of the goals of cryptanalysis is to reverse this diffusion in order to find collisions in hash functions or break block ciphers. For example, methods like linear cryptanalysis and differential cryptanalysis are used to achieve this goal.

So in general, using more rounds means "applying more diffusion" and thus making cryptanalysis more difficult. However, there is also the tradeoff that additional rounds require additional time to compute. Especially with hash functions and symmetric ciphers, speed is a valid concern and performance (usually measured in bits processed per second or similar) matters.

So in general, designers of hash functions and block ciphers will try to find an the "optimal" tradeoff between security and performance. Optimal is a very unspecific statement here, because security against cryptanalysis (especially against unknown attacks) is really hard to measure.

Why SHA-1 algorithm have exactly 80 rounds?

The answer to this is "Someone decided that 80 rounds are enough". This might be based on experience, rough estimations or just because the number 80 looks nice. Surely there was some thought behind this choice, but without being involved in the decision process we can not say for sure. From today's perspective, this choice was too low, as SHA-1 is considered broken. This is due to finding a weakness, that was unknown back then.

Is it to reduce collisions?

Surely, yes. That's the goal of a cryptographic hash function. But as I said, the choice of rounds comes down to the tradeoff between security and performance. Since collision resistance also implies preimage resistance, the focus really does lie on collision resistance. Today we consider hash fucntions broken, as soon as collisin resistance is lost. For example, SHA-1 and MD5 are considered broken with respect to collision resistance. As far as I know, preimage resistance is still not broken for both of them, but generally it is discouraged to use them any more.

If yes, then why SHA-2 and SHA-3 have less number of rounds?

Every hash function is different in their choice of round-function, and if the round function is more effective to achieve the goal of diffusion, then less rounds are required. But all these hash functions were designed at different times, and there were advances in both cryptanalysis and hash function design. In general, I would say they are just not comparable. And for each hash function the according designers made their choice based on their own reasons. There can not be made any kind of argument why more or less rounds are better in different hash functions.

Answer 3

As the other answers already allude to, it's a tradeoff between many simple rounds or a few complex rounds.

But consider that one of the challenges of crypto design is to make something easily implementable in hardware. A simple algorithm takes not a lot of space on a chip, even when it's run for many rounds. SHA-1 can reuse the same circuitry 80 times in a row, for minimal hardware costs. If top throughput is desired, a chip designer can copy the basic SHA-1 circuit 80 times and pipeline them together.