28 ms·

A Lesson In Timing Attacks

35 points by kapitalx 14y ago

stevencorona 14y ago
While I believe the author that it's measurable over the internet.. I'd love to see an example of the code on the attacking side, so I could test it for myself. It just seems like it wouldn't be measurable, and I'd love to test it and prove myself wrong.
- kapitalx 14y ago
  I've been looking at different security issues that I should protect against, and came across this article, and I also find it hard to believe that I'll need to worry about this even though the author insists that it's doable. I wonder if this is more relavant in much higher profile attacks (cyberwar,etc) than in some webapp.
  - tptacek 14y ago
    It's a crypto vulnerability. Either don't write crypto code (preferred), or know about and mitigate these kinds of flaws.
- tptacek 14y ago
  It's very annoying to build systems to test this vulnerability. Nate Lawson presented one such system at Black Hat a few years ago; he had to modify his ethernet drivers to take interrupt overhead out of the picture, IIRC. There are very common attack scenarios where the effect you're targeting is below the measurement threshold. For instance, "across the Internet", and "target is a compare implemented by memcmp". But there are others that aren't, and ways to pivot from one to the other (for instance, "buy account at same hosting provider"). The actual attack itself, mathematically, is very simple. It's high school statistics. (Crosby & Wallach's stuff is advanced statistical filtering, but that's to get better measurements; the core of the attack is much simpler).
- biot 14y ago
  While only tangentially helped by timing to reduce the amount of brute force involved, you might find "How I Hacked Hacker News" interesting: https://news.ycombinator.com/item?id=639976 https://news.ycombinator.com/item?id=639976
- floody-berry 14y ago
  djb's "Cache-timing attacks on AES" paper includes the code he used to carry out his attacks: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
jasonwatkinspdx 14y ago
Posted 3 years ago: http://news.ycombinator.com/item?id=760917 http://news.ycombinator.com/item?id=760917 It looks like kapitalx appended a query param (s=1) in order to avoid the duplicate url check.
- deleted 14y ago
  [deleted]
- dbaupp 14y ago
  I believe the duplicate url check only applies for a limited period of time, possibly as short a week. (I'm not sure of this though.)
  - jasonwatkinspdx 14y ago
    That's not the case. I used the bookmarklet to find the original submission before making my post.
    - jasonwatkinspdx 14y ago
      Yay hackernews, where people giving correct information get downvoted.
tlb 14y ago
You should never be doing a string compare on the exact string sent over the network anyway. You should be hashing it first. Hashing destroys any value in knowing how much of the substring you matched.
- tptacek 14y ago
  I'm not sure there's much of a security difference between secure compare functions and hashing, but it's worth knowing about that technique too; do whatever you're most confident in implementing.
  - tedunangst 14y ago
    If you hash the user session cookie before looking it up in your database, it has the minor advantage that in the event your cookie database is stolen, it's worthless.
- biot 14y ago
  If you know how much of the substring of the hash matches, you could use a timing attack to construct a hash collision.
  - tedunangst 14y ago
    Not really. The hash is going to change too much. Let's say you know the first digits of a hash are "ABCDEF". It's significant work to find something that hashes to that. And now you have to generate a whole bunch of them to guess the seventh letter.
mgallivan 14y ago
What happens if, on inequality, you have a 50% chance of doing one more comparison operation? The way I figure, which may be incorrect, is the following: You have x options (here it is 16). x^2 gives us 256 different options for this example. However, if it's only correct correct half of the time then we have to repeatedly cut down our search which results in series: sum (x^2)/(2n), n=1 to m which is (x^2 H_m) / 2 Is this correct? Could someone explain how many random extra comparisons would be needed to thwart a timing attack?
- tptacek 14y ago
  You can make it more painful to take accurate measurements by adding randomness, but adding noise doesn't kill the signal. It is never a good idea to pursue schemes like this; rather, fix the underlying leak.
qwertzlcoatl 14y ago
20µs == 20 microseconds == 20 * 10e-6 seconds. 100ns == 100 nanoseconds == 100 * 10e-9 seconds. 2 GHz == one clock cycle in 0.5 * 10e-9 seconds. And that's how long that one comparison would take; not accounting for branch prediction and other interferring stuff inside the processor. It's not an attack, it's a joke.

35 points by kapitalx 14y ago

While I believe the author that it's measurable over the internet.. I'd love to see an example of the code on the attacking side, so I could test it for myself. It just seems like it wouldn't be measurable, and I'd love to test it and prove myself wrong.

kapitalx 14y ago
I've been looking at different security issues that I should protect against, and came across this article, and I also find it hard to believe that I'll need to worry about this even though the author insists that it's doable. I wonder if this is more relavant in much higher profile attacks (cyberwar,etc) than in some webapp.
- tptacek 14y ago
  It's a crypto vulnerability. Either don't write crypto code (preferred), or know about and mitigate these kinds of flaws.
tptacek 14y ago
It's very annoying to build systems to test this vulnerability. Nate Lawson presented one such system at Black Hat a few years ago; he had to modify his ethernet drivers to take interrupt overhead out of the picture, IIRC. There are very common attack scenarios where the effect you're targeting is below the measurement threshold. For instance, "across the Internet", and "target is a compare implemented by memcmp". But there are others that aren't, and ways to pivot from one to the other (for instance, "buy account at same hosting provider"). The actual attack itself, mathematically, is very simple. It's high school statistics. (Crosby & Wallach's stuff is advanced statistical filtering, but that's to get better measurements; the core of the attack is much simpler).
biot 14y ago
While only tangentially helped by timing to reduce the amount of brute force involved, you might find "How I Hacked Hacker News" interesting: https://news.ycombinator.com/item?id=639976 https://news.ycombinator.com/item?id=639976
floody-berry 14y ago
djb's "Cache-timing attacks on AES" paper includes the code he used to carry out his attacks: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf http://cr.yp.to/antiforgery/cachetiming-20050414.pdf

jasonwatkinspdx 14y ago

Posted 3 years ago: http://news.ycombinator.com/item?id=760917 http://news.ycombinator.com/item?id=760917 It looks like kapitalx appended a query param (s=1) in order to avoid the duplicate url check.

deleted 14y ago
[deleted]
dbaupp 14y ago
I believe the duplicate url check only applies for a limited period of time, possibly as short a week. (I'm not sure of this though.)
- jasonwatkinspdx 14y ago
  That's not the case. I used the bookmarklet to find the original submission before making my post.
  - jasonwatkinspdx 14y ago
    Yay hackernews, where people giving correct information get downvoted.

tlb 14y ago

You should never be doing a string compare on the exact string sent over the network anyway. You should be hashing it first. Hashing destroys any value in knowing how much of the substring you matched.

tptacek 14y ago
I'm not sure there's much of a security difference between secure compare functions and hashing, but it's worth knowing about that technique too; do whatever you're most confident in implementing.
- tedunangst 14y ago
  If you hash the user session cookie before looking it up in your database, it has the minor advantage that in the event your cookie database is stolen, it's worthless.
biot 14y ago
If you know how much of the substring of the hash matches, you could use a timing attack to construct a hash collision.
- tedunangst 14y ago
  Not really. The hash is going to change too much. Let's say you know the first digits of a hash are "ABCDEF". It's significant work to find something that hashes to that. And now you have to generate a whole bunch of them to guess the seventh letter.

mgallivan 14y ago

What happens if, on inequality, you have a 50% chance of doing one more comparison operation? The way I figure, which may be incorrect, is the following: You have x options (here it is 16). x^2 gives us 256 different options for this example. However, if it's only correct correct half of the time then we have to repeatedly cut down our search which results in series: sum (x^2)/(2n), n=1 to m which is (x^2 H_m) / 2 Is this correct? Could someone explain how many random extra comparisons would be needed to thwart a timing attack?

tptacek 14y ago
You can make it more painful to take accurate measurements by adding randomness, but adding noise doesn't kill the signal. It is never a good idea to pursue schemes like this; rather, fix the underlying leak.

qwertzlcoatl 14y ago

20µs == 20 microseconds == 20 * 10e-6 seconds. 100ns == 100 nanoseconds == 100 * 10e-9 seconds. 2 GHz == one clock cycle in 0.5 * 10e-9 seconds. And that's how long that one comparison would take; not accounting for branch prediction and other interferring stuff inside the processor. It's not an attack, it's a joke.