4 ms·

Unfortunately, trying to defeat side-channel attacks by adding random noise usually only increases the number of samples required to extract information, rather

Unfortunately, trying to defeat side-channel attacks by adding random noise usually only increases the number of samples required to extract information, rather than preventing the attack entirely. (You can blame the central limit theorem for this.)

matthewdgreen 4y ago
This is not entirely true. Or rather: it is true when the countermeasure is to add random delays to pad out overall timing, since one can simply collect more samples to obtain an average. And that may be what the OP is suggesting: just scale the frequency to random levels that are not quite the pre-programmed ones, which is very similar to adding random delays. (In practice this might actually work well enough to defeat delicate attacks.) However what I hoped the OP was suggesting is to add random instructions as a way to prevent the processor from switching power modes: sort of like tapping your phone screen occasionally to keep it from dimming. There are also other (unrelated) techniques that use randomness to eliminate side channels. One of the most basic anti-timing-attack countermeasures is to use RSA blinding in which a base C is first randomized by computing C^r mod N before that (random) result is combined with the secret key. The randomness can then be removed from the final result. This defeats attacks that depend on choosing or knowing the value C.
- abiro 4y ago
  How about making operations constant time in application code by picking an upper bound which is acceptable for the application, but that is certainly longer than the actual CPU computation and then waiting until the upper bound to return the result? Eg. my app is performing digital signatures and I'm sure that they take <1ms CPU time, but performing digital signatures in 10ms is acceptable for my application, so when I perform a signature I measure the CPU time elapsed, say 0.5ms and then wait for 9.5ms.
  - matthewdgreen 4y ago
    What you are describing is called “quantization”. It has some disadvantages, one of which is that people tend to disable it the second they hit a use case that requires better performance. It is also sometimes possible to distinguish “doing nothing and waiting for a timer” from “actively computing the result” if you have other access (eg you can measure response time by making another connection.)
kelseyfrog 4y ago
Does that necessarily mean that all is lost? It sounds possible to arbitrarily extend the time necessary. Don't we already do this when we choose encryption keys with lengths that take an arbitrary amount of time to crack by brute force?
alanh 4y ago
100% correct

matthewdgreen 4y ago

This is not entirely true. Or rather: it is true when the countermeasure is to add random delays to pad out overall timing, since one can simply collect more samples to obtain an average. And that may be what the OP is suggesting: just scale the frequency to random levels that are not quite the pre-programmed ones, which is very similar to adding random delays. (In practice this might actually work well enough to defeat delicate attacks.) However what I hoped the OP was suggesting is to add random instructions as a way to prevent the processor from switching power modes: sort of like tapping your phone screen occasionally to keep it from dimming. There are also other (unrelated) techniques that use randomness to eliminate side channels. One of the most basic anti-timing-attack countermeasures is to use RSA blinding in which a base C is first randomized by computing C^r mod N before that (random) result is combined with the secret key. The randomness can then be removed from the final result. This defeats attacks that depend on choosing or knowing the value C.

abiro 4y ago
How about making operations constant time in application code by picking an upper bound which is acceptable for the application, but that is certainly longer than the actual CPU computation and then waiting until the upper bound to return the result? Eg. my app is performing digital signatures and I'm sure that they take <1ms CPU time, but performing digital signatures in 10ms is acceptable for my application, so when I perform a signature I measure the CPU time elapsed, say 0.5ms and then wait for 9.5ms.
- matthewdgreen 4y ago
  What you are describing is called “quantization”. It has some disadvantages, one of which is that people tend to disable it the second they hit a use case that requires better performance. It is also sometimes possible to distinguish “doing nothing and waiting for a timer” from “actively computing the result” if you have other access (eg you can measure response time by making another connection.)

kelseyfrog 4y ago

Does that necessarily mean that all is lost? It sounds possible to arbitrarily extend the time necessary. Don't we already do this when we choose encryption keys with lengths that take an arbitrary amount of time to crack by brute force?

alanh 4y ago

100% correct