Researcher uses 379-year-old algorithm to crack crypto keys found in the wild
arstechnica.com
arstechnica.com
Briefly, RSA relies on the product n=pq being hard to factor. If p and q are very, very close together then the Fermat Factoring algorithm will find the factors quickly. The article reports that there are implementations of RSA that choose such prime pairs, and as a result, the ciphers are quickly broken.
There are other poor choices for p and q, but this one is especially egregious.
Some previous discussion:
"2500 year old geometry calculates something or other". What does including age have to do with anything, other than trying to "wow" readers.
And they're not very big <grin>
> Is there an elegant way to eliminate bad pairs? Or do you have to enumerate all the reasons they could be bad and check after generation, regenerate if fail?
They've since deleted the question, but here is the reply I typed:
Broadly, you want p and q to differ in length by a few digits, and you want each of p-1 and q-1 to have large factors. So once you choose p and q literally at random, with no special structure, then you use Pollard Rho to strip small factors from each of p-1 and q-1 to make sure there's a large(ish) factor in each. Then that's about the best you can do.
Factoring integers is a heavily studied subject - for obvious reasons - so there are unexpected "gotchas" here and there, but the above is a reasonable compromise. There are those who advise never to use RSA at all, and they are probably better qualified than I. Even so, using the above heuristics, and large keys, it still seems a reasonable choice for some applications.
Also, others will say you should always use Elliptic Curves, but I have no personal knowledge about what makes a particular curve good or bad, and all my reading tells me nothing specific, so I'm relying on experts saying "Use this curve, it's a good one". I have no way of knowing if they're telling me the truth, or if there is some magic, cleverly disguised backdoor of which I am unaware.
TL;TD - Yes, you have to enumerate all the reasons your choice of (p,q) might be bad and simply try again if your choice fails.
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?
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.
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.
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.
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!
I remembered reading 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!
[0]https://people.csail.mit.edu/rivest/pubs/Riv19f.pdf Essentially, you use some high iteration count of the Blum Blum Shub pseudorandom number generator to encrypt some data. If you know the factorization of your modulus, you can randomly seek very far ahead in the Blum Blum Shub output. Others that don't know the factorization will need to sequentially generate random numbers from the known starting seed for several years to find the pseudorandom output needed to decrypt the message. Blum Blum Shub parallelizes very very poorly if the modulus factorization isn't known. Very well financed adversaries can use gallium arsenide/strained silicon on saphire ASICs, etc. to get constant factor speed-ups over a regular desktop machine, but one can make good educated upper limit guesses on these advantages.
For RSA weaknesses the Wikipedia page is a fair place to start:
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding
Simply doing a search for RSA attacks will give you several places to start ... this is a good one:
https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf
It's one thing to read about the design and implementation of a cryptosystem, but you really want to search for attacks against them.
This is a deep and gnarly area, with lots of people who know enough to be dangerous. Including me.
Not exactly; a uniformly random (admissible) p,q pair will suffice with very high probability, but in those cases p and q will likely have the same number of digits. One can avoid the bad case for Fermat's method by explicitly forcing p and q to be a couple orders of magnitude off, but the probability this helps is so low that you're only just reducing your security in aggregate: the bits of entropy you're shaving off by restricting the sample space are more impactful than the resilience gained by avoiding a (very, very) tail event.
Assuming, of course, your parameters and (P)RNG are decent. See further discussion here on the history of that recommendation https://crypto.stackexchange.com/questions/35087/should-rsa-... .
Why?
It's a complicated topic.
The magic terms to search for are "strong prime" or "Sophie Germain Prime".
Disclaimer: I'm not an expert ... someone else might be able to comment more usefully.
> with the current factorization technology, the advantage of using safe and strong primes appears to be negligible
(I'm not an expert either.)
If you take it to an extreme, using a prime p of the form 2^k+1 makes pq reasonably easy to factor (I think) using the Pollard P-1 algorithm.
So there's still value in ensuring that p-1 and q-1 both have a reasonably large factor.
But I'm at, and possibly beyond, my actual knowledge, and somewhat into "better safe than sorry" speculation.
> The numbers p and q should not be "too close", lest the Fermat factorization for n be successful. If p − q is less than 2n^{1/4} (n = p⋅q, which even for "small" 1024-bit values of n is 3×10^{77}), solving for p and q is trivial. Furthermore, if either p − 1 or q − 1 has only small prime factors, n can be factored quickly by Pollard's p − 1 algorithm, and hence such values of p or q should be discarded.
Wikipedia is not always right, and certainly shouldn't be trusted implicitly on details in depth, but it's an interesting thing for them to be saying.
I’ll see if I can find details.
Edit: found it: here’s the blog post where I first read about it: http://www.thebigquestions.com/2012/03/13/uh-oh/
edit: looks like public access is gone now, that's unfortunate.