Timing attacks against the CKS20 discrete Gaussian sampler

[tholop]

I wanted to leave a note about timing attacks in the discrete Gaussian sampler for differential privacy. OpenDP's implementation, which we are using in #578, is based on the CKS20 paper. CKS20 seems vulnerable to some timing attacks, as explained in JMRO22 (published at S&P '22):

Timing Attacks Against Discrete Distribution Samplers: In the second part of the paper we study the primary
method that has been proposed to defend against floating point attacks: discrete versions of the Laplace and Gaussian mechanisms [12], [13]. These approaches employ sampling algorithms that make no use of floating-point representations. We observe that such mechanisms, though defending against floating-point attacks, are susceptible to a timing side channel: an adversary who observes the time it takes to draw a sample can determine the generated noise’s magnitude. When used within a DP mechanism, our attack reveals the noise contained in the result, and thus reveals the noiseless (private) value.

In fact, the full version of CKS20 (https://arxiv.org/pdf/2004.00010.pdf) has a small discussion about this risk in Section 5.4. I don't think that OpenDP implements the mitigation mentioned in that section (terminate after a predetermined runtime). Another mitigation suggested by JMRO22 is to sample noise offline, which might not be always doable. There are also implementations in lattice cryptography that do constant time sampling (e.g. https://csrc.nist.gov/CSRC/media/Presentations/simple-fast-and-constant-time-gaussian/images-media/rossi-session-4-paper-pqc2019.pdf) but according to JMRO22 such algorithms don't work very well with the privacy analysis.

Originally posted by @tholop in #578 (comment)