Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Sha-1 - Compromised Security; another hash destroyed
Topic Started: Dec 19 2005, 08:49 PM (1,980 Views)
cows
Member Avatar
Advanced Member
[ *  *  * ]
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: 2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2
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:
2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2 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

sources: 'New Scientist 17th December 05'
Everything is possible,
The impossible just takes longer

If we do not know what a particle is doing then it is allowed t do everything possible simultaneously.
"Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it."
Offline Profile Quote Post Goto Top
 
Revelation
Member Avatar
Administrator
[ *  *  *  *  * ]
Nice article :) I think it would be wise for me to learn more about hashing...
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN
RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN
RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN
RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN
RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN
Offline Profile Quote Post Goto Top
 
cows
Member Avatar
Advanced Member
[ *  *  * ]
Thanks revelation - it took a while to make :)

I knew very little about how hashes worked until i read this then i understood more - i just thought that you guys might find his important.

Cows
Everything is possible,
The impossible just takes longer

If we do not know what a particle is doing then it is allowed t do everything possible simultaneously.
"Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it."
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Thank you for the article! Folks on Sci.Crypt have been suggesting that everyone move away from MD5 and SHA-1 for a while now. As the article points out, MD5 is truly compromised and SHA-1 is on the way down. (Attacks always get better, never worse)
"cows"
 
then we may be hitting the fan and all our secrets may not be secret at all.

Don't Panic. :) Yes, SHA-1 being broken is a bad thing, but it will not cause all secrets to be revealed. For example, if you use SHA-1 (or even MD5) to convert a text passphrase into a secure key, the hash being broken will not do much to weaken the strength of your key. The ability to find collisions does not allow anyone to guess either your key or your passphrase.

The big thing that broken hashes really threaten is message authentication. If you are signing encrypted messages with an MD5 hash, it is now within the realm of reason that someone could modify the message in a way that would "collide" with the original. In other words, the message would now say something different, but the has would still be the same.

This is, indeed, a bad thing, but it does NOT mean that hackers will be reading all your old encrypted files. And of course, the solution is easy, just switch to SHA-256. :)

Donald
Offline Profile Quote Post Goto Top
 
cows
Member Avatar
Advanced Member
[ *  *  * ]
Surely the problem with moving to yet another hash, such as SHA-256 is that it will not be long to break that. Especially seen as 5 hashes have been compromised in the last 18 months. Surely this is a bad thing to do and maybe we should rely on more secure ways - whatever we can call these now - as most hashes will be broken soon.

I predict by 2020 that all the hashes that we have today will have been broken and if i am wrong i will give Donald £20 :lol:
Everything is possible,
The impossible just takes longer

If we do not know what a particle is doing then it is allowed t do everything possible simultaneously.
"Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it."
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"cows"
 
Surely the problem with moving to yet another hash, such as SHA-256 is that it will not be long to break that.

Hashes are as different as cryptographic routines. Finding weaknesses in one does not necessarily indicate a weakness in others.

"cows"
 
I predict by 2020 that all the hashes that we have today will have been broken and if i am wrong i will give Donald £20

Ha! Keep your money. :) It's possible that SHA-256 has weaknesses as well, I don't know enough about hashes to say. But it's important to realize that hashing is (as far as I know) a fairly NEW science. We went from simple check-sums to MD5 and then to SHA-1. There is still a lot to learn here, especially in how to evaluate the security of a hash.

So, since our problem is ignorance about hashes and one way functions, I would be almost as nervous betting that SHA-256 is breakable as betting that it isn't.

Donald
Offline Profile Quote Post Goto Top
 
kryptosfan
Member Avatar
Kickass member
[ *  *  *  *  *  * ]
NIST should be announcing the SHA-3 competition winner next year. From what I can tell though no one has broken SHA-256 or SHA-512 although maybe I'm not looking in the right way.
OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · News · Next Topic »
Add Reply