Lessons from the History of Attacks on Secure Hash Functions
z.cash
z.cash
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_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
Does anyone know why hash algorithms keep using such small state sizes, leaving us vulnerable to this same issue?
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.
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.
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.
SHA-3 uses a different construction, and so is immune to this particular type of extension attack.
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.
Much appreciated!
I actually feel that this can be even more generalized: At some point people learned to create unbreakable algorithms. There is literally no mainstream crypto algorithm beyond the 2000s that has seen any significant breakage. And very likely there never will be, with one exception: quantum computers will break modern ECC.
I think there's simply a dark age of crypto research with 90s algos and earlier. Which isn't surprising: Back then people were fighting whether it's even legal to do that kind of research.
And RSA. And Diffie-Helman.
My point was: Modern ECC (X25519 and friends) are the only post-2000 invented mainstream algs where any realistic breakage is in sight.
But I'm not willing to be the farm on that risk. PQCrypto, please. :)
I am not very experienced with this, but isn't this clearly wrong?
If I have a controllable collision (like SHA1), I can get someone to sign document A, then destroy all evidence of document A's existence and claim they signed document B.
Isn't it essential that a digital signature scheme is immune against such an attack?
I believe that's an error: the official site¹ puts "collision resilience" in the list of features.