4 ms·

Re: timing attacks - can these be protected against by simply inserting into a protocol a mandatory random sleep that is strictly larger than the worst case run

by pdkl95 12y ago

Re: timing attacks - can these be protected against by simply inserting into a protocol a mandatory random sleep that is strictly larger than the worst case run time of the crypto implementation? For example, if it takes up to 1s to run the crypto, would a protocol that required a usleep() of uniform_random(5s..10s)? Such a scheme would obscure any variations in timing, right? I ask because I have been thinking recently about the cost of "realtime", when many use-cases don't actually need it. Bittorrent exploits this idea - multicast is hard and most methods never really worked well enough to become popular. Then bittorrent comes along and gives up on the idea preserving an ordered, realtime-streamable transmission. In return, bittorrent got a lot of other features and became a very useful tool. As these slides mention - it is easy to be blinded by a supposed need to make everything fast. (brainstorming) Perhaps something like a modern variation on the batched store-and-forward used in the old FidoNet could be useful for non-interactive needs; instead of trying to save on long-distance fees it tries use ideas like the usleep("many seconds or more") and much larger (slower) key sizes. /* Given the tone of those slides, I would guess that DJB just saw PHK's amazing "Operation Orchestra" talk? BULLRUN? "PSYOPS for nerds"? The lesson is important either way. */

MichaelGG 12y ago
Adding random sleeps does not prevent timing attacks. It just adds noise making them a bit more work to pull off.
- e12e 12y ago
  I suppose one (not very good) approach to "patching-in" constant run-time, would be to limit the runtime of every iteration to be that of the upper bound (possibly +some constant). I suspect that's pretty hard to actually do, and even if accomplished, would open up to other side-channel/timming attacks (eg: check cpu load, and infer timing).
- robryk 12y ago
  But, if you have an upper bound on the time of the operation, you can wait until the bound elapses, so that your operation always takes that long.
  - TheLoneWolfling 12y ago
    The problem is: good luck getting an upper bound. What happens if the process is paged to disk, for instance? No matter what upper bound you set you'll still end up with it going over at some point - and as soon as you go over the upper limit you're leaking timing information again. This also ups RAM requirements, drastically in some cases. And it isn't even necessarily secure against timing attacks! Because the thread scheduling by the OS changes depending on how much work is being done, and so it could take less or more time to retrieve the saved response depending on how long another request takes to process.
tptacek 12y ago
Apart from the fact that adding noise just increases the measurement cost, the "add random sleeps" solution has two other problems, one small and one big. The big one: it implies that you actually know what the side channel is, so you can sleep at a useful point. The virtue of relying solely on constant-time operations is that they're constant time by design. You don't have to worry about how the variable-time operations are implemented, because there aren't any. The smaller problem is that you have to make sure that your noise function is not itself a target of attack, which can be a little tricky because your noise function must be extremely, extremely cheap to compute. There's also the obvious "non-problem" that reducing a function to it's lowest common denominator of performance defeats the purpose of high-speed cryptography and variably-timed implementations in the first place.
- pdkl95 12y ago
  Ok, thanks! That was as very clear explanation!
- kragen 12y ago
  Random sleeps, as you say, have the problem that they don't eliminate the timing side channel, but just add noise to it. However, as robryk points out below, you can eliminate the timing side channel entirely, assuming you know what it is, by sleeping until a predetermined point. In pdkl95's example, you could sleep until 1.1 seconds after the cryptographic operation was initiated, then sending your response. The predetermined point could be determined randomly as long as the random number generator is constrained not to return a point that's so early that the crypto might still be running. But randomness does not help in this case.
  - tptacek 12y ago
    You addressed the "apart from the fact" point in my comment, but not the meat of it. I point that out because someone else already brought up the measurement cost issue; my point was that there are other concerns. Also, my comment directly addressed the notion of a lowest- common- denominator sleep. I think maybe you meant to respond to a different comment?

by pdkl95 12y ago

MichaelGG 12y ago

Adding random sleeps does not prevent timing attacks. It just adds noise making them a bit more work to pull off.

e12e 12y ago
I suppose one (not very good) approach to "patching-in" constant run-time, would be to limit the runtime of every iteration to be that of the upper bound (possibly +some constant). I suspect that's pretty hard to actually do, and even if accomplished, would open up to other side-channel/timming attacks (eg: check cpu load, and infer timing).
robryk 12y ago
But, if you have an upper bound on the time of the operation, you can wait until the bound elapses, so that your operation always takes that long.
- TheLoneWolfling 12y ago
  The problem is: good luck getting an upper bound. What happens if the process is paged to disk, for instance? No matter what upper bound you set you'll still end up with it going over at some point - and as soon as you go over the upper limit you're leaking timing information again. This also ups RAM requirements, drastically in some cases. And it isn't even necessarily secure against timing attacks! Because the thread scheduling by the OS changes depending on how much work is being done, and so it could take less or more time to retrieve the saved response depending on how long another request takes to process.

tptacek 12y ago

Apart from the fact that adding noise just increases the measurement cost, the "add random sleeps" solution has two other problems, one small and one big. The big one: it implies that you actually know what the side channel is, so you can sleep at a useful point. The virtue of relying solely on constant-time operations is that they're constant time by design. You don't have to worry about how the variable-time operations are implemented, because there aren't any. The smaller problem is that you have to make sure that your noise function is not itself a target of attack, which can be a little tricky because your noise function must be extremely, extremely cheap to compute. There's also the obvious "non-problem" that reducing a function to it's lowest common denominator of performance defeats the purpose of high-speed cryptography and variably-timed implementations in the first place.

pdkl95 12y ago
Ok, thanks! That was as very clear explanation!
kragen 12y ago
Random sleeps, as you say, have the problem that they don't eliminate the timing side channel, but just add noise to it. However, as robryk points out below, you can eliminate the timing side channel entirely, assuming you know what it is, by sleeping until a predetermined point. In pdkl95's example, you could sleep until 1.1 seconds after the cryptographic operation was initiated, then sending your response. The predetermined point could be determined randomly as long as the random number generator is constrained not to return a point that's so early that the crypto might still be running. But randomness does not help in this case.
- tptacek 12y ago
  You addressed the "apart from the fact" point in my comment, but not the meat of it. I point that out because someone else already brought up the measurement cost issue; my point was that there are other concerns. Also, my comment directly addressed the notion of a lowest- common- denominator sleep. I think maybe you meant to respond to a different comment?