4 ms·

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

113 points by codahale 17y ago

sophacles 17y 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.
- codahale 17y 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.
  - sophacles 17y 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 17y ago
  Or, just use the non short circuiting "&" instead of "and"
  - sophacles 17y ago
    Cool, I didn't know that would work in python in this case (testing shows it does). Thanks :)
naz 17y ago
Incredible, but nothing a little sleep(rand()) won't solve.
- sophacles 17y 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.
  - naz 17y ago
    That makes sense, maybe sleep(rand(1.0 - time_spent))
    - naz 17y ago
      Or just sleep(1.0 - time_spent)
      - JacobK 17y ago
        Or just don't short circuit ever, and do the entire computation every time.
- codahale 17y ago
  You may want to read this: http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf 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 17y 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?
jgrahamc 17y 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 17y 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 17y ago
  Tell the website first. Always.
mattj 17y 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.
- codahale 17y ago
  Again, you should read the Crosby et al. paper (http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf) and the Brumley & Boneh paper (http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf 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.)
- 17y ago
deleted 17y ago
[deleted]
mbrubeck 17y ago
This Google search reveals a ton of similar potential bugs: http://www.google.com/codesearch?hl=en&q=digest\.equals+file%3A\.java%24 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&ct=rc#UKcntCYb8Dw/trunk/src/org/apache/ws/security/processor/UsernameTokenProcessor.java&q=digest\.equals%20file:\.java$ http://www.google.com/codesearch/p?hl=en&sa=N&cd=31&...

113 points by codahale 17y 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.

codahale 17y 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.
- sophacles 17y 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 17y ago
Or, just use the non short circuiting "&" instead of "and"
- sophacles 17y ago
  Cool, I didn't know that would work in python in this case (testing shows it does). Thanks :)

naz 17y ago

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

sophacles 17y 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.
- naz 17y ago
  That makes sense, maybe sleep(rand(1.0 - time_spent))
  - naz 17y ago
    Or just sleep(1.0 - time_spent)
    - JacobK 17y ago
      Or just don't short circuit ever, and do the entire computation every time.
codahale 17y ago
You may want to read this: http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf 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 17y 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?

jgrahamc 17y 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 17y 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 17y ago
Tell the website first. Always.

mattj 17y 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.

codahale 17y ago
Again, you should read the Crosby et al. paper (http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf) and the Brumley & Boneh paper (http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf 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.)
17y ago

deleted 17y ago

[deleted]

mbrubeck 17y ago

This Google search reveals a ton of similar potential bugs: http://www.google.com/codesearch?hl=en&q=digest\.equals+file%3A\.java%24 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&ct=rc#UKcntCYb8Dw/trunk/src/org/apache/ws/security/processor/UsernameTokenProcessor.java&q=digest\.equals%20file:\.java$ http://www.google.com/codesearch/p?hl=en&sa=N&cd=31&...