[HN Gopher] Researcher uses 379-year-old algorithm to crack cryp...
___________________________________________________________________
Researcher uses 379-year-old algorithm to crack crypto keys found
in the wild
Author : punnerud
Score : 87 points
Date : 2022-03-21 20:01 UTC (2 days ago)
(HTM) web link (arstechnica.com)
(TXT) w3m dump (arstechnica.com)
| shiado wrote:
| 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/
|
| edit: looks like public access is gone now, that's unfortunate.
| cph123 wrote:
| "opendata.rapid7.com", not quite so open anymore then haha
| [deleted]
| moralestapia wrote:
| 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.
| AtlasBarfed wrote:
| I'm using a millenia-old algorithm to up and downvote stories.
| mcdonje wrote:
| I use an ancient algorithm to tie my shoes.
| ColinWright wrote:
| 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
| mc32 wrote:
| 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.
| WhitneyLand wrote:
| 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.
| [deleted]
| klyrs wrote:
| 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 wrote:
| (2^8)+1 and (2^16)+1, for example. Pretty easy to compute, and
| hack too :).
| ColinWright wrote:
| 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>
| SilasX wrote:
| 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/
| ColinWright wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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
| KMag wrote:
| 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.
| abdullahkhalids wrote:
| Is there a book that builds up this knowledge?
| jwilk wrote:
| > you want each of p-1 and q-1 to have large factors
|
| Why?
| ColinWright wrote:
| 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.
| jwilk wrote:
| https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_pri
| mes... says:
|
| > _with the current factorization technology, the
| advantage of using safe and strong primes appears to be
| negligible_
|
| (I'm not an expert either.)
| ColinWright wrote:
| 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.
| CaptainNegative wrote:
| > 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-... .
| [deleted]
| nonameiguess wrote:
| 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 and
| http://www.loyalty.org/~schoen/rsa/.
___________________________________________________________________
(page generated 2022-03-23 23:01 UTC)