I think this article is misinformed and also a bit of a killjoy. Modern random number generation uses many independent sources of entropy, which are hashed together into an entropy pool continuously while the computer is running. There is no singular "random seed" for a computer, it is constantly re-seeding using entropy from different sources while it runs using something like seed = hash(seed, new_data). Adding data from a camera filming a lava lamp absolutely does not reduce the security of the system in any way. Data fed into entropy pool is hashed together with other data that has been fed into the entropy pool. The system is designed to be secure as long as there is even a tiny amount of information not known to the attacker, which allows you to mix in lots of data of varying levels of randomness without compromising the security of the system in any way.
The lava lamps do not harm the system's security in any way, and in my opinion, serve as a delightful and functional art piece that forms a part of the system (and increases the random number quality by an infinitesimal amount), while visually illustrating the concepts of randomness and entropy.
Right, but kernel RNGs have been using diverse hardware randomness for over 30 years now, and be careful not to overstate how continuously or constantly they are re-seeded. Randomness is gathered from hardware continuously, but the Linux RNG is reseeded periodically: every few seconds during the first minute after boot, slowing down to once a minute after that.
Modern random number generation uses many independent sources of entropy, which are hashed together into an entropy pool continuously while the computer is running.
Where did I gave the impression that I was stating, or implying, otherwise? I didn’t mean to describe existing systems here (apart from the lava lamps bit), I wanted to stress how little we actually need. That is, 256 bits.
Adding data from a camera filming a lava lamp absolutely does not reduce the security of the system in any way.
Attack surface anyone? You’re adding an embedded computer and network communications between that and the server. To me it’s pretty clear that the (low) added risk far outweigh the (stupidly low) risk of actually needing the lava lamps.
Where did I gave the impression that I was stating, or implying, otherwise?
You mention Linux specifically as using one of the entropy sources you listed:
Using CPU jitter (currently used by the Linux kernel).
Which implies that Linux doesn’t use the other sources. But Linux also uses hardware RNGs and interrupt timing from the keyboard and mouse (and network, etc.) and it only uses the jitter dance as a last resort when the other sources aren’t available.
And later you suggest that what Linux does is a bad idea:
Thankfully, these days CPU jitter is all you need on a typical server. […] Anything more involved adds unnecessary complexity, and therefore unnecessary risk.
Dammit, that should have been obvious. Of course it does, thanks.
and interrupt timing from the keyboard and mouse (and network, etc.)
But they’re not available at boot time. And on a server, by the time you hit the network you might already need random numbers to secure your comms.
and it only uses the jitter dance as a last resort when the other sources aren’t available.
Does this implies that jitter is not as reliable as I thought it is? I know it definitely isn’t on many CPUs (especially in-order, small embedded cores), but I assumed on your typical x86-64 machine, it is. Was I wrong?
And later you suggest that what Linux does is a bad idea:
Well, I’m not so sure about jitter already, but if we assume the boot process generates a reliable random seed somehow (possibly with the help of hardware RNG), then we’re done. Fast key erasure until the next reboot, maybe reseed upon a security update (but if you make a security update you probably should reboot anyway).
If you can have that, then anything more complex is a bad idea. (Though of course Linux also runs on systems that don’t have that, and having custom code for your system, even if it’s simpler, is likely riskier than using the stock kernel… Defeats my whole point, but you get the ideal I strive to.)
Does this implies that jitter is not as reliable as I thought it is? I know it definitely isn’t on many CPUs (especially in-order, small embedded cores), but I assumed on your typical x86-64 machine, it is. Was I wrong?
As far as I know it’s still considered snake oil (see for instance the old comments about HAVEGE at https://lwn.net/Articles/525459/ or the skepticism in https://lwn.net/Articles/642166/) and it was added to Linux in full awareness that its security justification is no more than handwaving.
I've amended my article to stop recommending jitter as the only random source, and removed the misleading Linux kernel reference. Thanks a ton for the correction and references.
by the time you hit the network you might already need random numbers to secure your comms.
IRQs fire quite a bit before any packets are sent. Just enabling the interface will catch some negotiation / ARP happening. That will likely happen before you even start generating the SSH key. And long before you want to send encrypted traffic.
The lava lamps are a bit silly though, given just how good CCD shot noise is on its own. A digital camera is a fantastically good entropy source even facing a blank wall.
For cryptographic purposes we’ve settled on a predictability of 2^-256 but amusingly there are common processes where the number of possible outcomes can be much greater, and we want to be able to exercise every possible outcome no matter how unlikely that is. In that situation cryptographic randomness might be insufficient!
A standard deck of cards has 52! shuffles which is about 2^226, so you can get every possible shuffle from a cryptographically random seed. But if you are playing Uno or shuffling more than one deck together, a 256 bit RNG doesn’t have enough state to produce every shuffle. If all the userland randomness in a system comes from the kernel, and if the kernel funnels all the hardware randomness through a 256 bit CSPRNG, then it might not be good enough for shuffling cards in Las Vegas :-)
Something missing from the essay is reseeding, which is probably of interest because of how it interacts with fast key erasure, and how it highlights the difficulty of getting an initial seed. The article implies that Linux only uses CPU jitter, which is an oversimplification: it uses lots of sources of randomness, and only uses the jitter dance as a last resort.
For cryptographic purposes we’ve settled on a predictability of 2^-256 but amusingly there are common processes where the number of possible outcomes can be much greater, and we want to be able to exercise every possible outcome no matter how unlikely that is.
No we don’t. Ever.
In real life, you can’t even get 2^128 samples. A great deal less than that in fact, which is why AES-128 is still secure enough for many applications. "Exercising every possible outcome", when that number is greater than 2^256, is flat out impossible. Forget about it. It’s not a thing, it doesn’t exist.
When you play blackjack with 6 deck of cards instead of just one, you don’t actually want a shuffling process that distribute the probability evenly across each possible shuffle. You just want a distribution good enough that after you’ve sampled it as much as you possibly could, you can’t tell the difference. And you won’t, even when the number of shuffles is restricted to 2^256, or even 2^128.
Something missing from the essay is reseeding
That’s on purpose. We only need to reseed at specific points: suspected breaches and some security updates. And reboots if it’s simpler or more secure than maintaining RNG state in non-volatile memory. So rather than "reseeding", I prefer to just start over with a new initial seed.
Reseeding during normal operations is never needed. There’s no point implementing that, it just makes things more complex.
The article implies that Linux only uses CPU jitter
Oops, I should have checked. My understanding was that at boot time it’s the only thing it has. Especially before user and network input. What other sources are you aware of? I guess there’s support for hardware RNG already?
The possible vs. predictable distinction reminds me of a paper by Shamir, Rivest, and Adleman which proves that it's mathematically impossible for two people to play a secure game of poker over the phone with a virtual deck of cards. Can't be done. But with that out of the way, here's how you do it securely…
Do you have a proper explanation for the (hinted at) resolution to the paradox?
My reading is that S_a and S_b aren't actually of size 2 (coming back to a deck of 3 cards) in the cryptographic protocol, but I don't know how to formalise that claim. Something about the fact that inverting E(X) is too hard to compute for Bob, but we're still violating our assumption in the proof.
I think you're correct. I might be butchering this, but here goes from Bob's perspective:
Bob knows Alice's possible cards can't be S_a = {X,Y,Z} because Bob is holding Y right now, and the only way for Alice to have Y is if she violated the protocol. Bob also knows S_a can't be {X,Z} because Alice's card bounced back and forth between them as an encrypted message (i.e., the message is on the record and immutable), and the encryption was deterministic (it can only map to a single card). So Bob knows the size of the set S_a must be 1. By the proof, this means that Bob must have gained some information about Alice's card.
What Bob doesn't know is whether S_a = {X} or S_a = {Z}, but only for a lack of computation.
In theory: He could try all possible values for Alice's key until he finds the one that decrypts every message they had exchanged. That's a deterministic calculation he could run from start to finish, using only the info he already has, with guaranteed success.[♣]
In practice: Bob can't stall for that much time.
[♣] Technically, there's a very slim chance of there being multiple keys that decrypt all of the messages. Alice encrypted two cards with her key, and from Bob's perspective there are only two valid pairs of plaintexts: (Y, X) or (Y, Z). If these numbers were each deterministically padded out to 4096 bits, there's something like a 1 in 2^4095 chance that Bob will find a key that works purely by coincidence, not because it's Alice's actual key.
But if that ever did happen, Bob would truly not know which card Alice got. I think the reason it doesn't break the proof is because the protocol no longer immutably assigns cards to players; Alice could change her card by brute-forcing that alternate key, whereas the proof only covers the impossibility of protocols that prevent cheating.
I'll try to give a different explanation and see if the internet will shout at me for being wrong: When using cryptographic keys, we're not dealing with a set of 3 cards that we then start removing from. Instead, we start with a huge N of permutations of the 3 cards (lots of them the same). Each exchanged message removes some of the permutations (both parties know which), but the full contents of any of them can't be understood by a single party. This seems to tie in nicely with both short keys and key reuse, because after enough messages, the pool of permutations becomes small enough to check against all possibilities.
Yup, each message prunes down the state space. The distinction is Alice and Bob can only prune down what they are capable of computing, whereas a perfect logician eavesdropper would prune it down based on what is theoretically possible to compute.
As for "enough messages", the proof says you only need a single game's worth. Suppose Eve had unlimited compute and had listened in during a single game:
If the messages eliminate enough possibilities that she can deduce either player's card, then the protocol has a privacy flaw.
But if the messages don't lock in either player's card, then it's possible for both players to have chosen the same card, and the protocol has a correctness flaw.
So all protocols must be flawed, but it's only academic. They're flawed in the same sense that all ciphers are inferior to one time pads, or that a 128-bit RNG can't shuffle a deck fairly.
This is interesting. IIRC, reading a random source (true, not pseudo) is a blocking operation, meaning that if the kernel doesn't have enough random bytes it'll take some (potentially long) time to finish reading enough randomness.
I'm guessing, that the hardware cards with random generators existed to get parallel sources of randomness that's measured not only in bit denseness but also in bits per unit of time.
The Linux RNG behaviour has changed in the last several years: both /dev/random and /dev/urandom are now free running, there’s no ongoing entropy estimation. However most random APIs can block at boot if they are called before the RNG has finished seeding.
There's not much here I individually disagree with, but I found the through-line muddy. The article builds heavily around "modern crypto needs far less true randomness than people think" then lands on "therefore the lava lamps are worse because they expand the attack surface." Both claims may be true, but it's rough landing.
Lava rand was doing this >20 years ago. It was cute then, but the sensors on cameras of that era were much smaller and the predictable features of the lenses etc made it a poor source of entropy.
I love lavalamps, but the power draw of a wall of hundreds of them is pretty significant imho for a gimmick.
Depends on the interpretation of "stories and comments":
It's great to have authors participate in the community, but not to exploit it as a write-only tool for product announcements or driving traffic to their work. As a rule of thumb, self-promo should be less than a quarter of one's stories and comments.
With 1399 comments to their 15 stories, they're definitely participating in the community—unless they're leaving 90+ of their own comments on each of their own stories.
I just added the comments in the stories I submitted, total was 281. And that’s everyone’s comments, not just mine. Comparing that to my 1401 total comments, that’s almost exactly 20%, comfortably below the 25% "rule of thumb". I believe I’m okay. ☺️
Cloudflare contributed entropy from their lava lamps, University of Chile contributed seismic data, (iirc) EPFL contributed radioactive decay readings, and other folks a bunch of other stuff in the founding key ceremony of the drand network.
Could we have used CSPRNGs? Sure, but where’s the fun in that?
Fun is fine. Those lava lamps are pretty, and their wave motion wall is positively beautiful. Where they cross a line is when they pretend they actually help with security.
As a random source it’s not. Depending how it’s set up, it can range from quite okay to basically perfect. The real problem is the distance from the camera and the servers that get randomness from it. One more communication channel, one more way for things to go wrong, more complexity, more attack surface.
This additional complexity and attack surface, however tiny, hurts security more than a perfect random source could ever add.
spillybones | a day ago
I think this article is misinformed and also a bit of a killjoy. Modern random number generation uses many independent sources of entropy, which are hashed together into an entropy pool continuously while the computer is running. There is no singular "random seed" for a computer, it is constantly re-seeding using entropy from different sources while it runs using something like
seed = hash(seed, new_data). Adding data from a camera filming a lava lamp absolutely does not reduce the security of the system in any way. Data fed into entropy pool is hashed together with other data that has been fed into the entropy pool. The system is designed to be secure as long as there is even a tiny amount of information not known to the attacker, which allows you to mix in lots of data of varying levels of randomness without compromising the security of the system in any way.The lava lamps do not harm the system's security in any way, and in my opinion, serve as a delightful and functional art piece that forms a part of the system (and increases the random number quality by an infinitesimal amount), while visually illustrating the concepts of randomness and entropy.
fanf | 23 hours ago
Right, but kernel RNGs have been using diverse hardware randomness for over 30 years now, and be careful not to overstate how continuously or constantly they are re-seeded. Randomness is gathered from hardware continuously, but the Linux RNG is reseeded periodically: every few seconds during the first minute after boot, slowing down to once a minute after that.
https://www.zx2c4.com/projects/linux-rng-5.17-5.18/inside-linux-kernel-rng-presentation-sept-13-2022.pdf
[OP] Loup-Vaillant | 23 hours ago
Where did I gave the impression that I was stating, or implying, otherwise? I didn’t mean to describe existing systems here (apart from the lava lamps bit), I wanted to stress how little we actually need. That is, 256 bits.
Attack surface anyone? You’re adding an embedded computer and network communications between that and the server. To me it’s pretty clear that the (low) added risk far outweigh the (stupidly low) risk of actually needing the lava lamps.
fanf | 23 hours ago
You mention Linux specifically as using one of the entropy sources you listed:
Which implies that Linux doesn’t use the other sources. But Linux also uses hardware RNGs and interrupt timing from the keyboard and mouse (and network, etc.) and it only uses the jitter dance as a last resort when the other sources aren’t available.
And later you suggest that what Linux does is a bad idea:
[OP] Loup-Vaillant | 22 hours ago
Dammit, that should have been obvious. Of course it does, thanks.
But they’re not available at boot time. And on a server, by the time you hit the network you might already need random numbers to secure your comms.
Does this implies that jitter is not as reliable as I thought it is? I know it definitely isn’t on many CPUs (especially in-order, small embedded cores), but I assumed on your typical x86-64 machine, it is. Was I wrong?
Well, I’m not so sure about jitter already, but if we assume the boot process generates a reliable random seed somehow (possibly with the help of hardware RNG), then we’re done. Fast key erasure until the next reboot, maybe reseed upon a security update (but if you make a security update you probably should reboot anyway).
If you can have that, then anything more complex is a bad idea. (Though of course Linux also runs on systems that don’t have that, and having custom code for your system, even if it’s simpler, is likely riskier than using the stock kernel… Defeats my whole point, but you get the ideal I strive to.)
fanf | 22 hours ago
As far as I know it’s still considered snake oil (see for instance the old comments about HAVEGE at https://lwn.net/Articles/525459/ or the skepticism in https://lwn.net/Articles/642166/) and it was added to Linux in full awareness that its security justification is no more than handwaving.
There’s lots about the rationale for Linux’s /dev/random in https://www.zx2c4.com/projects/linux-rng-5.17-5.18/inside-linux-kernel-rng-presentation-sept-13-2022.pdf
[OP] Loup-Vaillant | 5 hours ago
I've amended my article to stop recommending jitter as the only random source, and removed the misleading Linux kernel reference. Thanks a ton for the correction and references.
viraptor | 14 hours ago
IRQs fire quite a bit before any packets are sent. Just enabling the interface will catch some negotiation / ARP happening. That will likely happen before you even start generating the SSH key. And long before you want to send encrypted traffic.
marginalia | 3 hours ago
The lava lamps are a bit silly though, given just how good CCD shot noise is on its own. A digital camera is a fantastically good entropy source even facing a blank wall.
fanf | a day ago
Another way to phrase the philosophical split is,
For cryptographic purposes we’ve settled on a predictability of 2^-256 but amusingly there are common processes where the number of possible outcomes can be much greater, and we want to be able to exercise every possible outcome no matter how unlikely that is. In that situation cryptographic randomness might be insufficient!
A standard deck of cards has 52! shuffles which is about 2^226, so you can get every possible shuffle from a cryptographically random seed. But if you are playing Uno or shuffling more than one deck together, a 256 bit RNG doesn’t have enough state to produce every shuffle. If all the userland randomness in a system comes from the kernel, and if the kernel funnels all the hardware randomness through a 256 bit CSPRNG, then it might not be good enough for shuffling cards in Las Vegas :-)
Something missing from the essay is reseeding, which is probably of interest because of how it interacts with fast key erasure, and how it highlights the difficulty of getting an initial seed. The article implies that Linux only uses CPU jitter, which is an oversimplification: it uses lots of sources of randomness, and only uses the jitter dance as a last resort.
[OP] Loup-Vaillant | 22 hours ago
No we don’t. Ever.
In real life, you can’t even get 2^128 samples. A great deal less than that in fact, which is why AES-128 is still secure enough for many applications. "Exercising every possible outcome", when that number is greater than 2^256, is flat out impossible. Forget about it. It’s not a thing, it doesn’t exist.
When you play blackjack with 6 deck of cards instead of just one, you don’t actually want a shuffling process that distribute the probability evenly across each possible shuffle. You just want a distribution good enough that after you’ve sampled it as much as you possibly could, you can’t tell the difference. And you won’t, even when the number of shuffles is restricted to 2^256, or even 2^128.
That’s on purpose. We only need to reseed at specific points: suspected breaches and some security updates. And reboots if it’s simpler or more secure than maintaining RNG state in non-volatile memory. So rather than "reseeding", I prefer to just start over with a new initial seed.
Reseeding during normal operations is never needed. There’s no point implementing that, it just makes things more complex.
Oops, I should have checked. My understanding was that at boot time it’s the only thing it has. Especially before user and network input. What other sources are you aware of? I guess there’s support for hardware RNG already?
bitshift | 23 hours ago
The possible vs. predictable distinction reminds me of a paper by Shamir, Rivest, and Adleman which proves that it's mathematically impossible for two people to play a secure game of poker over the phone with a virtual deck of cards. Can't be done. But with that out of the way, here's how you do it securely…
viraptor | 13 hours ago
That's such a cool paper, thank you for linking it.
Ambroisie | 22 hours ago
Do you have a proper explanation for the (hinted at) resolution to the paradox?
My reading is that S_a and S_b aren't actually of size 2 (coming back to a deck of 3 cards) in the cryptographic protocol, but I don't know how to formalise that claim. Something about the fact that inverting E(X) is too hard to compute for Bob, but we're still violating our assumption in the proof.
bitshift | 19 hours ago
I think you're correct. I might be butchering this, but here goes from Bob's perspective:
Bob knows Alice's possible cards can't be
S_a = {X,Y,Z}because Bob is holding Y right now, and the only way for Alice to have Y is if she violated the protocol. Bob also knowsS_acan't be{X,Z}because Alice's card bounced back and forth between them as an encrypted message (i.e., the message is on the record and immutable), and the encryption was deterministic (it can only map to a single card). So Bob knows the size of the setS_amust be 1. By the proof, this means that Bob must have gained some information about Alice's card.What Bob doesn't know is whether
S_a = {X}orS_a = {Z}, but only for a lack of computation.[♣] Technically, there's a very slim chance of there being multiple keys that decrypt all of the messages. Alice encrypted two cards with her key, and from Bob's perspective there are only two valid pairs of plaintexts: (Y, X) or (Y, Z). If these numbers were each deterministically padded out to 4096 bits, there's something like a 1 in 2^4095 chance that Bob will find a key that works purely by coincidence, not because it's Alice's actual key.
But if that ever did happen, Bob would truly not know which card Alice got. I think the reason it doesn't break the proof is because the protocol no longer immutably assigns cards to players; Alice could change her card by brute-forcing that alternate key, whereas the proof only covers the impossibility of protocols that prevent cheating.
viraptor | 13 hours ago
I'll try to give a different explanation and see if the internet will shout at me for being wrong: When using cryptographic keys, we're not dealing with a set of 3 cards that we then start removing from. Instead, we start with a huge N of permutations of the 3 cards (lots of them the same). Each exchanged message removes some of the permutations (both parties know which), but the full contents of any of them can't be understood by a single party. This seems to tie in nicely with both short keys and key reuse, because after enough messages, the pool of permutations becomes small enough to check against all possibilities.
bitshift | 54 minutes ago
Yup, each message prunes down the state space. The distinction is Alice and Bob can only prune down what they are capable of computing, whereas a perfect logician eavesdropper would prune it down based on what is theoretically possible to compute.
As for "enough messages", the proof says you only need a single game's worth. Suppose Eve had unlimited compute and had listened in during a single game:
So all protocols must be flawed, but it's only academic. They're flawed in the same sense that all ciphers are inferior to one time pads, or that a 128-bit RNG can't shuffle a deck fairly.
peter-leonov | 12 hours ago
This is interesting. IIRC, reading a random source (true, not pseudo) is a blocking operation, meaning that if the kernel doesn't have enough random bytes it'll take some (potentially long) time to finish reading enough randomness.
I'm guessing, that the hardware cards with random generators existed to get parallel sources of randomness that's measured not only in bit denseness but also in bits per unit of time.
fanf | 9 hours ago
The Linux RNG behaviour has changed in the last several years: both /dev/random and /dev/urandom are now free running, there’s no ongoing entropy estimation. However most random APIs can block at boot if they are called before the RNG has finished seeding.
jonathannen | 16 hours ago
There's not much here I individually disagree with, but I found the through-line muddy. The article builds heavily around "modern crypto needs far less true randomness than people think" then lands on "therefore the lava lamps are worse because they expand the attack surface." Both claims may be true, but it's rough landing.
[OP] Loup-Vaillant | 10 hours ago
To be honest I’m not very satisfied with the narrative structure. But I did write out half the conclusion in the title.
jmtd | 13 hours ago
Lava rand was doing this >20 years ago. It was cute then, but the sensors on cameras of that era were much smaller and the predictable features of the lenses etc made it a poor source of entropy.
I love lavalamps, but the power draw of a wall of hundreds of them is pretty significant imho for a gimmick.
ucirello | 18 hours ago
Self-promotion, almost never share links, when poster does, they post their own links. 5 out of last 5 posts refer to their own material.
bitshift | 18 hours ago
Depends on the interpretation of "stories and comments":
With 1399 comments to their 15 stories, they're definitely participating in the community—unless they're leaving 90+ of their own comments on each of their own stories.
[OP] Loup-Vaillant | 9 hours ago
I just added the comments in the stories I submitted, total was 281. And that’s everyone’s comments, not just mine. Comparing that to my 1401 total comments, that’s almost exactly 20%, comfortably below the 25% "rule of thumb". I believe I’m okay. ☺️
bitshift | 2 hours ago
I hope I didn't pressure you into counting! I was just trying to say that I already thought you were within the spirit of the
lawrule of thumb.CluEleSsUK | 15 hours ago
Cloudflare contributed entropy from their lava lamps, University of Chile contributed seismic data, (iirc) EPFL contributed radioactive decay readings, and other folks a bunch of other stuff in the founding key ceremony of the drand network.
Could we have used CSPRNGs? Sure, but where’s the fun in that?
[OP] Loup-Vaillant | 10 hours ago
Fun is fine. Those lava lamps are pretty, and their wave motion wall is positively beautiful. Where they cross a line is when they pretend they actually help with security.
justJanne | 9 hours ago
How is that wall of lava lamps worse than any other hardware RNG as one of the many sources for randomness?
[OP] Loup-Vaillant | 9 hours ago
As a random source it’s not. Depending how it’s set up, it can range from quite okay to basically perfect. The real problem is the distance from the camera and the servers that get randomness from it. One more communication channel, one more way for things to go wrong, more complexity, more attack surface.
This additional complexity and attack surface, however tiny, hurts security more than a perfect random source could ever add.
CluEleSsUK | 15 hours ago