Why does side-channel security focus on “shielding” rather than “jamming”?

Question

I have always found it weird when in a crypto discussion people stressed the importance of making algorithms runtime-deterministic, to the point of avoiding any compiler optimisations.

To me, it seems that it's from the start futile to try and completely avoid side-channel information leaking out. Even if an algorithm always takes the same number of processor cycles: the processor is ultimately a coupled bunch of wires, and any signal passing through anywhere will inevitably couple to output connectors in the form of clock jitter, power-supply sag, etc.

The real question seems to be not whether information leaks out but whether the secret pieces of information will be possible to reconstruct. Granted, minimising leakage does always make this more difficult, but it is only one factor. In isolation, even a very small signal can be analysed. Physically speaking, the crucial quantity is the signal-to-noise ratio: if a little bit of signal comes out on a given channel but also a whole lot of random noise, and you have no a-priori way of telling them apart, then extraction of the secret becomes exponentially inefficient.

In particular, for timing attacks, I think it would be a much better approach to not try and make the timing completely deterministic, but instead to make it deliberately completely nondeterministic. The simplest way would be to let the processor randomly intersperse the crypto calculation with nonsense boilerplate instructions (ideally, triggered right at the hardware level with a shot-noise source). The attacks I've read about seem rather delicate and would fail even if only part of the attacker's timings were foiled.

More sophisticated schemes might instead randomise the order of instructions or quickly multitask between many unrelated computations.

All such methods would incur some performance penalty, but it would likely be offset if we were again able to optimise our code without reservations. And we would be safer than with the approach of trying to eliminate any side-channels from forming in the first place. Processors are so complex that there will always be side-channels that weren't discovered, but the outside connections are better to oversee. If, without exception, all connections to the outside are thoroughly jammed, it doesn't matter what side-channels are open inside because only the public signal is strong enough to stand out over the noise floor.

What am I missing? Are these just my thoughts as a physicist and inapplicable to cryptography for some reason?

Answer 1

Physically speaking, the crucial quantity is the signal to noise ratio: if a little bit of signal comes out on a given channel but also a whole lot of random noise, and you have no a-priori way of telling them apart, then extraction of the secret becomes exponentially inefficient.

Actually, it becomes quadratically inefficient.

For example, if you have a signal to noise ratio of 1::1000 (1000 times more noise than signal), then it takes approximately $1000^2 = 1000000$ samples to extract the noise.

Given that:

• 1000 times more noise than signal is quite a lot

• 1,000,000 samples is quite doable in some scenarios

• The implementer would have to be quite careful to make sure that the signal cannot be extracted from the noise in some simple manner

That this approach is generally seen as mostly unworkable (and doesn't immediately address cache-based side channels).

In contrast, just designing the code to be constant time/memory access is, for the majority of primitives we're interested in, isn't that infeasible, and so that's the direction we tend to go.

In contrast, you appear to also be worrying about DPA style attacks, where the attack listens into the electronics (power draw, emitted EMF, etc). Well, we can't actually design gates that literally don't change power dissipation and don't generate EMF while switching, and so in that scenario, the strategy changes. When we do worry about that, the typical strategy is to include randomness, but not randomly (as you appear to be suggesting); adding randomness randomly would leave open the question of whether there is some nontrivial correlation present. Instead, we either:

• Use some mathematical property of the primitive we're using that allows us to include randomness without modifying the answer. As a simple example, to do modexp (where the exponent is secret) over a prime modulus, we may rely on:

$$A^B \bmod P = A^{B+R(P-1)} \bmod P$$

where $R$ is a random value we pick for this computation.

• Use threshold logic; where each logical bit of the computation is expressed as a function (often XOR) of $N$ physical bits, and each physical bit (actually, each set of $N-1$ physical bits) is uncorrelated to the logic bit; we use randomness to translate each logical bit into the actual set of physical bits to represent it.

The first strategy is often used for public key cryptosystems (which often have the internal symmetries we need); the second is usually used for symmetric systems (this strategy is significantly more expensive, however we don't have a cheaper alternative)

Answer 2

As a physicist who mades ICs, and not a cryptographer, I would say that shielding is just much easier. My approach has always been to just not leak information through dual-rail encoding of the circuits. This adds overhead but completely removes the problems of a power attack because the power profile is always uniform (edit: more uniform, see comments). Furthermore, I then remove the clock and make the systems asynchronous, that removes the "clocked" leakage of information. Previously, if I had physical access to the system, I could get your keys. Between decapping the ICs, power attacks, etc, I can basically make something leak or explicitly expose any piece of digital information. I made a career of making things that I cannot hack.

Here's an example of a block from an asynchronous FPGA that was specifically designed to have a uniform power profile. The fact that complimentary signals exist means that there's always the same current for the block.

One of the cool things that you can then do to asynchronous circuits is add noise to the circuit by having an RNG bit stream control some nFETs as switches to change the Poisson process of the charge across a few of the transistors so that even if you have the same numbers and voltages the completion time is different, which further puts your timing into the noise because ultimately, you must interface to a synchronous, clocked system. I cannot buy asynchronous memory from digikey so we have to have reservation stations if things are going off-chip.

The fundamental reason things like this are not done in the commercial market is because it doubles the silicon area for the same function and thereby the cost; however, a good chunk of my work and similar work of others ended up in custom ICs where performance and security were more important than if it was an x86 and ran Windows. If you can get to GoMAC, you'll get to see a lot of cool stuff in this vein.