LWN: Comments on "Waiting for entropy"

Why not involve the boot loader

nix — Fri, 28 Jul 2017 20:31:33 +0000

Yeah, that was my confusion, indeed. Thanks for clearing it up.

Why not involve the boot loader

flussence — Tue, 25 Jul 2017 14:59:39 +0000

You might be confusing it with the efivarfs problem (where rm -rf could brick the chipset). pstore is a different interface to the same storage area, but it's currently append-only. The one likely failure mode I'm aware of with it is the EFI variable store itself can become full if your system's crashing in a loop and set to dump panic logs there.

(I saw a colleague going in circles for hours trying to debug why their EFI bootloader changes weren't surviving a reboot, turns out it was that and the kernel wasn't yelling -ENOSPC at efibootmgr when it should've...)

Why not involve the boot loader

nix — Mon, 24 Jul 2017 16:55:55 +0000

My only worry about pstore is that with occasional reports of machines getting bricked by use of pstore I'm frankly scared to turn it on on anything but sacrificial machines...

Why not involve the boot loader

smckay — Fri, 21 Jul 2017 21:37:26 +0000

Do you need TLS in the kernel? I'm pretty sure iPXE supports HTTPS already.

Why not involve the boot loader

flussence — Thu, 20 Jul 2017 19:05:20 +0000

>This does then mean that the kernel has to get randomness somehow, but surely *it* is better able to get some randomness from somewhere on the disk than the bootloader? It already has tested, working filesystem access code, after all.
There's another alternative: store and load the entropy seed via pstore. Works on EFI, KVM and a few other platforms, no block device necessary. (and with the recent addition of in-kernel TLS, that opens the door to horrible ideas like netboot over HTTPS)

Waiting for entropy

vomlehn — Thu, 06 Jul 2017 01:34:27 +0000

An analogy--the mere presence of a lock on your door, no matter whether it is a lousy lock or even a fake, will prevent most people from even trying to open it. That's one of the social engineering aspects of security.

Hardware requirement

bfields — Mon, 12 Jun 2017 19:37:11 +0000

"There are a not insignificant number of people that believe the NSA worked through the hardware companies to produce hardware RNGs in a way that makes them deterministic for the group that understands the subtle bugs they put into the hardware."

What I don't get is why you'd focus on that specific attack. I'm not sure how you design an operating system kernel for security against an attacker with the resources to pressure hardware companies to add backdoors to their designs.

Waiting for entropy

dany — Mon, 12 Jun 2017 15:44:42 +0000

if that CPU instruction is available, /dev/urandom and /dev/random already use it (will mix bytes from this instruction into entropy pool)

Why not involve the boot loader

error27 — Mon, 12 Jun 2017 13:55:08 +0000

That was some years ago. I think we fixed this by feeding a bunch of stuff like mac address into the entropy pool. It's not really random but at least it's not exactly the same for every system on the internet so you don't end up with identical keys.

Feedback from the userspace: Python urandom disaster

vstinner — Sat, 10 Jun 2017 22:08:40 +0000

Oh, I am sorry to hear that feedback. Sometimes we try to be too kind and welcome on python-dev, nobody asks to stop the bikeshedding. Well, I did exactly that once, for the Python 3.6 fspath protocol. A PEP was written to make the discussion more constructive.

I was just wrote a PEP 546 to backport ssl.MemoryBIO to Python 2.7. After around 100 emails, the PEP was approved. The thing is that the discussion was interesting! But it's hard to follow such active discussion.

In my experience, writing a PEP is painful but it is also really worth it! After the long discussion, the quality is much better and also corner cases have been analyzed ;-)

Feedback from the userspace: Python urandom disaster

OrbatuThyanD — Sat, 10 Jun 2017 20:27:29 +0000

> Then the discussion became crazy, the bug tracker and the mailing list were flooded by hundred of messages of people wanting to give their opinon

ugh, I had almost the exact same experience dealing with the python dev community back when I wrote a pep that got included in 3.3. it felt like it was a full year of arguing with bike shedders and the whole thing really turned me off to python all together.

Why not involve the boot loader

mirabilos — Fri, 09 Jun 2017 12:34:38 +0000

This can be fixed in the distribution. I have patched embedded distros to both add a random seed (obtained from the build host) into the image *and* another small one (obtained from the host the imaging script is run on) during the time the image is installed/flashed onto the target.

Later firmware upgrades would then “just” need to carry over an entropy seed to the upgraded version before booting into it.

And if you combine this with bootloader and kernel patches to pass (part) of such entropy to the kernel before handing control over to it, you win. (No, we did not do that for Linux back then.)

Why not involve the boot loader

mirabilos — Fri, 09 Jun 2017 12:31:02 +0000

And not being able to do this everywhere is no reason to not do it on at least one set of systems that *are* capable of supporting it.

Passing entropy at boot

mirabilos — Fri, 09 Jun 2017 12:29:30 +0000

OpenBSD just changed the bootloader protocol, adding an additional entry that is bootloader-provided entropy passed to the kernel before handing control over to the kernel. The entropy is read from disc by their second-stage bootloader, and overwritten early by userspace to prevent repeats.

Of course, this won’t work for _all_ scenarios in which the Linux kernel is currently booted, but it can be added to _some_ of them peu à peu.

You could also conceivably put some write to /dev/urandom into the initrd, a couple of bytes just so that each initrd regeneration will add a bit of (by then pseudo-)random data to each boot, which, combined with the other input (including time, which, yes, I know, is not a secret and additionally susceptible to replay attacks in VMs, but still better than nothing¹), may help.

Investigating platform-specific things is also a (not very low-hanging though) fruit. For example, if a board of a system is known to have two separate oscillators, measure the delta for a short while during early boot and add that¹².

① In the words of the author of RANDOM.SYS for DOS: “Every bit counts.”
② My recipe for this is: add enough sources, for which each source is at least one of, and for which the (XOR or otherwise well-combined) sum of all sources is all of: unpredictable; unobservable; mathematically well-distributed (e.g. prior PRNG output) — then worry about the mixing algorithm ☺

Feedback from the userspace: Python urandom disaster

vstinner — Thu, 08 Jun 2017 12:42:26 +0000

> Wouldn’t you be better off only calling getrandom() once the first call to os.urandom() actually occurs, not unconditionally at startup or import of the random module?

It's more complex than that in practice :-)

To workaround a denial-of-service (DoS) on Python hash function, the hash function is now randomized by default. We need entropy for that. Python 3.6 now tries to get entropy from getrandom(), or falls back to /dev/urandom if getrandom() would block.

There is a similar strategy (fallback) when the random module is imported, to create an instance of the Mersenne Twister PRNG.

But when os.urandom() is called explicitly, we now always block on getrandom().

Feedback from the userspace: Python urandom disaster

robbe — Thu, 08 Jun 2017 12:10:41 +0000

Wouldn’t you be better off only calling getrandom() once the first call to os.urandom() actually occurs, not unconditionally at startup or import of the random module?

(Sorry for beating a dead horse.)

Hardware requirement

njs — Thu, 08 Jun 2017 08:32:22 +0000

There's an important distinction here between entropy *sources*, and the kernel's *estimate* of how much entropy it has. In practice, there are lots of good entropy sources: many modern systems have hardware RNGs, and even if they don't, then measuring on any modern CPU cache latencies gives non-deterministic values as far as anyone can tell. But in both of these cases, the problem is that it's very hard to *know* whether they're good sources of entropy. (For hardware RNGs, it's not just the NSA issue; it's also that if they suffer some internal physical failure then the first notification you get is that your bitcoin wallet is suddenly empty. And the cache thing works really well as far as anyone can tell but in theory it *should* be totally predictable to someone who understands the hardware, so it makes people nervous.)

Ted is happy to mix these sorts of sources into the pool, and they make you safer. But he doesn't count them when trying to estimate whether there's "enough" entropy for the kernel to *know* that you're safe. And it's that estimate that's used to decide whether to block or not during early startup, and causes difficult engineering problems downstream. So hardware RNGs don't actually help at all with that problem.

Hardware requirement

daenzer — Thu, 08 Jun 2017 06:39:51 +0000

FYI, the name of the botnet is not "Mirari" but "Mirai", the transliteration of Japanese 未来 for "future".

Hardware requirement

rahvin — Wed, 07 Jun 2017 21:15:26 +0000

There are a not insignificant number of people that believe the NSA worked through the hardware companies to produce hardware RNGs in a way that makes them deterministic for the group that understands the subtle bugs they put into the hardware. Whether or not you accept that it's not hard to understand that without genuine random data your encryption is worthless so any progress on making random numbers better is a good thing.

I'm personally concerned about RNG's on routers with thinks like the rise of Mirari botnet. Mirari uses the simplest of compromise methods, default passwords, but it wouldn't be hard to upgrade it to target routers with good passwords but bad entropy and in doing so it would go from 600 million devices to several billion. Mirari is actually a threat to the internet itself given its scale and the ease with which anyone can build their own mirari and use it.

Hardware requirement

flussence — Wed, 07 Jun 2017 20:39:16 +0000

Decreeing a billion tons of existing Linux devices to be e-waste might make the likes of Samsung happy, but a saner solution would be to fix it in software, like HAVEGE already does. There's plenty of usable entropy to be found in an average computer if you stop treating it as a perfectly spherical IBM 8088 with clock speed a fixed multiple of Planck time.

Hardware requirement

dps — Wed, 07 Jun 2017 17:26:59 +0000

Requiring a hadrware random number generator would be a really bad idea IMHO.

I have 6 core AMD phenom II box which AFAIK it does not have any random number generation hardware. I still works and I want to coninute to be able to run linux on it and a hardware requiremnet would make it this impossible. As a desktop stystem it probably has a reasonable amount of entropy most of the time. There are far too many boxes that don't have these features---last time I looked about 90% of amd motherboards do *not* have a tpm, random number hardware or efi firmware. I suspect that most mothetboards still don't have a tpm or rng hardware.

I usually build my own desktop boxes, patly because it is usuall significantly less expensive and partly because that way I know exactly what hardware is in the box.

Linux never ran on any hardware without a virtual pagied address space even in the days of 0.99pl13, which only supported <1Gb of memory, one core 32 bit 80x86 processors. At the time you could be the fastest x86 processor was a single core 80486DX2/66, and most motherboards did not support more than 16Mb of RAM. The elks project exists for those that can't afford a MMU but a 8086 compatible motheboard might not be cheap.

Waiting for entropy

hmh — Wed, 07 Jun 2017 16:30:48 +0000

There are documented security episodes due to identical systems with identical initial state early at boot and poor entropy gathering capabilities, yes. They end up generating the same crypto keys at first start-up.

Look for the paper "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices", by Nadia Heninger, Zakir Durumeric, Eric Wustrow and J. Alex Halderman. Read the "Repeated keys due to low entropy" section.

There is an online copy of that paper at: https://factorable.net/weakkeys12.extended.pdf

That has nothing to do with /dev/urandom being secure or insecure, though. The correct term would be "/dev/urandom misuse", IMHO. But it is too easy to misuse.

The problem is real.

Why not involve the boot loader

mjg59 — Wed, 07 Jun 2017 15:22:11 +0000

Of course, if you've got a TPM you've also got a hardware RNG…

Why not involve the boot loader

nix — Wed, 07 Jun 2017 14:47:20 +0000

Yes, that's actually what I was driving at. :)

I suppose you can encrypt the thing via the TPM at read time or something, to ensure that an attacker who removes the disks and reads the seed state still can't tell what the seed will be without also attacking the TPM, which we assume to be difficult to do undetected. (The usual objections to use of the TPM for anything, notably that it's really slow and that there isn't really very much information you actually want to become unreadable if your motherboard fails, don't apply here: the random seed is *random*, after all: all you're using the TPM for here is to make sure that the contents of the entropy pool are hard to predict from the entropy on the disk.)

This does seem like a rather extreme scenario to me, though it's so easy to defend against I might go off and hack this up just to learn something about EFI programming! Once the machine is booted the on-disk seed is useless and probably deleted: this is very much a defense against the sort of evil maid who not only sticks a USB into your machine but boots off a USB disk and clones the quiescent internal disk while you're out, and then finds a useful way to use that information before the entropy pool gets more unpredictable state dumped into it a few seconds into your next boot. I suppose if you were regenerating an SSH key on every boot this would let the attacker derive that, but... who does that except on a machine with no persistent storage at all? Even SSL session keys, etc, are generally derived long after the crucial instants.

Why not involve the boot loader

matthias — Wed, 07 Jun 2017 07:34:26 +0000

Many home routers initialize their private keys on first boot. There is no entropy available that could be read from disk (or whatever). I once read a report, which I do not find any more that harvesting many public keys from home routers yields a surprising number of pairs of public keys, where the gcd is greater than one. This allows for trivial factorization and thus breaking the encryption. The reason was insufficient entropy at first boot.

Unfortunately the installation images are identical on first boot. A seed would be the same on all identical routers providing no entropy at all.

Hardware requirement

tialaramex — Wed, 07 Jun 2017 07:05:37 +0000

Another way forward, which would be painful for Linux to choose today, but remains an option, is to decide that hardware RNG is a mandatory platform feature, the same way Linux insists platforms should have certain other features in order to get a Linux port, most obviously virtual addressing.

If you _want_ you could choose a platform in which the hardware RNG is set to output '4' or its own serial number, or whatever, and there would be some Linux whitening layer on top of your hardware RNG that would make that look at least pseudo-random, much like those old patches that would have Linux run "successfully" on machines where RAM didn't work properly. And when it breaks you'd get to keep both halves.

Waiting for entropy

gdt — Wed, 07 Jun 2017 02:57:21 +0000

Non-random keys and covert-channel (timing, power) attacks are the two ways into otherwise-secure crypto protocols. There's no shortage of academic papers with demonstrations against real platforms, and therefore likely no shortage of NSA implementations.

Waiting for entropy

neilbrown — Wed, 07 Jun 2017 00:46:14 +0000

Surely "get_random_bytes()" should return an error if there aren't any random (by which I suspect we really mean "unguessable") bytes to be had. Reporting success, but returning predictable data seems to violate the law of least surprise.
Then we could have "get_random_bytes_or_4()", which never fails, but sometimes just returns "4" (https://xkcd.com/221/). This can be used by code which cannot wait, but cannot handle failure.

Why not involve the boot loader

mjg59 — Tue, 06 Jun 2017 22:19:08 +0000

> It already has tested, working filesystem access code, after all.

So does the firmware. Just stash something on the ESP and read it in the boot stub (or use the EFI RNG interface if it's present). We'll just handwave about the risk of having your seed stored unencrypted…

Waiting for entropy

jepler — Tue, 06 Jun 2017 21:59:02 +0000

Try Weak Keys Remain Widespread in Network Devices and its citations [21] and [26]:

In 2012, two academic groups reported having computed the RSA private keys for 0.5% of HTTPS hosts on the internet, and traced the underlying issue to widespread random number generation failures on networked devices. The vulnerability was reported to dozens of vendors, several of whom responded with security advisories, and the Linux kernel was patched to fix a boottime entropy hole that contributed to the failures.…
In this [2016 -- jepler] paper, we measure the actions taken by vendors and end users over time in response to the original disclosure.

Spoiler: They didn't find that things had improved much, factoring over 313,000 public keys with the technique disclosed in 2012.

Waiting for entropy

pbonzini — Tue, 06 Jun 2017 21:41:13 +0000

I am reminded of those devices with the same SSH private key because the contents of /dev/random were entirely deterministic on the first boot.

So in addition to your question, I'd ask: besides problems due to lack of entropy in /dev/urandom, how much could you trust /dev/urandom to be sufficiently nondeterministic on embedded systems, before a seed has been read from disk?

Waiting for entropy

Cyberax — Tue, 06 Jun 2017 21:17:49 +0000

I'm kinda disgusted by all this crap about random numbers. Has there been an actual attack through insecure urandom? It all looks like a bunch of people thinking up hypothetical stuff and breaking actual code in process.

Feedback from the userspace: Python urandom disaster

vstinner — Tue, 06 Jun 2017 20:57:13 +0000

I modified Python 3.5 to use the new fd-less getrandom() syscall. Quickly, we got two blocker bug reports about Python blocked forever. The Debian issue was that a Python 3 script was used to compute a checksum at boot, but Python was blocked at getrandom(). The bugs occurred on VMs and embedded devices.

Quickly, our security experts concluded that it's a feature and that os.urandom() must block. Ok but how to fix the issur with Python initialization? Then the discussion became crazy, the bug tracker and the mailing list were flooded by hundred of messages of people wanting to give their opinon... The two most important security Python experts resigned...

Trust me or not: a new mailing list was created just to answer the question of os.random(), should it block or not?

Two PEPs were written. Mine won and is implemented in Python 3.6:
https://www.python.org/dev/peps/pep-0524/

Python 3.6 now blocks on os.urandom(), but Python internal code to initialize Python falls back on non-blocking but unsafe /dev/urandom if getrandom() would block.

Why not involve the boot loader

nix — Tue, 06 Jun 2017 18:35:24 +0000

It has filesystem code you're already relying on in any case. :)

Why not involve the boot loader

jdulaney — Tue, 06 Jun 2017 18:30:12 +0000

Well, in theory the kernel has tested, working file system code.

Why not involve the boot loader

nix — Tue, 06 Jun 2017 17:10:27 +0000

Because not every system *has* a bootloader any more. In fact, a number of kernel developers consider the ideal state to be the bootloaderless state: it's one less famously unreliable moving piece to break.

In particular, reading modern filesystems from a bootloader is a disaster waiting to happen: it's barely safe to read ext2 or FAT (with the only problem being the need to write yet more code to read filesystems when the kernel already contains perfectly good code to do just that), but as soon as you're reading a journalled filesystem, you really must replay the journal too. GRUB doesn't, leading to disaster on XFS, at least (since XFS considers everything committed to disk once it's committed to the journal, since, well, it is). Heck, in XFS the journal location can specified via a mount-time option if you're using an external journal: how on earth do you pass that to the bootloader? So there is nowhere safe to write the information out, unless you write it to a FAT filesystem or something simple like that.

Better to toss all that crap out of the window if possible and let the firmware handle the problem of picking an OS to load. Some EFI implementations can do this quite well (but, sigh, not all, hence the need for things like rEFInd for systems with EFI implementations too crap to let you choose among CONFIG_EFI_STUB-compiled kernels on the EFI System Partition). This does then mean that the kernel has to get randomness somehow, but surely *it* is better able to get some randomness from somewhere on the disk than the bootloader? It already has tested, working filesystem access code, after all.

Why not involve the boot loader

smurf — Tue, 06 Jun 2017 17:04:09 +0000

It's still a regression if you boot a new kernel without that bootloader. OpenBSD controls userspace, it do this. Linux cannot, and some embedded systems don't _have_ boot loaders which can be adapted to do so.

Why not involve the boot loader

hsivonen — Tue, 06 Jun 2017 16:28:30 +0000

Is there a reason better than NIH for not adopting the OpenBSD approach of making it the bootloader's responsibility to supply a seed to the kernel by having the boot loader read the seed from the disk from a location where the kernel wrote a seed when the system was previously running?

Waiting for entropy

arjan — Tue, 06 Jun 2017 16:13:35 +0000

entropy is a hard thing.

On the one hand, the hardcore crypto/random folks want to raise the bar (and block more), which from a strict perspective makes sense,

On the other hand, the result ends up hurting higher layers in the stack, and apps and libraries then sadly decide to implement their own poor PRNG instead, with a worse result.

I suppose the good news is that many modern cpus have instructions to get random numbers, and while the hardcore folks are very skeptical about those for /dev/random use, I can imaging /dev/urandom able to use them...