[Cryptography] Defeating timing attacks

[Arnold Reinhold]

On Fri, 14 Jul 2017 17:53 John Denker wrote:

> Furthermore, a much better way to defeat timing attacks is already
> known:
> a) use a dedicated machine,
> b) inside a Faraday cage, and
> c) emit the results at some pre-arranged time.
> 
> That's because
> a) in a multi-tasking environment, one task can spy on another
> b) timing isn't the only issue;  there are other side-channels
> c) you don't need to defeat the timing attack on an instruction-
>  by-instruction basis, just on a message-by-message basis.
> 
> Things get a little trickier in interactive situations (as opposed
> to file-sized messages) but still manageable.
> 
> This approach means you don't need to argue with the hardware
> designers and compiler designers.  They do their thing, and you
> do yours.

That is an excellent approach, but it can’t be the only answer. First, as you say: “... this still
requires tremendous attention to detail.” And not just in design and manufacture. A careless repair technician can defeat a Faraday cage by failing to replace one screw (that tiny one that fell behind the desk). A malicious tech can turn an RF gasketed seam into a slot antenna with a few drops of clear nail polish. Not all applications of cryptography can afford the extra costs or long term maintenance requirements. So addressing timing attacks through software design is part of a sensible belt and suspenders approach.

You are correct that:

> Randomizing the timing just turns the attack into a statistics
> problem.  The NSA is reeeeeally good at statistics.  You can
> "somewhat" slow down the leak, but it's still a leak.

Another way of saying that is randomizing the timing is equivalent to X decibels of shielding. How big an X can be achieved is a valid subject for research. There is no reason why one couldn’t put a crypto module in a test cell with appropriate sensors (RF, power line, and acoustic, with shields and filters removed) and allow the compiler to download different instructions configurations and make adjustments based on computed correlations between recorded test data and the signals we are trying to hide. If this process takes hours or weeks, so what?

Again as you say: "There is a rather long list of ways bad guys could exfiltrate information about your message, and you have to stop them all.” I don’t have to come up with every possible approach to argue that cooperative compilers could reduce the risk of many of those exfiltration paths. and certainly not to insist that crypto designers must have end-to-end control of the software that is put into production, lest the task become insurmountable.

Arnold Reinhold