5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As technology evolves, that 25 µs tolerance might soon look inadequate. Why not just introduce random variation in the timing of the string-comparison function itself? A tiny bit of such variation will make it far more difficult for even a large statistical analysis to detect and capitalize on unavoidable timing variations. $\endgroup$ – whuber Jan 7 '15 at 19:29
  • $\begingroup$ You are right: but the point is that there are diminishing returns. If you can double the standard deviation, you will quadruple the sample size needed, etc. This favors you versus the attacker, because for a given slow-down in verifying credentials you achieve a quadratic slow-down in the time needed for the attack. It is interesting to hear that 25 µs is a physical limit. Since light can travel 7.5 km in that time, it's a curiously high limit! Since your title refers to nanosecond results, perhaps you meant to write 25 ns instead? $\endgroup$ – whuber Jan 7 '15 at 20:40
  • $\begingroup$ The reduction in speed in copper is of little consequence: see en.wikipedia.org/wiki/Velocity_factor. Note that a limit in resolution does not necessarily impose a limit in how well one might estimate timing differentials. From your quotation I will emphasis this passage: "... we can (and should) assume that a higher sample size would offer an even better resolution." Your edit remains very confusing: where does "15µs" come from, given that none of your quotations mentions that number? (Note that it equals 15000 nanoseconds.) $\endgroup$ – whuber Jan 7 '15 at 21:40
  • $\begingroup$ Just to clarify, are there strong practical objections against the approach of always processing every request in time equal to the evaluation as if the key would be correct? After finding non-matching parts in the submitted key the algo could simply continue comparing the full key. I would presume the majority of all requests on the web happens with correct keys (most current browsers store the credentials). Otherwise you always leak information, even with countermeasures (manipulating the processing time of invalid keys). $\endgroup$ – means-to-meaning Jan 14 '15 at 11:26
  • 2
    $\begingroup$ ok. got you! basically the constant-time algorithms you are mentioning are aimed to be constant time by design, but aren't. Seems a bit weird that you are mentioning compiler and CPU as I would assume you are only looking to have constant processing time relative to a single machine (same CPUs) and single software instance (same compiled binary)!? The information leakage I was referring to was for the case if you don't use a constant-time algorithm so you can disregard it. $\endgroup$ – means-to-meaning Jan 14 '15 at 16:56
4
+50
$\begingroup$

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)

CDF

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})$

$\endgroup$
  • $\begingroup$ Awesome comments. KS-test it is. :) $\endgroup$ – Brian M. Hunt Jan 14 '15 at 17:09
  • 1
    $\begingroup$ +1 Excellent analysis and discussion. (I do not consider my comments to be any kind of answer, BTW--they were only trying to probe into the nature of the question.) $\endgroup$ – whuber Jan 14 '15 at 17:57
  • $\begingroup$ I have implemented the test, but am unsure how to interpret the results (I've only vague notions based on experimenting with it), so I added a related question: stats.stackexchange.com/questions/131304 :) $\endgroup$ – Brian M. Hunt Jan 14 '15 at 19:09
  • $\begingroup$ The null hypothesis for KS test is that sample A and B were drawn from the same continuous distribution. Pick a value alpha for the percentage of cases you are willing to accept where no difference in distributions exists despite one being reported by the test (false positive). Write it down, run the test, and if the p value is small (p-value < alpha) then the test evaluates to distributions being different -> you just detected an unwanted difference! $\endgroup$ – means-to-meaning Jan 14 '15 at 19:29
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A t-test does not appear to be called for here. You originally framed the question in terms of assuring there would be no variances greater than 15 ns. A t-test merely compares averages, not amounts of excursions. Maybe this is a matter of interpretation: precisely what do you mean by "differences of 15 ns" in the question? Rather than a long-run average difference, it would seem to refer to variations among individual calls: "whether the string comparison function takes the same amount of time in all cases (within 15ns or so)?" $\endgroup$ – whuber Jan 8 '15 at 21:01
  • $\begingroup$ @whuber - thanks for the comment. Sorry I am not very precise in my language. I think the question is: Can one detect, based on how long it takes (in ns) 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). $\endgroup$ – Brian M. Hunt Jan 8 '15 at 21:24
  • $\begingroup$ Does that help clarify at all? $\endgroup$ – Brian M. Hunt Jan 8 '15 at 21:24
  • $\begingroup$ That is extremely helpful. Perhaps you could edit your question to incorporate those thoughts? But it seems to bear out my initial interpretation and still suggests that a t-test has only partial relevance. You also want to assess variability. You might need to do that in a nonstandard way. It strikes me that your objectives will be beautifully achieved provided (a) all strings have comparable mean processing times and comparable timing variations; and (b) no strings ever will be processed in unusually short times. $\endgroup$ – whuber Jan 8 '15 at 21:53
  • $\begingroup$ @whuber - Very good. Once I figured out what the devil I'm talking about I planned on revising the question (and when I have done that encourage any edits that may improve it would be most welcome). Variability is indeed another vector, I had not even thought of. I am mulling your proposal and will post more when I have given it some thought. $\endgroup$ – Brian M. Hunt Jan 9 '15 at 0:43

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.