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!