Information-theoretic bound on leakage by timing measurement

Question

I'm looking for an information-theoretic bound on leakage by timing measurement. I'm assuming that an attacker

• wants to leak out of a black box a secret key of $k$ bits that is secretly injected into the black box;
• has written the black box's code (which can read the key and act accordingly), and can craft this code to the point of choosing the duration of a function performed by the black box among $n$ equally spaced durations $t_j=t_0+j/(n-1)$, $0\le j<n$ ($t_j$ is in units of clock period), with $t_0$ known;
• can measure the duration of that function with an uncertainty $u$ according to some distribution $U$, with $|u|<1/2$ unless otherwise stated, at each execution of that function.

and I'm looking for a tight upper bound on the number of timing measurements to leak the whole key (so that I can be sure that some of $k$ remains secret if we are below that bound).

An execution leaks at most $\log_2(n)$ bit worth of information by way of timing measurement, thus at least $\lceil k/\log_2(n)\rceil$ timing measurements are required to fully extract the key by that sole mean. That bound can be reached if the attacker further has $\big\lceil\log_2\big(\lceil k/\log_2(n)\rceil\big)\big\rceil$ bits of permanent storage in the black box that survive function execution, and are initially zero (sketch: we write the key $k$ in base $n$, and the permanent storage is used for a counter telling which digit of $k$ is leaked).

Update: I realize that the above bound of $\lceil k/\log_2(n)\rceil$ measurements also applies if the attacker can choose the input of the black box and have the code act accordingly; this makes Q1 and Q2 below far less relevant.

_{Q1: What if the attacker's code does not have any permanent storage, only a true random number generator internal to the blackbox? What's even an appropriate way to characterize the number of measurements required to leak the key?}

_{Q2: What if in the situation of Q1, the attacker also obtains in addition of each timing measurement some large random input or output of the black box, also available to the attacker's code?}

Q3: What if the attacker's uncertainty distribution $U$ becomes significant? Perhaps, consider that $U$ is the discrete uniform distribution on $[0\dots m-1]$; or $U$ is Gaussian; or something in between, like $U$ is the sum of two or three discrete uniform distribution on $[0\dots m-1]$.

---

Rationale: My true goal (hopefully reached is we can answer Q3 under the conditions of Q2) is assessing the demonstrable effectiveness of a countermeasure to timing attacks in Smart Cards (assumed running synchronously), consisting of inserting a random pause after a sensitive operation, as in Q3. The hypothesis that the attacker has written the code is of course a worst case scenario, crafted in order to obtain an upper bound of the leakage (a lower bound on the number of measurements necessary).
_{Q2 is asked because, in a real situation where the attacker did not write the code, it is reasonable to believe that there is no equivalent to permanent storage usable by the attacker, but that input (or output) has a deterministic effect on timing. Q1 is an introduction to Q2, without that data dependency.}

Answer 1

As you say, if the measurements are accurate then the device can leak $log_2(n)$ bits of information on each invocation. If it lacks internal storage then it can't track which parts of the key it has already leaked. What it can do is leak a random set of bits, but the recipient has to know which bits they are. I see two approaches.

If the timing channel is the only communication, then the $m = log_2(n)$ bits has to combine both key data ($d$ bits) and position ($p$ bits). If position indicates which group of $d$ bits we are leaking, then $p >= log_2(k/d)$. So for a 256 bit key this scheme requires that you be able to leak at least 9 bits at a time: 8 bits to indicate the key position and 1 for that key bit. The position bits would be randomly generated.

Another approach would be to communicate the position differently: instead of using an RNG to select the position and include that in the leaked data, you could use data from the ciphertext if your threat model includes the attacker seeing that. You could use the first $p$ bits of the ciphertext to choose/signal which key bits we are leaking, where $p = log_2(k/m)$.

In both cases, the solution to how long it takes to leak all $k$ bits of the key is given by the Coupon Collector's Problem, which is $O(n log n)$. In the second example, this should come out to $O(k/m log(k/m))$. Of course you don't have to wait to collect all of the sections. Especially with a low bandwidth channel it would make sense to start brute-forcing as soon as feasible.

Answer 2

For Q1, you could leak the key efficiently by using something like a fountain code (which are conceptually similar to secret sharing schemes).

For example, you could map the key to the coefficients of a polynomial $p$ over a finite field $F$ (of suitable size), evaluate it at a random point $a \in F$ (or $a \in S$ for some subset $S \subset F$), and leak $a$ and $p(a)$ (or possibly several such pairs). Once the number of distinct points leaked equals the order of $p$, interpolation should allow reconstructing $p$.

For Q2, you could derive the random points $a$ from the known input. This saves you from having to leak them, and thus allows you to leak (up to) twice as many useful bits per execution.

Q3 seems to be a coding theory problem. Basically, treating the timing measurements as a noisy channel, you want to pick an encoding that gets as close as possible to the Shannon capacity of the channel.

Note that the encoding scheme suggested above for Q1 already provides a kind of an implicit error detection and correction mechanism: if you extract a few more data points than strictly needed, and interpolate the polynomial based on all of them, you can tell if there are any errors by the fact that the resulting polynomial will (with high probability) have a degree higher than expected. If the number of errors is small, it's even possible to detect which points are wrong simply by testing which subset of the points yields the correct reconstruction. That said, especially for higher error rates, you might also want to simply apply a conventional error-correcting code on top of the fountain coding.