This may have some fairly dire consequences for internet crypto, certificates, and secure email.
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
-
Hey Guest. Check out your NeoGAF Wrapped 2025 results here!
SHA-1 has been cracked.
- Thread starter aaaaa0
- Start date
- Status
SHA-1 is a hash algorithm, like MD5. It is probably the most popular hash algorithm now used on the internet. SHA-1 is used for many things: certificates, secure web pages, email, secure file transfer, etc.
The paper says that it is possible to find two messages that result in the same SHA-1 hash with substantially less effort than the length of the hash itself would suggest.
This means it may now be practical to take a secure hashed message, append or alter it in some fashion, and create a second message that hashes to the same value.
This could then be used to trick users or software that rely on SHA-1 to prove that the data had not been tampered with or damaged.
The paper says that it is possible to find two messages that result in the same SHA-1 hash with substantially less effort than the length of the hash itself would suggest.
This means it may now be practical to take a secure hashed message, append or alter it in some fashion, and create a second message that hashes to the same value.
This could then be used to trick users or software that rely on SHA-1 to prove that the data had not been tampered with or damaged.
to elaborate, all it means is that SHA1 is not as collision resistant as we thought (and by extension sha1 must not be either).
practically this means that a lot of schemes which relied on the collision resistance of SHA1 are much less secure (among these are cryptographic schemes, message authentication, etc)
practically this means that a lot of schemes which relied on the collision resistance of SHA1 are much less secure (among these are cryptographic schemes, message authentication, etc)
To elaborate some more, imagine you had a file that was a bunch of numbers like this:
1 33 2 45 2 9 1 99
An extremely simple and insecure hash algorithm might be to add all the numbers up. So, just for example, the hash for this file would be 192.
If I tampered with your file and changed the 33 to a 34, then the hash of the file would now be 193, and anyone who knew that the original hash for the file was supposed to be 192 would be able to tell that I had changed something inside it.
To defeat this extremely simple and insecure hash algorithm, I could instead try swapping two numbers. Or adding to one number and subtracting from another.
Just as a simple contrived example (ignoring encryption and certificates), suppose the series of numbers indicated a bank account and a transfer amount. I could try to arrange it so that I could encode my bank account and a different amount into that message, and have it come out to the same hash value (192). Then, anyone expecting a messge from you with the hash value 192 would still be happy, even though they were executing my instructions instead of yours.
1 33 2 45 2 9 1 99
An extremely simple and insecure hash algorithm might be to add all the numbers up. So, just for example, the hash for this file would be 192.
If I tampered with your file and changed the 33 to a 34, then the hash of the file would now be 193, and anyone who knew that the original hash for the file was supposed to be 192 would be able to tell that I had changed something inside it.
To defeat this extremely simple and insecure hash algorithm, I could instead try swapping two numbers. Or adding to one number and subtracting from another.
Just as a simple contrived example (ignoring encryption and certificates), suppose the series of numbers indicated a bank account and a transfer amount. I could try to arrange it so that I could encode my bank account and a different amount into that message, and have it come out to the same hash value (192). Then, anyone expecting a messge from you with the hash value 192 would still be happy, even though they were executing my instructions instead of yours.
Diablos said:
The reason it is possible is something called the pigeonhole principle.
http://www.netaxs.com/people/nerp/automata/pumping1.html
Basically this says that if you have n holes, and m objects, if n < m, then at least one hole must have more than one object in it.
SHA-1 hashes a file of any length into a single 160-bit number. This means there are exactly 2^160 values it can represent. So, if SHA-1 is perfect, then every single 160-bit file will have a unique SHA-1 hash.
It follows then from the pigeonhole priciple that if you have a file that is 161-bits long, then there must exist at a minimum one other file with exactly the same hash value.
The paper released proves that not only is SHA-1 not perfect, it is substantially less than perfect as a hashing function. Which means for every 160-bit file, there exists MANY possible other files that hash to the same value. Moreover, it is substantially easier to find the colliding file than was expected based on the length of the hash (160-bits).
PGP, at its core, is a public key encryption tool. It uses hashes, but they aren't the core of it. Public key encryption involves having two keys, one that you give to everyone and can encrypt a message, and the other that you keep secret that can decrypt it (and in many cases, vice versa, to act as a signature mechanism).
The current mechanism of public key encryption is based on the difficulty of factoring large numbers that are generated from pairs of large prime numbers.
The current mechanism of public key encryption is based on the difficulty of factoring large numbers that are generated from pairs of large prime numbers.
- Status