17 ms·
Problems emerge for a unified /dev/*random
- thehappypm 5y agoWhy don’t all computers provide a random hardware generator? Randomness is trivial in dedicated hardware..
- willis936 5y agoIt 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 https://en.wikipedia.org/wiki/RDRAND#Reception
- hypertele-Xii 5y agoIf you don't trust the hardware, any software you run on it is already compromised.
- Vecr 5y agoYeah, but having a broken RNG in unauditable encrypted obfuscated microcode is more likely to go undetected than something hotter and more critical for performance, but even then meltdown and spectre took a long time to figure out.
- caf 5y agoBecause some computers are a 10c part in a 50c device.
- ironmagma 5y agoAre they the same computers running Linux though?
- bhawks 5y agoYes Linux has a tremendous existing embedded footprint across a number of interesting minimally specced devices. You (and everyone) should care because of the ever expanding internet of things movement connecting these devices up to the rest of the computing universe. This represents a brand new frontier for attack surfaces and if the kernel cannot provide foundational entropy there's no plausible security story for the rest of the stack. The cynic would be quick to point out that IoT is a nitemare anyway and even if the kernel gives the tools the manufacturer needs to use them and use them in the right way.
- ironmagma 5y agoI’d be more convinced by an example of a 10c microprocessor that can run Linux. Obviously it sounds better to support everything, but there also are (and should be) bounds to what Linux should try to support.
- jwilk 5y agoUnification discussed on HN: https://news.ycombinator.com/item?id=30373351 https://news.ycombinator.com/item?id=30373351 (62 comments)
- tinus_hn 5y agoSounds 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 5y agogetrandom(GRND_INSECURE) is this
- tinus_hn 5y agoI 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.
- staticassertion 5y agoYes, I think that ultimately the solution is to remove entropy counting entirely.
- KSPAtlas 5y agoDon't break userspace!
- sfblah 5y agoAdmittedly, 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_Quine 5y agoYou'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.
- spicybright 5y agoYou can easily seed randomness with the user input, like the mouse. https://security.stackexchange.com/questions/10438/what-are-you-doing-when-you-move-your-mouse-randomly-during-a-truecrypt-volume-c https://security.stackexchange.com/questions/10438/what-are-...
- NickNameNick 5y agoWhat mouse? You haven't finished booting yet. You don't know if you're a laptop, a router or a lightbulb.
- staticassertion 5y agoboot the mouse first, then the os
- spicybright 5y agoOk then. Laptops have temperature sensors that can add entropy. A super small embeded device like a lightbulb should keep one of it's I/O pins open. A floating wire also gives entropy. If the question is can you generate random numbers on a computer in a sealed room with absolutely no input, a static image loaded on it, and you have no storage devices to keep any sate, of course you can't generate a random number. The vast majority of things we put computers in do have some form of input that is random enough for a seed unless you design it that way on purpose.
- codeflo 5y agoThese 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.
- staticassertion 5y agoI 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.
- throwaway81523 5y agoYou'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 5y agoI 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 5y agoPedantic question: would it be pseudo-randomly blocking or randomly blocking?
- mobiletoss1337 5y agoIt would be somewhat deterministic and predictable and therefore pseudo-random.
- staticassertion 5y agoIt 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 5y agoThe 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.
- staticassertion 5y agoYou 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.
- semi-extrinsic 5y ago
- Waterluvian 5y agoOff 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 5y agoWikipedia [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 https://en.wikipedia.org/wiki/LWN.net
- Waterluvian 5y agoOh interesting. So maybe it’s intentionally meaningless now? Probably a good FAQ leading question. Thanks for looking it up.
- mzzter 5y agoAccording to the FAQ: https://lwn.net/op/FAQ.lwn#general 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 5y agoIt'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.
- 5y ago
- pmoriarty 5y agoWhat 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 5y agoThis is in fact discussed in the article.
- fullstop 5y agoI remember very early versions of Redhat (as in late 90s) saving the RNG seed on shutdown.
- loeg 5y agoYes, 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.
- pmoriarty 5y agoYou 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.
- rad88 5y agoWhat 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.
- rocqua 5y agoI 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.
- RL_Quine 5y agoKASLR, for one. The original gameboys have absolutely no entropy sources other than reading uninitialized SRAM memory.
- toast0 5y agoLots 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.
- RcouF1uZ4gsC 5y agoReading all this makes me almost suspect that real world security for most people would be to just use the RDRAND from the cpu.
- tptacek 5y agoYes, but lots of systems don't have it.
- eternityforest 5y agoDo 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.
- ufo 5y agoThe problem is that some environments don't have that kind of information. For example, VMs.
- rasz 5y agoVM host does, can expose emulated randomness source.
- Kubuxu 5y agobut it doesn't, so it isn't a solution
- eternityforest 5y agoI'm sure the kernel devs can make it happen, I don't see why VM devs wouldn't want to add this if thry saw clear demand. They probably couldn't just use RDRAND and the like since Linux doesn't seem to trust that though, so the API could be tricky.
- zamadatix 5y agoBeing able to have a solution isn't enough, even having a solution in hand people could switch to isn't enough. You need to actually show no currently working setups are going to break as a result of the change, regardless what those setups could do to avoid breaking after the change.
- hypertele-Xii 5y ago
- dylan604 5y agosomeone 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 5y agoSGI had an online random number source fed by cameras pointing at lava lamps.
- dylan604 5y agoOf 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.
- rascul 5y agoCloudflare does also. https://www.cloudflare.com/learning/ssl/lava-lamp-encryption/ https://www.cloudflare.com/learning/ssl/lava-lamp-encryption...
- burstmode 5y agoDon't give the systemd people any ideas ! PLEASE!
- rocqua 5y agoHow 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.
- brobinson 5y agoHow 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.
- tptacek 5y agoIt'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.
- loeg 5y agoIt'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-Xii 5y agoI wasn't aware randomness had behavior.
- shmageggy 5y agoThey 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-4fef-b2ad-ad80e79403ba/Whitepaper%20-%20The%20Windows%2010%20random%20number%20generation%20infrastructure.pdf https://download.microsoft.com/download/1/c/9/1c9813b8-089c-... https://www.schneier.com/wp-content/uploads/2015/12/fortuna.pdf https://www.schneier.com/wp-content/uploads/2015/12/fortuna....
- andbberger 5y ago
- narrator 5y agoDo 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?
- tptacek 5y 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 5y agoYes. 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 https://en.wikipedia.org/wiki/Fizz_buzz
- rocqua 5y agoI 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 5y agoWouldn'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?
- caf 5y agoOn 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? There are existing startup scripts out there that write, as root, completely predictable data (the example given is the kernel commandline in Android).
- rocqua 5y agoAt 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.
- caf 5y agoThose programs weren't "willfully wrong". That status quo is that whatever you wrote would be potentially mixed into the pool, but not counted as adding any kind of unpredictability unless the ioctl() was used to specifically indicate this.
- CyberRabbi 5y agoJason 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.
- bhawks 5y agoIn 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.
- CyberRabbi 5y agoWouldn’t it be easier to patch their startup scripts than freezing their kernel?
- efitz 5y agoMany 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.
- CorrectHorseBat 5y agoBut they do: https://en.m.wikipedia.org/wiki/RDRAND https://en.m.wikipedia.org/wiki/RDRAND
- zx2c4 5y agoCONFIG_RANDOM_TRUST_CPU=y CONFIG_RANDOM_TRUST_BOOTLOADER=y CONFIG_HW_RANDOM=y CONFIG_HW_RANDOM_TPM=y and so forth all exist.
- josefx 5y 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.
- efitz 5y agoA HES or a HRNG is observable and testable. And we trust purpose built security hardware all the time; think crypto accelerator cards and HSMs.
- CorrectHorseBat 5y agoIt's much harder to test the output of a TRNG
- throwaway81523 5y agoJust about all Linux-capable computers have hardware RNG by now, don't they? Just seed the random device from that.
- denton-scratch 5y 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 5y 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.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]