Skip to main content
added 149 characters in body
Source Link
CodesInChaos
  • 25.1k
  • 2
  • 90
  • 129

Most hashes are built from permutations (either keyed permutations/block-cipherciphers, 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 achieveachieves 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 is achievingthat 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 Cryptoanalysisdifferential cryptoanalysis, which is a popular technique for attacking hashes and blockciphersblock-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%. GoingAfter 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. The aim usingA 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.

inIn hindsight, they chose a too low value, since we have since found attacks onagainst SHA-1 that arefind collisions faster than brute-force.

Most hashes are built from permutations (either keyed permutations/block-cipher, 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 achieve 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 is achieving 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 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 blockciphers.

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%. 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. The aim using enough rounds that exploiting these shuffling flaws is more expensive than doing a brute-force attack.

(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 on SHA-1 that are faster than brute-force.

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.

Source Link
CodesInChaos
  • 25.1k
  • 2
  • 90
  • 129

Most hashes are built from permutations (either keyed permutations/block-cipher, 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 achieve 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 is achieving 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 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 blockciphers.

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%. 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. The aim using enough rounds that exploiting these shuffling flaws is more expensive than doing a brute-force attack.

(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 on SHA-1 that are faster than brute-force.