Hacker News new | past | comments | ask | show | jobs | submit login
/dev/random – a new approach (lwn.net)
265 points by Tomte on Apr 24, 2016 | hide | past | web | favorite | 126 comments



This proposed design comprehensively ratifies Linux's nonsensical legacy random/urandom division; for instance, it maintains a "512 bit emergency entropy level" in case urandom becomes "stressed". It appears to be motivated principally by concerns about the quality of entropy being fed continually into the LRNG --- which is a nonproblem.

This is silly.

There are three problems a kernel CSPRNG needs to address:

1. It needs to seed itself reliably and not provide output when it's not securely seeded.

2. It needs to re-key itself regularly to provide forward secrecy and recovery from attacks.

3. It needs to be performant enough to be used in applications to the exclusion of all other RNGs.

That's it. Once problem (1) is addressed, there is never again for the uptime of the system a concern about the quality or "level" of entropy in the LRNG. DRBGs like this document proposes are effectively stream ciphers (in fact: Salsa20, the new hotness in bulk cipher designs, is essentially a hash DRBG --- and, in the BSDs, a [crappy] stream cipher was the RNG). "Entropy" keys the cipher. The idea that you can "run low" on entropy is the same as the idea that you can "run low" on key. No.

Kernel CSPRNGs do need continually updated entropy pools. But not because their original entropy is depleted! Rather: you want your RNG to be updated so that its "key" changes regularly, so that if your system is compromised transiently, you'll recover.

And, of course, the division between /dev/random and /dev/urandom sabotages goal (3) --- arguably the most important goal. Almost every time you've read about some crypto randomness catastrophe --- from Debian commenting out their RNG and reducing SSH key space to 16 bits, to Bitcoin wallets coughing up private keys by repeating nonces --- you've been reading about userspace RNG failures. People use userspace RNGs because they think the kernel RNG is too slow. And they think the kernel RNG is too slow because they use /dev/random, which obstinately refuses to provide output when --- wait, I'm not dignifying /dev/random: it refuses to provide output at random.


A kernel CSPRNG needs to:

1. Seed itself reliably.

2. Do nothing unless seeded.

3. Re-seed itself regularly, for forward secrecy.

4. Have good performance.

How difficult is #1? It's as simple as gathering 128 bits of entropy. If you have 128 bits, you an expand them into an infinite sequence of random numbers, securely, forever.

I think this is the essence of your comment. The topic is important, so it's worth being clear.


It used to be a real problem in virtual environments. That's why they all have special drivers for randomness now.


Yup, mass cloning a VM is really bad if you rely on stream ciphers for communication over the Internet and you do not instantly reseed. Suddenly you'll have tons of identical keystreams otherwise, making plaintext recovery trivial.

Your VM host simply must instantly inject unique entropy into each VM guest instantly on creation, duplication and start. Otherwise you're breaking your own security.


It also makes #2 above hard in practice. You simply don't know when to block. That's one of the reasons Linux developers are, shall we say, conservative with regards to the entropy pool.

On a recent Linux environment those problems are solved however. Use proper random drivers for your virtualized environment and use getrandom() in your application.


Could the host set a 'dirty entropy' flag whenever it creates/duplicates/starts a new VM? The VM could then watch for this flag and reseed when it notices.


The solution in use now is that the guest OS asks the VM host for entropy using its VM guest specific kernel drivers, to seed the CSPRNG of the guest. If you have it do that on every guest RNG request you'll get the same desired effect without adding more communication.

When you duplicate any VM guest, all sensitive key material should be replaced instantly (preferably never copied to begin with, the host should generate and inject fresh key material).

Refilling the entropy pool alone isn't enough when reuse-insecure ciphers like stream ciphers are actively used, for the reasons stated above. Some ciphers are more tolerant of reuse (see AES-GCM vs AES-GCM-SIV).


> If you have 128 bits, you an expand them into an infinite sequence of random numbers, securely, forever.

How? And why 128 only?


Think of a CSPRNG as encrypting a simple incrementing counter with, say, AES using a random key (this is in fact one of the ways you can build a CSPRNG). A CSPRNG function that's not weak is basically equivalent in strength that has n bits of entropy is then basically equivalent to a cipher with that many bits of key.

The acceptable safe maximum length isn't quite infinite, it's basically 2^64 rounds (not necessarily bits or bytes) for 128 bits of entropy. But that's basically arbitrarily long in practice as anyone cares.


A psuedorandom generator G(x) can expand n random bits to n+1 psuedorandom bits that still "look random" to any efficient program that sees them. The existence of such a G that is efficiently computable is hard to prove (at least as hard as P!=NP) but there are many reasonable functions we theorize to have this property.

So with original entropy x, evaluate G(x) => x', c. Output the random bits c and repeat with x = x'. The sequence of c is psuedorandom.

k=128 is the key length of the generator. We define an efficient program to be one that runs in some time polynomial in k. How big of a k you need is based on how powerful computers are at present.


128 bits is widely considered a "big enough number" that a exhaustive search even on the fastest computers today will require an unthinkable amount of resources (time and power). It's the threshold for "secure" algorithms.


"unthinkable" is not really the right word. "impracticable", perhaps.


One way to think about producing random bits is to just imagine encrypting a large file full of zeros. If you use a good cipher, the result should look totally random. (And if it's not totally random, you have a bad cipher.)

So then the question becomes, what's the largest file you can encrypt with a single key? And the answer is any file you want. There's practically no size limit when you're encrypting files.

128 bits is usually the minimum recommended key size, not because of anything to do with the amount of randomness you can produce, but because you always have worry about an attacker guessing your key by brute force. Brute forcing a key is the same as just trying all possible keys to find one that works. (If there's another way to brute force the key, again you have a bad cipher.) We can estimate how big a key needs to be by looking at the fastest computers that exist: https://en.wikipedia.org/wiki/Supercomputer The fastest computer in the world does something like 2^55 operations per second. There are 2^25 seconds in a year, so if we generously assume that checking a key is just one operation, then a supercomputer like that could check about 2^80 keys per year. 128 is just the first nice power of 2 that's much larger than 80.


There technically is a size limit --- and, for some constructions (like GCM), the size limit is potentially meaningful. But it's (a) enormous and (b) irrelevant, because the LRNG rekeys itself regularly. You can't extract random bytes from /dev/urandom fast enough to beat rekeying.


The same way as any other cryptographic algorithm does that, e.g. RSA.


RSA is not used to encrypt large messages. Symmetric ciphers are used for this. With classic RSA, the secret key for the symmetric cipher is encrypted using RSA.

Often (e.g. in the Signal protocol), a short secret key is extended using a HKDF (RFC 5869) to create enough bits for a symmetric key and an IV or a nonce (and a MAC key if needed).

So for randomness, take 128 bits, use HKDF to extend to 192 bits, use 128 bits of output as AES-128 key, use next 64 bits of output as nonce, use 64 bits counter, produce AES-128(key, nonce||counter) for every value of counter until it overflows as randomness. 2^64 of 2^4 byte blocks is 2^68 bytes of randomness - enough for most purposes. An Intel chip will produce it at 1GB/sec per core.


The question is more how to make 'Have good performance' and 'good crypto'. It's mostly a tradeoff.


"Good performance" needs to be on par or better with any userspace RNG. It's great if it's better but as long as there's an implementation that is on par with userspace there's no reason to write userspace RNGs at least from the performance perspective.

Though there will still be people doing it for various reasons, one of them "because we can".


Is there a difference between re-seeding and re-keying?

I think of this analogy: you re-key/re-seed periodically not because the originally lock gets weaker, but in case someone stole your key without you knowing. Accurate?


Pretty much yes.


Has anybody made a set of patches to give linux the BSD behavior (block until seeded, then never block again)? I run into issues with /dev/random regularly and while I can patch every single application, that feels like playing whack-a-mole compared to patching the kernel.


The solution (currently sans kernel patching) is to just seed /dev/urandom yourself at system startup to avoid the issue of it not being seeded. Don't most distro's do this anyway?

After that it's just down to using /dev/urandom[1] or the getrandom syscall (which is the same as using /dev/urandom). Also the getrandom syscall actually has the behavior you're talking about.

[1] http://sockpuppet.org/blog/2014/02/25/safely-generate-random...


The point is that I run one kernel but dozens of applications; I feel like I'm playing application whack-a-mole trying to patch the applications, when I could just patch the kernel.


It seems that you're just complaining that some applications read from /dev/random, but you wish they would read from /dev/urandom. If I understand you correctly, then it seems there exists a simple solution. (Disclaimer: I don't use Linux, or any other Unix. I may not know what I'm talking about.)

  mv /dev/random /dev/badrandom
  ln -s /dev/random /dev/urandom # is this the right syntax?
Or something like that?


I'm not sure it's that simple. Someone mentioned a solution somewhere in this thread relating to if you're using udev. It still won't give you the block until seeded behavior but my post gave the solution to that (seed it yourself at system start (which most distro's may already do)). It should be possible to give /dev/random the same behavior as /dev/urandom I just haven't really looked into it.


The getrandom() system call does this. See http://man7.org/linux/man-pages/man2/getrandom.2.html



If you're using udev, you can configure it to make /dev/random a symlink to /dev/urandom (eg. [1]). Sadly that doesn't give you the "block until seeded" behaviour though, and I don't know of any kernel patch doing that yet.

1. http://superuser.com/questions/309840/how-can-i-point-dev-ra...


You could make a script that prevents /dev/urandom from being made available until /r/random stops blocking, to then also simultaneously create that symlink.

Edit: on boot, first prevent access to /dev/urandom, then symlink it to /dev/random. Then as soon as /dev/random stops blocking, reverse the direction of the symlink. Same improved security, much simpler to use.


This would also quiet a lot of the noise around the entropy estimation blocking in `/dev/random`. I mean, if basically everyone [1] agrees that you should just use `/dev/urandom/` because blocking on entropy estimation is misguided, then why not copy the behavior of every other Unix?

[1]: http://www.2uo.de/myths-about-urandom/


Thinking out loud here:

1 - try to read from /dev/random.

2 - While 1 has not succeeded, wait and try again

3 - Once it has succeeded, read from /dev/urandom on next reads


I've heard that reading from /dev/random tends to "steal" entropy from /dev/urandom or something. I'm not sure. But if you only use urandom, you're safe. Here, from a quick search: http://sockpuppet.org/blog/2014/02/25/safely-generate-random... http://www.2uo.de/myths-about-urandom/


Then you came to a different conclusion than me, because the text say a lot of times to use urandom

There's no stealing with entropy. And once random returns a read the RNG is seeded, period.


My memories are foggy, unreliable, and out of date. I did say I was not sure…


Not to /dev/urandom, AFAIK. But at least they have the new getrandom syscall.


Practically yes. But as cryptosystem security is based on teasing out differences with respect to various oracles, bounding the security of every piece of cryptographic software to the kernel PRNG algorithm gives me the willies. The only saving grace is that the specific algorithm can be changed out with no worries of backwards incompatibility.

I agree the current implementation makes this distinction worthless, but it doesn't have to be. The biggest hurdle is that true entropy is scarce, and thus must be strictly partitioned between users.

A hardware RNG would solve this, but RDRAND not so much. I feel that if consumer hardware is being subverted by TLAs, the RNG would be the most likely avenue of attack. We may even eventually see partitioning of secure systems into deterministic/functional and non-deterministic parts, with the non-deterministic tape being saved for auditing.


Neither of your first two paragraphs are correct. I don't have an opinion about the last.

First: while I don't know what you mean by "teasing out differences with respect to various oracles", the fact that you have a kernel CSPRNG that your system relies on means that diversity in CSPRNGs is a bad thing. Simply: alternatives to the LRNG lead to multiple single points of failure.

Entropy is not "scarce". In fact, it's infinite and renewable. To generate a practically unbounded number of random bytes from just 16 bytes of starting state entropy, just use those 16 bytes as an AES key, and use it to encrypt an incrementing counter.


I think my point is better made as such:

urandom only implements computational security, whereas random makes an attempt at information theoretic security (albeit an extremely poor one). Computational security is so practically useful that the difference between the two seems moot, but there still is a valid distinction.


In the context of /dev/random, "information-theoretically secure" means "equivalent to a one-time pad". Anyone can look at the design of the LRNG and see that it's not that. So, no.


Software engineering has a strong distinction between abstract model and concrete implementation, yes? The properties of the interface of /dev/random indicate an attempt at being information-theoretically secure. I've repeatedly disclaimed that I'm well aware the implementation falls well short of such.

To me, XOR using /dev/random should be usable for a true OTP [0] whereas XOR using /dev/urandom has the security of the effective stream cipher.

[0] (malleability disclaimer, lest you think I'm arguing for the practicalities of "OTP" or something)


A break of SHA1 (ie SHA1 preimage oracle) breaks u/random. This is less secure than something that is broken if SHA1 and SHA2 are broken. But since there are no known full breaks of either, this is "merely" hypothetical.

We can define our measure of entropy such that the output of AES (/SHA1) qualifies, or such that it does not. The way it is used in the random/urandom distinction, it's clearly not meant to include PRNG output.


random and urandom use the same cryptographic components, so if a break in SHA1 breaks urandom, it breaks /dev/random too.


Yes. As I said, the current implementation fails to live up to the distinction.

They should be completely partitioned pools, and collected entropy that goes out random should never be mixed into the urandom pool. Of course it's likely random still wants whitening, likely resulting in the use of a computationally-secure algorithm.

Practically since it's anyone's guess what the random clients expect, it's probably the right thing to `ln -f urandom random`. Bona fide hardware sources can come up with their own device/daemon to administer and/or stir into the kernel P/RNG. I'm just pointing out that there is a worthwhile distinction they were trying for, despite the engineering pitfalls of trying to make it available!


I have no idea what you're trying to accomplished by these "partitioned pools". Sorry, you've lost me.


'Entropy doesn't get depleted' seems to be something that I have read in many places yet the Linux kernel dev doesn't seem to focus too much on that. Any reason for them missing the point?

It seems you would want to slowly change/update the entropy pool to protect against compromise. So can there be a worst-case situation (if you don't block - for the different reason) that your entropy pool is not updating fast enough to recover from compromise. Or the pool update requires so little entropy (compared to what linux is doing with kind of refilling it) that its almost impossible for that to matter?


Ted T'so showed up here on HN in one of these discussions and derided any criticism as "ivory tower" and "academic".

OTOH, Kroah-Hartmann and Torvalds seemed to approve of my essay ("Myths about /dev/urandom"), so maybe not all hope is lost.

Still, let's not lose perspective here: the Linux random subsystem certainly has its flaws, but it is secure for all practical purposes. Just not convenient.


Any insight as to why Linux is continuing to insist on taking the approach it has thus far?


> wait, I'm not dignifying /dev/random: it refuses to provide output at random

Why would this be a problem? Read one byte from /dev/random, and observe one of 257 possible values chosen at random. :D


You'd have to correct for the biases. Not only in probability, but subsequent calls are also not independent.


Sure, I realize that. (Although "subsequent calls are not independent" means it's not actually refusing to respond "at random".) I'm just pointing out in a facetious, emoticon-marked manner that "it behaves randomly" is kind of an odd insult to level against a source of randomness.


I think the point is that it should behave predictably (but of course give you random data). Behavior is a "larger" concept than just what kind of data you get from a thing.


You can quite predictably drain dev/random and make it not respond randomly. in the 257-valued joke's terms, you can force it to always emit the blocking behavior.


Why are you posting this here instead of the Linux mailing list?


Interesting. Would the re-keying process require a source of fresh entropy, if it's to be non-deterministic?


No. Modern CSPRNGs based on DRBGs are relying on fundamental crypto building blocks like block ciphers and hashes. A single bit difference between the previous state and the new state after the addition of any entropy whatsoever completely scrambles the RNG state. Obviously, you're getting many more bits than one out of your regular updates from the entropy collection subsystem.


Well, maybe? If the purpose re-keying is to recover from a transient compromise, then a single bit isn't really sufficient, is it? If the attacker has completely recovered the old seed, they can recover the entire rng stream up to the point where the reseeding happens. The attacker would notice the new output doesn't match, and at that point can't the attacker simply (brute force) try mixing in a 0 or 1 bit to see which one matches the new output of the rng? Even a few bits wouldn't protect against a brute force simulation of the reseeding. It seems like re-seeding a few bits at a time is in fact worse than storing up, say, 128 bits of new entropy then reseeding all 128 bits at the same time. With small incremental reseeding, the attacker can brute force each small reseeding if they can observe the rng outputs.

Or is there something I'm not seeing about how reseeding works?


That's one of the things that's mentioned in the paper: don't seed one bit at the time. Moral of this discussion (not of the paper) is that you should regularly reseed, but only when you can completely replace the seed with entropy, and don't worry about making users wait for randomness because it makes you look interesting.


I knew someone was going to say this. In fact, the last sentence of my comment was added in an edit after this rebuttal occurred to me. Yeah. Dunno. Definitely don't slowly permute your CSPRNG state one bit at a time.


>Kernel CSPRNGs do need continually updated entropy pools. But not because their original entropy is depleted! Rather: you want your RNG to be updated so that its "key" changes regularly, so that if your system is compromised transiently, you'll recover.

It's very unlikely that a compromise will be temporary. This situation "transient compromise" will never happen. Moreover, once a system is compromised, by definition you cannot trust it until replacing it from a known-good source or backup, at which point, you just start the CSRNG with new entropy.

No system should need or even attempt to recover from a transient compromise, you are just causing a false feeling of security.


You don't necessarily know your rng is being attacked.

Rekeying frequently makes passive attacks way harder, so it makes sense to rekey as a often as you can.


What would be, for example, a passive attack against a CS-RNG?


Sidechannel leaks against mobile devices.


How do you feel about his use of all interrupts?


Linux RNGs: where refusing to XOR in additional hardware randomness into the output stream is not just a defensible opinion, but the dominant one.


Except they do use rdrand if supported. When the random function is called it does a SHA transform. The SHA state gets initialized with rdrand and then the kernel pool is mixed in. This avoids the theoretical issues with xoring rdrand directly into the output.

You should generally avoid xor when it comes to untrusted output such as rdrand since it could theoretically control what gets generated and as such could cancel out whatever you're xoring it with (or at least this is the claim AFAIK). It's better to mix it using some other method, e.g. hash or cipher[1].

[1] https://boringssl.googlesource.com/boringssl/+/master/crypto...


Refusing to XOR it in is sensible. That RNG hardware might know too much about your existing entropy pool (either malicious bias or design flaws). Rejecting to mix it in cryptographically is however dumb.


Gah. Another brain-damaged system that implements complex (and, no doubt, broken) "entropy estimation" with a goal of delivering "information theoretic" security that doesn't even have a structure where information theoretic security could actually be proven.

To the extent that any applications exist where a information theoretic RNG was required, this scheme does not provide one. Instead, it continues the to offer an interface that causes confusion and insecurity without an apparent benefit.


+1. As someone who has worked in the field of information theory, I strongly dislike the abuse of its usage here.

Funny that the term "information theoretic" is used with not even one "theorem" in the linked document.


Has anyone offered a better patch? I'm genuinely curious and don't know.


A patch [0] that added Fortuna [1] support to Linux was offered over 10 years ago.

Fortuna specifically addresses the problems of entropy estimation that the grandparent comment brings up:

"making any kind of estimate of the amount of entropy is extremely difficult, if not impossible. It depends heavily on how much the attacker knows or can know, but that information is not available to the developers during the design phase."

"Fortuna solves the problem of having to define entropy estimators by getting rid of them."

0: https://jlcooke.ca/random/

1: https://www.schneier.com/cryptography/paperfiles/fortuna.pdf


What's "a better patch"? We need to have a shared understanding of the problem before we can evaluate solutions.


Unpredictable and unbiased source of bytes, even on server machines and virtualized hardware at boot time.


If I read this correctly, this new suggestion also keeps the entropy estimation voodoo:

"By using the primary DRBG to serve /dev/random, the LRNG ensures that each random number generated by the primary DRBG must be backed by an equal amount of entropy that seeded the DRBG. Hence, the data derived from /dev/random is backed by information theoretical entropy."

(page 21 of the PDF documentation)


For an explanation of the voodoo nature of the blocking /dev/random, see:

http://www.2uo.de/myths-about-urandom/

EDIT: or read tptacek's root comment on this very page.


Thanks! This article was very helpful.


Note, that tomte is the author.


I used to think that entropy estimation was nonsense, but last year I finally understood it. Copying my comment at https://lwn.net/Articles/642839/:

Think of the pool's entropy as a "measure of unpredictability". If the entropy is ten bits, for instance, you'd need at most 1024 guesses to find the pool state.

You should think of the random generator as having two separate and independent parts: the pool itself and the output function.

Inputs are mixed into the pool using a cryptographic function which takes two values: the previous pool state and the input value, and outputs the new pool state. This function thoroughly mixes its inputs, such that a one-bit difference on any of them would result on average to half of the output bits changing, and other than by guessing it's not possible to get from the output back to the inputs.

Suppose you start with the pool containing only zeros. You add to it an input containing one bit of entropy. Around half of the pool bits will flip, and you can't easily reverse the function to get back the input, but since it's only one bit of entropy you can make two guesses and find one which matches the new pool state. Each new bit of entropy added doubles the number of guesses you need to make; but due to the pigeonhole principle, you can't have more entropy than the number of bits in the pool.

To read from the pool, you use the second part, the output function. It again is a cryptographic function which takes the whole pool as its input, mixes it together, and outputs a number. Other than by guessing, it's not possible to get from this output to the pool state.

Now let's go back to the one-bit example. The pool started with zero entropy (a fixed initial state), and got one bit of entropy added. It can now be in one of two possible states. It goes through the output function, which prevents one reading the output from getting back to the pool state. However, since there were only two possible states (one bit of entropy), you can try both and see which one would generate the output you got... and now the pool state is completely predictable, that is, it now has zero bits of entropy again! By reading from the pool, even with the protection of the output function, you reduced its entropy. Not only that, but there were only two possible outputs, so the output itself had only one bit of entropy, no matter how many bits you had asked for.

Now if you read a 32-bit number from a pool with 33 bits of entropy, you can make many guesses and find out a possible pool state. However, again due to the pigeonhole principle, there's on average two possible pool states which will generate the same 32-bit output. Two pool states = one bit. So by reading 32 bits, you reduced the remaining entropy to one bit.

This is important because if you can predict the pool state, you can predict what it will output next, which is obviously bad.

----

Now, why isn't the situation that bad in practice? First, the input entropy counter tends to underestimate the entropy being added (by design, since it's better to underestimate than to overestimate). Second, "by guessing" can take a long enough time to be impractical. Suppose you have a 1024-bit pool, and read 1023 bits from it. In theory, the pool state should be almost completely predictable: there should be only two possible states. In practice, you would have to do more than 2^1000 guesses (a ridiculously large number) before you could actually make it that predictable.

However, that only applies after the pool got unpredictable enough. That's why the new getrandom() system call (which you should use instead of reading /dev/random or /dev/urandom) will always block (or return failure in non-blocking mode) until the pool has gotten enough entropy at least once.


No. This would matter if entropy was somehow directly provided to applications. But no modern system does this. Instead, entropy is hashed into a key for a keystream generator (based either on a hash function, a MAC, or a stream cipher).

That's the entire point of a DRBG†: to securely incorporate inputs of wildly varying randomness into an RNG whose future outputs are as difficult to predict from past output as keys are to recover from ciphers.

To somehow "predict" the output of the system from its input, you would need to be able to work back from the output of a cryptographic keystream generator back to its key. If you can do that, forget the RNG: you've broken most modern cryptography.

and even prior to this proposal, that's what the LRNG implemented


You can easily predict the output of a system from its input, if said input can only take a few possible values, by simply trying all possible inputs until you find one which matches the output. The extra step of hashing the pool into a key to a keystream generator does not prevent that. If the key has only a few possible values, and you can observe enough of its output, you can brute force it.

If, for instance, the pool has only 256 possible values (8 bits of entropy), perhaps because the system just booted and almost nothing has been added yet to the pool, there will be only 256 possible keys, and only 256 possible output streams. If you have enough of the output (on average around one byte), you can try the 256 possible pool states, and see which one would give you the same output you have. And since now you know both the pool and generator state, the system's entropy is now zero: it's completely predictable.

The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable. Which AFAIK is what the new getrandom() syscall does.


The complaint isn't about blocking before you've been seeded, it's blocking afterwards because you've generated some random numbers and feel like you've somehow "used up" your entropy pool in doing so.


> The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable.

Fortunately, it's easy to store a value which can take one of 2^128 possible states: it's 16 bytes. That's all. That's all you need. That's all you'll ever need.

Take that one value; use it to key a keyed hash or an HMAC or a stream cypher or a block cypher. Encrypt the 16-byte value for 0, then 1, then 2 &c. You will get an effectively infinite sequence of random numbers.

'But wait!' you say, 'maybe I'm worried that I might expose some of that state!' Then just periodically rekey that keyed hash or HMAC or stream cypher or block cypher. There are a number of ways to do that: one possibility would be to hash the current key and the new entropy, but there are other, smarter ways to do it as well.

That's it. That's all you need.


Nobody is advancing pathological one bit starting entropy cases. Of course you need entropy. But you don't need thousands of fresh bits every millisecond. You need a few hundred once.

More important: nobody knows if the entropy counter is truly conservative, because nobody knows how to properly count entropy. Linux makes educated guesses by assuming a model of entropy for the inputs (inter-arrival times of events). That's far less solid than the rest of the random subsystem.


So, more half-assed entropy estimation voodoo neither verified nor endorsed by actual cryptographers?

For goodness' sake, Fortuna already exists. What happened to "don't invent your own cryptography"?


If I understood it, this change is supposed to be fully compatible with the existing interfaces and assumptions, it just claims to give more bits faster, using Fortuna would mean more changes at once and would mean the client code would have to change. Which is easier for OpenBSD to do than it is for Linux.


Replacing the LRNG with Yarrow or Fortuna or something like it would not break any client code, because no sane client code can rely on when /dev/random decides to block --- even by the LRNG's broken definition, that blocking happens at random, and could be deferred indefinitely if enough "entropy" were available.


How would it change the client code? If you use Fortuna to implement /dev/{u,}random, then the client code can just carry on opening that and reading as many bytes as it needs.


Also, should we use /dev/urandom (on the host) to seed the CSPRNG in virtual machines? https://lists.gnu.org/archive/html/qemu-devel/2016-04/thread...


The getrandom() call should be used if it's available, and /dev/urandom on legacy systems. The system call blocks once when the system starts until the RNG is initialized with enough entropy, and then never again.


It should probably just be using /dev/urandom in the first place.


Most likely yes.


So this makes /dev/urandom more like Window's CryptGenRandom (aka RtlGenRandom) which is using AES256 running in CTR mode as a DRNG.

I'm curious why there still needs to be a distinct /dev/random though. Hasn't history shown that they should really just both point to the same thing? Is there really a need for the difference here? Ditto with the entropy estimation, why is this still a thing?


The linked PDF: http://www.chronox.de/lrng/doc/lrng.pdf

Page 4: "The new approach implements the modeling of a slow noise source within the LRNG based on the timing of interrupts and allowing other, even fast operating noise sources to contribute entropy. As discussed above for the legacy /dev/random, only the high-resolution time stamps deliver entropy for hardware events and other information processed by the legacy /dev/random implementation hardly have any entropy. This identification is used as a basis that solely the timing of interrupts is used."


"The cryptographic processing of the entropic data is implemented with a well-known and well-studied deterministic random number generator: an SP800-90A DRBG as defined in [2] – naturally excluding the NSA-sponsored Dual-EC DRBG."

"The concept of the LRNG allows the selection of the used DRBG and the backend cipher implementations at compile time."

Is SP800-90A DRBG really state of the art?

According to Wikipedia "the publication contains the specification for four cryptographically secure pseudorandom number generators for use in cryptography." Without Dual-EC it's still three different DRBGs. How good are they? Is there anything better?


They're fine. They're sane, straightforward, relatively simple constructions based on hashes, HMAC, and ciphers running in CTR mode. You could make a CSPRNG more complicated, but there's not much reason to.

The stuff that extends the "state of the art" beyond SP800-90A tends to be system-specific and feature-based. For instance, the "estimators" in the LRNG are an extension to SP800-90A (and a bad idea). Rolling over seed files are another extension.


> They're fine

Thanks. Does it matter which one of the three is then selected? Only one can be a default.


Meh. Throw a dart.


I didn't RTFA, but I'm wondering why Fortuna[1] hasn't seen better adoption or excitement. I think the BSD team made the right approach of making /dev/random|urandom both a CSPRNG, which if seeded and mixed is an unlimited source of high quality entropy.

Fortuna also has the benefit of mitigating damage from a compromised generator. If the generator is compromised it's very difficult to rewind the RNG output and perform a history attack (is that even the right word for such a thing?).

[1] https://www.schneier.com/cryptography/fortuna/


Every kernel CSPRNG that continually collects entropy is effectively mitigating damage from a compromised generator. This isn't something specific to Fortuna.


+1

This!

Again I think this illustrates the echo chamber some camps can't seem to depart. But I agree with your thinking.


The Linux kernel is not using the true RNG circuitry included with all modern microprocessors (this is not entirely correct - see /u/matt_wulfeck's comment). As far as I know, this is because the kernel devs fear that the RNG circuit can be backdoored, allowing an unwanted entity to control the output of the random bitstream.

This is an issue I've been thinking about quite a bit. Is there a way to somehow sign a circuit design on silicon and allow devs to check the circuit's integrity?

For example, in the case of a TRNG, the developer can add a "verify" instruction to ensure that the TRNG on the user's CPU is not compromised before executing the RAND instruction. Of course, that's what the dev does, but the signing itself is much more complex.

I've been looking through the literature and I haven't found much to go on. I know it's likely impossible to do given how many layers there are between silicon and machine code, but I'd like to at least give it a try.


I'd venture there isn't.

The problem of verifying the integrity of embedded silicon (at the microcircuitry level) is one that hasn't really been solved yet. This has been a problem for the DoD since forever.

THEY solved it partially by using US-sourced parts and working with industry to make sure the designs weren't sabotaged or otherwise backdoored. It's still an active concern though.

http://www.dtic.mil/ndia/2014system/16990WedTrack1Shanahan.p...


I've never heard about the DoD initiative. Thanks for the link!


Yeah. This has been something they've been looking into for a while now. Read all of the updates. It's turtles all the way down.

https://www.schneier.com/blog/archives/2012/05/backdoor_foun...


AFAIK the linux kernel does use the RDRAND instruction set from example Intel. However, it uses it as a mix-in source of entropy and is not the sole source of the csprng seed.

I personally think this is a good approach, as it allows hardware TRNG to increase the quality and quantity of entropy without being able to own the internal generator.


You're correct it does. Specifically I believe it uses rdrand to fill the initial SSH values when get_random is called which then proceeds to mix in stuff from the kernel pool. This avoids the problem with using xor for mixing as has been discussed before (even though that attack vector is unlikely).

BoringSSL takes a similar approach with rdrand in that it mixes it using the chacha20 stream cipher. The operating system PRNG is used to generate the keys and rdrand is filtered on every call when you need a random number. I don't know what LibreSSL does (it uses chacha20 in some manner) and I'm pretty sure OpenSSL doesn't use rdrand at all unless you ask for it (in which case it will ONLY use rdrand).


There's a silicon doping attack for CPUs which makes them impossible to verify with current verification techniques (as far as I understand). The idea is that if you dope the silicon in the circuit you can change the circuit and it's not possible to figure out if it's been changed through forensics (x-rays, etc) or just using it (sufficiently clever backdoor). I'm unsure if FPGAs are vulnerable to this attack (though I've heard they might not be). This is the paper: http://sharps.org/wp-content/uploads/BECKER-CHES.pdf


A malicious module would only need to act like VW's defeat device to overcome that check. When it senses some integrity/signing routine, it simply isolates itself from a verifiable circuit.


There is no procedure you can run that would show that the RNG was compromised. They would still give you a stream that's indistinguishable from random noise, except it would be generated from a seed known to the attacker.


For VW, that was easy because the test setup was known and very rigid.

If you randomly check, say, power usage and latency of the on-board RNG (ideally combined with high-resolution IR recordings of the CPU), it will, at least, be harder for the CPU manufacturer to install a backdoored RNG that is active most of the time (but one that only gets activated after receiving some trigger, say a specific instruction sequence would still be virtually undetectable)


The problem you are trying to solve is much closer to the "decidability problem" than you might suppose at first sight.


/dev/urandom while entropy available is low:

  $ rngtest -c 200000 -b 2000 < /dev/urandom  
  .....

  rngtest: bits received from input: 4000000032
  rngtest: FIPS 140-2 successes: 199848
  rngtest: FIPS 140-2 failures: 152
  rngtest: FIPS 140-2(2001-10-10) Monobit: 24
  rngtest: FIPS 140-2(2001-10-10) Poker: 15 
  rngtest: FIPS 140-2(2001-10-10) Runs: 60
  rngtest: FIPS 140-2(2001-10-10) Long run: 54
  rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
  rngtest: input channel speed: (min=3.782; avg=63.752; max=82.928)Mibits/s
  rngtest: FIPS tests speed: (min=4.559; avg=158.909; max=194.627)Mibits/s
  rngtest: Program run time: 83882495 microseconds
It gets much worse.


Can someone help me understand why intel has both the rdrand and rdseed instruction set? If your device outputs high quality random data, why would it need two outlets?


https://software.intel.com/en-us/blogs/2012/11/17/the-differ...

rdseed directly gives you the output of a hardware RNG, limited by the rate that hardware RNG produces random bits. rdrand gives you CSPRNG output seeded by rdseed.


Because the DRNG (Digital RNG) on Intel processors filter the data through a DRNG (Deterministic RNG) (i.e. NIST 800-90)[1] which is constantly reseeded. The rdseed instruction was added later to allow for accessing the hardware generator directly (or the bits from the AES CBC-MAC conditioner directly).

I don't know why rdseed was added a generation after rdrand. Whatever the case is you can guarantee that rdrand's internal generator gets reseeded by calling it a certain number of times[2]. You can also wait some amount of time between calls but it's likely faster just to generate more data to force the reseed.

[1] Like Windows it uses AES-256 (AFAIK) in CTR mode as specified in NIST 800-90 or whatever the latest version of that standard is.

[2] the DRNG reseeds automatically after generating 511 128-bit samples (from Intel's drng_samples source package)


If a machine is land locked without good sources of entropy, maybe it can go out to the internet for some nice randomness.


Perhaps some lovely clean Irish randomness:

https://www.random.org/

Sadly, LavaRand, the connoisseur's choice of internet randomness, is no longer with us:

http://web.archive.org/web/20010926221159/http://lavarand.sg...


If the machine truly has little entropy to start, it might have trouble establishing a secure TLS connection to the remote source.

That said, here is my little "wwwrand" script, that assumes Google News will return unpredictable and unrepeatable content. You could also throttle curl using --limit-rate to generate more interrupts for strace to log.

nice -n 19 strace -CTiv -ttt curl -LNv https://news.google.com 2>&1 | shasum -a 512


Surely if you want unpredictable and unrepeatable content, 4chan is the place to go?


/r9k/ can hook you up.


That's a great idea!


See lavarnd.org for a modernized (2003) version.


I see random.org has an api https://api.random.org/json-rpc/1/



You need randomness to securely connect over TLS. If you have that, why go fetch more?


Is there a good reason not to copy what OpenBSD does in this area?


NIH




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: