Problems emerge for a unified /dev/*random

https://lwn.net/SubscriberLink/889452/953e190af78809a7/

by bitcharmer • 4 years ago

232 195 4 years ago

lwn.net

jwilk• 4 years ago

Unification discussed on HN:

https://news.ycombinator.com/item?id=30373351 (62 comments)

tinus_hn2• 4 years ago

Sounds like they need a way for userspace to state it accepts that it is running on a system that doesn’t have randomness available. Unfortunately that requires a change to userspace.

dinosaurdynasty• 4 years ago

getrandom(GRND_INSECURE) is this

tinus_hn2• 4 years ago

I mean some kind of toggle that disables the whole entropy counting so you don’t have to change all the executables.

Today you can emulate old computers in such a way you can run it 10 times and get exactly the same result each time. If you were able to run the Linux kernel like this there simply is no way to get randomness.

The solutions I can imagine are for the kernel to block, as happened here, for the kernel to give back numbers that aren’t really random (because if you rerun the emulation you’ll get the same numbers) or for userspace to say the system accepts numbers that aren’t secure random numbers.

KSPAtlas• 4 years ago

Don't break userspace!

sfblah• 4 years ago

Admittedly, this would assume the computer is connected to the Internet, but is there not some theoretically reasonable way to get entropy off the Internet? Maybe some server with a known certificate that can return entropy from lava lamps or similar?

I realize part of the issue here is kickstarting the process right after boot. But is that the entire issue?

RL_Quine6• 4 years ago

You're awoken abruptly, you've just got out of grub, you don't have networking interfaces, you don't have any higher level cryptography libraries, the concept of connecting to something on the internet to get entropy in order to continue booting seems like a complete fantasy. You can gather what little entropy you have, mix it with suspicious sources like RDRAND, and paper over the cracks once you've got some better sources on the burner.

spicybright3• 4 years ago

You can easily seed randomness with the user input, like the mouse.

https://security.stackexchange.com/questions/10438/what-are-...

a-dub5• 4 years ago

you could try rowhammering yourself maybe? aren't the bitflips both spatially and temporally random, depending on em conditions?

i never knew that any user could write into the entropy sources by writing to the random block devices... that's sketch.

gumby• 4 years ago

I realize part of the issue here is kickstarting the process right after boot.

Really it's during the bootstrap phase, unless you define that process as complete once the CPU has branched into the kernel's address space, which I wouldn't consider a useful definition. After all, kernel's enumeration of the attached devices and such is also part of the bootstrap process.

staticassertion9• 4 years ago

Yes, seeding entropy from a server is a thing you can do. One such service is "pollinate".

I don't think that would help here.

jazzyjackson• 4 years ago

If you ask me, every motherboard should ship with a bit of Americium 241, that way they have a physical entropy source AND can detect when a fire has occurred inside the case (:

akvadrako• 4 years ago

Processors already have instructions to generate random numbers from physical fluctuations.

zahllos• 4 years ago

No it isn't the entire issue. Or more precisely on your average desktop system this isn't really a problem. The jitter dance will suffice here.

The clue is in randomness seed files. You won't have one of these on a PC because you don't need it. Once you have your 128/256 bits of entropy you can stretch this using a DRBG for actual use and it'll be good.

The problem is systems that are much more deterministic, because they have simpler CPUs that don't do speculative execution, or have anything fancy by way of caching. Their peripherals are fixed at boot time via a devicetree file and udev style peripheral plug and play doesn't happen.

These tend to be embedded use cases. To get around this, you have a seed file to give you at least some good entropy. Then you mix in the best you can get and update that seed file for next boot. Hopefully this plus what you get while the device is on is enough for next time.

A lot of crypto including the tls you might use to get stuff off the internet will break if the quality of randomness is not good enough.

You are reading 'Linux' and hearing 'desktop' but the reality is there is a lot more embedded Linux than desktop Linux, and that's where the entropy problems start to creep in depending on the device in question.

Sharlin• 4 years ago

You are reading 'Linux' and hearing 'desktop' but the reality is there is a lot more embedded Linux than desktop Linux

Yeah, this is a weird example of availability bias. Of the literally billions of Linux instances on the planet, how many are desktops these days? One in a thousand? Even less? Most of them are Android phones, most of the rest (other) embedded devices, almost all of the rest, servers.

pronoiac2• 4 years ago

Sending an ssl/tls request also requires some entropy! It's needed to avoid MITM and replay attacks.

A bit more info: https://security.stackexchange.com/questions/157684/why-does...

simulate-me2• 4 years ago

It doesn't need to be encrypted, just signed by the entropy source. The signature should be verifiable without entropy.

tptacek8• 4 years ago

Apart from all the other reasons this is a very bad idea, the brick wall you run into is that you need cryptographically secure randomness to safely fetch randomness from the Internet.

mjg59• 4 years ago

I wrote https://mjg59.user.srcf.net/entropy/ over 20 years ago, so yes, this is an entirely solved problem.

(The issues associated with seeding an RNG with data entirely controlled by a third party are left as an exercise for the reader)

bhawks3• 4 years ago

Even assuming trust of the 3p service - establishing an ssl connection actually requires entropy too. Even more raw - how could a zero entropy client generate a nonce to protect itself against replay attacks by man in the middle?

I suppose this situation works if you assume both a trusted third party service and a trusted networking layer, but all those assumptions greatly inhibit usefulness.

denton-scratch4• 4 years ago

Anything you get from a network interface could have been interfered with by a third party.

codeflo• 4 years ago

These random/urandom blocking/nonblocking discussions have been going on for at least a decade at this point, maybe even longer. I get that RNG algorithms are hard. What’s surprising to me is that it seems so hard to even figure out the desired interface of such a basic thing in the kernel. Security in entropy-starved environments seems to be very hard to square with backwards compatibility.

staticassertion9• 4 years ago

I don't think it's hard to figure out the desired interface. As you said, the hard part is changing the interface to what's desired decades later.

throwaway815232• 4 years ago

You'd be amazed at how much stupidity lingers about this issue. I don't know if the present-day kernel devs are affected by it, but an awful lot of users are.

jonhohle• 4 years ago

I ran into it the first time in 2005 and it was a widely known issue, easy to find if you could find where your program was pseudo-randomly blocking (pun intended). FreeBSD already had unified random/urandom by that point.

I’m not sure if the Linux folks find something wrong with existing, time tested approaches or if there’s some NIH going on, but it doesn’t seem like a multi-decade problem.

adastra22• 4 years ago

Pedantic question: would it be pseudo-randomly blocking or randomly blocking?

jart• 4 years ago

Why is random so hard? If we assume best intentions then:

    uint64_t lemur64(void) {
      static uint128_t s =
        (uint128_t)426679527491843471ull << 64 | 2131259787901769494ull;
      return (s *= 15750249268501108917ull) >> 64;
    }

Passes bigcrush and PractRand and it won't ever cause your system to hang on boot.

aprdm• 4 years ago

What kind of wizardry is this doing?! :)

anonymousiam2• 4 years ago

Yeah, but it always returns the same pseudo random sequence of numbers. THAT'S part of what they're trying to fix by including entropy.

noselasd• 4 years ago

What it will also do is to allow anyone to predict your pseudo random numbers with high accuracy. (which is bad, as the use case here is for security)

tptacek8• 4 years ago

It's not hard by itself. These interfaces are actually pretty straightforward to design and implement; Linux made things hard for itself by designing a weirdly complicated interface with an entropy credit system, an idea that's more or less discredited now.

What's hard is accurately surveying the last 15 years of systems built on top of Linux's needlessly-complicated LRNG and making changes that don't violate the expectations of those systems. Nobody should be running "jitter entropy daemons" in userland (userland RNGs are essentially the source of all practical CSPRNG vulnerabilities in the past 2 decades), but people do, and if those systems exceeded some threshold of security before Donenfeld's patches, you can't merge those patches if they push security below that threshold.

It's a really irritating problem.

cperciva• 4 years ago

an entropy credit system, an idea that's more or less discredited now

... no pun intended, I'm sure.

yxhuvud• 4 years ago

Also,the problems seems mostly to be around Linux running in a VM rather than on actual hardware. Would it be possible to have the host urandom show up as a hw random number generator to the VM and then use that for initiating things? Seems less hacky than having to fiddle with seeds. Dunno how possible that is though.

rocqua7• 4 years ago

userland RNGs are essentially the source of all practical CSPRNG vulnerabilities in the past 2 decades

Is your point that CSPRNGs should not be implemented in userland, but instead should just read from /dev/random or do the equivalent on non-linux opperating systems?

amelius• 4 years ago

Nobody should be running "jitter entropy daemons" in userland (userland RNGs are essentially the source of all practical CSPRNG vulnerabilities in the past 2 decades), but people do, and if those systems exceeded some threshold of security before Donenfeld's patches, you can't merge those patches if they push security below that threshold.

Why not break their code? Seems justified in this case.

raverbashing• 4 years ago

What's hard is accurately surveying the last 15 years of systems built on top of Linux's needlessly-complicated LRNG and making changes that don't violate the expectations of those systems.

Sounds like they need a compatibility or feature (cmdline) flag.

Add the flag and you can use the new improved system. Establish dates for when the old method will not be the default anymore (but can be used with the flag) and when it will be deprecated for good

staticassertion9• 4 years ago

It seems like one of the main issues is that writes to /dev/urandom aren't counted towards the entropy count.

Torvalds's suggestion would help much. Ted Ts'o, the other kernel RNG maintainer, cautioned that writing to /dev/urandom is not a privileged operation, so a malicious user-space program could write specific values to it; that is the reason why inputs to the device are not used "until there is a chance for it to be mixed in with other entropy which is hopefully not under the control of malicious userspace".
"we can haphazardly mix whatever any user wants, without too much concern" as long as it is not given entropy credit.

What's the attack here? An attacker can't lower the security of a system by writing data to urandom if the data gets hashed and there's any other entropy in the system. If there isn't entropy in the system, how is it a regression?

The Android system writes its kernel command line to /dev/urandom early in the boot process with the expectation that it will not count as entropy, "given that the command line might not contain much entropy, or any at all".

So I assume the problem here is that if you write low entropy data here and then the system counts it, the threshold to reach 256bit is lowered?

Can a crypto-person explain? Is the issue basically that an attacker would be able to make the system look like it had more entropy than it does?

SnowHill9902• 4 years ago

The hash of known data is know data. So such an attacker could flood the system with zero-entropy data and predict with higher than baseline probability the output of “random” generators.

staticassertion9• 4 years ago

You can't reduce the entropy just by adding low entropy data to the pool. If I hand you 256bits of entropy you can hash "a" into it as many times as you like - it won't reduce the entropy.

The only thing I can think here is that the attacker would trick the system into thinking it had hit its 256bit entropy minimum before it actually had.

At which point... I don't know what they gain, but sure, it's at least a dick move.

tptacek8• 4 years ago

No, that's not the problem at all. Nobody is predicting anything. The issue as I understand it is that it might have been possible in some pathologically bad but real configurations for malicious userland code to trick the kernel into believing the LRNG had been seeded when it hadn't yet been.

AgentME• 4 years ago

You've got it: this is purely an issue during boot-up before enough quality entropy has been gathered. If a malicious userspace program writes predictable data to /dev/random immediately on boot, and the system counts it toward the entropy credit, then it's possible that other services on the system reading from /dev/random will get predictable improperly seeded randomness. It's fine to allow writes to /dev/random at any time as long as it is never given entropy credit.

staticassertion9• 4 years ago

I see. That is a bit tricky... the entire "count the entropy" thing sounds like a pain. I guess I don't see a way around it - they link to fortuna, but I don't see how that's going to fix it. It sounds like fortuna is a better prng, so in theory if you have N outputs it's harder to get back to the seed? But the attacker is so early in the boot process...

It would help I guess.

I'll have to read up on Fortuna, at the least, as it sounds really neat.

edit: OK Fortuna is more than I expected. I have to read up.

zvrba• 4 years ago

If a malicious userspace program writes predictable data to /dev/random immediately on boot,

Hmmm, how did the program get there? A case for secure boot, no? At least initialization of RNG state should be included in the trusted part.

Waterluvian3• 4 years ago

Off topic: I decided to try to figure out what LWN stands for. Not on front page. Not in FAQ (unless I missed it. Should be first question.)

I think this oversight is typical for humans but especially for experts. It’s like the inverse of Dunning-Kruger: you’re too smart to realize what others don’t know.

paskozdilar• 4 years ago

Wikipedia [0] states that:

    The acronym "LWN" originally stood for Linux Weekly News; that name is no longer used because the site no longer covers exclusively Linux-related topics, and it has daily as well as weekly content.

[0] https://en.wikipedia.org/wiki/LWN.net

Waterluvian3• 4 years ago

Oh interesting. So maybe it’s intentionally meaningless now? Probably a good FAQ leading question. Thanks for looking it up.

mzzter• 4 years ago

According to the FAQ: https://lwn.net/op/FAQ.lwn#general

What does LWN stand for, anyway?
LWN, initially, was "Linux Weekly News." That name has been deemphasized over time as we have moved beyond just the weekly coverage, and as we have looked at the free software community as a whole. We have yet to come up with a better meaning for LWN, however.

floren• 4 years ago

It's the last entry in the first section of the FAQ:

LWN, initially, was "Linux Weekly News." That name has been deemphasized over time as we have moved beyond just the weekly coverage, and as we have looked at the free software community as a whole. We have yet to come up with a better meaning for LWN, however.

AT&T used to stand for American Telephone & Telegraph, now it's just AT&T. Same idea.

Waterluvian3• 4 years ago

Thanks. I completely missed it. I went back and still missed it once more.

AnnikaL• 4 years ago

https://xkcd.com/2501/

pmoriarty2• 4 years ago

What about the idea of initializing the random pool from some entropy that was saved to a file on the previous boot?

Before the first boot, the entropy file could be initialized by the installation system.

Yes, these entropy files could be compromised, but that would be no worse than compromising the kernel binary or any number of other sensitive files. So as long as you have trust in the security of the most sensitive files on your filesystem, adding another sensitive file should not be much of a concern, as long as it's protected properly.

eklitzke• 4 years ago

This is in fact discussed in the article.

fullstop• 4 years ago

I remember very early versions of Redhat (as in late 90s) saving the RNG seed on shutdown.

loeg11• 4 years ago

Yes, that works iff (1) you have writable media, (2) you can actually feed it to the kernel RNG (and have it credited) before anything critical blocks on RNG output, and (3) the seed isn't (intentionally or accidentally) predictable (e.g., cloning an existing filesystem image, or cloning a VM, or any other design where the same entropy file is reused by multiple instances).

The kernel has limited ability to protect against (3). Some forms of it can be prevented with the VM Generation Counter PCI device, which Linux recently added support for.

pmoriarty2• 4 years ago

You don't actually have to have writable media on the system itself, as you should in principle be able to pass the entropy information to the system over netboot.

And now that I think about it, with BIOS being so sophisticated these days (with UEFI and the like), even before booting many systems should be able to use the network to get entropy information.

Regarding point (3), if an image is used in a VM, the VM host should be able to pass entropy to the guest, so the guest doesn't have to use its own entropy to boot.

zx2c44• 4 years ago

That's what this demo code project is about:

https://git.zx2c4.com/seedrng/tree/seedrng.c

https://git.zx2c4.com/seedrng/about/

https://twitter.com/EdgeSecurity/status/1509002499507818500

It's trying to do the seed file thing the "right way", and be portable enough that init systems can just copy and paste this where it fits.

rad88• 4 years ago

What are the kind of boot/init processes that require the RNG? Is it only a requirement on some systems, or does basically every gameboy, laptop, soda machine etc have init processes that would need the RNG?

The issue that triggered this revert, if I'm understanding it, was that RNG reads had to be minimally decent and non-blocking already in order for a certain system to seed the RNG.

This is definitely breakage, but it'd be interesting to know about the less "reflexive" applications.

RL_Quine6• 4 years ago

KASLR, for one.

The original gameboys have absolutely no entropy sources other than reading uninitialized SRAM memory.

toast02• 4 years ago

Lots of network things need (or desire anyway) randomness. A soda machine probably doesn't need randomness (unless it contacts a payment network), most early video game systems are deterministic, some games can have their 'random' state easily manipulated by user input.

A laptop is likely to need randomness during boot. DHCP is supposed to have a random 4-byte XID in the discover message (to be matched by the client in responses), ipv6 slaac privacy wants randomness too. 802.1x (flawed as it is) needs random values as well. If you're doing those, probably you've got a live network cable which might provide some entropy.

Things like address space randomization want to happen as well.

rocqua7• 4 years ago

I believe there are quite a few systems that generate and install their own private-keys / certificates at boot time. Those should be rather unpredictable, being private-keys and all.

RcouF1uZ4gsC• 4 years ago

Reading all this makes me almost suspect that real world security for most people would be to just use the RDRAND from the cpu.

tptacek8• 4 years ago

Yes, but lots of systems don't have it.

eternityforest3• 4 years ago

Do they have CPU temperature at that point in boot? That should still work given enough time to gather entropy, on jitterless platforms.

They also have fixed seeds+ RTC on some platforms.

Seems like they should be able to find a few bits of entropy on almost any platform.

ufo2• 4 years ago

The problem is that some environments don't have that kind of information. For example, VMs.

rasz• 4 years ago

VM host does, can expose emulated randomness source.

akira2501• 4 years ago

Seems like they should be able to find a few bits of entropy on almost any platform.

We often do.. the seed file from last boot. Just need a /dev/no_im_root_and_i_really_want_to_add_and_credit_this_entropy_random

device.

dylan6044• 4 years ago

someone needs to take a radio telescope and point it at random (haha) bit of sky with a live feed of the noise being turned into a live stream of 1s & 0s. then create an API that allows one to get a number of bits from the live stream. let's make /dev/*random require an internet connection!

Also, we'll need some jammers so the haxors don't try to rick roll the signal

kps• 4 years ago

SGI had an online random number source fed by cameras pointing at lava lamps.

dylan6044• 4 years ago

Of course they did. Something that was slower than christmas to make noticeable changes, got hotter than hell, and took up way more space than anything else for the performance.

burstmode• 4 years ago

Don't give the systemd people any ideas ! PLEASE!

rocqua7• 4 years ago

How do you verify, without being able to send a random challenge, that you are really talking to the radio telescope when it feeds you random data?

If you want to do TLS as a client you still need secure randomness. You need it as input to Diffie-Helman (or whatever key-agreement system you are using). Or, if you are dong old TSL with pure RSA, you need an unpredictable RSA key.

In any case, if an attacker can predict your randomness, he can pretend to be the radio telescope over TLS. The problem is inherent in all asymmetric crypto you would use. You could 'get around this' by using symmetric crypto, but then you need a shared secret, which does not scale.

dylan6044• 4 years ago

Thanks for reminding me why I'm not a comedian. If you couldn't tell that anything in my comment was a joke, then I'm obviously not good at comedy.

tomcatfish• 4 years ago

Not quite stars, but this is super duper close:

https://www.random.org/

RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

dylan6044• 4 years ago

There are fictional plot lines that involve using atmospheric/space noise as the methods for creating one time cypher pads for the ultimate in security. How much of that is based in reality is not known to me, but I know Tom Clancy used this type of encryption as a plot device.

For one time use cyphers or other non-realtime use, it seems like a good source. For realtime back and forth computer negotiating it seems to be much less useful.

brobinson• 4 years ago

How do other OSes handle this "lack of entropy at startup" problem? (Windows, FreeBSD, OpenBSD, etc.) I've only ever seen this discussed in the context of Linux.

tptacek8• 4 years ago

It's not that this is hard to design, it's that it's hard to retrofit given the installed base of weird shit that already cryptically relies on the existing behavior, bugs and all.

loeg11• 4 years ago

It's kind of both. There's the existing behavior, and also it's also just sort of impossible to solve on some of these weird archs with nothing unpredictable going on.

hypertele-Xii3• 4 years ago

I wasn't aware randomness had behavior.

shmageggy• 4 years ago

They both use a system with multiple entropy pools, and incoming entropoy is distributed over them in a staggered fashion such that eventually one of them will accumulate sufficient entropy. You'll notice there is discussion in all of these Linux patches/blog posts about eventually moving to such a design because entropy estimation is too hard and full of pitfalls.

I thought that neither try to estimate entropy, but I see that apple provides a blocking getrandom(2) system call, so maybe they additionally do some entropy estimation alongside the Fortuna design?

They are both very well documented (pdf):

https://download.microsoft.com/download/1/c/9/1c9813b8-089c-...

https://www.schneier.com/wp-content/uploads/2015/12/fortuna....

andbberger• 4 years ago

how does the kernel estimate entropy?

loeg11• 4 years ago

The entropy pool design protects against some attacks, but, critically, it actually makes this boot-time initial seeding problem harder because you need to gather a lot more total entropy (spread over all pools) before the initial pool has enough bits, vs a non-staggered design.

tytso• 4 years ago

In practice it's not hard that hard to solve if you only are supporting a limited number of CPU architectures (e.g., all the world's x86) or only one bootloader. Even if some of the BSD systems support multiple architectures, in practice, they are mostly used only in x86 servers --- and are mostly judged by how well or poorly they work on x86. In contrast, Linux has to work on a very large number of embedded architectures, and some of the CPU architectures don't even have a fine-grained CPU cycle counter, let alone something like RDRAND. And some architectures have practically no peripherals that provide unpredictable input, and some of them very cleverly generate RSA keys and x.509 certificates as the very first thing they do as part of their "out of box" experience.

If you can assume that you're always running on x86 architecture, with RDRAND and RDSEED, and pretty much all desktops, servers, and laptops have TPM chips (which have their own hardware random number generator) and are using UEFI boot (which also has a random number generator) --- and while maybe one of these are either incompetently designed, or backdoored by either the NSA or MSS, hopefully not all of them have been compromised, it's really not that hard.

The challenge has always being on the crap embedded/mobile devies, where manufacturers live and die based on a tenth of a penny in BOM costs..... (and where they tend to have hardware engineers writing firmware and device drivers, and contractors implementing their Minimum Viable Product, and no one ever goes back to retrofit security....)

dehrmann• 4 years ago

Even if some of the BSD systems support multiple architectures...In contrast, Linux has to work on a very large number of embedded architectures

Doesn't NetBSD target an absurd number of platforms?

loeg11• 4 years ago

In FreeBSD, we're equally screwed on these architectures with no good source of random data and no ability to persist some entropy from a previous boot.

gbrown_• 4 years ago

There’s a nice overview of OenBSD’s RNG system here[1] or video if you prefer [2].

[1] https://www.openbsd.org/papers/hackfest2014-arc4random/index...

[2] https://m.youtube.com/watch?v=aWmLWx8ut20

narrator• 4 years ago

Do people trying to crack crypto go after trying to predict the outputs of these random number generators? Would they be used to generate keys for SSL key exchange?

tptacek8• 4 years ago

(1) They do if the RNG isn't seeded or is seeded improperly; otherwise, it's pointless (you might as well try to break AES).

(2) Yes.

uxp• 4 years ago

Yes. Here's a non-crypto instance of using a seed value to deterministically identify the output of a random number generator. This only works in Python 2.x:

    import random
    for i in range(0,50):
        if not i % 15:
            random.seed(1178741599)
        print [i+1, "Fizz", "Buzz", "FizzBuzz"][random.randint(0,3)]

By seeding the PRNG with a known value, one can literally predict the output of a weak number generation utility. In this case, it solves the FizzBuzz puzzle.

https://en.wikipedia.org/wiki/Fizz_buzz

rocqua7• 4 years ago

I recall a piece of research looking at all RSA public keys in certificates on the web they could find. They found a few keys that were very _very_ common. This was the result of exactly these kinds of low entropy key generation problems.

This is problematic even if no-one manages to predict the outcome of the random generator, because it means if someone throws a stupid amount of compute at the problem to brute-force the private key, they can compromise many different people.

But if the source of those repeated keys can be found, an attacker could get their own copy, reverse-engineer the key-generation process, and then try to predict the randomness. In which case they would have a rather cheap way to compromise many different keys.

Looking at it differently, if the problem is big enough, then it can leave a signature of duplicate keys being out their in the wild. These duplicate keys on their own are bad, but the signature can also be used by attackers to know much better where to look for bad entropy.

vlovich123• 4 years ago

Wouldn't switching the order of operations & getting Fortuna to be the PRNG be an easier first step and then try merging /dev/urandom and /dev/random? Since Fortuna doesn't have the entropy estimation problem, doesn't that bypass the issue? I imagine it would also bypass the related RNDADDTOENTCNT issue because you can just ignore that API call and writes would be contributing entropy just like anything else.

On a separate note, I'm not sure I understood the problem with crediting writes to random as contributing that many entropy bits when the write happens by Admin & the pool isn't yet initialized. It seems like it would largely solve this class of problems without introducing any security issues, would it?

caf4• 4 years ago

There are existing startup scripts out there that write, as root, completely predictable data (the example given is the kernel commandline in Android).

rocqua7• 4 years ago

At what point does "you made a willfully wrong program" override "we don't break userland"? Normally I would expect something like "we don't break documented and intended behavior we told userland to expect". It makes sense that Linux tries for a bit more than that, but if you do it too much you get almost instant ossification, which is bad.

CyberRabbi2• 4 years ago

Jason is doing great work here. These aren’t fun to solve problems.

Even if long term he can bootstrap a proper userspace ecosystem of using /dev/*random, will the unification ever be possible if we have to support these old systems?

I am generally in favor of maintaining 100% userspace backward compatibility but in this case I would support changing the behavior since the old shell scripts were exploiting behavior that wasn’t documented and was always incorrect.

bhawks3• 4 years ago

In the context of Linux on embedded and mobile breaking user space would lead to hardware manufacturers essentially freezing on the kernel version right before the break. (For both new projects or in the exceedingly rare case where they upgrade deployed devices).

This would be exceedingly unwise and pushes against the vast amount of effort the kernel community is expending to secure the kernel and bring OEMs on non ancient versions of the kernel.

Essentially these are not old devices, they are new and you likely have purchased some of them without even knowing.

CyberRabbi2• 4 years ago

Wouldn’t it be easier to patch their startup scripts than freezing their kernel?

thehappypm• 4 years ago

Why don’t all computers provide a random hardware generator? Randomness is trivial in dedicated hardware..

willis936• 4 years ago

It is but you need to trust the hardware. Trust is the keyword here. Long battles have been fought over this. Many high profile authors have (successfully) argued against the use of unauditable sources of entropy being used in /dev/random.

https://en.wikipedia.org/wiki/RDRAND#Reception

hypertele-Xii3• 4 years ago

If you don't trust the hardware, any software you run on it is already compromised.

caf4• 4 years ago

Because some computers are a 10c part in a 50c device.

ironmagma2• 4 years ago

Are they the same computers running Linux though?

efitz2• 4 years ago

Many computers have TPMs or Secure Enclaves or whatnot these days. Many CPUs have similar or subset functionality built in. Why don’t manufacturers start to add hardware entropy sources? Then /dev/*random could source entropy from a driver, not an algorithm.

Yes, I know that it only fixes things going forward, and I know that the answer to any question that starts with “why don’t they” is “money”.

Sigh.

CorrectHorseBat2• 4 years ago

But they do: https://en.m.wikipedia.org/wiki/RDRAND

zx2c44• 4 years ago

CONFIG_RANDOM_TRUST_CPU=y

CONFIG_RANDOM_TRUST_BOOTLOADER=y

CONFIG_HW_RANDOM=y

CONFIG_HW_RANDOM_TPM=y

and so forth all exist.

josefx• 4 years ago

“why don’t they” is “money”.

More likely "trust". A purpose build instruction with a black box implementation on hardware that has its own hidden OS with direct access to the network is one issue. The fact that Intels CPUs are a bug riddled mess that have been a significant headache to anyone caring about kernel and application layer security is another. Who needs security if disabling all the mitigations makes you look great on benchmarks.

efitz2• 4 years ago

A HES or a HRNG is observable and testable.

And we trust purpose built security hardware all the time; think crypto accelerator cards and HSMs.

throwaway815232• 4 years ago

Just about all Linux-capable computers have hardware RNG by now, don't they? Just seed the random device from that.

denton-scratch4• 4 years ago

"Nobody knows what entropy really is, so in a debate you will always have the advantage."

~ Claude Shannon

I've become more and more uncomfortable with the word "entropy" as used in cryptography. The word "random" has always been problematic. I try to use "unpredictable" instead, because I have half a clue what that word means.

I think "entropy" is used to mean "unpredictable in principle", which would exclude chaotic processes like CPU jitter. Chaotic processes like the weather are predictable in principle; but they are so complex that in practice they are unpredictable. Quantum processes such as radioactive decay or tunneling seem to be unpredictable in principle. If it's unpredictable, then to my mind it's sufficiently unpredictable for cryptography.

The Intel HWRNG depends on chaos - the jitter in gate propagation times. I'd settle for that, if it weren't for the fact that the raw chaos from the process isn't available for inspection - you can only see the result of obfuscating it using AES. How much bias is there in the raw bitstream from the unencrypted HWRNG output? I have no way of finding out.

Entropy accounting in the Linux RNG seems to be somewhere between heuristics and guesswork. It seems to be awfully complicated, given that it comes down to finger-in-the-air estimates.

/me not a cryptographer, mathematician or physicist.

effie• 4 years ago

I've become more and more uncomfortable with the word "entropy" as used in cryptography.

I don't like the word either. On the other hand, the meaning in the kernel seems clear: with a threat model of the attacker, it's the amount of bits that could be generated from internal state that are believed to be random, i.e. not predictable by the attacker.

The word "random" has always been problematic. I try to use "unpredictable" instead, because I have half a clue what that word means.

Yes, "random" has many meanings. Sometimes it means simply that variable has non-repeating values with few desired statistical properties. This is not enough in cryptography, where we care about the attacker, so random there is much more demanding.

If a bit stream is looking unpredictable, but is known to be actually produced purely algorithmically, it is then not called random, but pseudo-random, because in principle, with enough knowledge of internal state, it can be predicted.

I think "entropy" is used to mean "unpredictable in principle", which would exclude chaotic processes like CPU jitter.

"In principle" is too strong and vague. We don't have a way to test and verify a source is unpredictable in principle. We can only pronounce it based on current state of knowledge. In practice, the criterion is always "unpredictable in practice". A number source like CPU jitter may be declared unpredictable in practice. It is a decision of the implementor.

Chaotic processes like the weather are predictable in principle; but they are so complex that in practice they are unpredictable.

Chaotic processes like weather are theoretical continuous processes, i.e. whose description is based on real numbers. We can measure such numbers only with unknown non-zero error, which makes predictions have errors too, which makes fine enough details of these processes unpredictable. There is nothing qualitatively better in unpredictability that quantum phenomena bring here. Classical thermal noise is already unpredictable.

The Intel HWRNG depends on chaos - the jitter in gate propagation times. I'd settle for that, if it weren't for the fact that the raw chaos from the process isn't available for inspection - you can only see the result of obfuscating it using AES. How much bias is there in the raw bitstream from the unencrypted HWRNG output? I have no way of finding out.

How do they obfuscate it using AES? Maybe the AES obfuscation could be reversed?

Entropy accounting in the Linux RNG seems to be somewhere between heuristics and guesswork. It seems to be awfully complicated, given that it comes down to finger-in-the-air estimates.

This seems to be the state of the things. Kernel programmers are constantly dabbling in RNG science which they shouldn't - they end up changing kernel RNG system design and breaking stuff. I don't expect kernel to provide high quality RNG, I expect it to boot and get out of my way.

denton-scratch4• 4 years ago

whose description is based on real numbers.

Yes, I get it. But you mean real real numbers from the real world, not the representations used in computers. Real real numbers have infinite precision, which means you can't measure a real real quantity.

cyphar (parents sibling) said:

a double pendulum is a very simple system and is still chaotic

You're right, it's nothing to do with complexity. It's that immeasurably small changes in initial conditions lead to huge differences in the way a system develops. So a chaotic system that depends on real-world real quantities is in principle unpredictable, because you can't measure real-world reals precisely.

Thanks people, for nailing a stake through my misguided notion that you need a quantum process to be sure your RNG is immune to prediction by some hypothetical arbitrarily-powerful computer.

cyphar• 4 years ago

I think "entropy" is used to mean "unpredictable in principle", which would exclude chaotic processes like CPU jitter. Chaotic processes like the weather are predictable in principle; but they are so complex that in practice they are unpredictable.

Chaotic systems are practically unpredictable because they have an exponential dependence on their initial conditions. It has nothing to do with complexity -- a double pendulum is a very simple system and is still chaotic.

In other words, as you evolve t, you need more and more bits of precision in the state variables of the initial condition in order to continue predicting the future state correctly. As soon as you start drifting away from the real state the gap between your prediction and reality exponentially increases.

As there is a physical limit to what accuracy you can measure things, at some point is becomes physically impossible to continue accurately predicting the future state.

NateLawson• 4 years ago

You need to get access to the raw entropy stream in order to characterize it and test it under a number of different situations. At Cryptography Research, we did a number of reviews of hardware entropy sources.

You have to look into behavior during very early startup (power on reset), suspend/resume from low power states, under high heat and thermal shutdown, as well as stable operation. You look at different samples of chips to look for production variation. You build software models that try to simulate the underlying hardware behavior to see how close they get to predicting outputs (which is a bad thing if it works too well!)

You then review how the system processes this entropy since ideas that look good to hardware engineers (like a string filter) are actually really bad for entropy. You analyze the path for side channels or race conditions that could leak raw entropy across process boundaries.

Anyway, here are the reports:

https://www.rambus.com/wp-content/uploads/2015/08/IntelRNG.p... (1999)

https://www.rambus.com/wp-content/uploads/2015/08/VIA_rng.pd... (2003)

https://web.archive.org/web/20141230024150/http://www.crypto... (2012)

denton-scratch4• 4 years ago

~ Claude Shannon

I misattributed that quote. It's from a conversation between Shannon and Von Neumann; Shannon attributed the quote to Von Neumann.

  I thought of calling it "information", but the word was overly used, so I decided to call it "uncertainty". [...] Von Neumann told me, "You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage."

https://en.wikipedia.org/wiki/Entropy#Entropy_of_a_system

Sorry.

Problems emerge for a unified /dev/*random

Related Stories