The Futility of Lava Lamps: What Random Really Means
17 points by Loup-Vaillant
17 points by Loup-Vaillant
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.
But Linux also uses hardware RNGs
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.
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
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.
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.
[♣] 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.
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.
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.
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.