Crack in SHA-1 code 'stuns' Security Gurus

Three chinese researchers said on February 14, 2005 that they have compromised the SHA-1 hashing algorithm at the core of many of today's mainstream security products.

In the wake of the news, some cryptographers called for an accelerated transition to more robust algorithms and a fundamental rethinking of the underlying hashing techiques.

"We've lost our safety margin, and we are on the edge," said William Burr, who manages the security technology group at the National Institute of Standards and Technology (NIST).

"This will create big waves, in my opinion," said the celebrated cryptographer and co-inventor of SHA-1 (Shamir hashing Alg.), Adi Shamir. "This break of SHA-1 is stunning," concurred Ronald Rivers, a professor at MIT who co-developed the RSA with Shamir.

RSA is a public-key cryptosystem for both encryption and authentication; it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman [RSA78]. Details on the algorithm can be found in various places. RSA is combined with the SHA1 hashing function to sign a message in this signature suite. It must be infeasible for anyone to either find a message that hashes to a given value or to find two messages that hash to the same value. If either were feasible, an intruder could attach a false message onto Alice's signature. The hash functions SHA1 has been designed specifically to have the property that finding a match is infeasible, and is therefore considered suitable for use in this role.

One or more certificates may accompany a digital signature. A certificate is a signed document that binds the public key to the identity of a party. Its purpose is to prevent someone from impersonating someone else. If a certificate is present, the recipient (or a third party) can check that the public key belongs to a named party, assuming the certifier's public key is itself trusted. These certificates can be held in the Attribution Information section of the DSig 1.0 Signature Block Extension and thus passed along with the signature to aid in validating it. (See section Attribution Information section in the DSig 1.0 Specification.)

The signature section of the DSig 1.0 Signature Block Extension is defined in the DSig 1.0 Specification. For the RSA-SHA1 signature suite, the signature section has the following required and optional fields.

Who are these three chinese researchers? One of the member, Lisa Yin was a Ph.D student who studied under Ronald Rivest (RSA inventor) at MIT. Another one was responsible for cracking the earlier MD5 hashing algorithm (also developed by Rivest in 1991) which happened in August 2004.

To learn more about MD5, please visit http://en.wikipedia.org/wiki/MD5. For RSA: http://en.wikipedia.org/wiki/RSA, and for SHA-1: http://en.wikipedia.org/wiki/SHA-1

The open-source code version of the algorithm can be found in http://www.cr0.net:8040/code/crypto/sha1/. Samir et.al published their paper at ACM forum: The RSA Encryption Algorithm, R.L. Rivest, A. Shamir, L.M. Adleman, "A method of Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, v. 21, n. 2, Feb. 1978, pp 120-126.