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.