An Almost-Secret Algorithm Researchers Used to Break Thousands of RSA Keys
algorithmsoup.wordpress.com
algorithmsoup.wordpress.com
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).
> URL: http://www.loyalty.org/~schoen/rsa/
> Block reason: Violence/Hate/Racism
So... what exactly is loyalty.org all about?
If 90% of the company employees only use IE and MS Word and are actually likely to install malware, and the last 10% are software engineers/data analysts/numerical simulation people, the latter are gonna have to work within/around these types of constraints.
I don't know where you work, but off-hand I would postulate that working at "such places" also has advantages over where you work (e.g. better work-life balance, living in an area where property prices are not insane, etc.). As I said, we find different optima in these tradeoffs.
http://www.loyalty.org/~schoen/
That's the most controversial thing about the page. In my view it's not a big deal to have that stance but some people don't like others who rock the boat when it comes to the status quo.
[1] https://en.wikipedia.org/w/index.php?title=88_(number)&oldid...
For what it's worth, I enjoyed the puzzle when I completed it three years ago. A practical exercise cracking the RSA keys followed by a small classic code breaking puzzle.
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.
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.
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?
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:
You do not need to give urandom a kick of any kind; once the KRNG is seeded, urandom will for all intents and purposes perpetually feed you secure random bytes. It's likely your distro already goes through some effort to make sure urandom is seeded by the time you start up a shell.
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...
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.
(getrandom(..., 0) is probably the right long-term solution).
Glad to see you've come around.
Now: as recently as 5 months ago, when you and I discussed the matter, you replied to a post that expressly suggested `getrandom(..., flags=0)` (what you called the "blocking variant", although it's not that simple) and dismissed it in favor of /dev/urandom (and also strangely referred to security.stackexchange as "the wrong stackoverflow boards"). [0]
This was bad advice. It's good to see that you have come around to the position taken by the Python core team and just about everybody else that using getrandom(..., 0) in a best practice in this situation.
Also, you live a bit far from me, but see you at Black Hat maybe :D
Agreed, but `getrandom(..., 0)` largely does. And thus, Python's `urandom` is also a good fit for very nearly every use case for randomness inside business logic.
> The proper approach for high-volume random numbers is probably to seed a userspace PRNG from /dev/random...
At a high-level, I don't agree. I think that for high-volume random numbers the best solution is nearly always a trustworthy hardware RNG.
I also think that, while it's possible to properly seed a userspace PRNG from /dev/random, it's rarely a good idea because 1) it's (at least relatively) difficult to do without introducing other vulnerabilities, and 2) if you trust /dev/random as a seed, then you have other viable options in every case.
If you have a need to use a userspace PRNG - and more importantly, the wherewithall and self-awareness to do it properly, then you are almost certainly in a position to need to seed it from an oracle other than your system's /dev/random.
Again, it makes no sense to say that a CSPRNG can start "running low" on entropy.
Here's what djb has to say about this:
Cryptographers are certainly not responsible for this superstitious nonsense. Think about this for a moment: whoever wrote the /dev/random manual page seems to simultaneously believe that
(1) we can't figure out how to deterministically expand one 256-bit /dev/random output into an endless stream of unpredictable keys (this is what we need from urandom), but
(2) we _can_ figure out how to use a single key to safely encrypt many messages (this is what we need from SSL, PGP, etc.).
For a cryptographer this doesn't even pass the laugh test.
For reference, here's the classic source I think you're referring to: https://www.2uo.de/myths-about-urandom
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".
which is fine. The idea that entropy is a consumeable resource is a crypto myth that needs to die.
Then folks discovered -- in production -- that some cloud computing environments just don't get any other new entropy after boot, and so instances would hang on generating SSH host keys.
Some folks went to /dev/urandom. Other folks decided to seed instances with entropy from another computer (with fancy names like "cloud entropy service"). And then someone had to decide how that machine gets entropy (like plugging in an FM radio into the mic jack).
For environments like that, I think Haveged is the general approach these days. Latest dev code (revived project) is now here:
https://github.com/jirka-h/haveged
It's the (officially blessed, I think) continuation from the original Haveged:
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?
The devices people are concerned with are things like embedded devices and sometimes virtual devices.
https://github.com/daedalus/misc/blob/master/testQuasiLinear...
Devices that create TLS and SSH keys just after boot when there is not enough entropy.
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.
As a result, writing a getentropy() shim around getrandom is feasible; FreeBSD and Linux (glibc) have done so.
> 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.
How could something like that pass peer review? Their claim is effectively unable to be reproduced.
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.
https://eprint.iacr.org/2018/749.pdf
New systems should generally avoid RSA, for this reason among several others.
You're right, of course.
What are the others?
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018...
(you can find subsequent journalism about the effects of this if you're interested).
There have also been other cryptocurrency PRNG attacks that weren't as high-profile as this issue.
https://news.ycombinator.com/item?id=18917385
https://eprint.iacr.org/2019/023.pdf
(This is a nonce reuse issue rather than a common-factor vulnerability, but one reason for nonce reuse can also be CSPRNG seeding problems.)
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.
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.
BS