3
$\begingroup$

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 exact 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 form of clock jitter, power-supply sag etc.

The real question seems to be not whether information leaks out, but whether the secret pieces 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 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 side-channels that weren't discovered, but the connections to the outside 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?

$\endgroup$
  • $\begingroup$ I realise that there are applications where you definitely can't have lots of random performance fluctuations – anywhere where consistent low latency matters. But these applications value deterministic runtime for its own sake. Many other applications don't much care for latency at all though, as long as average throughput is good. These are the settings to which my question would apply. $\endgroup$ – leftaroundabout Jun 9 '18 at 11:46
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ By exponential I didn't mean “a signal-noise ratio $S/R$ makes it $\mathcal{O}(e^{S/R})$ inefficient to intercept messages” (which as you say it doesn't), but “it makes it $\mathcal{O}((S/R)^{2\cdot\ell})$ inefficient to intercept a message of length $\ell$”. Of course this only holds if you need to crack each bit (or at least each chunk) of the message sequentially; when you can just intercept a whole transmission, know where each bit is and can attack each one individually then it's much easier, but that I would consider quite strong a-priori knowledge. $\endgroup$ – leftaroundabout Jun 10 '18 at 10:27
  • $\begingroup$ "If you need to crack each bit of the message sequentially"; you mean in parallel. In any case, the standard assumption in crypto is that the attacker knows everything about the system other than the key (and random data chosen as a part of the encryption process); it is assumed that the attacker knows how the implementation is constructed. And, if you assume that the random data used to obscure the message prevents attacks, you need to show that it does it completely, difficult for randomly constructed systems. $\endgroup$ – poncho Jun 10 '18 at 17:21
2
$\begingroup$

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. Asynchronous LUT 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.

$\endgroup$
  • $\begingroup$ I was under the impression that things such as "dual rail encoding" didn't have a precisely constant current draw. Certainly, it is considerably closer to constant than standard gates, however if the current variation for dual rail is 1% (warning: number I just made up, not an indication of how it performs in practice) of the variation with standard gates, that implies that the attack needs 10,000x as many samples to filter out the noise; this may be doable. $\endgroup$ – poncho Jun 9 '18 at 18:33
  • $\begingroup$ @poncho You are correct on all counts. however, dual encoding helps, but the caveat is that 'it depends'. If you have an older process, the mobility ratio of nFET to pFET is 1:2, and the threshold mismatch tends to be better. This is where dual rail encoding really helped because it was obvious what the state was by comparison. With modern processes, you have undoped channels so your mobilities are similar but your thresholds are all over the place. I'm sure there's a way to extract the data from the noise, but just not with the current state of the art test and measurement equipment. $\endgroup$ – b degnan Jun 10 '18 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.