News for hackers. Stuff that matters.
Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Monday March 21, 2022 @04:12PM (#30759104)
This isn't particularly news. If you choose your parameters badly, RSA is insecure.

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:

https://news.ycombinator.com/item?id=30672999

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Wednesday March 23, 2022 @11:11AM (#30779268)
Someone asked:

> 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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by CaptainNegative on Wednesday March 23, 2022 @02:05PM (#30781421)
> you want p and q to differ in length by a few digits

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-... .

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by WhitneyLand on Wednesday March 23, 2022 @11:31AM (#30779505)
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?

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by thomasahle on Wednesday March 23, 2022 @12:14PM (#30780015)
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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by kwantam on Wednesday March 23, 2022 @12:43PM (#30780402)
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

[2] https://eprint.iacr.org/2020/815.pdf

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by thomasahle on Thursday March 24, 2022 @02:04PM (#30793407)
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... which I suppose only says this _could_ be very bad.

Very interesting and great that it was resolved in the negative!

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Wednesday March 23, 2022 @11:44AM (#30779668)
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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by thomasahle on Wednesday March 23, 2022 @12:18PM (#30780065)
> 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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by KMag on Wednesday March 23, 2022 @12:34PM (#30780275)
Note that some algorithms (Rivest's time lock puzzles[0] come to mind) don't have obvious equivalents for elliptic curves, so it's still important to be able to generate good RSA keys.

[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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by jwilk on Wednesday March 23, 2022 @02:22PM (#30781602)
> you want each of p-1 and q-1 to have large factors

Why?

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Wednesday March 23, 2022 @02:28PM (#30781664)
At it's simplest, the algebraic structure of the integers modulo (pq) is simpler when p-1 or q-1 are "smooth" (have no big factors for some definition of "big") and that means that algebraic methods of factoring can be more effective.

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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by jwilk on Wednesday March 23, 2022 @05:06PM (#30783382)
https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes... says:

> with the current factorization technology, the advantage of using safe and strong primes appears to be negligible

(I'm not an expert either.)

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Saturday March 26, 2022 @01:34PM (#30813683)
While doing other rsearch I stumbled across this quotation from Wikipedia:

> 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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Wednesday March 23, 2022 @05:22PM (#30783572)
With a quick skim by my non-expert eye, they are really saying that using the full limit of "strong primes" is unnecessary, and that it suffices to use random primes. But random primes are not such that p-1 is smooth, "random primes" will still have a reasonably large factor, so the comment remains.

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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by abdullahkhalids on Wednesday March 23, 2022 @12:55PM (#30780555)
Is there a book that builds up this knowledge?
Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Saturday March 26, 2022 @03:22PM (#30814557)
I don't know of a single book that covers this sort of thing. There are lots of on-line resources, and it's very much a case of having to chase down references and read them, and then read the works they refer to, and so on.

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.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by mc32 on Wednesday March 23, 2022 @10:59AM (#30779138)
I also dislike the pretentiousness of "379 year old".

"2500 year old geometry calculates something or other". What does including age have to do with anything, other than trying to "wow" readers.

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by WhitneyLand on Wednesday March 23, 2022 @11:35AM (#30779543)
Other times I might agree with you, but it’s hard to be pretentious when you’re talking about Fermat. The guy was such a badass in so many ways… For God’s sake he wasn’t even a mathematician if I recall correctly he had a day job.
Re:Researcher uses 379-year-old algorithm to crack crypto ke... by klyrs on Wednesday March 23, 2022 @03:43PM (#30782459)
I'd call it condescending, not pretentious. Is it reasonable to expect somebody implementing security to be aware of an algorithm that's 4 years old? 38 years old? 379 years old? I'd say yes to the last two, and only prevaricate about the first. I think some condescension is warranted in this case (less so for a 38 year old algorithm -- there's 38 year old hardware out there). We want people to hit the clickbait when it includes lessons so important.
Re:Researcher uses 379-year-old algorithm to crack crypto ke... by SilasX on Wednesday March 23, 2022 @03:26PM (#30782272)
This one says it was a bad randomizer, which I vaguely recall as being behind another vulnerability from ~10 years ago where a researcher found that many RSA keys shared a prime factor with another key, which allows the pair to be easily factored — so you could just iterate over all the pairs and quickly check which one share a factor, which breaks them.

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/

Re:Researcher uses 379-year-old algorithm to crack crypto ke... by anthk on Wednesday March 23, 2022 @11:04AM (#30779200)
(2^8)+1 and (2^16)+1, for example. Pretty easy to compute, and hack too :).
Re:Researcher uses 379-year-old algorithm to crack crypto ke... by ColinWright on Wednesday March 23, 2022 @11:13AM (#30779289)
Yes, broadly you want p and q to differ in length by a few digits (so one is tens or hundreds of thousands bigger than the other), and you want p-1 and q-1 both to have at least one large factor. So the example you give here fails on the second of those, since both p-1 and q-1 are comprised only of small factors.

And they're not very big <grin>