Timing attacks: When the time to complete two different tasks are statistically indistinguishable

Question

This question is related to the open source security package for node/Javascript called credentials, and in particular how to evaluate whether a comparison of two strings is "constant time", though the test being sought would theoretically apply to every implementation of a constant time function.

Timing attacks reveal the secret keys used by secure communication channels, and are particular pernicious because they can occur online - often without detection. In essence the time of an activity can reveal the secret keys that power public key crypto, for example when an HMAC is given an incorrect key it can take a different amount of time depending on how much of the key is incorrect (with more correctness taking a longer period of time since more comparisons occur before inequality is detected). This is the naïve timing attack; there are much more sophisticated versions that could theoretically detect differences even when one has supposedly constant-time algorithms. It is these sophisticated cases about which we are particularly concerned.

An excellent talk on this topic is: Black Hat USA 2010: Exploiting Timing Attacks in Widespread Systems by Lawson/Nelson. While not the most up-to-date publication, the information in that talk remains relevant and forms the basis for the numbers and assertions in this question.

The significance of timing attacks cannot be overstated. Not long before the presentation the vast majority of civilian encrypted http/web based communication was vulnerable to these timing attacks, essentially meaning that there were no secret communications over the web. Much effort has been made to fix these attacks, with the most common solution being constant-time comparisons of the sort referred to in credential.

Because these attacks occur over the network, there is a lot of jitter. One model to weed out the jitter and get to the raw timings is to use a "box model" t-test that chops off the top and bottom percentiles of the data in terms of response-time. Owing to the automation, the sample sizes can be astronomically large, as the vast majority of potential targets do not test for or block the type of failures that reveal these secrets.

So the essential question would seem to be: Can one detect, based on how many ns it takes to perform a comparison, whether one is comparing equal or inequal strings of characters. A bad compare function will have wildly different run-times depending on the difference in string lengths and the position of the first inequal character, but a good function ought to have effectively indistinguishable run-times (i.e. it should call the exact same instructions, and they should not be optimized away by the compiler/CPU/cache).

We can generate with significant precision the timings of the local compare functions, in the example case with process.hrtime, which gives us the ns (and we do not have to deal with the network jitter, but there will be variation).

The Black Hat 2010 conference indicated that timings as little as 15ns are detectable with 9,000 samples over even jittery networks with sufficient samples. Additional samples similarly eliminate the benefit of adding random delays. One ought to presume that attackers will have essentially unlimited samples.

@whuber suggested the following as the test:

1. all strings have

   1. comparable mean processing times; and
   2. comparable timing variations; and

2. no strings ever will be processed in unusually short times.

Subject to further input and clarification, I believe this is essentially correct. The second question is easy to answer, but the first question is more difficult.

Answer 1

The question has been answered by @whuber in a series of comments. I would like to add a couple of comments that might be helpful:

For making two tasks statistically indistinguishable in a scenario where an attacker has unlimited access to the system, I think you would need to make sure that not just their means are indistinguishable, but their entire probability distributions of the processing times. One simple way to verify this visually is to compare the histograms of the two samples belonging to your respective tasks. Alternatively you could also compare the cumulative distribution functions (CDF) of the processing times for the two tasks.

There is a statistical test to verify whether two empirical distributions come from the same underlying distribution - the two-sample Kolmogorov-Smirnov test. You might want choose this test to compare the samples of your processing times since the t-test actually assumes that the processing times of the two different tasks follow a normal distribution and while there is whole set of tests out there for equal variance, most of them assume normality of the underlying distribution as well (though sometimes tolerating smaller, or greater departures from normality).

To illustrate the point (using R):

> seed <- 432
> library(distr)
> D <- DExp(rate = 1)

> # simulate samples from task A (follows a Laplace distribution) and B (follows a Gaussian)
> x_a <- r(D)(1000)
> x_b <- rnorm(1000,mean(x_a),sd(x_a))
> 
> # we can verify that the means and standard deviations are very similar
> mean(x_a)
[1] 0.08802492
> mean(x_b)
[1] 0.08622842
> sd(x_a)
[1] 1.433169
> sd(x_b)
[1] 1.441664
> 
> # the t-test detects no difference of course
> t.test(x_a,x_b)    

        Welch Two Sample t-test    

data:  x_a and x_b
t = 0.0279, df = 1997.93, p-value = 0.9777
alternative hypothesis: true difference in means is not equal to 0
95 percent confidence interval:
 -0.1242732  0.1278662
sample estimates:
 mean of x  mean of y 
0.08802492 0.08622842     

But if we look at the densities of x_a (in red) and x_b (in green) we notice that the two samples are probably not from the same task:

> # let's check the density function (smoothed histogram) and the empiricical CDF of our samples
> plot(density(x_a),col=2)
> lines(density(x_b),col=3)
> 
> plot(ecdf(x_a),col=2)
> lines(ecdf(x_b),col=3)

We can also confirm this formally using the K-S test, which would refute the null hypothesis that sample A and B were drawn from the same continuous distribution.

> ks.test(x_a,x_b)    

        Two-sample Kolmogorov-Smirnov test    

data:  x_a and x_b
D = 0.081, p-value = 0.002829
alternative hypothesis: two-sided

Do you need to go and compare histograms now? I don't think you need to care about the attacker being able to distinguish between two tasks based on their processing times, as that information is made available anyway!? The real question is whether an attacker can learn the function $f$ of your algorithm which maps the proportion of correctness $p$ in the key to the processing time $t$. My real goal would be to ascertain that if I process a many different keys with different proportion of correctness and estimate the function $p = f(t)$ it wouldn't be useful for gradually improving the proportion of correctness in a fake key.

Distinguishing tasks with the t-test

Regarding the t-test for distinguishing two tasks $A$ and $B$, where the sample mean processing time of $A$ is $\hat{X}_A$ and time of $B$ is $\hat{X}_B$. The two tasks will be always distinguishable in your use case in terms of the difference of sample means $d = \hat{x}_A - \hat{x}_B$ if you use a two-sample t-test. The power $\pi$ of the t-test (the probability to detect a difference if there really is one):

$\pi(d,n,m) = P(\text{detect difference} | \text{difference exists})$

is an increasing function of the number of observations $n$, meaning that with sufficiently many samples you can detect arbitrary small differences in the mean processing times of the two tasks with very high probability (see details below).

I hope this sheds light on

The Black Hat 2010 conference indicated that timings as little as 15ns are detectable with 9,000 samples over even jittery networks with sufficient samples.

in particular that given any amount of (finite) network jitter (variance) you can detect any timing difference with finitely many data samples.

You can do the power calculation also the other way around, where you fix a certain power and ask what is the required sample size to achieve it. But as @whuber pointed out this concerns only the difference in the means.

Power two sample t-test:

In the case where the variance $\sigma$ is known and the samples of both tasks have equal size $n = m$, the group means have a normal distribution $\hat{X}_A - \hat{X}_B ∼ N(d, 2σ^2/n)$

$\pi(d,n) = P(Z>z_{α/2} − d/\sqrt{2σ^2/n}) + P(Z < −z_{α/2} − d/\sqrt{2σ^2/n})$

Answer 2

Ok, here's what I did: I used a t-test with a mu of 15 and an alpha of 0.001 with the library ttest on the arrays of nanosecond timings of comparing strings that are equal, inequal (same lengths), and inequal (differing lengths).

If I understand the terminology and execution correctly, if the ttest is "valid" (i.e. the p-value is greater or equal to the alpha value) the sample sizes are considered equal with a variation of 15ns (mu) and a confidence of 99.999% (being 1 - alpha×100%).

The result appears to be as expected; if I introduce variations of timing then the tests I've put together fail. Not being very steeped in stats though, I would be grateful for validation that the methodology and execution is what one would ordinarily do to achieve the desired result.