7 ms·

Researcher uses 379-year-old algorithm to crack crypto keys found in the wild

97 points by punnerud 5y ago

ColinWright 5y ago
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 https://news.ycombinator.com/item?id=30672999
- deleted 5y ago
  [deleted]
- mc32 5y ago
  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.
  - deleted 5y ago
    [deleted]
  - WhitneyLand 5y ago
    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.
  - klyrs 5y ago
    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.
- anthk 5y ago
  (2^8)+1 and (2^16)+1, for example. Pretty easy to compute, and hack too :).
  - ColinWright 5y ago
    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>
- ColinWright 5y ago
  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.
  - WhitneyLand 5y ago
    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.
- SilasX 5y ago
  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/ http://www.thebigquestions.com/2012/03/13/uh-oh/
deleted 5y ago
[deleted]
moralestapia 5y ago
I really like this, this is somehow akin to looting random boxes in RPGs. Most of them are full of rubbish but once in a while you get to find some real treasure.
nonameiguess 5y ago
As far as I know, the most common RSA vulnerability found in the wild tends to be predictable random number generators that aren't actually random generating the same factors over and over for host keys on servers. Once one of p or q is shared between multiple hosts, you can factor using Euclid's algorithm for finding a GCD, which is over 2,300 years old. See, for instance, https://esj.com/articles/2012/02/27/rsa-key-kerfuffle.aspx https://esj.com/articles/2012/02/27/rsa-key-kerfuffle.aspx and http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/.
mcdonje 5y ago
I use an ancient algorithm to tie my shoes.
shiado 5y ago
Rapid7 has some very good datasets to play around with certificates. If you want a fun project try to find bad parameters. https://opendata.rapid7.com/ https://opendata.rapid7.com/ edit: looks like public access is gone now, that's unfortunate.
- cph123 5y ago
  "opendata.rapid7.com", not quite so open anymore then haha
AtlasBarfed 5y ago
I'm using a millenia-old algorithm to up and downvote stories.

97 points by punnerud 5y ago

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 https://news.ycombinator.com/item?id=30672999

deleted 5y ago
[deleted]
mc32 5y ago
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.
- deleted 5y ago
  [deleted]
- WhitneyLand 5y ago
  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.
- klyrs 5y ago
  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.
anthk 5y ago
(2^8)+1 and (2^16)+1, for example. Pretty easy to compute, and hack too :).
- ColinWright 5y ago
  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>
ColinWright 5y ago
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.
- WhitneyLand 5y ago
  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.
SilasX 5y ago
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/ http://www.thebigquestions.com/2012/03/13/uh-oh/

deleted 5y ago

[deleted]

moralestapia 5y ago

I really like this, this is somehow akin to looting random boxes in RPGs. Most of them are full of rubbish but once in a while you get to find some real treasure.

nonameiguess 5y ago

As far as I know, the most common RSA vulnerability found in the wild tends to be predictable random number generators that aren't actually random generating the same factors over and over for host keys on servers. Once one of p or q is shared between multiple hosts, you can factor using Euclid's algorithm for finding a GCD, which is over 2,300 years old. See, for instance, https://esj.com/articles/2012/02/27/rsa-key-kerfuffle.aspx https://esj.com/articles/2012/02/27/rsa-key-kerfuffle.aspx and http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/.

mcdonje 5y ago

I use an ancient algorithm to tie my shoes.

shiado 5y ago

Rapid7 has some very good datasets to play around with certificates. If you want a fun project try to find bad parameters. https://opendata.rapid7.com/ https://opendata.rapid7.com/ edit: looks like public access is gone now, that's unfortunate.

cph123 5y ago
"opendata.rapid7.com", not quite so open anymore then haha

AtlasBarfed 5y ago

I'm using a millenia-old algorithm to up and downvote stories.