Crypto researchers break SHA-1

[egibbs]

http://www.theregister.co.uk/2005/02/17 ... ng_broken/

This was all over the news yesterday. I only mention it here because the TCPA embedded security chip in our TPs implements SHA-1 in hardware.

Practical implications are probably nil right now - if someone has physical access to your machine, can read the hash of your passphrase from the chip, and has a supercomputer they could likely brute force (given enough time) a phrase that computes to the same hash and would unlock your machine.

But these types of discoveries imply unknown holes in the algorithm - this was not supposed to be possible. In the past such discoveries have sometimes served as wedges to crack the algorithm open, and been followed quickly by discovery of much more serious cracks.

Ed Gibbs

[Batuta]

...

[Moroner]

This attack is currently quite theoretical: It reduces the collision detection strength from 80 to 69 bits, saving a nice factor of 2048 in the process. The trick of course, is to generate collisions that are plausible: You cannot simply change 80 random bits in a 20 KByte text, it must look "natural". And this is much harder to achieve. So for now, SHA-1 is still practically safe, unless this attack yields new breakthroughs.

[egibbs]

Right - and if anyone signs a document electronically today that could wind up in court a year or two from now (when SHA-1 cracking software for dummies will be all over the net) they are a fool.

It's safer to treat anything encrypted with an unbreakable code as probably safe for 6 months to a year. After that all bets are off.

[Batuta]

...

[Moroner]

Short explanation of digital signatures:
1. You have a document you want to sign
2. You compute a hash over that document
3. You use public key encryption to sign that hash

There are a few attacks possible:
1. You find a hash collision, and use it to forge the document.
2. You break the public key encryption (If you can do that, claim your 100 000 USD at RSA Securities right now )
3. You fool the real signer to sign your forged document

All of these attacks are not simple. 3) is probably the easiest, given how many holes in security protocols have been found with Casper (a protocol anlysis tools developed at Oxford University). A variant on 3) is that, after you found a collision, you prepare two documents, get one signed, and pretend that actually the other was signed. But, as said previously, you still have the problem of getting a "natural" looking hit.

For documents already posted, you can either break PKE. This will probably remain hard until quantum computers arrive, and then we will have to revert to one-time-pads. Or you can find a hash collision to an existing hash value. And this doubles the number of bits you have to search, making it completely unfeasable with today's technology. So these will be safe, until there are further breakthroughs.

For some further explanations on hash collisions, have a look at http://www.cryptography.com/cnews/hash.html

[Batuta]

...