Constant-time prime generation?

[fjarri]

1. Is it possible to make random prime generation constant-time? Lucas-V test looks like it can be made constant-time (assuming the constant bit length of generated primes); for (extra) strong Lucas and MR test it doesn't seem to be possible. Finding the (P,Q) pair for the Lucas test (both iterating through possible pairs, and calculating the Jacobi symbol) is inherently variable-time.
2. Is it even necessary? Is any information leaked this way? GMP, for example, generates primes in variable time.

[jellevos]

In the other thread, you mentioned that: "Miller-Rabin requires the number of iterations equal to the number of trailing zeros in n - 1". Could you point me to the source of that? I have a hard time understanding this step. Of course, an easy but slow approach is to hardcode this number of iterations for a given size of integer.

Regarding leakage, the number of trailing zeros in n-1 certainly brings down the search space for someone wanting to retrieve the secret prime. Even more so, I think, if the primality test is used in a sieve. However, I don't have a source for this.

[fjarri]

Could you point me to the source of that?

See Miller-Rabin test, "Strong probable primes" section (or the corresponding code in the crate).

Of course, an easy but slow approach is to hardcode this number of iterations for a given size of integer.

Unfortunately, n is not the size of the integer here, but the integer itself.

[jellevos]

Hey, so I did some digging, and I found some sources about how to mitigate some timing side channels.

Addressing timing side channels in the MR test: Check out this blog/book. They present a very convincing constant-time algorithm.

Addressing timing side channels in the sieve: I found multiple sources that analyze the danger of using sieving, including this one. As a potential countermeasure they suggest using the work by Fouque and Tibouchi. At first glance, Algorithm 2 is promising as a potentially 'constant-time' candidate generation technique that still seems somewhat efficient.

What are your thoughts on this? If you would like, I can look into an initial implementation.

[fjarri]

Interesting, I wonder if that's what OpenSSL uses, seeing as how it chooses not to employ Lucas test and instead do 32-64 iterations of MR (although another reason for that might be that it has optimized implementations of MR using vector instructions).

Unfortunately I cannot dedicate much time to it at the moment, so if you want to help, that would be great. Even if we can only get rid of constant-timeness in the sieve and MR, this can be exposed as a "constant-time" preset, with the same parameters OpenSSL uses (or the ones from FIPS-186, see also #4).

[jellevos]

It's also interesting that even if OpenSSL's MR is constant-time, the leakage from sieving is quite significant. I agree that offering both variable-time and constant-time methods is a nice idea. I can look into it.

[fjarri]

I had some time to look at the constant-time MR algorithm, and I was hoping there's some smart way to remove the dependency on the number of trailing zeros of n - 1. But evidently it just iterates log2(n) times only counting the results that are within the number of trailing zeros. Which means that, say, for a 1024 bit prime it will be about 100 times slower on average... not great.

[jellevos]

The nice thing is, given that we only apply the test on random inputs, it is extremely unlikely for there to be e.g. more than ~40 trailing zeros. What do you think about iterating at most 40 times instead of log2(n)? Given that the last bit is always 0, that is a probability of $2^{-39}$ that the limit is insufficient.