Category: Hacking

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.

The Debian PGP disaster that almost was

~ Nate Lawson ~ 3 Comments

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.

Forged CA cert talk at 25C3

~ Nate Lawson ~ 3 Comments

A talk entitled “MD5 considered harmful today” (slides) is being presented at 25C3. The authors describe forging a CA cert that will be accepted by all browsers by exploiting the fact that several trusted root CAs sign certs with MD5. This allows them to spoof their identity as any SSL-enabled website on the Internet, and it will look perfectly valid to the user.

The growth of trusted root CAs included in standard browsers has been an issue for a while. Every root CA is equal in the eyes of the browser, thus the end-user’s security is equivalent to the security of the weakest root CA. The default Firefox install will accept a Yahoo cert signed by “TurkTrust”, or any other of more than 100 root certs. I don’t know how good each of those companies are at securing their keys, implementing strict cert chain validation, and checking the identity of every submitter. So, it’s a good bet that putting crypto authority in the hands of that many people will result in some failures, repeatedly.

The attack is interesting since they take advantage of more than one flaw in a CA. First, they find a CA that still uses MD5 for signing certs. MD5 has been broken for years, and no CA should have been doing this. Next, they prepared an innocent-looking cert request containing the “magic values” necessary to cause an MD5 collision. They were able to do this because of a second flaw. The CA in question used an incrementing serial number instead of a random one. Since the serial is part of the signed data, it is a cheap way to get some randomness. This would have thwarted this particular attack until a pre-image vulnerability was found in MD5. Don’t count on this for security! MD4 fell to a second pre-image attack a few years after the first collision attacks, and attacks only get better over time.

This talk definitely points out that crypto attacks are not being addressed quickly enough in the real world. While it is difficult to roll out a new root CA cert, it’s better to do so over the years we have known MD5 to be insecure than in a rush after an attack has already occurred. Another excellent talk at 25C3 on the iPhone described how the baseband processor was compromised via the lack of validation of RSA signature padding. What’s intriguing is that Apple’s own RSA implementation in their CDSA code was not vulnerable to this flaw, but apparently a different vendor supplied the baseband code.

To paraphrase Gibson, “Crypto security is available already, it just isn’t equally distributed.”

Xbox 360 security talk

~ Nate Lawson

This recent video of Michael Steil and Felix Domke talking about the Xbox 360 security scheme is the best overview I’ve seen so far.

Michael previously gave a nice talk summarizing the security flaws in the original Xbox.

The CPU itself supports hashing and/or encryption of physical pages, based on flags set in the upper word of the 64-bit virtual address.  They talk about how Felix was able to leapfrog off shader-based DMA to write to an unencrypted register save state structure, jumping through a syscall gate (sorta like return-to-libc) that was improperly validated by the hypervisor.  The end result was arbitrary code execution in the context of the hypervisor.  Quite impressive.

I’ve always wondered how different security features like encrypted RAM that have long been present in smart cards would take to “trickle-up” to the more complex platforms like game consoles.  While the Xbox 360 security is much better than the original Xbox, it seems like the big-systems people are reinventing techniques already tested and worked out in the microcontroller world.

For example, the 360 was vulnerable to a timing attack, where an internal secret key can be guessed by timing how long it takes to validate the submitter’s HMAC.  I’d be extremely surprised if any mainstream smart card were vulnerable to such a well-known legacy bug.

I have yet to see anyone publish information about applying power or RF-based side channel analysis to a game console, despite smart cards adding countermeasures to these almost 10 years ago.  Even earlier attacks on encrypted RAM have still not been attempted on modern systems.

These attacks probably haven’t been needed yet since software bugs were still present. However, the push by game consoles and cellphone manufacturers to increase their resistance to software attacks means it won’t be long before side-channel resistance becomes a must-have feature.  It will be interesting to see how long it takes big-system manufacturers to add countermeasures and whether they’ll choose to learn from the hard lessons we have seen in the smart card world.

What probably happened with Mythbusters and RFID

~ Nate Lawson

People seem to be upset at the potential censorship Mythbusters’ Adam Savage described when he said industry lawyers prevented him from creating an episode about security problems with RFID.  Now new accounts are being released both by TI and Adam indicating the situation wasn’t so coercive.

According to a TI spokesperson, this all began when:

“To move the process along, Texas Instruments coordinated a conversation with Smart Card Alliance (SCA) who invited MasterCard and Visa, on contactless payments to help MythBusters get the right information.”

And, instead of an army of credit card company lawyers, TI claims that:

“Of the handful of people on the call, there were mostly product managers and only one contactless payment company’s legal counsel member.”

Since I’ve developed for smart cards before and attended an SCA event, I can give more background information on the players involved.  I doubt anything sinister happened, and Mythbusters’ status as an outsider probably contributed to the misunderstanding.

There may be hundreds of different types of system covered by the name “RFID”, so when Mythbusters contacted TI, it’s likely they hadn’t identified exactly what they wanted to talk about.  Given the references to “contactless payment” in TI’s statement, they’re probably talking about ISO 14443 contactless smart cards.  However, there are numerous other implementations of “contactless payment”, for example, the proprietary (and broken) SpeedPass system.

Once they had narrowed down the discussion, it still would not have been clear which payment application Mythbusters would examine.  This is because ISO 14443 merely specifies the communication protocol and modulation, not how to talk to an application to perform credits, debits, etc.  This is probably what the spokesperson was referring to when he said:

“Some of the information that was needed to pursue the program required further support from the contactless payment companies as they construct their own proprietary systems for security to protect their customers.”

The most common application standard is EMV.  It describes a standard between readers and cards to perform payment transactions on top of the underlying wire protocol, whether it is contactless or not.  There are other payment applications supported on a single card.  EMV does describe cryptographic security (encryption and signatures) to authenticate the transactions, say, to prevent unauthorized debits.

But there may be more here when the spokesperson said “proprietary systems for security”.  Depending on the direction Mythbusters took, he could also be talking about attempts to prevent side-channel (DPA) or physical attacks (glitching, probing).  Those are usually very specific to a given implemenation of a device.  It would be interesting to see if Mythbusters was really that skilled to consider attempting those kinds of attacks.

The other interesting thing to note is the presence of product managers on the call.  Most of the time, a product manager can’t answer really technical questions about protocols, interfacing, etc.  Their job is a marketing role — to explain the features of the product in the most appealing light.  A product manager wouldn’t know how to help someone attack their system (nor would they want to), however they would be good at extolling the many great security features their product has.

So while Mythbusters was probably not threatened by the industry, they were definitely being provided a very RFID-positive perspective.  That’s obvious and what any company would do in the same situation.

The biggest question that remains is what exactly did Mythbusters hope to show?  Did they have some outside expert lined up to do the actual work?  If not, why did they start by asking the parties least motivated to help them?

[Update: I think the episode Mythbusters did air about RFID is this one.  They test that an implantable RFID chip does not heat up or explode when present during an MRI.  At the end, they hint that they might investigate payment systems (a quite different type of RFID), but dismiss that plan.]

Hacker or hooker?

~ Nate Lawson ~ 5 Comments

Well-funded and motivated attackers are typically the hardest to defend against when designing a system.  Governments can attack systems in different ways and with more resources than a typical threat.  Consider a recent example where a British aide lost his Blackberry after spending the night with a woman who approached him in a Chinese disco.  While it’s possible he just lost it while drunk, this is a good example of how unconventional threats need to be carefully considered.

Let’s analyze the cost of two routes to getting this same information: hacker or hooker.  The hacker might try to crack passwords or develop a 0-day exploit against the Blackberry server.  Or, build a custom trojan and send it via a forged email that appears to come from the Prime Minister.  The hooker would try to get to his hotel room and steal the phone.  It would actually suffice to just borrow it for a few minutes and dump the RAM since passwords are often cached there.  This has the added advantage that he might never know anything had happened.

A 0-day exploit could be in the $20,000 range.  Hiring someone to develop and target a trojan at this aide would be less, but the chance of succeeding would be lower.  According to the stories about Eliot Spitzer, a high-end call girl is $1,500 per hour.  Assuming it takes four hours, the total cost would be $6,000.  The fact that both these approaches could be done in China means the actual cost would be lower but probably still a similar ratio.

There are a lot of other advantages to the hooker approach besides cost.  There is good deniability if the call girl gets caught.  Since the call girl remains within the attacking country’s jurisdiction, the police can be used to recover the Blackberry if she makes an extortion attempt.  The hacker approach has a lot more uncertainty as flaws could be patched or blocked, making the exploit useless.

I also think this gives good support to my claim that software protection techniques are on the verge of wider adoption.  With cold boot attacks and growing news of governments seizing laptops or stealing cell phones, systems must remain secure even when an attacker has physical possession of a powered-up device.  The only way to do this is to adopt software and hardware techniques that are already used to protect games, DRM, and satellite TV.  Traditional approaches like those used in network security are no longer enough.

I’ll be speaking on this topic along with Thomas Ptacek at WOOT, co-hosted at USENIX on July 28th in San Jose.  Since this event is invite-only, send me email if you’re a security researcher who would like to attend.  Please include a brief summary of your background.