3 ms·

Do people ask/answer this question out of instinct, curiously or practically? The article says the chances of a problem with independent randomization are appr

Do people ask/answer this question out of instinct, curiously or practically? The article says the chances of a problem with independent randomization are approximately 1 in 2^500. Recall a UUID is 128 bits. Am I thinking right, this would be the odds of roughly duplicating UUIDs multiple times in a row? At what limit is the additional code complexity warranted?

ColinWright 5y ago
I don't know why people ask the question, but it's good that it gets asked. It's possible to choose p and q badly, even if you're choosing them randomly, so yes, it's always worth checking. Without the checks there is a chance, even if it's a small one, that your communications are completely insecure. But in truth the answer is : It depends. Always do the analysis, and understand the risks and trade-offs.
- thomasahle 5y ago
  > yes, it's always worth checking. If the error probabilities are low enough, it's much more likely that your computation is invalidated by atmospheric radiation. On the other hand, some of the code could be wrong, so I agree it's good to have an independent soundness check.
thomasahle 5y ago
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!

ColinWright 5y ago

I don't know why people ask the question, but it's good that it gets asked. It's possible to choose p and q badly, even if you're choosing them randomly, so yes, it's always worth checking. Without the checks there is a chance, even if it's a small one, that your communications are completely insecure. But in truth the answer is : It depends. Always do the analysis, and understand the risks and trade-offs.

thomasahle 5y ago
> yes, it's always worth checking. If the error probabilities are low enough, it's much more likely that your computation is invalidated by atmospheric radiation. On the other hand, some of the code could be wrong, so I agree it's good to have an independent soundness check.

thomasahle 5y ago

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!