Eurocrypt 2009 was recently held from April 26-30 in Cologne, Germany. Sponsored by the International Association for Cryptologic Research (IACR), the website states that "It is devoted to all aspects of cryptology." This year's Eurocrypt rump session was held on April 28, which featured a talk entitled "Automatic Differential Path Searching for SHA-1". Authored by researchers at Macquarie University in Sydney, Australia, their work reveals a collision attack on SHA-1 with a complexity of 252 operations (the previous fastest known SHA-1 collision attack had required 263 operations). This is a significant improvement in finding SHA-1 collisions.
Hash Function Attacks:
A cryptographic hash function is an algorithm that takes a message as an input and computes a fixed-size digest. SHA-1 generates 160-bit digests. The generated digest is used for a variety of applications related to information security, information assurance, and digital trust relationships. When designing new algorithms, designers of cryptographic hash functions aim to fulfill three basic properties:
- Pre-image Resistance:
Given a hash digest, it is difficult to find any message that will hash to the specified digest value. - Second Pre-image Resistance:
Given a message, it is difficult to find a different message that hashes to the same digest value as the original message. - Collision Resistance:
It is difficult to find any two unique messages that hash to the same digest value.
In this case, the SHA-1 attacks affect collision resistance, not pre-image or second pre-image resistance. This means that after 252 operations, the researchers are able to generate two unique messages that hash to the same digest value. Obtaining a SHA-1 collision via brute force would require 280 operations. To date, it remains computationally infeasible to perform pre-image and second pre-image attacks on SHA-1. At the time of writing, I am unaware of a practical collision that has been found.
One iteration of the SHA-1 function:
Until recently, SHA-1 was widely regarded as the standard in cryptographic hash functions, and remains widely used in a variety crypto systems and as a normative reference in other RFCs and standards. The transition to the stronger SHA-2 functions presents the potential for interoperability issues, as SHA-2 signatures generated by updated systems may be unsupported by older systems. Adoption of the stronger hash functions must be carefully planned in order to reduce disruption to critical business functions.
The Digital Signature Algorithm (DSA) is an example of an important standard that relies in part on SHA-1. It specifies the use of a 160-bit hash function for the signatures used in 1024-bit DSA keys. The SHA-1 algorithm is nearly always the one used to sign these 1024-bit DSA keys. In order to eliminate reliance on SHA-1, users of 1024-bit DSA keys will need to transition to 2048-bit or larger DSA keys.
The OpenPGP Message Format (RFC 4880) also presents a challenge to the transition away from SHA-1. Section 13.3.2 states that SHA-1 is "the MUST-implement algorithm," and that even "if it is not explicitly in the list [of hash functions configured to be supported], it is tacitly at the end. However, it is good form to place it there explicitly." The GNU Privacy Guard (GnuPG) gnupg command-line tool will automatically re-enable SHA-1 if you removed it from a key's list of supported hash functions, visibly adding it to the end of the list just as suggested in RFC 4880. On the bright side, both GnuPG and the proprietary PGP have supported SHA-256 for well over 5 years now, making inter-operability during the transition must less of an issue for users of those popular implementations.
The OpenPGP Web of Trust (WOT) is almost exclusively made up of SHA-1 signatures. Abandoning SHA-1 signatures today would immediately "evaporate" the Web of Trust. Because of the decentralized nature of the WOT, transitioning off SHA-1 will require a collective and distributed effort on the part of WOT users. There is much work to be done to eliminate reliance on the SHA-1 hash function.
The Debian Project uses OpenPGP and the WOT extensively, and has begun the process of transitioning Debian Developers and Debian Maintainers onto stronger crypto algorithms. That link contains some valuable guidance on making the switch as non-disruptive as practicable. Debian's transition might well serve as an example for other organizations they rely heavily PGP-based cryptgraphic infrastructure.
A centralized, Certificate Authority (CA) based chain-of-trust Public Key Infrastructure (PKI) forms the basis for SSL/TLS authentication, and with that, the trust needed for secure use of the Web. Such a system offers a different set of challenges for a transition to the SHA-2 familiy of hash functions. CAs will need to recreate their intermediate chains-of-trust using SHA-2 signatures and make plans to revoke their SHA-1 signed certificate chain. (Will someone please explain to me how you revoke a root CA certificate?). Users and system administrators with certificates signed using SHA-1 will need to be issued SHA-2 replacements, or more likely will receive a new SHA-2 certificate when they go to renew their certificate with a CA. OS and web browser makers will need to build in support for SHA-2 hash functions if they have not already, and update their lists of trusted root CAs. And of course, users will need to update their OSes and web browsers to support SHA-2 and to receive the updated lists of trusted root CAs.
Every actor has a role to play: end users, organizations, software makers, Certificate Authorities, standards bodies, and of course let's not forget the system administrators.