Ring: Experiment with caching information needed to verify primality of RSA private key primes

[briansmith]

We've been told (IIRC) that Go's crypto library doesn't verify primality of (p, q) in RSA private keys when loading an RSA private key because the primality test is too slow. For similar reasons BoringSSL doesn't do so. This discourages us from doing so too.

However, maybe it is possible to store some values in an PKCS#8 extension for an RSA private key that would allow us to do the primality testing quickly enough that we could always do it. Either we could always do it only if this information is present, or we could always do it and require this extra information to be present if one wants it to be fast.

In https://twitter.com/riking27/status/824355840949776384 it was suggested that we might be able to use the technique described in http://web.archive.org/web/20170120061931/http://primes.utm.edu/prove/prove3_1.html for this.

It's not clear what the performance goals are, what the performance of using that technique is, or if there is a better technique (that requires storing less, and/or that is faster). However, it seems promising, so I'm recording this issue so we don't forget.

[riking]

To clarify, talking about Theorem 1 here:

Let P > 1. If for every prime factor f of P-1 there is an integer a such that

• a^(P-1) = 1 (mod P), and
• a^((P-1)/f) is not 1 (mod P);

then n is prime.

The other theorems on the page don't seem to be general-purpose - applicable to any prime you give them.

And yeah, a straight implementation looks like it would majorly leak timing on the private key load phase. And there's going to be someone out there loading a private key in a timing-visible manner.

[riking]

Existing research, pointed out by @lgarron: https://en.wikipedia.org/wiki/Primality_certificate

[briansmith]

Existing research, pointed out by @lgarron: https://en.wikipedia.org/wiki/Primality_certificate

Nice, thanks for sharing! Note that we don't care about how expensive it is to generate the primality certificate (within reason). We're optimizing primarily for size of the certificate and speed of verification of the certificate.

[lgarron]

We're optimizing primarily for size of the certificate and speed of verification of the certificate.

With the constraint of constant-time for a given key size, right?
(That's the part that makes this an open problem, as far as I know.)

[briansmith]

With the constraint of constant-time for a given key size, right?
(That's the part that makes this an open problem, as far as I know.)

Yes, but if it is possible to know the maximum number of steps we might need for any prime of a given size, we might be able to just do dummy multiplications to make it constant-enough-time™.

From “Very Short Primality Proofs” by Carl Pomerance:

However, from Yao [14] it is possible to reduce this to O((log p)/log log p)), and it is not inconceivable (but unlikely) that it could be reduced to O(log p).

That paper has a bunch of citations (https://scholar.google.com/scholar?um=1&ie=UTF-8&lr&cites=1323824402063569397) but I don't have time to follow up more now.

[briansmith]

On Twitter, @s-zanella wrote:

Impossible? Using a Pocklington certificate best case is more like O(sqrt(N)) state and O(log^c(N)) verif. time for a prime N. - https://twitter.com/xEFFFFFFF/status/824576782741430272

and

See https://projecteuclid.org/download/pdf_1/euclid.bams/1183492108 (Theorem 3) and http://www.mast.queensu.ca/~math418/m418oh/m418og26.pdf - https://twitter.com/xEFFFFFFF/status/824577326759497728

[lgarron]

Ooh, that's nice, since candidates are strong primes. :-)

However, that still requires a recursive proof that q is prime. But I imagine that it's reasonably likely you can built a log-length tiered chain of proofs, each of which are a deterministic size of bits?

[briansmith]

On Twitter, @s-zanella just wrote:

My last reply should read O(log(N)) not O(sqrt(N)). I think ECPP is still state of the art, O(log^c(N)): http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718-1993-1199989-X.pdf - https://twitter.com/xEFFFFFFF/status/826355216165588992

[briansmith]

I suspect I won't get to this anytime realistic. I'm marking this as a good-first-bug to encourage people to try to design something and document in concrete terms what the storage space would be for 1048-bit primes (for 2-prime RSA-2048) and 683-bit primes (for 3-prime RSA-2048). I strongly suspect somebody who has time to read the above papers can say "it would take X bytes of storage and would require Y modular multiplications in the worst case" and we'll find that X and Y are too high to even bother. (Note that the worst-case is also the best case because we'd need to make it constant time.)

[briansmith]

Despite not wanting to think about this anymore, I stumbled across FactorDB, which publishes lots of primes. More to the point, when one publishes a prime on FactorDB, one does so by uploading a "Primo certificate" which is an instance of one of the things mentioned above. Primo is non-open-source software available at http://www.ellipsa.eu/public/primo/primo.html.

Example of a prime with a certificate: http://factordb.com/index.php?id=1100000000777689641&open=prime.

Thus, it seems like we could use Primo to generate a certificate for an 2048-bit prime and then compress it with gzip -9, to give us a reasonable lower bound of the size of a certificate for an RSA private key.

(FactorDB claims the certificate for the above prime is 12,882,193 bytes, but keep in mind that that is one of the biggest primes ever found, not a tiny 2048-bit prime like we'd typically use.)

[s-zanella]

Primo proofs for the primes in RFC 7919:
https://github.com/dkg/tls-negotiated-ff-dhe/tree/master/ffdhe-primality-proofs