4 ms·

Robust and Efficient Elimination of Cache and Timing Side Channels

35 points by luu 11y ago

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.
themeek 11y ago
Wow, this is incredible. Great work and an out-of-the-box and obvious-in-hindsight solution. The performance numbers are inspiring. Will be interesting to see crypt-analysis that attempts to break a solution like this.
- tptacek 11y ago
  There are so many moving parts, and so much of this pertains to the microarchitecture (which isn't really documented), that it seems inevitable. It's very cool; I'm not sure how practical it is.
julie1 11y ago
Since wait/sleep are not CPU intensive does not it open the door for a "power consumption" attack? Plus, using interruption/clock is not very stealth: it implies switching context, sending signal to a clock, and waiting for a specific interrupt to wake you up (plus reloading context ....). I guess as usual that during heavy load it may backfire on some hardware by changing its behaviour when there is a pressure to access the clock enabling a potential DOS (on some hardware like heavily asynchronuous equipment like routers for instance, I totally can feel the CPU overload while there is almost no process, IO that requires close to RT beginning to fail unexpectedly, clock drift...). I mean you don't need a PhD to anticipate this. It seems a totally elegant, simple and wrong solution to me.
- loser777 11y ago
  Power consumption is assumed to not be part of their threat model. >Similarly, we assume that the attacker >does not have physical access to the hardware and cannot >monitor side channels such as electromagnetic radiations, >power use, or acoustic emanations.

35 points by luu 11y ago

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.

themeek 11y ago

Wow, this is incredible. Great work and an out-of-the-box and obvious-in-hindsight solution. The performance numbers are inspiring. Will be interesting to see crypt-analysis that attempts to break a solution like this.

tptacek 11y ago
There are so many moving parts, and so much of this pertains to the microarchitecture (which isn't really documented), that it seems inevitable. It's very cool; I'm not sure how practical it is.

julie1 11y ago

Since wait/sleep are not CPU intensive does not it open the door for a "power consumption" attack? Plus, using interruption/clock is not very stealth: it implies switching context, sending signal to a clock, and waiting for a specific interrupt to wake you up (plus reloading context ....). I guess as usual that during heavy load it may backfire on some hardware by changing its behaviour when there is a pressure to access the clock enabling a potential DOS (on some hardware like heavily asynchronuous equipment like routers for instance, I totally can feel the CPU overload while there is almost no process, IO that requires close to RT beginning to fail unexpectedly, clock drift...). I mean you don't need a PhD to anticipate this. It seems a totally elegant, simple and wrong solution to me.

loser777 11y ago
Power consumption is assumed to not be part of their threat model. >Similarly, we assume that the attacker >does not have physical access to the hardware and cannot >monitor side channels such as electromagnetic radiations, >power use, or acoustic emanations.