SHA-1 and XMLDSIG: No Plan B?

People in the know are reporting that the 160-bit Secure Hash Algorithm has been broken by a group in China. When the group's paper is published we'll all be able to judge, but the initial reports indicate that SHA-1 has about 11 bits worth (2000 times) less collision resistance than its output length would suggest. This isn't a huge surprise; there were some indications last year that this might happen eventually although I don't think anyone expected things to move so quickly.

The break is a big deal for academic cryptographers, but it doesn't seem to represent an immediate disaster in practice. Existing digital signatures and certificates are probably safe for now, in particular, as the kind of attacks you can mount against a system using collisions mainly apply to new signatures. The revised 69-bit strength of SHA-1 is still good today against all but fairly wealthy adversaries; Bruce Schneier has some estimates of how rich.

Obviously, there will now be a move towards beefier hash algorithms like SHA-256 or SHA-512 (PDF link). In the long run, because these come from the same family they may turn out to give only temporary respite. More immediately, they aren't implemented by all current cryptographic libraries: for example, they have been in Java since 1.4 but the extremely popular OpenSSL package doesn't ship with support for them yet.

Further up the stack, many standards already allow for selectable algorithms and for negotiated selection of them at run time. That's harder to do with digital signature applications, because in this kind of context there isn't normally a way to negotiate algorithms. This means, for example, that public suppliers of digital certificates probably won't be able to shift from SHA-1 very soon, as many of the systems that use their certificates (browsers, for example) are based on cryptographic libraries that don't support anything stronger than SHA-1 today.

One place where there seems to be a complete absence of a "Plan B" at present is the joint IETF/W3C standard for digital signatures in XML (XMLDSIG). The published standard from 2002 (also RFC3275) only discusses SHA-1. Moving away from this position requires several steps:

  • Implementation of additional algorithms in the basic cryptographic libraries such as OpenSSL (already true for some libraries, OpenSSL has code checked in but not released). [20050421: OpenSSL change log indicates this is scheduled for the 0.9.8 release.]
  • A specification of URIs naming additional algorithms for XMLDSIG (Don Eastlake has an Internet Draft on this dating from last year.) [20050421: this is now RFC4051.]
  • Access to those algorithms from XMLDSIG implementations, such as Apache XML Security.
  • Either:
    • Some sort of standard specifying that XMLDSIG implementations should implement additional algorithms, or
    • A similar kind of must-implement agreement even higher in the stack, in my area of interest either at the level of SAML or Shibboleth.
  • Last but not least: everyone installs new versions of all of the above.

None of this sounds like it is going to happen overnight. It is important that it all happens some time soon, though, as the general feeling seems to be that it is likely that further progress will be made against SHA-1; it is just the timing that is unknown.

[Last updated 20050421: OpenSSL status, RFC4051.]