Viewing Single Post From: Sha-1 - Compromised Security

Viewing Single Post From: Sha-1 - Compromised Security
cows	Dec 19 2005, 08:49 PM
Advanced Member Posts: 91 Group: New Members Member #20 Joined: October 10, 2005	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."

Sha-1 - Compromised Security · News