Further problems with SHA-1

on Friday, August 19, 2005
So what is SHA-1?

From wikipedia: The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions. The most commonly used function in the family, SHA-1, is employed in a large variety of popular security applications and protocols, including TLS, SSL, PGP, SSH, S/MIME, and IPSec. SHA-1 is considered to be the successor to MD5, an earlier, widely-used hash function. The SHA algorithms were designed by the National Security Agency (NSA) and published as a US government standard.

The first member of the family, published in 1993, is officially called SHA; however, it is often called SHA-0 to avoid confusion with its successors. Two years later, SHA-1, the first successor to SHA, was published. Four more variants have since been issued with increased output ranges and a slightly different design: SHA-224, SHA-256, SHA-384, and SHA-512 — sometimes collectively referred to as SHA-2.

From w3c.org: The Secure Hash Algorithm takes a message of less than 264 bits in length and produces a 160-bit message digest which is designed so that it should be computationaly expensive to find a text which matches a given hash. ie if you have a hash for document A, H(A), it is difficult to find a document B which has the same hash, and even more difficult to arrange that document B says what you want it to say.

Some months ago a team of chinese researchers found an algorithm that could produce collisions in SHA-1, i.e., different messages could produce the same hash, which could be used, in theory, to forge certificates. SHA-1 is supposed to require at least 2^80 to produce a collision, which would be enough to keep it squarely out of supercomputer realm. The researchers initially managed to produce collisions in 2^69 operations, and now they were able to do it in 2^63. The lower it gets, the faster it is to break :D

For now, this is only a paper... until someone implements it, and then the fun begins. Although the US are recommending a move to SHA-2, there's this interesting quote by the NIST security technology group manager William Burr, in Federal Computer Week: "SHA-1 is not broken, and there is not much reason to suspect that it will be soon." Should become an interesting tagline in a bit of time... hehehe


matthewkline2262 said...

i thought your blog was cool and i think you may like this cool Website. now just Click Here