4 ms·

From what I understand, the Feb 23rd SHA-1 attack was possible because they figured out how to get the internal state (160 bits or 5 words of 32 bits) to match

From what I understand, the Feb 23rd SHA-1 attack was possible because they figured out how to get the internal state (160 bits or 5 words of 32 bits) to match from two separate pieces of data. After that, additional data could be appended to the first two pieces as long as it was identical. The internal state would play back the same sequence from there on, just like two random number generators starting from the same seed. Here is a comparison of internal state sizes: https://en.wikipedia.org/wiki/SHA-0#Comparison_of_SHA_functions https://en.wikipedia.org/wiki/SHA-0#Comparison_of_SHA_functi... SHA-256 is susceptible to this same flaw, it would just take longer because it has about about 128 bits of security instead of less than 80 for SHA-1. It looks like only SHA-3 really "gets it" with a 1600 bit state size. After all of the effort put into making highly pseudo-random hash functions, it's a wonder that the state size was only the size of the hash. By comparison, Mersenne Twister's state size is 19937 bits (624 words of 32 bits minus 31 bits): http://www.quadibloc.com/crypto/co4814.htm http://www.quadibloc.com/crypto/co4814.htm Does anyone know why hash algorithms keep using such small state sizes, leaving us vulnerable to this same issue?

jstrom 10y ago
I can't speak specifically to SHA-1/2, but typically the criteria for the standards takes into account lower-end hardware that must be able to execute the algorithms with limited memory and processing (especially embedded systems). For example, smart cards and terminals for the payments/banking industry. These algorithms came out in the 90's when you often had 8-bit processors and very little memory to work with.
deleted 10y ago
[deleted]
sebcat 10y ago
128 bits are 2^48 (~2.81*10^14) times larger than 80 bits (80 bits is the brute force, and SHAttered was less than that), and comparing SHA-2 to a Mersenne Twister is just picking two numbers and saying "this one is less than that one" without context. EDIT: "The computational effort spent on our attack is estimated to be equivalent to 2^63.1 SHA-1 calls" [1] Comparing that to 2^128 (birthday paradox SHA-256) is... It doesn't apply. [1] http://shattered.it/static/shattered.pdf http://shattered.it/static/shattered.pdf
benchaney 10y ago
This issue only means that once you find a collision, you kind find more collisions by extending it. Generally speaking it is expected that once a collision is found in a hash function it has already been mostly phased out, so this flaw is not seen as particularly important.
ctz 10y ago
> Does anyone know why hash algorithms keep using such small state sizes, leaving us vulnerable to this same issue? Because small internal state is not actually the issue. SHA-1 was broken with 2^63 work, not 2^80 work. That discrepancy is why SHA-1 was deemed broken back in 2005, not because people regularly do 2^80 work.
wyager 10y ago
This is a consequence of the Merkle–Damgård construction. It has little to do with the state size. SHA-3 uses a different construction, and so is immune to this particular type of extension attack.
- wyager 10y ago
  I thought about this more and realized I was wrong. Sponge construction doesn't help in this case. It's too late to edit.
meta_AU 10y ago
A 1:1 state to input ratio is just the optimal performance value (more input than state lowers secury, and the other way lowers efficiency). SHA-3 still has that ratio, it just supports consuming more bytes at a time. Increasing this size too much reduces efficiency for small input sizes. SHA-512/256 is in a pretty good spot, as the internal state is twice the recommended hash security size, and the output is equal to the recommended size (256bit for "128bit security level). Common tree hash constructions will want to take 2 inputs and reduce to 1 output, which is the exact ratio for SHA-512/256.
- magila 10y ago
  What you really care about for tree hashes is the block size to output ratio. SHA-512/256 has a 1024 bit block size so it is less optimal than SHA-256, which has a 512 bit block size, for tree hashes. This is assuming you don't need any extra data in the internal nodes.
  - ribasushi 10y ago
    Could you expand on this comment and/or provide links to relevant reading? Much appreciated!

jstrom 10y ago

I can't speak specifically to SHA-1/2, but typically the criteria for the standards takes into account lower-end hardware that must be able to execute the algorithms with limited memory and processing (especially embedded systems). For example, smart cards and terminals for the payments/banking industry. These algorithms came out in the 90's when you often had 8-bit processors and very little memory to work with.

deleted 10y ago

[deleted]

sebcat 10y ago

128 bits are 2^48 (~2.81*10^14) times larger than 80 bits (80 bits is the brute force, and SHAttered was less than that), and comparing SHA-2 to a Mersenne Twister is just picking two numbers and saying "this one is less than that one" without context. EDIT: "The computational effort spent on our attack is estimated to be equivalent to 2^63.1 SHA-1 calls" [1] Comparing that to 2^128 (birthday paradox SHA-256) is... It doesn't apply. [1] http://shattered.it/static/shattered.pdf http://shattered.it/static/shattered.pdf

benchaney 10y ago

This issue only means that once you find a collision, you kind find more collisions by extending it. Generally speaking it is expected that once a collision is found in a hash function it has already been mostly phased out, so this flaw is not seen as particularly important.

ctz 10y ago

> Does anyone know why hash algorithms keep using such small state sizes, leaving us vulnerable to this same issue? Because small internal state is not actually the issue. SHA-1 was broken with 2^63 work, not 2^80 work. That discrepancy is why SHA-1 was deemed broken back in 2005, not because people regularly do 2^80 work.

wyager 10y ago

This is a consequence of the Merkle–Damgård construction. It has little to do with the state size. SHA-3 uses a different construction, and so is immune to this particular type of extension attack.

wyager 10y ago
I thought about this more and realized I was wrong. Sponge construction doesn't help in this case. It's too late to edit.

meta_AU 10y ago

A 1:1 state to input ratio is just the optimal performance value (more input than state lowers secury, and the other way lowers efficiency). SHA-3 still has that ratio, it just supports consuming more bytes at a time. Increasing this size too much reduces efficiency for small input sizes. SHA-512/256 is in a pretty good spot, as the internal state is twice the recommended hash security size, and the output is equal to the recommended size (256bit for "128bit security level). Common tree hash constructions will want to take 2 inputs and reduce to 1 output, which is the exact ratio for SHA-512/256.

magila 10y ago
What you really care about for tree hashes is the block size to output ratio. SHA-512/256 has a 1024 bit block size so it is less optimal than SHA-256, which has a 512 bit block size, for tree hashes. This is assuming you don't need any extra data in the internal nodes.
- ribasushi 10y ago
  Could you expand on this comment and/or provide links to relevant reading? Much appreciated!