5 ms·

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 – th

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.
      - mreiland 12y ago
        I don't see it. I get what you're saying, but how does latency not swallow that difference? Or load balancing, or routing through the internal network behind the router. It's really hard for me to buy that an attacker can determine the execution characteristics of your crypographic functions via ping over the internet.
        renfredxh 12y ago
        He/she said "ignoring loads of complexity". It was a gross oversimplification, but over thousands of trials it is possible to extract the information using a similar method.
        mreiland 12y ago
        I'm interested in reality, not an oversimplification for academic reasoning. I thought that was clear.
        matthewmacleod 12y ago
        It's not much of a stretch from the Lucky 13 attack (http://www.isg.rhul.ac.uk/tls/TLStiming.pdf http://www.isg.rhul.ac.uk/tls/TLStiming.pdf) to something like I described – it might be worth having a look at that paper if you're interested in seeing how much information can be extracted from delicate timing changes! I understand your scepticism, but there have been a fair few timing attacks showing the viability of this approach.
  - zvrba 12y ago
    A remote attacker is only able to measure total predetermined latency T = t_work + t_sleep. (Actually, he will measure T + t_noise [network, etc.]). By what means can he determine which percentage of T+t_noise was spent in actual work?
JonnieCache 12y ago
The solution i've seen is: sleep(float(hash(request_content)) % n) this assumes that the attacker cannot control any non-relevant part of request_content.
- nickodell 12y ago
  This seems like it's insecure if the attacker can predict request_content, too.
  - TheLoneWolfling 12y ago
    That's secure as long as the hash is (securely) salted.
- matthewmacleod 12y ago
  As far as I can tell, that would not be secure – wouldn't it end up being essentially cryptographically secure random timing noise? We already know that random jitter doesn't work, because it can be averaged out given enough samples. I'm not a cryptography guy though, so I could well be wrong!
  - TheLoneWolfling 12y ago
    It cannot be averaged out, as there is no way to take multiple samples. Look at it: for any specific input it always sleeps for a deterministic amount of time. Unlike random timing noise, which can be averaged away. You take averages and all you know is the value of (actual time + some unknown value) very precisely. That doesn't help you. (He is, however, missing that it should also have a random salt, generated once and stored.) Of course, this is still breakable most of the time.
- deleted 12y ago
  [deleted]

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.
    - mreiland 12y ago
      I don't see it. I get what you're saying, but how does latency not swallow that difference? Or load balancing, or routing through the internal network behind the router. It's really hard for me to buy that an attacker can determine the execution characteristics of your crypographic functions via ping over the internet.
      - renfredxh 12y ago
        He/she said "ignoring loads of complexity". It was a gross oversimplification, but over thousands of trials it is possible to extract the information using a similar method.
        mreiland 12y ago
        I'm interested in reality, not an oversimplification for academic reasoning. I thought that was clear.
      - matthewmacleod 12y ago
        It's not much of a stretch from the Lucky 13 attack (http://www.isg.rhul.ac.uk/tls/TLStiming.pdf http://www.isg.rhul.ac.uk/tls/TLStiming.pdf) to something like I described – it might be worth having a look at that paper if you're interested in seeing how much information can be extracted from delicate timing changes! I understand your scepticism, but there have been a fair few timing attacks showing the viability of this approach.
- zvrba 12y ago
  A remote attacker is only able to measure total predetermined latency T = t_work + t_sleep. (Actually, he will measure T + t_noise [network, etc.]). By what means can he determine which percentage of T+t_noise was spent in actual work?

JonnieCache 12y ago

The solution i've seen is: sleep(float(hash(request_content)) % n) this assumes that the attacker cannot control any non-relevant part of request_content.

nickodell 12y ago
This seems like it's insecure if the attacker can predict request_content, too.
- TheLoneWolfling 12y ago
  That's secure as long as the hash is (securely) salted.
matthewmacleod 12y ago
As far as I can tell, that would not be secure – wouldn't it end up being essentially cryptographically secure random timing noise? We already know that random jitter doesn't work, because it can be averaged out given enough samples. I'm not a cryptography guy though, so I could well be wrong!
- TheLoneWolfling 12y ago
  It cannot be averaged out, as there is no way to take multiple samples. Look at it: for any specific input it always sleeps for a deterministic amount of time. Unlike random timing noise, which can be averaged away. You take averages and all you know is the value of (actual time + some unknown value) very precisely. That doesn't help you. (He is, however, missing that it should also have a random salt, generated once and stored.) Of course, this is still breakable most of the time.
deleted 12y ago
[deleted]