Liberty's Blog: SHA-1 Broken ?

Friday, February 18, 2005

SHA-1 Broken ?

Data security is usually concerned with two seperate functions. The first is ensuring the data is originating from those whom it is supposed to and that it is complete and unaltered. This is sometimes called signing, The other function is encryption. Encryption is used to ensure privacy. The most practicle way of encryption is to use a public key. A public key is typically widely available, decryption is done with a private key that should only be accessable by the owner, therefore only the key owner can decrypt a message. If anyone can access the public key, then it becomes important that the owner of the sent data be known, and it is some how verififyable that the data hasn't been tampered with. Signing is very important in sending of encypted data, as well as any other secure data transport, and is therefore the most important part of any data security icluding PGP. Signing is often invisible to many users, when we use our Credit cards, access financial accounts, or even apply software patches our browsers use signing. The most common algorithm to date is called the SHA-1 Hash. It seems that it is not as secure as we had once thought.

SHA-1 Broken
SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing their results:
collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length.
collisions in SHA-0 in 2**39 operations.
collisions in 58-round SHA-1 in 2**33 operations.

Bruce Schneier is one of the most highly respected folks in the science of Cryptology, and it apears that his concerns should be taken seriously. Maybe though its not really really broken but frayed with some cracking. Its going to take a while but we are all going to be affected and a swithchover to a more secure algorithim is sure to replace the, until now, reliable SHA-1 hash. Until this happens we will go on just as we have before using secure web pages and PGP until something better comes along.