Category: Crypto

XMLDsig welcomes all signatures

~ Nate Lawson ~ 6 Comments

There’s a new flaw in the W3C XMLDsig standard, found by Thomas Roessler. This standard specifies the procedure for signing and validating XML data, such as for SOAP. The document is validated with HMAC; however, an additional parameter can be supplied, <HMACOutputLength>. This allows the signer to use a truncated HMAC.

As you may remember, an HMAC is a way of validating data by using a secret key and a cryptographic hash algorithm. I avoid using the term “keyed hash” as that leads to bad implementations like “HASH(key || data)”. The output of an HMAC is the size of the hash algorithm, say 160 bits for SHA-1. This value is sometimes truncated in space-constrained designs. For example, only the first 128 bits might be sent and verified. This is sometimes acceptable because circumventing an HMAC requires a second-preimage attack (2n), unlike forging a signature which only requires a collision (2n/2).

The problem is that there is no specified lower bound on <HMACOutputLength>. So this is a perfectly valid signature field in XMLDsig:

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

Yes, an attacker can send any request and any signature and it will be accepted if the server follows the field blindly and validates only 0 bits. Even a server that checked for 0 might allow a truncated length of 1 bit or 8 bits or whatever.

According to the advisory, it has taken 6 months to release this simple spec erratum. This is because it affected so many vendors. This is a great example how a little leniency in crypto can have a huge impact on security.

Also, I’m not certain this bug is actually fixed. For example, I see that the algorithm can be specified by the same field. So could an attacker specify a broken algorithm like MD4, which has a second-preimage attack? If the server’s crypto library just maps the given Algorithm field to a hash function, this might be possible.

The spec says:

Requirements are specified over implementation, not over requirements for signature use. Furthermore, the mechanism is extensible; alternative algorithms may be used by signature applications.

So it’s not clear whether or not this is a problem, although ambiguity in crypto is one of the biggest sources of flaws.

The most annoying thing about this entire vulnerability is why were truncated HMACs even included in the standard at all? This is XML we’re talking about, not some packed binary protocol. The difference between full HMAC-SHA1 and the new minimum allowed truncated value is 10 bytes (plus base64 encoding expansion). You’re telling me that it’s worth exposing all your implementers to this kind of crypto risk to save 10 bytes? Really?

NaCl: DJB’s new crypto library

~ Nate Lawson ~ 8 Comments

NaCl is a new crypto library, courtesy of Dan Bernstein of qmail fame and Tanja Lange. After my series of posts on why crypto libraries have seriously hurt web security by offering an API that is too low-level, I was pleased to find NaCl’s main interface is high-level. In addition to the kind of fanatical attention to security you can expect from DJB, it also has his unique (some would say quirky) viewpoint.

On a related note, I’m sorry to say I have to withdraw my recommendation of Google Keyczar. It has had another vulnerability announced, this time in the random source for the python library. This is exactly the same attack against DSA I described previously. I may reconsider this decision as it matures.

There’s a lot Keyczar gets right. Its high-level API and key management make a lot of sense. Up until recently, there haven’t been many high-level libraries I could recommend. Gutmann’s cryptlib is probably the best one. It has been around a while and is implemented in C with multiple language bindings. It is covered by the Sleepycat license, so it works like the GPL or you can pay for closed-source use. GPGME provides well-reviewed crypto with the simple PGP usage model. However, it only offers a C API. It also works by forking the command-line gpg underneath, something that may bother some developers. It is covered by the LGPL license.

While cryptlib and GPGME have been around a while, I have not personally reviewed either of them and can’t vouch for their implementation security. When I found the timing attack in Keyczar’s HMAC verification, I took a brief look around. It seemed ok overall, but I did not do a thorough review. I was so glad to see another high-level library that I included Keyczar along with cryptlib and GPGME as a good alternative to implementing your own crypto in a recent talk. I should have emphasized that while these libraries are taking the right approach, we need much more thorough reviews by cryptographers before standardizing on them. Keyczar, as the newest library of those three, deserved a note that it especially needed review.

NaCl is the latest entry on the scene and it shows a lot of promise. Take a moment to read its design features. The code is public domain. It offers a set of high-level functions such as:

There are some good things to be excited about here. The design is extremely high-speed, although that isn’t my personal priority. The high-level APIs are good but not perfect. For example, the caller is expected to specify a nonce and set certain bytes to zero for crypto_box. This is a little too much control for a high-level API. It might be better if NaCl created its own nonce using its PRNG (/dev/urandom, actually), and then focused on making sure it was seeded well.

The design and implementation security, as expected for DJB, is excellent. (Note that I have not done a thorough review and thus cannot yet recommend it.) For example, he focuses on side channel resistance, creating a non-branching scalar multiplication routine and an API for comparing secrets that resists timing attacks. Also, his design choice of using ECDH, a stream cipher, and a MAC algorithm to implement crypto_box fit together well.

However, that’s where the quirkiness comes in. As with qmail, DJB has a really unique way of doing things. The default ECDH implementation uses Curve25519, the stream cipher is Salsa20, and the authenticator is Poly1305. All of these are primitives designed by DJB in the past four years. If it wasn’t DJB, you’d think I was crazy to even consider a library that implements all new ciphers and constructions. Even though I respect him and these may turn out to be good choices, four years is not enough time to review all of these to be certain they are sound. This will limit NaCl’s appeal until more standard ciphers are available.

While NaCl is a good start, here’s what is missing before it can be more widely adopted:

  • Language bindings: NaCl is C-only for now and needs at least Java, python, and C# bindings
  • More standard crypto primitives: NIST P-256 or other curves, AES, and SHA2-HMAC
  • Signature API: ability to do public-key signatures

Since all these items are marked TODO, it’s clear that Dan recognizes the need for them as well. Perhaps NaCl will mature into the library of choice in the future. If you’re a cryptographer and have a chance to review it, please publish your findings. If you’re a developer, how about contributing language bindings?

On a side note, I’m convinced that the right way to create a crypto library is to do a single implementation in C with architecture awareness (e.g., cache layout, some assembly language) and then offer language bindings. This is the route NaCl and cryptlib took. It’s nearly impossible to prevent side channel attacks when your crypto is implemented in a high-level language.

When Crypto Attacks! slides posted

~ Nate Lawson ~ 8 Comments

I have now posted slides for the talk I gave yesterday at Yahoo Security Week (see below). I also took this opportunity to upload the previous talks I have given since 2004 to Slideshare.

The talk was mostly an in-depth list of attacks against various crypto implementations. The good news is that developers seem to have gotten the message not to design their own ciphers. Now, we’re trying to get the message out that you shouldn’t be implementing your own crypto protocols or constructions, using low-level crypto libraries.

Instead, developers should work at a higher level, using libraries like GPGME, Keyczar, or cryptlib. You wouldn’t write a web application in assembly language. Why take the risk of implementing your own crypto constructions?

If you do end up designing/implementing your own construction, it is really important to get it reviewed by a third party. Since it can be expensive and time-consuming to gain assurance, it’s better in nearly all cases to use a high-level library. The alternative is a potential root key compromise. Are you willing to take that chance?

Web crypto talk at Yahoo Security Week

~ Nate Lawson

On June 9, I’ll be giving a talk on web crypto flaws at Yahoo Security Week. The talk is titled “When Crypto Attacks!” and will go into ways cryptography has been misapplied to solving web application problems. You can get a flavor for the talk by reviewing these recent posts.

I also wanted to mention another high-level API that is pretty good: Peter Gutmann’s cryptlib. It provides a simple API with a lot of internal validation of parameters and state. For example, you can’t send messages in the wrong order and keys have types associated with them.

If you are a Yahoo employee, you can attend the talk. For everyone else, I will post slides here afterwards.

Timing attack in Google Keyczar library

~ Nate Lawson ~ 22 Comments

I recently found a security flaw in the Google Keyczar crypto library. The impact was that an attacker could forge signatures for data that was “signed” with the SHA-1 HMAC algorithm (the default algorithm).

Firstly, I’m really glad to see more high-level libraries being developed so that programmers don’t have to work directly with algorithms. Keyczar is definitely a step in the right direction. Thanks to all the people who developed it. Also, thanks to Stephen Weis for responding quickly to address this issue after I notified him (Python fix and Java fix).

The problem was that the HMAC verify function (Python src/keyczar/keys.py, Java src/org/keyczar/HmacKey.java) leaked timing information based on how long a verify operation took to fail. The function was defined as follows for the HMAC mode:

Python

    return self.Sign(msg) == sig_bytes

Java

    return Arrays.equals(hmac.doFinal(), sigBytes);

Since the return value is a SHA-1 hash string, the operation devolves to a byte-by-byte compare against sig_bytes. In both Python and Java, this is a classic sequence comparison that terminates early once an incorrect match is found. This allows an attacker to iteratively try various HMAC values and see how long it takes the server to respond. The longer it takes, the more characters he has correct.

It may be non-intuitive, but the symmetric nature of MACs means the correct MAC value for an arbitrary message is a secret on-par with key material. If the attacker knows the correct MAC for a message of his choosing, he can then send that value to forge authentication of the message to the server.

I’ve implemented a simple test server using the Python version of Keyczar. It verifies an HMAC and sends back “yes” or “no” if the value is correct. I then wrote a client in C that connects to the server and tries various values for the HMAC. It tries each value multiple times and records a set of TSC differences for each. These can be fed to a program like ministat to decide when a significant difference has been confirmed (based on mean and standard deviation).

I can confirm that localhost tests have a discernible difference, depending on whether each subsequent byte is correct. I have not optimized the attack to work over a LAN or the Internet yet. However, this does not mean remote attacks are infeasible. Where jitter and other noise is present in the samples, an attacker just needs to collect more data to average it out. Remote timing attacks on SSL have been demonstrated where the timing difference was only a few native multiplies.

I recommended changing the verify function to use a timing-independent compare, such as the following.

    correctMac = self.Sign(msg)
    if len(correctMac) != len(sig_bytes):
        return False
    result = 0
    for x, y in zip(correctMac, sig_bytes):
        result |= ord(x) ^ ord(y)
    return result == 0

This function is data-independent, except for revealing the total length of the correctMac string. Since this is not considered important to security, it is acceptable. Of course, this might not be true for another use of this same code, so it cannot be blindly used in other applications.

The lesson from this is that crypto flaws can be very subtle, especially when it comes to transitioning from an abstract concept (“compare”) to a concrete implementation (“loop while bytes are equal”). Keyczar was implemented by some smart people. If you’re a programmer, you should be using a high-level library like Keyczar or GPGME to take advantage of this knowledge. If you ignore this and develop your own design, it’s likely it would have many worse problems than this one. For those that have to build crypto, please get a third-party review of your design.

I consider it a failing of the crypto community that these libraries are still so new, while the past 20 years we’ve focused on providing raw algorithm APIs. But at least now we have a chance to build out a few important high-level libraries, review them carefully, and encourage application developers to use them. It’s not too late.

Amazon web services signature vulnerability

~ Nate Lawson ~ 17 Comments

Colin Percival announced an interesting bug back in December in howAmazon Web Services signs data. Amazon allows users of their APIs (e.g., EC2 and SimpleDB) to authenticate requests by applying an HMAC. This is supposed to ensure the request was unmodified after the sender created it; however, there was a subtle flaw that allowed an attacker to forge requests in certain circumstances.

An HMAC works by applying a cryptographic hash algorithm to the user’s data and a secret key. Another party who knows the same secret key can perform the same calculation. If the HMAC results match, the data has not been modified. The problem lies in the lack of structure Amazon applied to the data, resulting in exploitable ambiguity. You can see Colin’s advisory for more details about how this can be exploited. See also the function signParameters() in the client code, AmazonEC2Client.java, for all three versions of this function.

To prepare a URL to be authenticated in AWS-Signature v1, the API caller concatenates all the key/value pairs into a single string (key1 || value1 || key2 || value2). Then, the caller calculates the HMAC of this value and attaches it to the original API request as the “Signature=” key. The HMAC is supposed to authenticate this request, proving that the sender originated the request and that it had not been modified in transit.

It’s pretty obvious that this lack of structure results in an ambiguous interpretation. The HMACs of the following URLs are identical:

…?GoodKey1=GoodValue1BadKey2BadValue2
…?GoodKey1=GoodValue1&BadKey2=BadValue2

As long as the attacker can change the value of any tag in the request and observe the resulting HMAC, he can later add any number of bad keys and bad values and resubmit the request with the same HMAC. The fix in AWS-Signature v2 is to add back various delimiters between the key/value pairs before calculating the URL’s HMAC.

There’s a variant of this attack that even AWS-Signature v2 does not appear to address. If an attacker can observe a single signed request, that request can be resubmitted any number of times. Thus, an API call like “credit account $10” could be repeated any number of times. Of course, using SSL for the request would prevent this attack, and it’s likely that users would send most financially-related messages over SSL. However, given that this protocol is intended to be secure over plain HTTP, it’s possible some users trust it to ensure message uniqueness in addition to integrity protection.

I’ve observed this kind of flaw before in other systems, including specifications for single-sign-on cookies. Vendors that specify their own signature format should get a review of their design to be certain they strictly validate the structure for any values that they sign.