Incorrect statistical test for the timing data

[tomato42]

Few days ago I have published a paper about the Marvin Attack in which I've used timing information to detect secret data leakage in OpenSSL, NSS, GnuTLS, and other libraries.

One of the core contributions of the paper is that timing data is not independent, and thus using tests like the Welch t-test or Kolmogorov-Smirnov test to compare them is not correct (more details are in the Out of the Box Testing paper).

The correct approach is to randomise the order in which the inputs are executed, and then use one of the paired difference tests (sign test, Wilcoxon signed-rank test, bootstrapping of median of differences, etc.) or repeated measurement tests (Friedman test, Durbin test, etc.).

Use of the correct tests also shouldn't require reporting of the raw |t| statistic, but rather could be converted to the standard, and inherently much more easy to interpret, p-value. Bootstrapping of the differences provides the information about the practical precision of the collected data, and thus can be used to say when the data set is big enough to exclude possibility of a side channel (as if it reports precision of below a single clock cycle, a leak is theoretically not possible).

Hope this will help make dudect much more robust and thus useful tool.

[oreparaz]

Thanks @tomato42 for the extensive comment! I agree with the general feeling that there are tons of different statistical tests with very different assumptions. And as you hint different test have different statistical power (sensitivity).

I guess the thing I'm missing is some empirical evidence that those work better. There's no harm of running several distinguishers in parallel, but I usually tend to pick the simplest. Want to implement some of these?

[tomato42]

My point is not about using tests with different statistical power. My point is about using the correct test for data at hand.

If you don't use the correct test for the data, then you will be getting false positives or false negatives. The test will be simply unreliable in the general case.

The empirical evidence is in the linked paper. Other example you can find on Cross Validated.

Now, will using a wrong test work when the difference is large, but the correlation is small? Yes, it will appear to work. But you won't be able to get large p-values consistently when there is no difference (for example when testing a function with two identical inputs).

Finally, no, I don't want to implement them, I already have implementation of them in tlsfuzzer.

[oreparaz]

Thanks for your input @tomato42. One thing that would be useful is to implement some of the tests that you mention and plugging them in parallel. Going to leave this open in case anyone wants to take a stab.