Tuesday, July 22, 2014

Timing attack, 6.66% faster

Personally I'm not a big fan of timing attack as I believe they are impractical for web apps (while perfectly useful in other fields). To make them useful you need to reduce latency and put your script just in front of the victim's server, send zillions of requests (which will most likely be blocked & investigated) and even if everything seems to go smoothly your script might have chosen a wrong character and you're going "dead way" - you never know. And obviously it's even less useful against black box apps.

As long as it is a real attack nobody cares about my opinion - it is a vulnerability. But I recently realized all timing attack scripts I saw in the blog posts can be a little bit more efficient.

I have no idea if this is a known tactic, but if it is why don't we use it every time we write about Frightful Timing Attack?

Given, somewhere on the server side there's hash == params[:hash] comparison and hash is e.g. 123234.
Strategy we see most of the time:
Probe 000000 N times
Probe 100000 N times
Probe 200000 N times
Probe 300000 N times
...
Probe 900000 N times

Then find the slowest one. Those starting with wrong character will essentially execute just one operation String1[0] == String2[0] and then fail. But the string with right one (100000) will have 1 more operation String1[1] == String2[1], making the average timing significantly longer.

The idea is to go deeper. 

Tree #1, N=100 checks
Probe 000000
Probe 001000
Probe 002000
...
Probe 010000
Probe 011000
Probe 012000
...
Probe 098000
Probe 099000

Tree #2, N=100 checks
Probe 100000
Probe 101000
Probe 102000
...
Probe 120000
Probe 121000
Probe 122000
Probe 123000
...

As you can see the second tree will have not just usual +N operations, but extra +N/A for all 12***** and +N/A^2 for 123***, where A is Alphabet length (10 for 0-9 digits, 16 for 0-9a-f).

In our example we will have 211 operations in the tree starting with "1" and regular 100 operations in others, making it 11% easier to distinguish which pattern is the right one. We can go even deeper and never probe the pattern we checked before but it looks like only first two chars have a significant impact on performance, next N/A^3 and N/A^4 will not make it much better: 11.11...%

The other perk of this technique is when you are starting to probe next character you don't need to repeat the job you've done already (probing 10*000, 11*000, 12*000, and others ending with 000), which makes your job 1/A easier (10% less requests).

For hexadecimal values A=16 successful tree is 6.66..% easier to detect and attack is 6.25% faster.

I believe there are better timing tricks, will appreciate if you can share a link!

6 comments:

  1. Because we hash passwords. Therefore there is no way this timing attack would work.

    ReplyDelete
  2. It works if you know the hash algorithm and parameters used.

    Say for example a password that hashes to "a..." is consistently slower than one that hashes to "b..." or "c...", then I know that the hash likely starts with a. Continue this untill you can just brute-force all the possibilities.

    ReplyDelete
  3. Not if they're salted too

    ReplyDelete
  4. HAS NOTHING TO DO WITH PASSWORDS

    ReplyDelete
  5. Interesting, I'm sure it's possible to build in some simple heuristics to determine the ideal number of bytes to brute-force at a time, and change it dynamically based on a number of things.

    As an aside, I have /no/ clue what the other retards on this thread are commenting about.

    ReplyDelete
    Replies
    1. they think "hash" i used in the post is password hash. But here hash means an api_key.

      This attack can only improve working vectors. Web apps timing is not working and 11% improvement of 0 is still 0. But binary / local exploits can really get faster

      Delete