[e-privacy] Crypto researchers break SHA-1

[info at dataprotection.it]

Segnalo un' altro articolo apparso su The Register circa la " rottura " di
SHA-1 (information from
:http://www.theregister.co.uk/2005/02/17/sha1_hashing_broken/ )

Crypto researchers break SHA-1
By Thomas C Greene in Washington
Published Thursday 17th February 2005 11:04 GMT
Long rumored and now official, the popular SHA-1 hashing algorithm has been
attacked successfully by researchers in China and the US. A collision has
been discovered in the full version in 269 hash operations, making it just
possible to mount a successful brute-force attack with the most powerful
machines available today.

This is by no means a disaster in practical terms, as the amount of
computational power and mathematical insight needed to perform a successful
attack is still great. But SHA-1 has been demonstrated not to be beyond the
reach of current supercomputers, as had previously been believed, or at
least hoped. Theoretically, 280 operations should be necessary to find a
collision.

By using reduced-round versions of the algorithm, and the team's technique,
it was possible to attack SHA-1 in fewer than 233 operations. Using the same
technique, the full SHA-0 could be attacked in 239 operations.

SHA-1 is regarded as more secure than MD5, in which collisions were found
last year by some of the people who reported the recent discovery. Also last
year, collisions were found in SHA-0 by a French team.

The researchers in the latest effort, Xiaoyun Wang and Hongbo Yu from
Shandong University and Yiqun Lisa Yin from Princeton University, have
released a paper briefly outlining their findings. The technical details
will be released in the near future. Wang and Yu were part of the team that
discovered the weakness in MD5.

Hashing is a one-way cryptographic function. It differs from encryption in
that the original input creating the hash should not be recoverable under
any circumstances, whereas in encryption, the original input is meant to be
recovered, albeit under tightly controlled circumstances. Hashing is used in
many applications, from passwords and other authentication schemes, to
digital signatures and certificates, to creating checksums used to validate
files.

Ideally, no two inputs would create the same hash. However, in the real
world this inevitably happens, and when it does, it's called a collision.
Finding a collision is a matter of brute-force hashing until two different
inputs are found to create the same output. This could, with considerable
effort, be used to forge certificates and signatures.

Still, in practical terms, things are not as bad as they might seem.
Collisions are irrelevant in a number of crypto implementations, and in
those where they are relevant, the trick is to keep them ahead of the
practical computing resources required to find them. The chief consequence
of these discoveries is that there is now a degree of uncertainty about
whether a digital signature, say, is authentic, because it is not impossible
for a duplicate to be created. But it's also not likely to happen, either,
at least with current technology. Indeed, collisions notwithstanding, the
algorithm remains the strongest element of most crypto implementations. It
would be wise to approach any encryption or hashing scheme as a fine boost
in security that can never be trusted one hundred per cent. Which is exactly
how every security scheme should be approached.

The US National Institute of Standards and Technology (NIST) has recently
begun recommending that government phase out SHA-1 in favor of SHA-256 and
SHA-512.

NIST security technology group manager William Burr was recently quoted in
Federal Computer Week saying that, "SHA-1 is not broken, and there is not
much reason to suspect that it will be soon."

NIST had been recommending that SHA-1 be phased out by 2010. It looks as if
that date will have to be tweaked just a bit. R


Alessandro