SHA-1 Compromised Security
[View]
[Reply]
[Top]
Posted by Tr theanonymoustree
On 2005-12-19 23:11:22
|
Recently – as most of us know - the security provided by the MD5 hash has been broken. This tremendous achievment was performd by a Chinese cryptographer called, Xiaoyun Wang.
This is not a new thing although it has destroyed the security provided by the hash and forced people to use other hashes to provide security. Well – yet again, Wang has hit the world of cryptography hard and strong by breaking the SHA-1 hash, another hash used by many to ensure security over the internet.
SHA stands for ‘Secure Hash Algorithm’. Hash Algorithms are mathematical procedures that ‘engulf’ a message – be it a 8 letter password or a 20 page essay – and produce a fixed length of 1’s and 0’s. This is done by mixing up bits from the message with other bits chosen at random and then distilling the resulting string of bits down to a particular length.
These ‘hash algorithms’ or ‘hash functions’ are used in nearly every aspect of digital security nowadays and are supposed to be the most secure way to encrypt anything over the internet.
They are used to secure your passwords that give you access to computers, your email, secure websites. They enable digital signatures to be used to authenticate messages and their senders, are used for time-stamping legal, financial and copyright-sensitive documents, for checking that software has not been tampered with, to authenticate secure websites before credit card numbers are typed in and transmitted and even to generate random numbers for encryption keys.
Meanwhile, cryptographers sprinkle them liberally thoughout their protocols to add some more security at every stage.
MD5 is the hash that she broke last year, devised by Ronald Rivest in 1991, used mainly in older applications now but used to be very popular (until she broke it).
SHA-1 is the hash that she has just broken, the pinnacle of computer security. The algorithm was invented and endorsed by the NSA (National Security Agency) in 1995 and used in a mass of security applications (look above). This is used in the latest and most secure applications as it has been thought safe, evidently not.
These two are massively popular because it makes in extremely difficult (cryptographers call it ‘computationally unfeasible’) to recreate the starting message exactly from it’s hash. This is obviously a desirable factor for those who want uncomprimisable security for extremely sensitive messages. The second factor is the fact that it is ‘computationally unfeasible’ to find two messages with exactly the same hash.
Those messages that do end up having the same hash - this is because of the relatively short length of the hash, MD5 for instance is an 128-bit hash – are said to ‘collide’ The hash algorithm makes it practically impossible, given todays computer power, for anyone to find a collision, and thus enable the message open to tampering, by random guessing or by brute forcing.
For MD5 it would take an average of 2^64 guesses to find a collision. For this article ‘2^64’ means ‘2 to the power of 64’.
To put this into a bigger perspective: 2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x
2x2x2x2x2x2x2x2x2x2x2x2x2x2
or better yet - 188446744073709551616 guesses to find a collision
SHA-1 hashes are longer and it would take an average of 2^80 guesses to find a collision or:
2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x
2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2 guesses – or better yet – 1208925819614629174706176 guesses to find a collision
This would take millions of millions of years to compute, or that is what everybody thought – Wang has just rewritten the numbers, and proved us all wrong.
She did it by examining what happens to strings of data at different stages of the algorithm. As the message goes through the different mathematical procedures, as it’s bit string is rewritten at every different stage of the algorithm. If you put two messages thrugh the system and watch how they change at each step – you can get a mathimatical ‘feel’ for the kind of bit strings that will result in a collision.
Wang has found that just finding the path to a collision is enough to break some algorithms – She broke SHA-0 (SHA-1’s predecessor) in exactly this way in 1997 with 2^58 computations, just by mapping out the collision paths.
This is not an immediate threat – noone has yet managed to compute a collision for SHA-1 such as they have for MD5 and other compromised hashes, but it is inevitable that it will happen and we are in for a shock when it does – nothing will be safe.
At the moment – the safest thing to do is to change our security to SHA-256, an algorithm created by the NSA to replace SHA-1 by 2020. We will not be in too much trouble – until Wang breaks this – then we may be hitting the fan and all our secrets may not be secret at all.
In the last 18 months five hashes have been broken - the question i shall leave you with is: Are hashes really safe? Should we use a different system
|
RE: SHA-1 Compromised Security
[View]
[Reply]
[Top]
Posted by Alpha Tr dragonxhero13
On 2005-12-22 05:10:23
|
On 2005-12-19 23:11:22, theanonymoustree wrote
>These ‘hash algorithms’ or ‘hash functions’ are used in nearly every aspect of digital security nowadays and are supposed to be the most secure way to encrypt anything over the internet.
>
this part of your information is partially correct. in theory, a hash algorithm is a one way permutation of data that will produce a _unique_ fixed length ciphertext. in theory, there should never be a collision. anyway, hashes aren't used to encrypt all kinds of data, since you can't (read: ‘computationally unfeasible’) decrypt them. they are generally used in authentication, as they prove something you know, which is one member of the auth trinity.
>SHA-1 is the hash that she has just broken, the pinnacle of computer security.
this is incorrect. Xiaoyun and her team are methodically and ruthlessly exposing weaknesses in sha-1 and other algorithms that other people hadn't yet found. a fundemental truth about crypto (read 'secrets and lies' by schnier) is that 100 great cryptographers not finding a flaw in an algorithm does not in any way suggest that there aren't fundemental flaws in the algorithm.
my (limited) understanding of her work is that she has improved the ease of finding collisions by many order of magnitude, but that it is still no quick task.
plus (don't remember if it's related to some other teams work) the way kaminsky (much smarter than me) explained it to me was that we don't have a way to take a hash with an unknown plaintext and find a different plaintext that hashes out to a collision. such an attack would completely undermine the fabric of whatever algo was broken like that.
atm i think we can only say: hey looky, after weeks/months/? on the supercomputer we created these two plaintexts that hash out as a collision.
|
RE: SHA-1 Compromised Security
[View]
[Reply]
[Top]
Posted by Gamma Tr The Digital Poet
On 2005-12-22 09:41:05
|
this part of your information is partially correct. in theory, a hash algorithm is a one way permutation of data that will produce a _unique_ fixed length ciphertext. in theory, there should never be a collision. anyway, hashes aren't used to encrypt all kinds of data, since you can't (read: ‘computationally unfeasible’) decrypt them.
This is not completely correct, infact a "unique, fixed length ciphertext" contains a contradiction in terms. If the cipher text is fixed length then it only contains a fixed number of possible values (x), if I hash x+1 different pieces of plain text then I will get at least 1 collision. The fixed length hash does not provide enough 'data space' to give me a unique result every time. Infact, if their is no restriction on input data length, then there is an infinate number of values that will hash to any given hash value. They are just very difficult to find.
Also, it is not just computationally unfeasible to decrypt a hash, it is computationally impossible. This is because the hash is a summary of the original data and while a piece of input data will only have one hash value (per algorithm) a hash has an infinate number of possible input data values. Let's say I contrive a hash function, input data has to be a series of numbers (bytes) and my hash function just adds the numbers...
input = 123 output = 6
input = 18 output = 7 etc
If I give you the number 12 as the output, what was the input?... see what I mean?
The best you can do with a hash is to try to find a piece of plain text that hashes to the same value, and the only (current) way to do this is bruteforce. Even if i find a value that hashes to the same hash, I cannot be sure that the value I have found is the exact value used to create the hash in the first place. It may be possible to tell from context, if I find a piece of text that is written in natural language and hashes to the right value then I have probably found the original input, while theorectically there are an infinate number of natural language inputs that will hash to a given value, most will be many orders of magnatude larger than the combined text of everything ever written (except, possibly, for this post ;o)).
|
RE: SHA-1 Compromised Security
[View]
[Reply]
[Top]
Posted by Alpha Tr dragonxhero13
On 2005-12-24 06:28:02
|
On 2005-12-22 09:41:05, The Digital Poet wrote
>this part of your information is partially correct. in theory, a hash algorithm is a one way permutation of data that will produce a _unique_ fixed length ciphertext. in theory, there should never be a collision.
>
>This is not completely correct, infact a "unique, fixed length ciphertext" contains a contradiction in terms.
Yea, I'll conceed the point, and was thinkin the same when i wrote that. I was thinkin that if a hash allowed ciphertext length == plaintext length, then you'd get no collisions... but then would it be a 'hash'? if you don't lose data, can your algo be unreversible and reproduceable?
>Also, it is not just computationally unfeasible to decrypt a hash, it is computationally impossible.
Kinda pickin up where I left off, I felt as you did, until I lost a bet w/ someone over whether or not DES and 3DES are reversible algo's, which were ( / sometimes still are? ) used as password hashes for some *nix systems (and prolly other stuff). I never dug enough to be sure the (3)DES hash is the same algo as the (3)DES (de)crypt. But, I did read something back int he day that said hashed passwords were put in /etc/passwd b/c they were so infeasbily difficult to decrypt. no one had yet thought of guessing plaintexts and crypting/hashing them, which turned out to be much more computationally feasible than decrypting. ;))) after this was discovered, *nix moved to the /etc/shadow convention.
Maybe my info is way wrong, but it's what I've read w/ what time I've had to dig on it. I don't think md5 or sha are reversible, but if (3)DES is, then it doesn't seem right to say it's computationally impossible to decrypt any hash. just unfeasible ;)
>while theorectically there are an infinate number of natural language inputs that will hash to a given value, most will be many orders of magnatude larger than the combined text of everything ever written (except, possibly, for this post ;o)).
lol... a healthy debate is good for the soul ;)
|
|
|
2^80 collision on SHA-1...That's old dude [nt]
[View]
[Reply]
[Top]
Posted by Gamma Cpt Mardukk
On 2005-12-20 00:44:48
|
|
|
FUD...
[View]
[Reply]
[Top]
Posted by Gamma Tr The Digital Poet
On 2005-12-20 00:22:15
|
We need to get a perspective on this. The attack against MD5 and SHA-1 makes it slightly easier to find two random sets of bytes that will hash to the same value. This is not particularlly useful to an attacker. We are still unable to easily find data that will hash to a given value, and we are a long long long way from being able to calculate bytes with which to 'pad' a message so that we can alter a signed message and have it provide the same hash. This is not a reason to run to another algorithm or to abandon hashing altogether.
Anyone that requires absolute security of their digital signature, should use HMAC-SHA1, or better yet, provide multiple hashes using different algorithms, that way, you should be good for a few centuries at least.
On 2005-12-19 23:11:22, theanonymoustree wrote
>Recently – as most of us know - the security provided by the MD5 hash has been broken. This tremendous achievment was performd by a Chinese cryptographer called, Xiaoyun Wang.
>
>This is not a new thing although it has destroyed the security provided by the hash and forced people to use other hashes to provide security. Well – yet again, Wang has hit the world of cryptography hard and strong by breaking the SHA-1 hash, another hash used by many to ensure security over the internet.
>
>SHA stands for ‘Secure Hash Algorithm’. Hash Algorithms are mathematical procedures that ‘engulf’ a message – be it a 8 letter password or a 20 page essay – and produce a fixed length of 1’s and 0’s. This is done by mixing up bits from the message with other bits chosen at random and then distilling the resulting string of bits down to a particular length.
>
>These ‘hash algorithms’ or ‘hash functions’ are used in nearly every aspect of digital security nowadays and are supposed to be the most secure way to encrypt anything over the internet.
>
>They are used to secure your passwords that give you access to computers, your email, secure websites. They enable digital signatures to be used to authenticate messages and their senders, are used for time-stamping legal, financial and copyright-sensitive documents, for checking that software has not been tampered with, to authenticate secure websites before credit card numbers are typed in and transmitted and even to generate random numbers for encryption keys.
>
>Meanwhile, cryptographers sprinkle them liberally thoughout their protocols to add some more security at every stage.
>
>MD5 is the hash that she broke last year, devised by Ronald Rivest in 1991, used mainly in older applications now but used to be very popular (until she broke it).
>
>SHA-1 is the hash that she has just broken, the pinnacle of computer security. The algorithm was invented and endorsed by the NSA (National Security Agency) in 1995 and used in a mass of security applications (look above). This is used in the latest and most secure applications as it has been thought safe, evidently not.
>
>These two are massively popular because it makes in extremely difficult (cryptographers call it ‘computationally unfeasible’) to recreate the starting message exactly from it’s hash. This is obviously a desirable factor for those who want uncomprimisable security for extremely sensitive messages. The second factor is the fact that it is ‘computationally unfeasible’ to find two messages with exactly the same hash.
>
>
>
>
>
>Those messages that do end up having the same hash - this is because of the relatively short length of the hash, MD5 for instance is an 128-bit hash – are said to ‘collide’ The hash algorithm makes it practically impossible, given todays computer power, for anyone to find a collision, and thus enable the message open to tampering, by random guessing or by brute forcing.
>
>For MD5 it would take an average of 2^64 guesses to find a collision. For this article ‘2^64’ means ‘2 to the power of 64’.
>To put this into a bigger perspective: 2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x
>2x2x2x2x2x2x2x2x2x2x2x2x2x2
>or better yet - 188446744073709551616 guesses to find a collision
>
>SHA-1 hashes are longer and it would take an average of 2^80 guesses to find a collision or:
>2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x
>2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2 guesses – or better yet – 1208925819614629174706176 guesses to find a collision
>
>This would take millions of millions of years to compute, or that is what everybody thought – Wang has just rewritten the numbers, and proved us all wrong.
>
>She did it by examining what happens to strings of data at different stages of the algorithm. As the message goes through the different mathematical procedures, as it’s bit string is rewritten at every different stage of the algorithm. If you put two messages thrugh the system and watch how they change at each step – you can get a mathimatical ‘feel’ for the kind of bit strings that will result in a collision.
>
>Wang has found that just finding the path to a collision is enough to break some algorithms – She broke SHA-0 (SHA-1’s predecessor) in exactly this way in 1997 with 2^58 computations, just by mapping out the collision paths.
>
>This is not an immediate threat – noone has yet managed to compute a collision for SHA-1 such as they have for MD5 and other compromised hashes, but it is inevitable that it will happen and we are in for a shock when it does – nothing will be safe.
>At the moment – the safest thing to do is to change our security to SHA-256, an algorithm created by the NSA to replace SHA-1 by 2020. We will not be in too much trouble – until Wang breaks this – then we may be hitting the fan and all our secrets may not be secret at all.
>
>In the last 18 months five hashes have been broken - the question i shall leave you with is: Are hashes really safe? Should we use a different system
|
actually his post quite informative and correct -nt-
[View]
[Reply]
[Top]
Posted by Delta Maj comet
On 2005-12-20 15:42:30
|
|
I didnt say it wasnt...
[View]
[Reply]
[Top]
Posted by Gamma Tr The Digital Poet
On 2005-12-20 16:01:52
|
What I said was that the severity of this attack is grossly over exagerated. Unless I am mistaken, the attack discovered made it easier to work out two pieces of random input data that will hash to the same value. This is not very useful for any kind of attack.
For it to be useful, you need to control some of the input bytes. I cannot, using this attack, generate a set of bytes that will hash to a given value.
I am sure the attack is fascinating from a mathematical standpoint (I wouldnt know, it is beyond my skills) but in pratical terms it represents a very small crack. It is possible that small crack will grow into a larger one eventually, but for now there is no rush.
|
|
|
|
|