3 ms·

I never really understood why just placing the equivalent of `wait(GetRandom())` isn't an efficient way to block timing attacks

by earlz 11y ago

tptacek 11y ago
This paper is essentially a long, detailed answer to that question.
resc1440 11y ago
One reason is that in many cases, it's easy to do a large number of trials, so this only makes an attack slightly less practical. They go from being able to tell your secret after 10 packets to needing 100 or 1000.
- throwawait 11y ago
  Yep. After many trials you're just left with the addition of the average value of whatever random distribution you're pulling delays from.
bmm6o 11y ago
These types of attacks generally have to already extract signal from noise, you're just introducing more noise. The correct solution is to remove the signal, not bury it under more noise. Also, the Law of Large Numbers works against you here - the amount you have to sleep grows faster than the number of attacks your attacker gets.
Natsu 11y ago
They're simply averaged out after a number of trials. You're trying to scramble information that needs to be removed. It's like how a blurred image can be brought back into focus, but a removed one cannot, e.g. -- http://yuzhikov.com/articles/BlurredImagesRestoration1.htm http://yuzhikov.com/articles/BlurredImagesRestoration1.htm
patio11 11y ago
Assume you have two doors, one guaranteed to only allow randomly selected women to walk through it, and one similar one for men. For weird reasons, you're unable to make any judgement about the person coming through the door except height. This is sufficient to figure out which door is which: on average, women are shorter then men. After that, it is a high school statistics exercise. Suppose in addition to being unable to distinguish a man from a woman you are also not really good with your ruler and each person is recorded at 6 +/- 6 inches above their true height. Does this make it impossible do distinguish the women's door from the men's? Not in the slightest: the averages are now wrong, but they're still different. It's still a high school stats exercise. It's a very important thing for science that a real world which easily permits measurement errors like this doesn't by itself make science impossible. Most timing attacks on e.g. HMAC functions are the door problem in disguise: we know there is going to be a fast code path (e.g. early termination of a string comparison) and a less fast code path (e.g. a string comparison which had to examine every character). You're allowed to take an arbitrarily large number of measurements -- determine whether you're on the fast path or the less fast path. Great, you just solved N bits of the problem -- now, do that in a for loop and you win.

I never really understood why just placing the equivalent of `wait(GetRandom())` isn't an efficient way to block timing attacks

by earlz 11y ago

I never really understood why just placing the equivalent of `wait(GetRandom())` isn't an efficient way to block timing attacks

tptacek 11y ago

This paper is essentially a long, detailed answer to that question.

resc1440 11y ago

One reason is that in many cases, it's easy to do a large number of trials, so this only makes an attack slightly less practical. They go from being able to tell your secret after 10 packets to needing 100 or 1000.

throwawait 11y ago
Yep. After many trials you're just left with the addition of the average value of whatever random distribution you're pulling delays from.

bmm6o 11y ago

These types of attacks generally have to already extract signal from noise, you're just introducing more noise. The correct solution is to remove the signal, not bury it under more noise. Also, the Law of Large Numbers works against you here - the amount you have to sleep grows faster than the number of attacks your attacker gets.

Natsu 11y ago

They're simply averaged out after a number of trials. You're trying to scramble information that needs to be removed. It's like how a blurred image can be brought back into focus, but a removed one cannot, e.g. -- http://yuzhikov.com/articles/BlurredImagesRestoration1.htm http://yuzhikov.com/articles/BlurredImagesRestoration1.htm

patio11 11y ago

Assume you have two doors, one guaranteed to only allow randomly selected women to walk through it, and one similar one for men. For weird reasons, you're unable to make any judgement about the person coming through the door except height. This is sufficient to figure out which door is which: on average, women are shorter then men. After that, it is a high school statistics exercise. Suppose in addition to being unable to distinguish a man from a woman you are also not really good with your ruler and each person is recorded at 6 +/- 6 inches above their true height. Does this make it impossible do distinguish the women's door from the men's? Not in the slightest: the averages are now wrong, but they're still different. It's still a high school stats exercise. It's a very important thing for science that a real world which easily permits measurement errors like this doesn't by itself make science impossible. Most timing attacks on e.g. HMAC functions are the door problem in disguise: we know there is going to be a fast code path (e.g. early termination of a string comparison) and a less fast code path (e.g. a string comparison which had to examine every character). You're allowed to take an arbitrarily large number of measurements -- determine whether you're on the fast path or the less fast path. Great, you just solved N bits of the problem -- now, do that in a for loop and you win.