Check for more kinds of timing correlation in (EC)DSA

[adampetcher]

The DSA timing test in DsaTest.testTiming() (and the equivalent ECDSA test) currently looks for small k values that are correlated with short timings. I would like to suggest the following enhancements:

1. Look for correlation between large k values and longer timings. I could imagine countermeasures that introduce some artificial delay, but not enough to cover the time of the longest executions. If the test had another loop that looks at increasingly small groups of executions with large timings, then it would be able to identify problems like this.
2. Look for inverse correlation between timing and the size of k. I have encountered countermeasures that introduce a large amount of delay, but only when k is small. So smaller k values (below some threshold) actually produce longer timings.

[bleichen]

Sorry for not answering earlier.
You are right. The current test checks just for one common implementation flaw:
using modular exponentiation with a variable length exponent.
OpenJdk CVE-2016-5548 and BouncyCastle CVE-2016-1000341 failed this test.
The problem I have here is that checking for timing attacks in a unit test environment
is quite difficult because the setup adds a lot of noise and the maximal time to test
an implementation is limited. Probably, I'm also not using the best tools.

The test is not looking a samples with large timings since large timings are often because
of some warmup phase and possibly unrelated events like garbage collections.

I'll the code so that it checks for inverse correlations between timing and the size of k.

In any case, I don't see a good way to check for smaller timing differences with the given
setup. There is just too much noise. In particular, there is no test for timing differences
of RSA computations, simply because my attempts so far to measure such timing differences
failed to produce results.

[adampetcher]

Thanks for the response. These are only suggestions based on my analysis of CVE-2016-5548. Feel free to resolve/close this issue at any time.

I see your point about the large timings, and I agree that this is complicated by the noise that comes from warmup/JIT/GC/etc. I found a test that looks at large timings useful, but I wasn't running it in a regression test environment, and I could give the test a lot more time in order to get useful results. Still, it may be worthwhile to investigate how to do this (if you have some spare time to do so). I worry that implementers will include countermeasures that get this test to pass, but the countermeasures introduce different timing issues that are not considered by the test.

[bleichen]

Yup. Unfortunately, there is a chance that an implementer adds countermeasures that will not be detected by this test.

The timing differences that are necessary for failing the tests are in the order of 10'000 ns, which is also about what one gets if modular exponentiation or point multiplication is used without any countermeasures. Hence the test is quite weak. But increasing the test time (which can be done by changing the constant samples in testTiming) likely has the result that the test itself is disabled in continuous tests.

Since detecting timing differences that are n times smaller requires about n^2 times more samples, it seems hopeless to me to get good results with the current test. However, the tests don't have to simulate an actual attack, they just have to detect weak implementations. This may allow to use information that are typically not available to an attacker. E.g. one option to consider is to profile signature generation and check if k correlates with the number of internal function calls.