Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Constant-time prime generation? #17

Open
fjarri opened this issue Feb 23, 2023 · 7 comments
Open

Constant-time prime generation? #17

fjarri opened this issue Feb 23, 2023 · 7 comments
Labels
enhancement New feature or request

Comments

@fjarri
Copy link
Member

fjarri commented Feb 23, 2023

  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
Copy link

jellevos commented Feb 24, 2023

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
Copy link
Member Author

fjarri commented Feb 24, 2023

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
Copy link

jellevos commented Feb 28, 2023

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
Copy link
Member Author

fjarri commented Feb 28, 2023

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
Copy link

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
Copy link
Member Author

fjarri commented Mar 3, 2023

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
Copy link

jellevos commented Mar 7, 2023

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants