3 ms·

The issues happen because people cut corners to optimize performance. Even if it's just generating random numbers, they use unproven heuristics that seem "just

The issues happen because people cut corners to optimize performance. Even if it's just generating random numbers, they use unproven heuristics that seem "just as good". An example from a few years ago: To find a random prime, the "correct" way is to generate a random number, and check if it's prime. However, for performance, people would instead generate a single random number, n, and then try n+1, n+2, etc. until they got a prime. The result? Too many RSA keys used the same primes, because primes following "a long run of non primes" were much more likely to get picked than say the upper prime in a prime pair. Once two RSA keys share a prime, you can use Euclid's algorithm to find out which. Get a large batch of badly generated RSA key pairs, and you were likely to find some collisions. In conclusion it's not that looking for performance optimizations is inherently bad, but you really have to strictly prove that you don't change anything important.

kwantam 5y ago
The general message here is true, but I suspect that your specific example is not. Do you have a citation for the claim that PRIMEINC (generate random odd value, increment by 2 until you find a prime) caused overlapping prime factors? The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this). In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most. But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe! [1] https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf [2] https://eprint.iacr.org/2020/815.pdf https://eprint.iacr.org/2020/815.pdf
- thomasahle 5y ago
  Thank you for clearing this up! I knew I should have found my source before posting. I remembered reading https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between-primes-affect-rsa-keys/ https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between... which I suppose only says this _could_ be very bad. Very interesting and great that it was resolved in the negative!

kwantam 5y ago

The general message here is true, but I suspect that your specific example is not. Do you have a citation for the claim that PRIMEINC (generate random odd value, increment by 2 until you find a prime) caused overlapping prime factors? The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this). In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most. But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe! [1] https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf [2] https://eprint.iacr.org/2020/815.pdf https://eprint.iacr.org/2020/815.pdf

thomasahle 5y ago
Thank you for clearing this up! I knew I should have found my source before posting. I remembered reading https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between-primes-affect-rsa-keys/ https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between... which I suppose only says this _could_ be very bad. Very interesting and great that it was resolved in the negative!