HMAC truncation in XML Signature: When Alice didn't look.

Today, we've published a proposed correction against XML Signature. Normally, errata are published without much ado, and largely cover minor points of specifications. This one's a bit different: You haven't seen any public discussion of this particular erratum before, and it comes with a CERT Vulnerability Note and a bunch of software updates from various vendors.

What has happened? In January, I was reviewing the algorithms section in XML Signature while working on the XML Security Working Group's Algorithms Cross-Reference draft. I read a certain paragraph. I read it twice. I grabbed a copy of the nearest open source implementation of the spec that I could find. I read some code. I built an example to play with. And then, I took up the phone. A week later, we spent some time on a Working Group call to talk things through, followed by a series of informal conference calls to understand how serious the problem was, and what to do when. Half a year later, a number of vendors are pushing patches to fix their versions of the hypothetical problem I had stumbled over.

The paragraph that struck me was about HMACs. An HMAC is a message authentication code that lets Alice determine that a message came from Bob, if Alice and Bob share some sort of secret. It is much faster to compute than a usual public key signature, and therefore popular for authenticating large amounts of data. There are some reasons (which don't matter here) why it can be desirable to truncate the output of the HMAC function; hence, XML Signature introduces a parameter that defines a truncation length.

Here is the text that struck me:

The HMAC algorithm (RFC2104...) takes the truncation length in bits as a parameter; if the parameter is not specified then all the bits of the hash are output. An example of an HMAC SignatureMethod element:

   <SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#hmac-sha1">
      <HMACOutputLength>128</HMACOutputLength>
   </SignatureMethod>

The output of the HMAC algorithm is ultimately the output (possibly truncated) of the chosen digest algorithm. This value shall be base64 encoded in the same straightforward fashion as the output of the digest algorithms.

Conventional wisdom is that you don't lose much in terms of security if you throw away up to half of the output. And that's where it gets interesting: XML Signature provides markup to send the truncation length along with the signature. But it doesn't say who has to worry about checking the truncation length.

Imagine Alice and Bob agree on a secret, and imagine that Alice will accept that a message comes from Bob if it's signed with an HMAC using that secret. They use XML Signature to encode the signatures. Enter Mallory: She doesn't know the secret, but she has a message that she wants to send to Alice, claiming that it comes from Bob. Guessing the right HMAC value is basically impossible when the output of the HMAC function is a string of 160 bits. But what if Mallory could convince Alice to throw away 152 of the 160 bits? Suddenly, she has a chance of 1 in 256 of guessing the right signature value. Or what if Mallory could convince Alice to throw away all of the 160 bits? There's only one signature value that's possible, regardless of the message and the key. Now, if Alice has a careful look at the messages she receives, she will surely notice when Mallory's message tells her to throw most of the signature away.

But what if Alice doesn't look?

That's precisely what has happened here: A naive implementation of XML Signature simply accepts an HMAC-based signature, including the truncation length parameter, looks at the number of bits it's been told to look at, and reports back whether the signature was good or bad. It doesn't do any other check of the output length, or report it back, or ask the calling code for a minimum (while, perhaps, setting a sane default).

Now, strictly speaking, the specification isn't even wrong. It does, however, leave a critical decision to "somebody else", without saying so. It turns out that the HMAC specification itself warns about too short output lengths -- and, indeed, we know of one implementation that got this right from the beginning. Others had simply not cared to implement this particular feature. But many (see the CERT vulnerability note for details) had implemented the feature, and then forgotten about it -- from all we know, the output length parameter is hardly, if ever, used with XML Signature.

Likewise, some specifications that refer to XML Signature come close to dealing with the issue, but ultimately don't: The WS-I basic security profile forbids sending the truncation length parameter -- but it doesn't keep implementations from accepting it. WS-SecurityPolicy has information about minimum key lengths for HMACs -- but none about minimum output lengths.

If there is a security critical parameter in a specification, then, at the very least, that needs to be said clearly and loudly. In this case, we're going one step further: The proposed correction that was published today adopts the limits recommended by RFC 2104 and tells implementers to consider signatures as invalid whose truncation length falls below these limits.

Why did it take half a year?

Releases across a possibly significant number of vendors had to be coordinated. Today was the earliest date everyone could agree on. At the same time, it didn't look like services exposed to the Internet would be adversely affected by the delay.

A number of people helped with dealing with this situation: Hal Lockhart was instrumental in helping to understand the implications in the Web Services space. Frederick Hirsch made time available during XML Security Working Group calls. Will Dormann at CERT helped to coordinate vendor responses during the last few weeks.

How do I know if my software is affected?

Probably not. It turns out that the affected feature in XML Signature is used less frequently than we had at first thought. If you use Web Services in a way that relies on the HMAC feature in XML Signature, then you might want to make sure that you're using the latest release of your toolkit. The same holds if you've built your own protocols and toolkits on top of XML Signature. See the CERT vulnerability note for details. (Please understand that we won't discuss individual implementations here.)

Does this affect other protocols?

We are not aware of any.