12 ms·
An Almost-Secret Algorithm Researchers Used to Break Thousands of RSA Keys
- sempron64 8y agoThis is very interesting. I wonder what key generators were used to create the insecure keys.
- schoen 8y agoSee https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf, which includes some identifications of some of the responsible devices. (Two groups of researchers published independently on this issue at nearly the same time.)
- lixtra 8y agoTLDR: Devices that create TLS and SSH keys just after boot when there is not enough entropy.
- loeg 8y agoThat's not a great takeaway. The takeaway is: Linux's /dev/random and /dev/urandom interfaces are both broken, in the sense that neither is reliable for embedded developers during certain early boot conditions. Some of that was maybe worse in 2012 than today, but the fundamental interface properties have not changed. Tl;dr: Use getrandom() instead of /dev/[u]random. Do not use GRND_RANDOM. Do not use GRND_NONBLOCK.
- SEJeff 8y agoI was 1/2 way through reading your comment and was thinking, "Yeah, but they can use the getrandom() that was ported from OpenBSD", but you obviously beat me to it. Take your upvote!
- loeg 8y agoOpenBSD's interface is getentropy(), but yeah, basically the same idea! I believe Linux was the second actor and intentionally made getrandom() a superset of the getentropy interface (i.e., no EINTR below 256 bytes). As a result, writing a getentropy() shim around getrandom is feasible; FreeBSD and Linux (glibc) have done so.
- SEJeff 8y agoYes, it was ported from OpenBSD. Ted literally calls it out in the commit: https://lkml.org/lkml/2014/7/17/145 https://lkml.org/lkml/2014/7/17/145
- pera 8y agoFor keys that are generated during early/first boot conditions, couldn't one wait until /proc/sys/kernel/random/entropy_avail is greater than 256 and then read from urandom? IIRC getrandom still isn't universally available on SoCs kernels.
- Scoundreller 8y agoBut maybe better pre-2009: > Surprisingly, modern Linux systems no longer collect entropy from IRQ timings. The Linux kernel maintainers deprecated the use of this source in 2009 by removing the IRQF_SAMPLE_RANDOM flag, apparently to prevent events controlled or observable by an attacker from contributing to the entropy pools. > Although mailing list discussions suggest the intent to replace it with new collection mech- anisms tailored to each interrupt-driven source [21], as of Linux 3.4.2 no such functions have been added to the ker- nel. > The removal of IRQs as an entropy source has likely exacerbated RNG problems in headless and embedded devices, which often lack human input devices, disks, and multiple cores. If they do, the only source of entropy—if there are any at all—may be the time of boot.
- X6S1x6Okd1st 8y agoRemoving something from an entropy pool because it could be used by an attacker seems really odd to me.
- schoen 8y agoIt may have been inspired by arguments like https://blog.cr.yp.to/20140205-entropy.html https://blog.cr.yp.to/20140205-entropy.html (although that one was published five years later than the change we're talking about).
- clarry 8y agoThat would be rather misguided though. It's not like a device is going to know the exact time the interrupt handler routine would run, hash it, and go back "whoops, better not fire an interrupt yet because it won't be on the right tick!"
- loeg 8y agoNo. The fundamental problem — random blocks arbitrarily after seeding, and urandom does not block even before seeding — existed prior to the 2009 change.
- Scoundreller 8y agoBottom left of page 9 for RSA and middle left of Page 10 goes through which manufacturers were the mode.
- schoen 8y agoThis describes research published in 2012 by Arjen Lenstra et al. (https://eprint.iacr.org/2012/064.pdf 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/ 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/ 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).
- ikeyany 8y agoI attempted to do your puzzle but the link was blocked by my employer's firewall: > URL: http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/ > Block reason: Violence/Hate/Racism So... what exactly is loyalty.org all about?
- gtsteve 8y agoIt appears to be a personal website; I believe it is miscategorised.
- inciampati 8y agoI really doubt that shoen's page is any issue. Perhaps you can get to it in the way back machine.
- 8y ago
- truantbuick 8y agoWhat 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?
- z3t4 8y agoSome RNG's use the time of the day in milliseconds as seed, I guess those are easy to brute force. I guess it's all about the size of the seed and it's randomness!?
- schoen 8y agoThis is probably the most famous issue about that phenomenon: https://people.eecs.berkeley.edu/~daw/papers/ddj-netscape.html https://people.eecs.berkeley.edu/~daw/papers/ddj-netscape.ht... You could say that our understanding of PRNGs has improved a bit since then. A recent thread about brute-forcing PRNG states in a game: https://news.ycombinator.com/item?id=18880528 https://news.ycombinator.com/item?id=18880528
- rincebrain 8y agoI would have thought https://github.com/g0tmi1k/debian-ssh https://github.com/g0tmi1k/debian-ssh would be the most famous issue in many people's memories of poor (read: absent) PRNG use. ;)
- NelsonMinar 8y agoOne would hope no RSA key generation software is so stupid as to use that kind of RNG. OTOH, apparently 0.2% of RSA keys were generated by something effectively that dumb.
- phw 8y agoThis 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/ 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.
- cbhl 8y agoPuTTYgen, 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".
- hackcasual 8y ago> "to be blocked until enough entropy is available" which is fine. The idea that entropy is a consumeable resource is a crypto myth that needs to die.
- tlb 8y agoIt's not consumable, but it can be in short supply right after boot. So /dev/random should block until there's sufficient entropy, but never after that.
- cperciva 8y agoThe problem with "block until you have enough entropy" is that the amount of entropy you have is literally unknowable.
- tux1968 8y agoHow can that be true? The kernel at least, knows how much you have and knows to block consumption until it crosses the desired threshold.
- cperciva 8y agoThe kernel knows how many bytes you've fed into it. But it has no fundamentally sound way of computing a lower bound on how much entropy those bytes contained; the best approaches involve calculating an upper bound and then say "well hopefully it's at least X% of this".
- lipnitsk 8y agoAnother group did a talk on this at DEF CON 26 last year: https://research.kudelskisecurity.com/2018/08/16/breaking-and-reaping-keys-updated-slides-and-resources/ 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/ https://keylookup.kudelskisecurity.com/
- jMyles 8y agoA 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-always-use-dev-urandom-still-good-advice-in-an-age-of-containers-and-isola https://security.stackexchange.com/questions/186086/is-alway...
- aidenn0 8y agoPart of the problem is that neither /dev/urandom nor /dev/random on linux do what most people want. /dev/urandom never blocks even right after you've spun up a fresh machine that has not seeded the PRNG, while /dev/random blocks very conservatively, to the point where it is not useful for certain things. The proper approach for high-volume random numbers is probably to seed a userspace PRNG from /dev/random but that's extra work, particularly in a concurrent program.
- jMyles 8y agoI think that the approach taken in Python as of PEP524[0] gets it about right. And it achieves a very similar level of exposure and performance across platforms as well. 0: https://www.python.org/dev/peps/pep-0524/ https://www.python.org/dev/peps/pep-0524/
- tptacek 8y agoPlease do not seed a userspace RNG from /dev/random. Most major crypto RNG attacks trace back to userspace RNGs. If you can trust /dev/random to provide a seed for your userspace RNG, then by definition you can also from that point on trust urandom as well. (getrandom(..., 0) is probably the right long-term solution).
- incompatible 8y agoCould 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.
- sowbug 8y agoWith a tiny number of exceptions, Bitcoin private keys are just random sequences of 256 bits. They don't involve primality. So unless a shared CRNG is truly awful, there shouldn't be any reason why keys would cluster around certain values.
- tptacek 8y agoWhich is basically the thesis of the underlying "Ron Was Wrong Whit Was Right" paper --- that discrete log systems are safer than RSA. Since then, there's been more work done on the pitfalls of prime generation, perhaps most notably the "Prime And Prejudice" paper, which is really excellent and more interesting technically than this article: https://eprint.iacr.org/2018/749.pdf https://eprint.iacr.org/2018/749.pdf New systems should generally avoid RSA, for this reason among several others.
- pbsd 8y agoIsn't the point of "Prime and Prejudice" that primality tests that are perfectly adequate for RSA key generation are inadequate to verify the primality of adversarial inputs, in protocols like negotiated DHE or whatnot?
- tptacek 8y agoDammit. I just wanted a cool link to Prime and Prejudice! You're right, of course.
- AlexCoventry 8y ago> generally avoid RSA, for this reason among several others. What are the others?
- gtsteve 8y agoOn 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?
- amlozano 8y agoModern desktops have had RNGs built into their chips since Ivy Bridge. Beyond that, they have plenty of decent sources for random numbers such as network traffic. Similarly, mobile devices can use sensor noise to create random numbers pretty well. The devices people are concerned with are things like embedded devices and sometimes virtual devices.
- amenghra 8y agoA zener diode costs $0.01 and gives pretty good randomness. You mix network traffic, user input, other sensors when available and you are gold.
- userbinator 8y agoIMO 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.
- schoen 8y agoA bigger problem for many readers might be that this is a new post, mainly summarizing research from 2012. So it's not really appropriate to say "(2012)", but it also doesn't announce new discoveries since that time.
- daedalus2027 8y agohi, I attempted to recreate the algorithm in the post: https://github.com/daedalus/misc/blob/master/testQuasiLinearGCD.py https://github.com/daedalus/misc/blob/master/testQuasiLinear...
- sliken 8y agoAnyone know of a service (https://factorable.net/keycheck.html https://factorable.net/keycheck.html was discontinued) or code that would help identify particularly weak keys?
- sliken 8y agoActually factorable.net does have code. Planning to analyze the 1200 user keys I have around to see if any are weak. From what I can tell you can just convert public keys into hex and feed them into their program.
- anomalroil 8y agoYes, but it will only batch-factor the 1200 keys you'd be feeding it with. For such factorization attacks to work best, you need a dataset as large as possible.
- spiridow 8y agoHave you tried keylookup? https://keylookup.kudelskisecurity.com/ https://keylookup.kudelskisecurity.com/
- sliken 8y agoTried a few, doesn't seem to handle more than one key well. Worried that 1500 submissions would cause a DoS. After a few it stopped giving me results saying computations were queued.
- betolink 8y agoI 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-gritty-technical-details/ https://blog.cloudflare.com/lavarand-in-production-the-nitty...
- sublupo 8y ago> 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.
- codezero 8y agoIt’s not clear to me that the journal it was published in is peer reviewed. Not all are. https://www.springer.com/computer/theoretical+computer+science/journal/145?detailsPage=editorialBoard https://www.springer.com/computer/theoretical+computer+scien... It’s useful to have such places to publish things, but unfortunate that it’s not clear whether it’s peer reviewed.
- ric2b 8y agoMaybe the reviewers had access.
- rincebrain 8y agoA number of CS publications (or non-CS publications with custom software) don't include the source/enough exact parameters/... to reproduce their results.
- andreareina 8y agoIf I'm reading the numbers right, even using the slow way you'd expect to break on the order of tens of keys per day. Thus the claim that "two out of every one thousand RSA moduli [...] offer no security" is easily verified. The secret algorithm doesn't compute secret data that can't be verified.
- skookumchuck 8y agoAfter 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.
- tatersolid 8y agoThere is. RDRAND for x86/x64 has been in all Intel/AMD for several years. Most ARM SoC have some equivalent device, but they are nonstandard and require driver support. Even the TPM chips in basically every desktop, laptop, and server for over a decade have hardware RNG. Again driver support is needed. The problem is cheap “blue plastic boxes” may not have a hardware RNG, nor will Virtual machines or containers. Writing code to figure out what RNG is available and how to use it is a nightmare so few people do it. This is why most security people say “use the OS CSPRNG always”. That way user-space code doesn’t have to carry all the platform specifics with it. And presumably integrating the hardware RNG can be done once at the OS layer.
- deleted 8y ago[deleted]
- zde 8y ago> 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