Nate Lawson Breaks Google Keyczar's HMAC Crypto Signatures

http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/

by tptacek • 17 years ago

62 24 17 years ago

rdist.root.org

tptacek7• 17 years ago

Smart Google people worked really hard to get this right. But they used the wrong comparison function --- one that leaked timing information --- and so attackers could forge messages.

Atwood really thinks we should be trying to educate developers about how to build crypto?

codahale• 17 years ago

Atwood thought cryptography was easy and screwed it up. Then he thought teaching people about cryptography was easy and screwed it up.

I, for one, am terrified by what the third derivative of his ignorance might be.

cperciva2• 17 years ago

This is an incredibly dumb bug -- while Nate claims that "The lesson from this is that crypto flaws can be very subtle", this isn't really a subtle or novel flaw from a cryptographic perspective: Replace "HMAC" with "password", and this attack was published decades ago and is probably the most commonly mentioned side channel attack in the cryptographic literature.

Atwood really thinks we should be trying to educate developers about how to build crypto?

I'm not sure where Atwood comes into this; but I don't see how having non-skilled developers stay away from cryptographic code would have helped here. Yes, this is the sort of mistake which people with a little bit of cryptographic knowledge ("just enough to be dangerous") can make easily -- of course, that's as much an argument for giving them more knowledge as it is for preventing them from having any at all -- but Stephen Weis is not such a person. He did a PhD in cryptography, supervised by Rivest; no amount of saying "crypto is hard, you should use existing libraries instead of writing your own" would have kept him away from making this mistake.

tptacek7• 17 years ago

I don't see how your argument coheres. Someone who did a PhD under Rivest made a trivially exploitable crypto error, which is evidence that lay programmers should be implementing crypto too?

NateLawson4• 17 years ago

I have found this exact bug (MAC compare timing attack) in three different products over the past few years. I could only talk publicly about this one. The fact that it's so common indicates it hasn't been publicized well enough, especially for crypto implementers.

My recommendation to use libraries is so all engineers can benefit from the review. The more crypto libraries there are, the less reviewed each is. I get all twitchy when I see how many different single sign-on and cookie verification libraries there are out there. There's even duplication between OAUTH and OpenID.

We need libraries to operate at a higher level. We need less of them (proliferation). We need more review of those libraries. The latter two things go hand-in-hand.

smanek• 17 years ago

There is obviously plenty of literature about side channel attacks, particularly timing attacks (which you have contributed to ;-)).

But, among 'lay programmers' I've met, I would say that more than 9/10 have no idea what a 'side channel attack' is. In my experience, its unusual (~ 3/10) for a programmer to know what asymmetric encryption is. I don't expect most programmers to know the particular math behind RSA (let alone ECC/etc), but many don't even the general idea of having a function and its inverse with properties A, B, and C.

sweis• 17 years ago

As the person who made the coding mistake, I think the lesson drawn from this is the benefit of open sourcing Keyczar. I've seen this exact type of timing attack before, but overlooked it in my own code. There's a real advantage to having fresh eyes find bugs like this.

Thanks to Nate and other people who have been contributing. Keep the bug reports coming.

ankhmoop• 17 years ago

While I don't believe Atwood should have anything to do with educating developers about how to build crypto, the fact is that the available libraries are remarkably poor, and as a developer I've been placed in the unfortunate position of "building crypto", with my OpenSSL reference and Applied Cryptography in-hand.

Until we developers have books that better elucidate the pitfalls of implementation, or better libraries that avoid the pitfalls on our behalf, we'll be stuck "building crypto", somewhat blindly.

I've seen you recommend GPGME previously. It's practice of executing the GPG command line tool is just not workable in many implementation environments. In my most recent use-case (several years ago), if there had been a decent portable, liberally licensed stream-supporting implementation of CMS (RFC3852), I would have gladly, readily used it.

tptacek7• 17 years ago

What did you implement crypto for? Can I see it?

brl4• 17 years ago

> Until we developers have books that better elucidate the pitfalls of implementation, or better libraries that avoid the pitfalls on our behalf, we'll be stuck "building crypto", somewhat blindly.

There are a lot of really good books about cryptography now.

This book is the best one that I've seen for coverage of the pitfalls of implementation.

http://www.amazon.com/Modern-Cryptography-Practice-Hewlett-P...

> I've seen you recommend GPGME previously.

I missed the context in which tptacek was recommending GPGME, but if your problem is something other than authenticating downloaded packages or signing and encrypting email, designing with GPG as a 'primitive' is probably not such a great idea. I have seen some attempts to repurpose GPG into new applications and every time these protocols have been badly flawed because the authors don't even realize that they are inventing a brand new protocol.

pj• 17 years ago

That is so sick. (in an awesome way)

It's like evolution in action. The defensive crypto guy's carapace has been pierced by the hacker's slow methodical leverage.

tptacek7• 17 years ago

You want sick? Here's sick.

An AES block is 16 bytes long. You want to encrypt the lyrics to "Yellow Submarine". You can't just repeat AES for each 16 byte block, because then you can tell where the words "yellow submarine" --- 1 AES block --- occur: they'll encrypt to the same block. So you use CBC mode, XOR'ing each plaintext block to the previous ciphertext block, creating a unique ciphertext every time you encrypt those lyrics. But "Yellow Submarine" is 902 characters long; the last block is 6 bytes short. So you pad the message which a count of the pad characters --- 06h 06h 06h 06h 06h 06h.

With me so far?

Decrypt the message. Check the padding: it should repeat as many times as the value of the last byte. If not, you decrypted badly. Send an error to that effect.

Hey guess what! I can decrypt parts of your message!

If I stick a random AES block in your message, it will scramble the padded block. Every once in awhile, that scrambled message will end in 01h. 01h is valid padding. The message will be gibberish, but you at least won't tell me it had bad padding.

You wouldn't tell me if you decrypted to bad padding if I generated 02h 02h either. But that's much less likely than 01h.

Now I know that your plaintext XOR my random block produces a last byte of 01h. Solve.

Now my point: this is actually way old news --- back to Bleichenbacher and Vaudenay and probably before that (I'm not the resident expert) --- but attacks like this have broken peer-reviewed versions of TLS, the most peer-reviewed crypto protocol ever designed.

Don't build crypto.

NateLawson4• 17 years ago

This attack was found by Bodo Moeller in OpenSSL. I posted about this here, including a link to the slides: http://rdist.root.org/2008/01/25/tlsssl-mac-security-flaw/

crescendo• 17 years ago

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.

Can one of the security gurus here explain this in a bit more detail? I'm guessing he would base this on an average over a sample of response times with the same input. Otherwise, how would he account for other things happening on the server that could affect the timing for a single request?

tptacek7• 17 years ago

Exactly like that.

NateLawson4• 17 years ago

The important thing that probably isn't obvious is how few samples you actually need. Jitter is essentially random, which means it is decorrelated from the repeated pattern (1 compare takes longer, 255 take the same time)

With the added noise (jitter), all you need to do is distinguish the two normal distributions. This takes less samples than you might guess at first. Think of it as the same problem as distinguishing a biased coin (51% heads) from an indentical-looking unbiased one, merely by flipping each. Given the known bias percent and a desired confidence level (say 95%), calculate how many flips you will need to make a decision.

brl4• 17 years ago

I'm skeptical that this attack would work against the Java implementation. Surely a language which rivals C for performance does not compare arrays of primitives one byte at a time?

I've thought about locally attacking Unix password authentication in a similar way for quite some time by throwing random passwords at something like 'su' until I have guessed the first 3-4 bytes of the password hash (with timing) and then performing a dictionary attack against the truncated hash. This could never work though unless the hashes are compared bytewise instead of with something like an optimized memcmp().

brl4• 17 years ago

I looked it up and I'm wrong. Copying an array is implemented with native memmove() but comparing two arrays really is done one element at a time.

Nate Lawson Breaks Google Keyczar's HMAC Crypto Signatures

Related Stories