A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals)

http://codahale.com/a-lesson-in-timing-attacks/

by codahale • 17 years ago

113 30 17 years ago

sophacles5• 17 years ago

The python code mentioned is still susceptible to timing attacks. Not on the same scale as a bytewise, return on first inequality algorithms, but it's there. The return statement will take longer when the result value is 0, because then it will compare 2 lengths of strings. This could be enough to distinguish between correct and incorrect compares.

Since the usage of zip in that case will only compare the shorter of the strings to the start of the longer string, you can still achieve the timing attack, since the only inconsistency happens on the final comparison.

A better solution would be to check for length equality before doing the zip, or to pad the shorter of the strings compared to the length of the longer. Maybe also to just make the return statement:

return (len(a) == len(b)) and (result == 0)

which may be sufficient.

codahale7• 17 years ago

Ah, that's a very good point. I've updated the post to return early, since figuring out the short-circuiting behavior across a handful of languages is obviously not my strong suit. Thanks for pointing that out, sophacles.

sophacles5• 17 years ago

y/w. This actually brings up an deeper problem too: the vast majority of the timing attacks exist because of little algorithmic optimizations, such as return on first inequality. In most cases such a comparison is desirable, as it is on average 50% faster (depending on specific data characteristics). We as computer people do these sorts of things as second nature, because we have been taught that efficient algorithms are always best. In cases like these, even when I know that there is a major problem being fixed, I cringe at the inefficiencies. It seems also to be a cause of other types of security hole, e.g. "why should I check this data, it should have already been checked, If I do it here, it's a bad redundancy".

Anyway, rambling thoughts aside: thanks for the article.

matthavener• 17 years ago

Or, just use the non short circuiting "&" instead of "and"

sophacles5• 17 years ago

Cool, I didn't know that would work in python in this case (testing shows it does). Thanks :)

naz3• 17 years ago

Incredible, but nothing a little sleep(rand()) won't solve.

sophacles5• 17 years ago

Not really, if this attack is doable over the internet, which will have latencies randomly[1] distributed (in a normal curve), rand does not actually do anything, well maybe require a few more sample points to get that noise out.

naz3• 17 years ago

That makes sense, maybe sleep(rand(1.0 - time_spent))

codahale7• 17 years ago

You may want to read this:

http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf

Adding jitter will not defeat timing attacks unless the jitter is dependent on the input, like blinded RSA.

commiebob• 17 years ago

What if you did something like (using the example from the article) A value which shares no bytes in common with the secret digest will return immediately; a value which shares the first 15 bytes will return 15 compares later.

You keep track of the time while doing the comparison, then before spitting back the result you feed the amount of time to a separate function that will sleep (or whatever) a certain amount of predetermined time so that all results process in the same time.

I realize this is a bit excessive, and will slow down your code quite a bit, but if you are really that worried about this type of attack, why not?

eru• 17 years ago

Sleeping for a random amount of time will make it more difficult to mount a timing attack. But not impossible in theory. You just have to do more statistics --- significance tests and the like.

anamax4• 17 years ago

Why not sleep a variable amount of time, so all calls take the same amount of time?

jgrahamc• 17 years ago

I believe that Ruby's Digest == method suffers from a similar issue. It uses rb_str_cmp to compare the hex strings, which uses rb_memcmp to do the comparison which uses memcmp.

The implementation of memcmp bails out as soon as it finds a difference:

  int
  memcmp(const void *s1, const void *s2, size_t len)
  {
    register unsigned char *a = (unsigned char*)s1;
    register unsigned char *b = (unsigned char*)s2;
    register int tmp;

    for (; len; --len) {
        if (tmp = *a++ - *b++)
            return tmp;
    }
    return 0;
  }

I suppose I ought to be reporting that somewhere. OK, I just told the security alias for Ruby about it.

pj• 17 years ago

I can’t tell if that’s terrible or awesome.

This is a mathematical problem like poker. On one hand, it exposes the issue for attack by hackers who didn't know about it before. But it also makes systems in the future more secure. What is the probability that a malicious hacker has found this issue before you and is using it to attack java based systems? What is the probability that after you expose the issue, all the vulnerable systems will be patched with your suggestion?

I'm curious what other hackers think of this. I've found XSS vulnerabilities in sites and other security issues. What do you do when you find these? Do you notify the sites? Sometimes I notify the website of the issue, sometimes I don't. I struggle with the decision myself, but I don't think I'd ever go open with such a vulnerability without first being more determined about getting a response from those who can fix the issue before the hackers find it.

pjhyett• 17 years ago

Tell the website first. Always.

mattj• 17 years ago

I get that timing attacks are reproducible in test environments and in a theoretical sense, but have any major real-life attacks been based on a timing vulnerability? Most websites anyone would want to attack will be running off of multiple servers (which will be reading from replicated mysqls, parts of the requests will likely be memcached, the load balancers will likely have fluctuating load etc. etc.), even multiple data centers. The number of requests you'd have to observe before you could have any statistically meaningful information would be huge. And we're talking about sub-millisecond differences (even Google routinely serves pages in the 50ms range, so this difference is tiny).

Seems like other, more traditional problems (weak / poor crypto, social engineering) are much more important problems.

I kind of wonder if people just really like timing attacks because they're so easy to understand, and, once you spot them, so easy to fix.

codahale7• 17 years ago

Again, you should read the Crosby et al. paper (http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf) and the Brumley & Boneh paper (http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf). However complicated you think the infrastructure is, you're radically underestimating the power of modern statistical analysis.

Crosby et al. conclude: We have shown that, even though the Internet induces significant timing jitter, we can reliably distinguish remote timing differences as low as 20µs. A LAN environment has lower timing jitter, allowing us to reliably distinguish remote timing differences as small as 100ns (possibly even smaller). These precise timing differences can be distinguished with only hundreds or possibly thousands of measurements.

If you'd like to bet that this sort of statistical analysis will get harder to perform over time, I'll take your wager. I'm not willing to wait until someone is publicly compromised before I fix security vulnerabilities—I do not work for an employer who's willing to tolerate a few break-ins before fixing the locks.

I'd also argue that a) a timing attack vulnerability is "weak/poor crypto," b) I don't need to write about the importance of other attack vectors (XSS, CRSF, social engineering, telepathy, bats, etc.) while writing about timing attacks, and c) if timing attacks are easy to understand and fix there would be less of them.

(Edit: fixed the B&B paper link. Derp.)

sophacles5• 17 years ago

Heres one: http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf which is rumored to have been used a couple of times "in the wild".

(edited to have the link i meant).

mbrubeck• 17 years ago

This Google search reveals a ton of similar potential bugs:

http://www.google.com/codesearch?hl=en&q=digest\.equals+...

For example, it looks like org.apache.ws.security.processor.UsernameTokenProcessor.handleUsernameToken might be vulnerable (although WS-Security's nonces and timestamps make things more complicated, since you have to generate a timestamp like a week in the future, and then hope that the server does the digest comparison before rejecting you based on the nonce or timestamp):

http://www.google.com/codesearch/p?hl=en&sa=N&cd=31&...

A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals)

Related Stories