cyberspacial musings
bits about the real and virtual worlds

16 Feb

SHA-1 Broken

Bruce Schneier reports on his blog that SHA-1 has been broken as described in a paper by Chinese researchers Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Federal Information Processing Standard 180 (FIPS-180) describes SHA-1 in the following way:

Explanation: This Standard specifies a Secure Hash Algorithm, SHA-1, for computing a condensed representation of a message or a data file. When a message of any length

The SHA-1 is called secure because it is computationally infeasible to find a message which corresponds to a given message digest, or to find two different messages which produce the same message digest. Any change to a message in transit will, with very high probability, result in a different message digest, and the signature will fail to verify. SHA-1 is a technical revision of SHA (FIPS 180). A circular left shift operation has been added to the specifications in section 7, line b, page 9 of FIPS 180 and its equivalent in section 8, line c, page 10 of FIPS 180. This revision improves the security provided by this standard. The SHA-1 is based on principles similar to those used by Professor Ronald L. Rivest of MIT when designing the MD4 message digest algorithm (“The MD4 Message Digest Algorithm,” Advances in Cryptology – CRYPTO ’90 Proceedings, Springer-Verlag, 1991, pp. 303-311), and is closely modelled after that algorithm.

The general conclusion of this paper is that collisions can be found after 2^69 hash operations, instead of the brute force 2^80. A collision is where two given messages are found to produce the same result. This effectively means that 2^11 fewer operations are required to produce a collision. Computationally, this means that if it took a week to compute 2^69 hash operations before a collision, it would have taken 2048 weeks to compute 2^80 hash operations before, which is about 39 years. That’s a pretty significant reduction in the amount of time necessary to break a hash. Now it still takes a long time to compute a hash and 2^69 of them is a huge amount, but as Moore’s law continues to give us faster processors, a 2^11 reduction in operations is very, very important. It effectively renders SHA-1 useless for the long-term, and maybe even for the short term.

Leave a Reply

cyberspacial musings is is proudly powered by Wordpress and the Magellan Theme

Contact me at <jeff@jeffreykay.com> if you'd like to comment on this site.


All content on this site copyright © 2002-2009 by Jeffrey Kay. All Rights Reserved. Other trademarks are the properties of their respective owners. All views and opinions contained in the columns, interviews, or other articles on this site are solely the opinion of the writer.