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?
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.
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.
[1] https://en.wikipedia.org/w/index.php?title=88_(number)&oldid...
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...
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
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).
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.
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.)
https://eprint.iacr.org/2018/749.pdf
New systems should generally avoid RSA, for this reason among several others.
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?
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.
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:
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.
Devices that create TLS and SSH keys just after boot when there is not enough entropy.
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.
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.
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.
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.
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.
https://github.com/daedalus/misc/blob/master/testQuasiLinear...
BS