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.

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?

share|improve this question

migrated from security.stackexchange.com Mar 13 at 14:38

This question came from our site for Information security professionals.

1  
As a note, the larger versions of SHA-2 also have 80 rounds. –  AJ Henderson Mar 13 at 13:50
    
SHA-2(SHA-256 and SHA-224) have 64 rounds and yes larger versions have 80 rounds. –  tausif Mar 13 at 14:06

3 Answers 3

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.

share|improve this answer
1  
Also, since the state consists of 5 words, the round count is a multiple of 5 –  Richie Frame Mar 14 at 9:42
    
As someone who's not really familiar with crypto, a really nicely written explanation. –  Nit Mar 14 at 11:23

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.

share|improve this answer
    
In a block cipher, each round function is actually a bijection, and often the inverse is (almost) as easy to calculate as the original one. In hash functions based on block ciphers (like SHA-1 and SHA-2), it is the same. –  Paŭlo Ebermann Mar 13 at 16:00
    
The F function in a Feistel network is only a bijection if you consider the subkey to be fixed, otherwise it's $X+Y$ bits of input and $X$ bits output. So it's only a bijection if you know the according subkey (but if you do cryptanalysis, you don't have that). And considering hash functions this isnt true either, e.g. the F function in SHA-1 takes $3\cdot 32$ bits input and returns $32$ bit output. –  tylo Mar 13 at 16:52
    
In general, the statement that bijections are easy to compute backwards is only valid if a) it has low nonlinearity (e.g. if expressed as polynomial of low degree) b) it is designed that way (like a block ciphers with a fixed key used as 1 function) c) you can just have a lookup table for all inputs/outputs. –  tylo Mar 13 at 17:02
    
You are right, not every "round" function is a bijection. I generalized too much from AES here, I suppose. –  Paŭlo Ebermann Mar 13 at 19:02
    
@PaŭloEbermann: Even AES is harder to decrypt than encrypt in many cases due to the 'worse' coefficients in the mixcolumns matrix. @ Tylo: v minor - 'number 80 looks nicely'->'nice'; If you wanted to improve your answer (which is already good) you could elaborate on the 'is it to reduce collisions' section –  figlesquidge Mar 14 at 9:22

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.

share|improve this answer

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.