May 28, 2009

Timing attack in Google Keyczar library

Filed under: Crypto,Hacking,Network,Protocols,python,Security — Nate Lawson @ 11:30 pm

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:


    return self.Sign(msg) == sig_bytes


    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.

May 20, 2009

Amazon web services signature vulnerability

Filed under: Crypto,Network,Security — Nate Lawson @ 6:00 am

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:


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.

May 17, 2009

The Debian PGP disaster that almost was

Filed under: Crypto,Hacking,Network,Protocols,Security — Nate Lawson @ 5:23 pm

A year ago, I wrote about the Debian OpenSSL PRNG bug that reduced the entropy of its random seed to 15 bits. There was a little-noticed part of the advisory that said all DSA keys used on the affected systems should be considered compromised. In the rush to find and replace SSL certs and SSH keys generated on Debian or Ubuntu systems, very few people grasped the significance of this other warning. This is important because an attacker can retroactively seek out DSA signatures generated during the vulnerable period and use them to recover your private key.

DSA is a public-key signature algorithm. Unlike RSA, it isn’t useful for encryption or key exchange. Like other public key algorithms, it is extremely sensitive to the choice of parameters. I’ve written about RSA signature flaws (1, 2, 3) that resulted from too much ambiguity in how a signature verify operation was interpreted.

With DSA, the entropy of the random signature value k is critical. It is so critical that knowledge of only a few bits of k can reveal your entire private key to an attacker. Interestingly enough, the Wikipedia article on DSA doesn’t mention this concern. This is why it’s so important to get your crypto reviewed by an expert. Small, obscure flaws can cause immense damage.

To generate a DSA signature, the signer calculates (r, s) as follows:

r = gk mod p mod q
s = k-1 (H(m) + x*r) mod q

The message to be signed is m, H(m) is the SHA hash function, and p and q are primes. The value k is a random nonce and x is the signer’s private key. If an attacker knows k and has a single signature (r, s), he can recover the signer’s private key with a simple calculation. In the case of the vulnerable PRNG, he can just repeat this process for all 32,767 possible values. Remember that the message m is not secret, so neither is the SHA-1 hash H(m). The attacker calculates x as follows:

x = ((s * k) – H(m)) * r-1 mod q

The impact of this attack is that every signature generated on a vulnerable system reveals the signer’s private key. An attacker can find old signatures by crawling your website, examining signed email, analyzing saved packet captures of an SSL exchange, etc. The associated DSA key has to be revoked, regenerated and redistributed. Luckily for Debian, their packages are signed using GnuPG, which did not use the OpenSSL PRNG. But for anyone using other software based on OpenSSL, you need to revoke all DSA keys used to sign data on vulnerable Debian or Ubuntu systems. Even if the key was generated securely, a single insecure signature reveals the entire private key. It’s that bad.

I hope a year has been enough time for people to revoke their DSA keys, even though the warning was somewhat obscure. Thanks to Peter Pearson for interesting discussions about this issue.

May 15, 2009

Next Baysec: May 21st at Kate O’Briens

Filed under: Security — Nate Lawson @ 11:49 am

The next Baysec meeting is Thursday, May 21st at Kate O’Briens. Come out and meet fellow security people from all over the Bay Area. As always, this is not a sponsored meeting, there is no agenda or speakers, and no RSVP is needed.

See you Thursday, May 21st, 7-11 pm. We’ll be towards the back.

Kate O’Briens
579 Howard St. @ 2nd, San Francisco
(415) 882-7240

Blog at WordPress.com.