A Lesson In Timing Attacks | Hacker News Reader

A Lesson In Timing Attacks

codahale.com

35 pointskapitalx18 comments

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.

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.)

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

Yay hackernews, where people giving correct information get downvoted.

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?

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.

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.

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.

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.

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

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.

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.

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.

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

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).

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

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

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.

Reply on news.ycombinator.com