Robust and Efficient Elimination of Cache and Timing Side Channels(arxiv.org)
arxiv.org
Robust and Efficient Elimination of Cache and Timing Side Channels
http://arxiv.org/abs/1506.00189
3 comments
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.
The performance numbers are inspiring.
Will be interesting to see crypt-analysis that attempts to break a solution like this.
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.
I never really understood why just placing the equivalent of `wait(GetRandom())` isn't an efficient way to block timing attacks
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.
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.
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.
Yep. After many trials you're just left with the addition of the average value of whatever random distribution you're pulling delays from.
This paper is essentially a long, detailed answer to that question.
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
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
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.
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.
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.