A Lesson In Timing Attacks

http://codahale.com/a-lesson-in-timing-attacks/?s=1

by kapitalx • 14 years ago

35 18 14 years 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• 14 years 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.

tptacek4• 14 years ago

It's a crypto vulnerability. Either don't write crypto code (preferred), or know about and mitigate these kinds of flaws.

tptacek4• 14 years 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).

biot2• 14 years 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

floody-berry• 14 years 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

jasonwatkinspdx3• 14 years ago

Posted 3 years ago:

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.

dbaupp• 14 years 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.)

jasonwatkinspdx3• 14 years ago

That's not the case. I used the bookmarklet to find the original submission before making my post.

tlb• 14 years 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.

tptacek4• 14 years 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.

tedunangst2• 14 years 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.

biot2• 14 years ago

If you know how much of the substring of the hash matches, you could use a timing attack to construct a hash collision.

tedunangst2• 14 years 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• 14 years 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?

tptacek4• 14 years 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• 14 years 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.

A Lesson In Timing Attacks

Related Stories