7 ms·

I wonder if introducing a sleep that is longer than the computation could conceivably take would work to solve (or at least make it a lot harder to defeat) the

by yxhuvud 12y ago

I wonder if introducing a sleep that is longer than the computation could conceivably take would work to solve (or at least make it a lot harder to defeat) the actual problem. The failure case where the computation actually is slow enough to matter could be detected and thrown away. This of course would require a fully async crypto lib..

dragontamer 12y ago
If the sleep were cryptographically random, I can imagine it working out actually. But I wouldn't approach the subject unless I were more confident in my knowledge of cryptography.
mikeash 12y ago
The timing is a signal, and you're proposing to mask that signal by adding noise. This does work, but you can work around it by gathering more samples and averaging out the noise. You increase the work required from an attacker, but it's not insurmountable.
- semi-extrinsic 12y ago
  What if you use random noise from a Cauchy distribution? It (interestingly enough) has no mean, so the amount of time the attacker thinks she has to subtract from her average depends on the number of samples that she takes, and does not converge as she increases the number of samples.
  - dcauchy 12y ago
    Attacker uses the median
    - semi-extrinsic 12y ago
      Hmm. How does she know to use the median? What if I alternate between a Cauchy distribution and a lognormal (having different mean and median)? (Very apropos nick, by the way)
  - mikeash 12y ago
    I'm not particularly familiar with this so the odds of the following being correct are not terribly great.... As far as I can tell, the interesting properties of the Cauchy distribution come from the "fat tail," which means that large numbers are relatively more likely than if you used, for example, a gaussian distribution. This is going to cause problems when applying it to this case because you can't sleep arbitrarily long. There will have to be some sort of ceiling on it, and I think that will bring the behavior back into a realm where the attacker can make use of it. As to your question in your other reply about how the attacker will know to use the median instead of the mean, is there any distribution where using the median wouldn't work? If not, the attacker could just use the median as a matter of course. The idea posted here is interesting: https://news.ycombinator.com/item?id=9264760 https://news.ycombinator.com/item?id=9264760 Basically, have the artificial delay be unpredictable to an attacker, but constant for any given input. You'd still have to watch out for inputs which are computationally equivalent but not bytewise equal, but perhaps that can be managed.
fchollet 12y ago
How about random sleeps distributed so that the mean sleep time is always the same for every computation? (and much longer than any likely computation). timer.start(); computation(); time = timer.stop(); sleep(random_centered_on(mean-time));
- deleted 12y ago
  [deleted]
- TheLoneWolfling 12y ago
  For one thing, that means that your performance is horrible. And it doesn't prevent against indirect sidechannels. For instance, seeing how long other requests take.
saidajigumi 12y ago
This is only if the channel is a purely-external measurement of the computation, e.g. total turnaround time time to a result. A sleep won't do anything to mask a side-channel which involves (sometimes obscure) access to the actual work being done by the processor.
- ewindisch 12y ago
  Up-voting the parent. There are attacks such as FLUSH-RELOAD which are today difficult to avoid on modern hardware and allow this sort of introspection into the CPU instructions and their timings. Of course, there are a whole range of active and valid side-channels that are readily exploitable today. These are no longer NOBUS vulnerabilities, but are increasingly within the range and scope of ordinary attackers.
  - saidajigumi 12y ago
    And relevant to the post re: sleep, there are things like Cross-VM side channels[1], an important consideration given how much infrastructure runs in shared environments these days. [1] PDF: https://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf https://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf
    - ewindisch 12y ago
      Interestingly, the authors of the CCS paper are Yinqian Zhang and Michael K. Reiter. More recently, they've been publishing papers which deepen our understanding of the FLUSH+RELOAD side-channel as I described in my post (F+R was originally discovered by Yuval Yarom).
matthewmacleod 12y ago
That's not an effective technique, unfortunately. You still end up leaking timing information. Lets say you add a small, random sleep after each operation – this still leaks information, as the delay can be averaged out over multiple runs. A fixed sleep after each operation is no use either, for obvious reasons. One approach I've seen is to break time into discrete quanta – for example, you could guarantee that every operation will take an integer number of seconds to complete (i.e. an operation takes exactly 1 second, or exactly 2 seconds, or… scaled as required). There are still statistical techniques to extract timing information regardless, however! The takeaway is the cryptography is really, really hard; system integrity is even harder.
- chaosphere2112 12y ago
  What if, instead of a random sleep, you have a defined period of time for a function to take– you take a clock reading at the start and end of your execution, and sleep the remainder of the execution time?
  - matthewmacleod 12y ago
    The problem there is that sleeping alters the performance characteristics of your system. If an attacker submits multiple requests simultaneously, it would be possible for them to determine if you were actually working, or just sleeping - and you're back to leaking. Sure, every confounding factor makes it more difficult to extract information. But there are many effective techniques for doing so, and we keep getting better at using them.
    - mreiland 12y ago
      > If an attacker submits multiple requests simultaneously, it would be possible for them to determine if you were actually working, or just sleeping - and you're back to leaking. how?
      - matthewmacleod 12y ago
        The basic cause of a timing attack is that if cryptographic operations can take different amounts of time depending on the content, then we can potentially be leaking information to an attacker. If we try to solve this by padding our work using sleep() or similar, we might reveal less information directly – but the performance characteristics of our machine will still be different when we complete and operation quickly then sleep, versus when we complete an option slowly and sleep for less time. Here's a not-at-all real-world example – say an attacker causes a cryptographic operation to happen, while at the same time monitoring the time taken to respond to a ping request. Ignoring loads of complexity, we might find that a machine takes slightly longer to respond to a ping when it is performing an operation (i.e. the CPU is busy) than when it is sleeping. If that's the case, we're suddenly leaking timing information again.

by yxhuvud 12y ago

dragontamer 12y ago

If the sleep were cryptographically random, I can imagine it working out actually. But I wouldn't approach the subject unless I were more confident in my knowledge of cryptography.

mikeash 12y ago

The timing is a signal, and you're proposing to mask that signal by adding noise. This does work, but you can work around it by gathering more samples and averaging out the noise. You increase the work required from an attacker, but it's not insurmountable.

semi-extrinsic 12y ago
What if you use random noise from a Cauchy distribution? It (interestingly enough) has no mean, so the amount of time the attacker thinks she has to subtract from her average depends on the number of samples that she takes, and does not converge as she increases the number of samples.
- dcauchy 12y ago
  Attacker uses the median
  - semi-extrinsic 12y ago
    Hmm. How does she know to use the median? What if I alternate between a Cauchy distribution and a lognormal (having different mean and median)? (Very apropos nick, by the way)
- mikeash 12y ago
  I'm not particularly familiar with this so the odds of the following being correct are not terribly great.... As far as I can tell, the interesting properties of the Cauchy distribution come from the "fat tail," which means that large numbers are relatively more likely than if you used, for example, a gaussian distribution. This is going to cause problems when applying it to this case because you can't sleep arbitrarily long. There will have to be some sort of ceiling on it, and I think that will bring the behavior back into a realm where the attacker can make use of it. As to your question in your other reply about how the attacker will know to use the median instead of the mean, is there any distribution where using the median wouldn't work? If not, the attacker could just use the median as a matter of course. The idea posted here is interesting: https://news.ycombinator.com/item?id=9264760 https://news.ycombinator.com/item?id=9264760 Basically, have the artificial delay be unpredictable to an attacker, but constant for any given input. You'd still have to watch out for inputs which are computationally equivalent but not bytewise equal, but perhaps that can be managed.

fchollet 12y ago

How about random sleeps distributed so that the mean sleep time is always the same for every computation? (and much longer than any likely computation). timer.start(); computation(); time = timer.stop(); sleep(random_centered_on(mean-time));

deleted 12y ago
[deleted]
TheLoneWolfling 12y ago
For one thing, that means that your performance is horrible. And it doesn't prevent against indirect sidechannels. For instance, seeing how long other requests take.

saidajigumi 12y ago

This is only if the channel is a purely-external measurement of the computation, e.g. total turnaround time time to a result. A sleep won't do anything to mask a side-channel which involves (sometimes obscure) access to the actual work being done by the processor.

ewindisch 12y ago
Up-voting the parent. There are attacks such as FLUSH-RELOAD which are today difficult to avoid on modern hardware and allow this sort of introspection into the CPU instructions and their timings. Of course, there are a whole range of active and valid side-channels that are readily exploitable today. These are no longer NOBUS vulnerabilities, but are increasingly within the range and scope of ordinary attackers.
- saidajigumi 12y ago
  And relevant to the post re: sleep, there are things like Cross-VM side channels[1], an important consideration given how much infrastructure runs in shared environments these days. [1] PDF: https://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf https://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf
  - ewindisch 12y ago
    Interestingly, the authors of the CCS paper are Yinqian Zhang and Michael K. Reiter. More recently, they've been publishing papers which deepen our understanding of the FLUSH+RELOAD side-channel as I described in my post (F+R was originally discovered by Yuval Yarom).

matthewmacleod 12y ago

That's not an effective technique, unfortunately. You still end up leaking timing information. Lets say you add a small, random sleep after each operation – this still leaks information, as the delay can be averaged out over multiple runs. A fixed sleep after each operation is no use either, for obvious reasons. One approach I've seen is to break time into discrete quanta – for example, you could guarantee that every operation will take an integer number of seconds to complete (i.e. an operation takes exactly 1 second, or exactly 2 seconds, or… scaled as required). There are still statistical techniques to extract timing information regardless, however! The takeaway is the cryptography is really, really hard; system integrity is even harder.

chaosphere2112 12y ago
What if, instead of a random sleep, you have a defined period of time for a function to take– you take a clock reading at the start and end of your execution, and sleep the remainder of the execution time?
- matthewmacleod 12y ago
  The problem there is that sleeping alters the performance characteristics of your system. If an attacker submits multiple requests simultaneously, it would be possible for them to determine if you were actually working, or just sleeping - and you're back to leaking. Sure, every confounding factor makes it more difficult to extract information. But there are many effective techniques for doing so, and we keep getting better at using them.
  - mreiland 12y ago
    > If an attacker submits multiple requests simultaneously, it would be possible for them to determine if you were actually working, or just sleeping - and you're back to leaking. how?
    - matthewmacleod 12y ago
      The basic cause of a timing attack is that if cryptographic operations can take different amounts of time depending on the content, then we can potentially be leaking information to an attacker. If we try to solve this by padding our work using sleep() or similar, we might reveal less information directly – but the performance characteristics of our machine will still be different when we complete and operation quickly then sleep, versus when we complete an option slowly and sleep for less time. Here's a not-at-all real-world example – say an attacker causes a cryptographic operation to happen, while at the same time monitoring the time taken to respond to a ping request. Ignoring loads of complexity, we might find that a machine takes slightly longer to respond to a ping when it is performing an operation (i.e. the CPU is busy) than when it is sleeping. If that's the case, we're suddenly leaking timing information again.