17

I read recently about profiling for valid user accounts with timing attacks, IE the application-under-attack takes a predictably different amount of time to process say a login on a non-existent user from an existent user. Yet I've never seen in any examples or framework code any protection against this. Would it be sufficient to simply insert a random delay before the response so that the timing attacker is getting a whole mess of response times? If so, why haven't I seen this? If not, what's bad about this scheme?

Iain Duncan
  • 382
  • 2
  • 12

2 Answers2

19

This is actually a common misconception because intuitively, it seems like adding random delays should thwart timing attacks, until you think about it a bit deeper.

Theoretically, if the lengths your random delays are unbounded, ie drawn from [0, infinity] then it would thwart a timing attack for the reason that you suggest. In practice you A) don't want to make legitimate users wait an infinite amount of time for their login, and B) have to draw your random delays from some finite range [0, a]. This means that on average (ie with enough samples) you are simply adding a/2 to the time.

So let's say that without random delays you have the following timing profiles:

  • query existing user name: x ms
  • query non-existing user name: y ms

With random delays you now have (on average):

  • query existing user name: x + a/2 ms
  • query non-existing user name: y + a/2 ms

Since x - y = (x + a/2) - (y + a/2), the timing difference is still there for an attacker to exploit. The only thing that you've changed is that in addition to having to filter out network lag, cpu-scheduling lag, load-balancing lag, etc, they also have to filter out your intentional sorta-random lag. A successful timing attack will already be doing multiple queries for each username and averaging, but now they may have to add more samples in order to get their "clean" average.

Bottom-line: adding random noise may make the attack slower, but it will not make it any more complex.

The only real way to protect against timing attacks is to make sure that every possible code-path has takes the same amount of time.

  • query existing user name: x ms
  • query non-existing user name: x ms

Then there really is no way to tell those two apart.

Warning! Writing time-invariant code can be tricky, hence the maxim "don't roll your own". If you can find a login-manager that already implements timing-invariance, then using that would be both easier and safer.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • Timing invariance isn't hard. Lookup up the the time, x, before even looking at anything. Then do your stuff. Then wait until time x+1 seconds. Simple! – PyRulez Aug 10 '15 at 23:45
  • 2
    @PyRulez Umm, maybe? Remember that `wait` is a complex operating system call and therefore takes time itself. [This attack](http://www.isg.rhul.ac.uk/tls/TLStiming.pdf) showed that a timing difference of 500 - 1000 assembly instructions can be exploited over a network (that is fractions of milliseconds). So if I was buying software from you and you claimed that your code was timing invariant, I would want an assembly expert to inspect your compiled binaries and guarantee that every possible code path takes the same number of assembly instructions (btw, that is hard). – Mike Ounsworth Aug 11 '15 at 00:01
  • The point is the timing code is independent of the other code looking at the username. I don't see how you can get better than that. – PyRulez Aug 11 '15 at 00:14
  • @PyRulez: But "wait until time x+1 seconds" is not so easy to guarantee. – ruakh Oct 26 '15 at 19:48
  • @ruakh Well sure, but it probably wouldn't be influenced by the rest of the program, would it? – PyRulez Oct 26 '15 at 20:33
  • 1
    @PyRulez: Right -- it **probably** wouldn't. Now re-read Mike Ounsworth's answer and comment, and you'll see the problem. :-) – ruakh Oct 26 '15 at 20:37
3

Theoretically, this will not work. The attacker already has randomness from the delays of the network, adding extra randomness doesn't prevent timing attacks, it just means the attacker needs more data for their analysis.

Practically, it might make timing attacks infeasible because of the amount of data needed for analysis

But there are better ways to prevent timing attacks. For web applications, timing attacks are mainly prevented by performing things in fixed time. In your example, that would mean that you want to compare the password to an imaginary password, even if the username does not exist.

Of course, usernames are generally not considered sensitive information, and if you have a signup page, an attacker could bruteforce that instead. On the other hand, it's generally recommended to make password comparisons timing safe.

tim
  • 29,018
  • 7
  • 95
  • 119
  • So does this mean to prevent profiling, we would just make sure we have an identical instruction set for checking the user as well? – Iain Duncan Aug 10 '15 at 19:22
  • 1
    @IainDuncan Right, the instruction set should be as similar as possible. Eg `($user, $pw1) = dbquery(...); if(!userExists($user)) { timingSafeCheckPW($pw1, 'nothing'); exit; } else if(timingSafeCheckPW($pw1, $pw2)) { logUserIn(); } else { exit; }` (of course, the actually executed code will still have different times because of branching, but that really shouldn't matter for network based attacks). In practice, I wouldn't reduce code readability to prevent an unlikely timing attack on usernames (protecting passwords is a different matter). – tim Aug 10 '15 at 19:51