from Hacker News

An Almost-Secret Algorithm Researchers Used to Break Thousands of RSA Keys

by williamkuszmaul on 1/15/19, 7:13 PM with 109 comments

• by schoen on 1/15/19, 8:55 PM

  This describes research published in 2012 by Arjen Lenstra et al. (https://eprint.iacr.org/2012/064.pdf), which relied on a scalable n-way GCD algorithm that Lenstra's team thought best not to explain to readers (in the hope that the attack wouldn't be quickly replicated for malicious purposes). Coincidentally, another team (Nadia Heninger et al., https://factorable.net/) published extremely similar research in a similar timeframe, without withholding details of that team's GCD calculation approach.

  The Heninger et al. paper explains quite a lot about where the underlying problems came from, most often inadequately seeded PRNGs in embedded devices. As the linked article mentions, other subsequent papers have also analyzed variants of this technique and so there's not much secret left about it.

  If people are interested in learning about the impact of common factors on the security of RSA, I created a puzzle based on this which you can try out, which also includes an explanation of the issue for programmers who are less familiar with the mathematical context: http://www.loyalty.org/~schoen/rsa/

  Notably, my puzzle uses a small set of keys so you can do "easy" pairwise GCD calculations rather than needing an efficient n-way algorithm as described here (which becomes increasingly relevant as the number of keys in question grows).

• by phw on 1/15/19, 9:44 PM

  This idea has since been applied to several other domains. Last year we had a look at all archived RSA keys of Tor relays: https://nymity.ch/anomalous-tor-keys/

  We found that several thousand relays that shared prime factors (most part of a research project), ten relays shared moduli, and 122 relays used a non-standard RSA exponent, presumably in an attempt to manipulate the Tor network's distributed hash table, which powers onion services.

• by lipnitsk on 1/15/19, 10:01 PM

  Another group did a talk on this at DEF CON 26 last year: https://research.kudelskisecurity.com/2018/08/16/breaking-an...

  They analyzed over 340 million keys from the web.

  > As part of the presentation given at DEF CON 26, one of the outputs was Kudelski Security’s Keylookup application. On this site, you can submit your own public keys and have them tested against our dataset. We will let you know if your key is vulnerable to Batch GCD and ROCA attacks. If your key is in our database, we will be able to give you an answer immediately, if it is not, you may have to wait a bit until the tests complete.

  > https://keylookup.kudelskisecurity.com/

• by truantbuick on 1/15/19, 9:34 PM

  What are the characteristics of those who generated an RSA key sharing a prime factor? Can they be linked back to a few bad CSPRNG implementations?

  What are practical steps to be responsible about it?

  It's contrived, but I just imagine that if I'm generating some particularly important keys, that I should somehow find a way to give /dev/urandom a kick of some kind. Even if that were possible, it's more likely to make things worse than better. Still, it makes me a little paranoid to even hear about theoretical weaknesses -- especially like collision attacks. I have no idea how long it takes for the CSPRNG to get properly seeded. Does it take a microsecond after booting? 10 minutes? A day?

• by jMyles on 1/15/19, 10:04 PM

  A lot of people over the years have gotten the message that "use /dev/urandom and forget about it" is the final, end-all, be-all for secure random number generation.

  In fact, this ideology (and that's what it is - an ideology) has been trumpeted right here on HN, in some cases by people who repeatedly seem to comment on topics that they don't fully understand. Security is hard, but there's also a high reputational value on being perceived as an authority on the topic. As a result, there are some nuggets of "wisdom" that require asterisks next to them, including this one.

  Even though "just use /dev/urandom" is almost always true, it isn't always true. In fact, the universe of cases where some form of blocking entropy is needed (and again, this is a very tiny set) is growing, not shrinking.

  https://security.stackexchange.com/questions/186086/is-alway...

• by cbhl on 1/15/19, 9:50 PM

  PuTTYgen, being a Windows application, assumes that a mouse is connected and prompts the user to move the mouse to generate entropy during key creation.

  By comparison, ssh-keygen documents the SSH_USE_STRONG_RNG environment variable -- but then recommends against its use (!) since it can cause key generation "to be blocked until enough entropy is available".

• by userbinator on 1/16/19, 1:14 AM

  IMO a bit clickbaity of a title --- I thought there was a recent breakthrough in integer factorisation, when in fact this is really attributable to insufficient randomness.

• by gtsteve on 1/15/19, 11:13 PM

  On this topic, I recall reading earlier computers (of the 80s) used radio tuners tuned into nothing to generate random numbers. Of course, you need some way to randomly choose the frequency but then what comes out should be pretty unpredictable.

  I believe Random.org uses an approach similar to this. What is so special about this approach that we couldn't install it as a card in a desktop for example?

• by daedalus2027 on 1/16/19, 3:10 AM

  hi, I attempted to recreate the algorithm in the post:

  https://github.com/daedalus/misc/blob/master/testQuasiLinear...

• by sempron64 on 1/15/19, 7:19 PM

  This is very interesting. I wonder what key generators were used to create the insecure keys.

• by sublupo on 1/16/19, 7:39 AM

  > The authors hint in a footnote that at the heart of their computation is an asymptotically fast algorithm, allowing them to bring the running time of the computation down to nearly linear; but the actual description of the algorithm is kept a secret from the reader

  How could something like that pass peer review? Their claim is effectively unable to be reproduced.

• by sliken on 1/16/19, 3:38 AM

  Anyone know of a service (https://factorable.net/keycheck.html was discontinued) or code that would help identify particularly weak keys?

• by incompatible on 1/15/19, 10:59 PM

  Could you use a similar idea to go after bitcoin keys? If so, you may not be able to crack any particular key, but you could steal the bitcoins from the ones you did crack.

• by skookumchuck on 1/16/19, 8:51 AM

  After decades of problems with seeding RNGs, why isn't there a electronic circuit that gets a seed from quantum noise or something like that? The circuit could be part of the CPU or support chips.

  After all, amplifiers are always trying to increase the signal/noise, and the basis of the reliability of digital circuits is avoiding the noise. Instead, a circuit can amplify the noise and sample it.

• by betolink on 1/16/19, 4:46 AM

  I don't know why this is still a problem these days, let's just use lava lamps for entropy: https://blog.cloudflare.com/lavarand-in-production-the-nitty...

• by zde on 1/18/19, 11:05 AM

  > But since they both used the same program to generate random prime numbers, there’s a higher-than-random chance that their public keys share a prime factor

  BS