5 ms·

Adding random delays does not remove signal; it only adds noise. Noise can be removed by simply performing more trials.

by stouset 12y ago

Narishma 12y ago
The delays aren't random. They last just enough so that the function always takes the same amount of time, presumably the worst-case amount of time.
- dllthomas 12y ago
  'If that's deemed too heavyweight, you can just add "delay" as a random amount of computation overhead (say a loop that does nothing but does not get optimized away).' If the delay here is not meant to be random, what is the "that" being contrasted against? I understood "that" to be what you say, which would imply this is something different.
- tedunangst 12y ago
  > presumably the worst-case amount of time. Determining the the worst case amount of time is far from trivial. What's the slowest amount of time it takes lookup table based AES to decrypt a block? The only answer to that question is to measure it a bunch, then pick some percentile and hope your margin of safety is sufficient. Or you could use a constant time algorithm to start and rely less on hope.
  - eps 12y ago
    It is actually quite trivial. You simply align function running time to the worst case _so far_. Start with 0, put it through a warm-up cycle and use it to set a reasonable default. Cache the value between app's sessions, re-initialize when changing the setup.
PeterisP 12y ago
The point is to pad the time to a random amount, not by a random amount. If a particular function by design needs to have a throughput of at least 100 requests/sec, then you ensure that it has a throughput of exactly 100 rq/sec by calculating the response and then busywaiting until 10ms has elapsed - no matter if the actually neccessary things took 1 or 9 ms based on the input, caching and whatever else. Alternatively, you use a secure random to state that this request will respond in exactly x ms - not when some calculations are finished. Again, you need to be sure that your calculations are guaranteed to finish before x, so you need to know the worst case time of your algorithm, but you don't need it to be constant time.
deleted 12y ago
[deleted]
norswap 12y ago
I know, that was my point about making the random delay large enough that recovering the signal would be less efficient than a brute-force attack. And I also suggest a scheme that is about rounding to a fixed delay.

Adding random delays does not remove signal; it only adds noise. Noise can be removed by simply performing more trials.

by stouset 12y ago

Adding random delays does not remove signal; it only adds noise. Noise can be removed by simply performing more trials.

The delays aren't random. They last just enough so that the function always takes the same amount of time, presumably the worst-case amount of time.

dllthomas 12y ago
'If that's deemed too heavyweight, you can just add "delay" as a random amount of computation overhead (say a loop that does nothing but does not get optimized away).' If the delay here is not meant to be random, what is the "that" being contrasted against? I understood "that" to be what you say, which would imply this is something different.
tedunangst 12y ago
> presumably the worst-case amount of time. Determining the the worst case amount of time is far from trivial. What's the slowest amount of time it takes lookup table based AES to decrypt a block? The only answer to that question is to measure it a bunch, then pick some percentile and hope your margin of safety is sufficient. Or you could use a constant time algorithm to start and rely less on hope.
- eps 12y ago
  It is actually quite trivial. You simply align function running time to the worst case _so far_. Start with 0, put it through a warm-up cycle and use it to set a reasonable default. Cache the value between app's sessions, re-initialize when changing the setup.

PeterisP 12y ago

The point is to pad the time to a random amount, not by a random amount. If a particular function by design needs to have a throughput of at least 100 requests/sec, then you ensure that it has a throughput of exactly 100 rq/sec by calculating the response and then busywaiting until 10ms has elapsed - no matter if the actually neccessary things took 1 or 9 ms based on the input, caching and whatever else. Alternatively, you use a secure random to state that this request will respond in exactly x ms - not when some calculations are finished. Again, you need to be sure that your calculations are guaranteed to finish before x, so you need to know the worst case time of your algorithm, but you don't need it to be constant time.

deleted 12y ago

[deleted]

norswap 12y ago

I know, that was my point about making the random delay large enough that recovering the signal would be less efficient than a brute-force attack. And I also suggest a scheme that is about rounding to a fixed delay.