Probable timing leakage detected in dilithium implementation in liboqs library

[koyeerathjoshua]

Hi, I am a graduate student at George Mason University. One of my courses required me to test open source implementations for any security vulnerabilities. In order to test for timing attacks, I and my teammate used a tool "dudect" on the liboqs library . After testing, we found out that Dilithium may have timing leakage. Below attached is the dudect folder containing the test files for all the tested algorithms in liboqs including dilithium. Also attached is our paper which gives a detailed description of dudect and reports the results we have obtained from it. Click here to view the paper published by dudect authors.

Attachments dudect.zip ISA_681_Final_Report.pdf

[david-a-wheeler]

I'd love to hear thoughts about this!

[gregorseiler]

Hi,

Thank you for your interest in timing side channel attacks on Dilithium.

We proposed deterministic and randomized versions of the Dilithium scheme, as each may be useful in different scenarios. The signing time in the randomized version of Dilithium is a random value, due to the rejection sampling, but is independent of the secret vectors (s1 and s2) and the message. If we make the scheme deterministic, then the randomness is generated as H_k(msg) (where H_k, for a random k, is modelled as a random oracle), and thus the signing time will be dependent on the message as well. We believe that this is what is coming through in your experiments.

In particular, for the concrete analysis that you have done, Dilithium fails in what you call the "One-Key-Different-Inputs Test". In this test the average signing time for a fixed (all-zero) message is compared to the average signing time for random messages.

In the case where the message is fixed, due to the default use of deterministic signing in Dilithium, you get the average running time for exactly the same computation and in particular a fixed number of rejections. In the second case where you sign random messages you get an average over random rejections. So it is clear that you see variation in your measurements.

If you want to get rid of the timing dependence on the message you can use the probabilistic signing mode of Dilithium that we describe in the specification and which is available in the official implementation, or use deterministic Dilithium and add a random nonce to your message.

I hope this helps to clarify things.

Cheers, Gregor