Ask HN: Why don't PCs have better entropy sources?
138 comments
PCs can and do include hardware support for entropy gathering, see RDSEED [1]
Linux is aware of RDSEED and uses it to provide additional randomness when available. You do need to trust the implementation to be free from backdoors and bugs - some CPUs are known to be buggy. [2]
Randomness seeding issues largely does not concern desktop PCs or smartphones (although you can easily catch early booting programs like systemd reading randomness before it has been fully seeded) [3].
It is a much bigger issue on either small embedded devices or VMs, both of which may have very few peripherals to gather entropy from. They can be provided randomness through dedicated hardware support, or from the host, and they probably should be, but that still leaves many real-world systems currently running Linux out in the cold. This is not just a theoretical problem, as has been shown by looking at indicators like RSA keys with colliding primes, which should never happen when generated with good RNG. [4]
[1] https://en.wikipedia.org/wiki/RDRAND
[2] https://github.com/systemd/systemd/issues/18184
[3] https://github.com/systemd/systemd/issues/4167
[4] https://freedom-to-tinker.com/2012/02/15/new-research-theres...
Linux is aware of RDSEED and uses it to provide additional randomness when available. You do need to trust the implementation to be free from backdoors and bugs - some CPUs are known to be buggy. [2]
Randomness seeding issues largely does not concern desktop PCs or smartphones (although you can easily catch early booting programs like systemd reading randomness before it has been fully seeded) [3].
It is a much bigger issue on either small embedded devices or VMs, both of which may have very few peripherals to gather entropy from. They can be provided randomness through dedicated hardware support, or from the host, and they probably should be, but that still leaves many real-world systems currently running Linux out in the cold. This is not just a theoretical problem, as has been shown by looking at indicators like RSA keys with colliding primes, which should never happen when generated with good RNG. [4]
[1] https://en.wikipedia.org/wiki/RDRAND
[2] https://github.com/systemd/systemd/issues/18184
[3] https://github.com/systemd/systemd/issues/4167
[4] https://freedom-to-tinker.com/2012/02/15/new-research-theres...
I can't agree on embedded devices.
They have plenty of peripherals that can act as sensors, where you can draw entropy seeds from.
You can even leave an empty pin with a PCB trace to act as a crude antenna and pick up garbage RF.
You can use the built in RC oscillator as a crude temperature sensor.
My point is, if you're creative, embedded systems offer you so many options without any added cost.
They have plenty of peripherals that can act as sensors, where you can draw entropy seeds from.
You can even leave an empty pin with a PCB trace to act as a crude antenna and pick up garbage RF.
You can use the built in RC oscillator as a crude temperature sensor.
My point is, if you're creative, embedded systems offer you so many options without any added cost.
You don't even need sensors. STMicroelectronics has a TRNG block [1] that "passes" NIST SP 800-22 statistical analysis [2]. I used quotes because the 800-22 is an analysis test suite and the notion of passing is based on your hypothesis parameters, but the suite itself is considered the de-facto analysis mechanism.
I don't follow where the confusion is coming from?
[1] https://www.st.com/resource/en/application_note/dm00073853-s...
[2] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...
I don't follow where the confusion is coming from?
[1] https://www.st.com/resource/en/application_note/dm00073853-s...
[2] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...
The problem with using pins to pick up 'garbage' RF is that an attacker can transmit some actual RF and make your entropy a lot more predictable.
A real randomness source would be really great to have in pretty much every computing device these days, considering the widespread use of encryption.
A real randomness source would be really great to have in pretty much every computing device these days, considering the widespread use of encryption.
Agreed, but my example was for very low cost embedded systems where that makes sense like super cheap IoT sensors where every fraction of a cent is accounted for.
If your security threat profile has to account for actors with the resources to perform reverse engineering of your hardware, side channel analysis and RF injection, then we're already way out of the realm of low cost devices.
If your security threat profile has to account for actors with the resources to perform reverse engineering of your hardware, side channel analysis and RF injection, then we're already way out of the realm of low cost devices.
You're probably right, the issue might be that there's no standard way for an OS to hook into that.
The embedded systems that GP is referring to generally don't have a full-stack OS; hardware access is performed by directly reading to/writing from registers.
Hmm good points, but you also ignore the power costs here - using oscillators, open pins as thermometers and rf antennas requires additional power draw, not to mention modifying these devices may be nearly impossible due to their embedded nature.
Even presuming you modify the hardware/firmware, the additional cycles to handle and process the sensor data mean additional power draw compared to normal operation (embedded devices may frequently power down to wake from some interrupt to save power, additionally not all instructions turn on the same number of transistors - floating point ops require more power than simple branch instructions) - something again that prohibits doing this easily.
So "without any added cost" is simply untrue.
The reality is that randomness is relatively expensive, whether via hardware or software. Phones have more sensors - they also have massively complex SoCs and large batteries, which still are drained often over the course of a single day. They also tend to cost 1k+ USD, at least for flagship models (prices go as low as 50$ these days, but this is more from economies of scale and resale value economics than because phone hardware/software is suddenly cheap to manufacture)
Even presuming you modify the hardware/firmware, the additional cycles to handle and process the sensor data mean additional power draw compared to normal operation (embedded devices may frequently power down to wake from some interrupt to save power, additionally not all instructions turn on the same number of transistors - floating point ops require more power than simple branch instructions) - something again that prohibits doing this easily.
So "without any added cost" is simply untrue.
The reality is that randomness is relatively expensive, whether via hardware or software. Phones have more sensors - they also have massively complex SoCs and large batteries, which still are drained often over the course of a single day. They also tend to cost 1k+ USD, at least for flagship models (prices go as low as 50$ these days, but this is more from economies of scale and resale value economics than because phone hardware/software is suddenly cheap to manufacture)
None of that is at all expensive.
Reading from RF trace does not take any more power than any other analog pin voltage measurement.
Running a few more instructions to "process" (not as if there's much processing needed) the sensor readings is also hardly measurable.
Reading from RF trace does not take any more power than any other analog pin voltage measurement.
Running a few more instructions to "process" (not as if there's much processing needed) the sensor readings is also hardly measurable.
[deleted]
For KVM VMs, please use virtio-rng! If you have virtio (which most VMs do) then adding a virtio-rng virtual device costs nothing and gives the VM access to the host's entropy. systemd etc in the VM should then have no problem at all consuming as much entropy as it likes as early in the boot as it needs.
https://wiki.qemu.org/Features/VirtIORNG
https://wiki.qemu.org/Features/VirtIORNG
Could timing be used to seed a cpu? ie, not all cpus are built the same, and similarly for all powersupplies, could the two be used together to bootstrap seeding i.e. by measuring voltage or voltage differences?
Tha'ts effectively how a lot of the jitter sourced entropy ends up working, sometimes in a more round about way though.
Yes! I went to a talk given by a security researcher who proposed using the difference in clocks between north bridge and south bridge to generate randomness.
this article mentions timing of hardware interrupts as an entropy source. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72...
another possible entropy source: the sequence of different kinds of hardware interrupts should be very hard to predict.
I think it's worth repeating this:
While there are platforms with better and worse hardware sources of unpredictable bits, the problem with Linux /dev/random isn't so much a hardware issue, but rather a software one. The fundamental problem Linux tries to solve isn't that hard, as you can see from the fact that so many other popular platforms running on similar hardware have neatly solved it.
The problem with the LRNG is that it's been architecturally incoherent for a very long time (entropy estimation, urandom vs random, lack of clarity about seeding and initialization status, behavior doing bootup). As a result, an ecosystem of software has grown roots around the design (and bugs) of the current LRNG. Major changes to the behavior of the LRNG breaks "bug compatibility", and, because the LRNG is one of the core cryptographic facilities in the kernel, this is an instance where you really really don't want to break userland.
The basic fact of kernel random number generation is this: once you've properly seeded an RNG, your acute "entropy gathering" problem is over. Continuous access to high volumes of high-entropy bits are nice to have, but the kernel gains its ability to satisfy gigabytes of requests for random numbers from the same source that modern cryptography gains its ability to satisfy gigabytes of requests for ciphertext with a 128 bit key.
People looking to platform hardware (or who fixate on the intricacies of threading the LRNG isn't guest VMs) are mostly looking in the wrong place for problems to solve. The big issue today is that the LRNG is still pretty incoherent, but nobody really knows what would break if it was designed more carefully.
While there are platforms with better and worse hardware sources of unpredictable bits, the problem with Linux /dev/random isn't so much a hardware issue, but rather a software one. The fundamental problem Linux tries to solve isn't that hard, as you can see from the fact that so many other popular platforms running on similar hardware have neatly solved it.
The problem with the LRNG is that it's been architecturally incoherent for a very long time (entropy estimation, urandom vs random, lack of clarity about seeding and initialization status, behavior doing bootup). As a result, an ecosystem of software has grown roots around the design (and bugs) of the current LRNG. Major changes to the behavior of the LRNG breaks "bug compatibility", and, because the LRNG is one of the core cryptographic facilities in the kernel, this is an instance where you really really don't want to break userland.
The basic fact of kernel random number generation is this: once you've properly seeded an RNG, your acute "entropy gathering" problem is over. Continuous access to high volumes of high-entropy bits are nice to have, but the kernel gains its ability to satisfy gigabytes of requests for random numbers from the same source that modern cryptography gains its ability to satisfy gigabytes of requests for ciphertext with a 128 bit key.
People looking to platform hardware (or who fixate on the intricacies of threading the LRNG isn't guest VMs) are mostly looking in the wrong place for problems to solve. The big issue today is that the LRNG is still pretty incoherent, but nobody really knows what would break if it was designed more carefully.
The piece I've been missing in this whole debate: why isn't the existing RNG simply frozen in its current bug-exact-behavior state and a new /dev/sane_random created?
Stuff that depends on the existing bugs in order to function can keep functioning. Everything else can move to something sane.
Obviously I'm missing something here.
Stuff that depends on the existing bugs in order to function can keep functioning. Everything else can move to something sane.
Obviously I'm missing something here.
Because /dev/sane_random or sane_random(2) has better security properties than what we have now, and you want the whole gamut of Linux software to benefit from that; just as importantly, you don't want /dev/urandom and getrandom(2) to fall into disrepair as attention shifts to the new interface, for the same reason that you care very much about UAF vulnerabilities in crappy old kernel facilities most people don't build new stuff on anymore.
Also, just, it seems unlikely that the kernel project is going to agree to run two entire unrelated CSPRNG subsystems at the same time! The current LRNG is kind of an incoherent mess root and branch; it's not just a matter of slapping a better character device and system call on top of it.
Also, just, it seems unlikely that the kernel project is going to agree to run two entire unrelated CSPRNG subsystems at the same time! The current LRNG is kind of an incoherent mess root and branch; it's not just a matter of slapping a better character device and system call on top of it.
Because you answered their question, I'm hoping you can answer my question.
How is there any overlap in the devices that can't have something clever figured out and devices that could possibly see an update to their kernel code?
How is there any overlap in the devices that can't have something clever figured out and devices that could possibly see an update to their kernel code?
Kernel side something clever almost certainly will be figured out eventually just not in time for the 5.18 release (or probably following release either realistically). User space side it doesn't matter if there is an absolutely trivial clever fix available you can't just break it without extremely good reason.
Note: Extremely good reason for breaking userspace is along the lines of "/dev/random has been found to be insecure causing mass security mayhem" not "man I'd really like to ignore the 0.01% of users this would cause an issue for so I can get my patch in faster".
Note: Extremely good reason for breaking userspace is along the lines of "/dev/random has been found to be insecure causing mass security mayhem" not "man I'd really like to ignore the 0.01% of users this would cause an issue for so I can get my patch in faster".
cough mysql_real_escape_string cough
Windows APIs from what I hear share a similar issue to /dev/random (apps rely on bugs in APIs). Maybe the problem is the lack of forward thinking to fix issues.
> Obviously I'm missing something here
For a start, there's a long tail of migrating all useful software to /dev/sane_random. Moreover, there's a risk new software accidentally uses the old broken /dev/random.
Besides, /dev/sane_random essentially exists; it's just a sysctl called getrandom().
For a start, there's a long tail of migrating all useful software to /dev/sane_random. Moreover, there's a risk new software accidentally uses the old broken /dev/random.
Besides, /dev/sane_random essentially exists; it's just a sysctl called getrandom().
> Moreover, there's a risk new software accidentally uses the old broken /dev/random.
but that risk is at 100% NOW, how is it not worth reducing it?
but that risk is at 100% NOW, how is it not worth reducing it?
I fully agree.
It's not that simple; Donenfeld wants to replace the whole LRNG with a new engine that uses simpler, more modern, and more secure/easier-to-analyze cryptography, and one of the roadblocks there is that swapping out the engine risks breaking bugs that userland relies on.
What kind of bugs are visible to userland? I would have thought a random number device would be the least likely thing to have upgrade problems like that: applications should not be able to assume anything at all since the output is literally random...
Shouldn't it be easier than a kernel parameter to compare the performance of specific applications that relied upon the current behaviors; at least for a major rev or two?
All x86 CPUs sold after 2015 or so have built-in hardware random number generators [1]. They get their entropy by sampling thermal noise on the input of a meta-stable logic gate [2].
[1] https://en.wikipedia.org/wiki/RDRAND
[2] https://www.electronicdesign.com/resources/article/21796238/...
[1] https://en.wikipedia.org/wiki/RDRAND
[2] https://www.electronicdesign.com/resources/article/21796238/...
Is that just Intel CPUs or did AMD copy it too?
AMD CPUs have it, but have a different hardware design for its random number generator.
In both cases, RDSEED is "true random", according to Intel and AMD (though the specific argument for why it qualifies as true random differs on their designs)
RDSEED is like /dev/random while RDRAND is like /dev/urandom.
In both cases, RDSEED is "true random", according to Intel and AMD (though the specific argument for why it qualifies as true random differs on their designs)
RDSEED is like /dev/random while RDRAND is like /dev/urandom.
Read the LWN article. The problem isn’t PCs at all - it’s virtual machines, and embedded machines, that hang at startup, waiting for any entropy at all. Of course you could say the bug is in the hypervisor, or the embedded board designer, but the Linux kernel developers can’t afford to break these use cases just for purity’s sake.
So the problem is very practical, not theoretical. Someone just needs to do the plumbing, and get that entropy from host to guest OS.
> get that entropy from host to guest OS.
There are some ways, although that doesn't mean they're always used.
I read this week QEMU has provides a virtio RNG device to the guest, that reads from the host. That's good. What I'm less clear about is other hypervisors, or whether x86 hypervisors tend to provide RDRAND support.
There are some ways, although that doesn't mean they're always used.
I read this week QEMU has provides a virtio RNG device to the guest, that reads from the host. That's good. What I'm less clear about is other hypervisors, or whether x86 hypervisors tend to provide RDRAND support.
> or whether x86 hypervisors tend to provide RDRAND support.
One issue that I've been wondering about is how safe this is. Presumably you can't let a VM use the RDRAND directly because it could starve the entropy of other VMs. Assuming that presumption is true, a hypervisor would need to manage that shared resource fairly amongst the VMs.
One issue that I've been wondering about is how safe this is. Presumably you can't let a VM use the RDRAND directly because it could starve the entropy of other VMs. Assuming that presumption is true, a hypervisor would need to manage that shared resource fairly amongst the VMs.
I don't know this for sure, but I'm not under the impression that RDRAND has the same "entropy as a scarce resource" or "block waiting on entropy" issue that the Linux apis have.
RDSEED is actually what people want most of the time. RDRAND may return before sufficient entropy has been gathered.
Basically, RDRAND was made first to be something like a hardware /dev/urandom. Of course, people started using RDRAND to generate RSA-keys or whatever, but the entropy may be depleted between uses.
So you're supposed to use RDSEED whenever you need something that'd actually be truly random with a full set of entropy.
Basically, RDRAND was made first to be something like a hardware /dev/urandom. Of course, people started using RDRAND to generate RSA-keys or whatever, but the entropy may be depleted between uses.
So you're supposed to use RDSEED whenever you need something that'd actually be truly random with a full set of entropy.
Ah I realise I meant RDSEED
AFAIK part of the problem is Linux doesn't fully trust RDRAND. If it did, people would riot because they don't trust that Intel hasn't backdoored it.
If you don't trust the CPU wouldn't you have bigger and more fish to fry than just RDRAND?
Yes but RDRAND is easy to hide. No test can tell the difference between a good and a backdoored RNG, you don't know what to look for, the whole point of randomness is that you don't know what it will do, so you can only trust reasoning based on understanding where the numbers come from.
I'm pretty sure rdrand is fine, and would not bat an eye if Linux trusted it, but I'm not sure I would bet some nuclear launch codes on it. Linux is trying to be as safe as practically possible, not just "Probably safe".
I'm pretty sure rdrand is fine, and would not bat an eye if Linux trusted it, but I'm not sure I would bet some nuclear launch codes on it. Linux is trying to be as safe as practically possible, not just "Probably safe".
There are such sensors, listening to thermal noise, right inside most CPUs https://en.wikipedia.org/wiki/RDRAND It's a question of trust. Do you trust that Intel (or whoever builds the physical RNG) didn't build a backdoor, a secret predictability?
Maybe it's safer to build your own.. or combine several sources (like linux kernel does).
I don't see any problem with an INTEL on-cpu-die random number generator based on Johnson noise. What level of concern would someone have to have to NOT trust that?
If it's even remotely an issue there are dedicated hardware sources in various form-factors like PCIE or USB. They're pricey but at least you can vet what your getting if that matters so much.
Are there any real-world accounts of people getting pwned because of a bad pseudo rng?
If it's even remotely an issue there are dedicated hardware sources in various form-factors like PCIE or USB. They're pricey but at least you can vet what your getting if that matters so much.
Are there any real-world accounts of people getting pwned because of a bad pseudo rng?
A thermal noise-generator is fine from a physics perspective. I think that people maybe can't verify what's actually on the die.
How much do we trust what we're told about the circuit? Does its interface talk to that noise-source all the time? Or is there a cutaway inside that maybe jumps to a seeded PRNG in response to a special memory-write? Would you know if it did?
I'm not saying that RDRAND is backdoored. I've got no reason to assume that it is. But it would also be very hard to prove that it -isn't-. If I was doing something where I actually cared about the quality of my entropy, I might not want to just take Intel at their word.
How much do we trust what we're told about the circuit? Does its interface talk to that noise-source all the time? Or is there a cutaway inside that maybe jumps to a seeded PRNG in response to a special memory-write? Would you know if it did?
I'm not saying that RDRAND is backdoored. I've got no reason to assume that it is. But it would also be very hard to prove that it -isn't-. If I was doing something where I actually cared about the quality of my entropy, I might not want to just take Intel at their word.
> magnetometer, accelerometer, simple GPS,
At boot time, on a server sitting in a rack beside thousands of others ... how are these going to help any? They aint moving and the RF/energy environment around them should be steady state or well within characterize-able bounds of noise.
"Random enough" is a metaphysical question when you get into it. If an RTLSDR stick and a site customized munger script can't provide enough entropy for the entire data center you've fallen into a Purity spiral and will never be happy, anyway.
At boot time, on a server sitting in a rack beside thousands of others ... how are these going to help any? They aint moving and the RF/energy environment around them should be steady state or well within characterize-able bounds of noise.
"Random enough" is a metaphysical question when you get into it. If an RTLSDR stick and a site customized munger script can't provide enough entropy for the entire data center you've fallen into a Purity spiral and will never be happy, anyway.
There are true hardware random number generators. IIRC, one example is based on a reverse biased diode. Due random quantum effects, an electron flow backwards occasionally and measuring that gives you a source of real randomness.
The dedicated RNG scares the paranoid the most because it is an obvious target for corruption.
The best RNG solution for the paranoid would have been to have a standardized internal header/connector with an analog-digital converter input and a power supply, like the connector that exists on most motherboards for the front-panel audio (but preferably with a higher-frequency and lower-resolution ADC than for audio, even if an audio ADC is also acceptable).
If such a connector would have been standardized, very small analog noise generator boards that could be plugged in it would cost only a few dollars at most, and they would not contain any device more complex than an operational amplifier.
This solution cannot be back-doored, because it is trivial to test the ADC without a noise-generator attached, to verify that it really is an ADC and the small PCB with the analog noise generator can also be easily inspected to verify that it contains only the specified (analog) devices.
All this could have been very simple and cheap if it would have been standardized, and not more difficult to use than the unverifiable CPU instructions.
As it is, the paranoid must have electronics experience, to design and make their own analog-noise generator, to be used either with the microphone input of the PC audio connectors (which includes a weak power supply), or better with the ADC of a small microcontroller board, to be connected via USB (preferably on an internal USB connnector of the PC motherboard).
If such a connector would have been standardized, very small analog noise generator boards that could be plugged in it would cost only a few dollars at most, and they would not contain any device more complex than an operational amplifier.
This solution cannot be back-doored, because it is trivial to test the ADC without a noise-generator attached, to verify that it really is an ADC and the small PCB with the analog noise generator can also be easily inspected to verify that it contains only the specified (analog) devices.
All this could have been very simple and cheap if it would have been standardized, and not more difficult to use than the unverifiable CPU instructions.
As it is, the paranoid must have electronics experience, to design and make their own analog-noise generator, to be used either with the microphone input of the PC audio connectors (which includes a weak power supply), or better with the ADC of a small microcontroller board, to be connected via USB (preferably on an internal USB connnector of the PC motherboard).
> standardized, very small analog noise generator boards
The following design[1] uses _two_ pluggable analog noise generator boards (since you don't trust one). The writeup will be of interest to the paranoid in this thread.
[1] http://nosuchlabs.com/
The following design[1] uses _two_ pluggable analog noise generator boards (since you don't trust one). The writeup will be of interest to the paranoid in this thread.
[1] http://nosuchlabs.com/
Thanks for the link.
This is a good example of how you can make a RNG using a microcontroller board connected to an internal USB connector of the motherboard.
However what they have is not perfect, because the RNG boards include the ADC and some simple digital post-processing, providing a RS-232 serial output. For better auditability, the RNG boards should have been simpler, with only the analog part of the RNG, and they should have used an ADC input of the microcontroller instead of using a RS-232 input. If you compile from source and you write the flash of the microcontroller yourself, then it is secure enough.
Because only seldom such boards are available for buying, many people have done something like this only for themselves.
However the problem is that this is a non-standard solution. A connector like the 3-pin header shown at this link should have existed on every motherboard (but with analog input, not with RS-232 input). All software should have expected to have a standard RNG input on the motherboard, like it expects to have HD Audio input/output or temperature/RPM sensors. If the ADC would have been provided by the motherboard chipset, which already provides many other ADCs, there would have been no need for a microcontroller and no need of firmware for the microcontroller.
Had they wanted, Intel could have easily standardized a RNG input for the chipset, like they have standardized HDAudio, SMBus and countless other chipset features. Anyone else would have followed.
It is very likely that standardizing such a solution would have been actually much cheaper for Intel and AMD than implementing RNG instructions inside the CPU, which will always remain non-recommendable for any serious applications, so they waste die area and testing time during manufacturing, and they may also reduce a little the yields of good dies.
This is a good example of how you can make a RNG using a microcontroller board connected to an internal USB connector of the motherboard.
However what they have is not perfect, because the RNG boards include the ADC and some simple digital post-processing, providing a RS-232 serial output. For better auditability, the RNG boards should have been simpler, with only the analog part of the RNG, and they should have used an ADC input of the microcontroller instead of using a RS-232 input. If you compile from source and you write the flash of the microcontroller yourself, then it is secure enough.
Because only seldom such boards are available for buying, many people have done something like this only for themselves.
However the problem is that this is a non-standard solution. A connector like the 3-pin header shown at this link should have existed on every motherboard (but with analog input, not with RS-232 input). All software should have expected to have a standard RNG input on the motherboard, like it expects to have HD Audio input/output or temperature/RPM sensors. If the ADC would have been provided by the motherboard chipset, which already provides many other ADCs, there would have been no need for a microcontroller and no need of firmware for the microcontroller.
Had they wanted, Intel could have easily standardized a RNG input for the chipset, like they have standardized HDAudio, SMBus and countless other chipset features. Anyone else would have followed.
It is very likely that standardizing such a solution would have been actually much cheaper for Intel and AMD than implementing RNG instructions inside the CPU, which will always remain non-recommendable for any serious applications, so they waste die area and testing time during manufacturing, and they may also reduce a little the yields of good dies.
Here's another iteration: A user supplied board with a high-gain op-amp, a comparator, and a latch -- accepting a clock line -- could produce a definite noise-informed bit sequence. This bit sequence could be observed both at that level and the software level, to confirm that no alteration had taken place in-between, in the motherboard/chipset etc.
That would just give an attacker an easy way to control the entropy source.
Paranoid implies some aspect of unjustified fear. In this case the fear is quite justified.
What’s the point of not trusting the hardware entropy source while still trusting the rest of the chip / hardware?
For the rest of the chip / hardware there are at least some chances to test what they do and discover any suspicious behavior.
Any well-designed back-door in a black-box RNG cannot be discovered by testing.
Except for the RNG, the only other thing that cannot be trusted at all is because your computer/smartphone might allow remote connections to a management component of its hardware, regardless how you configure it.
Wired connections are not very dangerous, because you can pass them trough an external firewall and you can block anything suspicious.
The problem is with the WiFi connections, e.g. of the WiFi Intel chipsets in laptops, and obviously the least under your control are the mobile phones.
However even a smartphone can be put in a metal box to ensure that nobody can connect to it (even if that also defeats the main use of a mobile phone, it can make sense if you are worried about remote control only sometimes, not permanently).
On the other hand, a RNG that cannot be verified to be what it claims to be, is completely useless.
Any well-designed back-door in a black-box RNG cannot be discovered by testing.
Except for the RNG, the only other thing that cannot be trusted at all is because your computer/smartphone might allow remote connections to a management component of its hardware, regardless how you configure it.
Wired connections are not very dangerous, because you can pass them trough an external firewall and you can block anything suspicious.
The problem is with the WiFi connections, e.g. of the WiFi Intel chipsets in laptops, and obviously the least under your control are the mobile phones.
However even a smartphone can be put in a metal box to ensure that nobody can connect to it (even if that also defeats the main use of a mobile phone, it can make sense if you are worried about remote control only sometimes, not permanently).
On the other hand, a RNG that cannot be verified to be what it claims to be, is completely useless.
> For the rest of the chip / hardware there are at least some chances to test what they do and discover any suspicious behavior.
That there are some chances to test them does not provide any measure of trust... you actually have to perform the audit to achieve that.
>... On the other hand, a RNG that cannot be verified to be what it claims to be, is completely useless.
If we are going to take such an absolute line over RNGs, then, to be consistent, we should take the same attitude to the rest of the hardware and software we use - but, per my previous point, that means actually evaluating it, not just having the possibility of doing so.
One might, instead, argue that we should use only verifiable RNGs because that is actually feasible (at least for non-mobile equipment), but that does nothing to bring the rest of the system up to the standard of your last paragraph.
That there are some chances to test them does not provide any measure of trust... you actually have to perform the audit to achieve that.
>... On the other hand, a RNG that cannot be verified to be what it claims to be, is completely useless.
If we are going to take such an absolute line over RNGs, then, to be consistent, we should take the same attitude to the rest of the hardware and software we use - but, per my previous point, that means actually evaluating it, not just having the possibility of doing so.
One might, instead, argue that we should use only verifiable RNGs because that is actually feasible (at least for non-mobile equipment), but that does nothing to bring the rest of the system up to the standard of your last paragraph.
Like I have said, besides the RNG, the only other problem is with the possibility of remote connections to the computer chipset.
Any other malicious behavior is implausible, as either easy to detect or requiring too much information about the future (to be able to determine what to do and when to do without a remote control connection). Self-destruct is something that could happen e.g. after a certain number of active hours, but this would make sense only if you are a target for someone able to load special firmware into your own computer. If that would be a general feature of a computer, it would be easily detected after it would happen randomly.
So if you do not trust the HW, you must prevent remote connections. This is easy for desktop/server computers, if you do not have WiFi/Bluetooth/LTE and you do not use Intel Ethernet interfaces (or other chipset Ethernet interfaces, with remote management features) connected to the Internet or to any other untrusted network. Towards untrusted networks, you must use Ethernet interfaces without sideband management links, e.g. you may use securely USB Ethernet interfaces.
Unfortunately, currently there is no way to completely trust laptops when WiFi connections are possible, even if they claim that e.g. Intel vPro is disabled. In any case, it is still better if the manufacturer claims that this is true (like in my Dell laptop), even if you cannot verify the claim with certainty.
Even if someone would be able to connect remotely to your computer and spy you, they will have access only to your unencrypted or active documents.
If you use a bad RNG for encryption purposes, then the spies could also access any encrypted and non-active documents, which is a much greater danger.
In conclusion, the RNG is still in the top position of the hardware that cannot be tested and cannot be trusted. Nothing else comes close.
Any other malicious behavior is implausible, as either easy to detect or requiring too much information about the future (to be able to determine what to do and when to do without a remote control connection). Self-destruct is something that could happen e.g. after a certain number of active hours, but this would make sense only if you are a target for someone able to load special firmware into your own computer. If that would be a general feature of a computer, it would be easily detected after it would happen randomly.
So if you do not trust the HW, you must prevent remote connections. This is easy for desktop/server computers, if you do not have WiFi/Bluetooth/LTE and you do not use Intel Ethernet interfaces (or other chipset Ethernet interfaces, with remote management features) connected to the Internet or to any other untrusted network. Towards untrusted networks, you must use Ethernet interfaces without sideband management links, e.g. you may use securely USB Ethernet interfaces.
Unfortunately, currently there is no way to completely trust laptops when WiFi connections are possible, even if they claim that e.g. Intel vPro is disabled. In any case, it is still better if the manufacturer claims that this is true (like in my Dell laptop), even if you cannot verify the claim with certainty.
Even if someone would be able to connect remotely to your computer and spy you, they will have access only to your unencrypted or active documents.
If you use a bad RNG for encryption purposes, then the spies could also access any encrypted and non-active documents, which is a much greater danger.
In conclusion, the RNG is still in the top position of the hardware that cannot be tested and cannot be trusted. Nothing else comes close.
I can design a CPU that reads the operating system’s clock (easy-peasy) and is actually a time bomb that does something at a predefined time.
You could now argue that we can use some workbench that simulates these conditions, but then I will catch you on the fact that you can also determine that random output is changed (statistically for example) for some parameters of the system.
Either way enumerating all of these parameters is intractable due to the size of the search space.
Same thing goes to the fact that you can’t definitely say whether your CPU will always do what it says it does, purely because you can’t enumerate all possible execute paths as they are infinite.
You could now argue that we can use some workbench that simulates these conditions, but then I will catch you on the fact that you can also determine that random output is changed (statistically for example) for some parameters of the system.
Either way enumerating all of these parameters is intractable due to the size of the search space.
Same thing goes to the fact that you can’t definitely say whether your CPU will always do what it says it does, purely because you can’t enumerate all possible execute paths as they are infinite.
> you can’t enumerate all possible execute paths as they are infinite.
How do you design a CPU that isn't a finite state machine?
How do you design a CPU that isn't a finite state machine?
As soon as you try to tell us which kind of FSM the CPU is, you'll realize why it isn't any of them
I used to have a friend who worked at AMD, and he said they simulated one of their in-progress CPUs on five Virtex-5 FPGAs.
Looking here: https://docs.xilinx.com/v/u/en-US/ds100
* I see a lot of LUTs, adders, and common operations(not a theoretical problem).
* There's memory and IO, but that shouldn't matter for defining a single clock tick.
* Thermal/power monitoring - not sure how important that is, but sure that's outside the definition of a FSM.
I have written simple software and FPGA CPU cores, and I would describe all of them as FSMs. It's possible that newer CPUs wouldn't qualify because e.g. they rely on metastable circuits for randomness, power-monitoring, etc. but most of it should be a FSM and the exceptions aren't anything like "infinite execution paths".
Looking here: https://docs.xilinx.com/v/u/en-US/ds100
* I see a lot of LUTs, adders, and common operations(not a theoretical problem).
* There's memory and IO, but that shouldn't matter for defining a single clock tick.
* Thermal/power monitoring - not sure how important that is, but sure that's outside the definition of a FSM.
I have written simple software and FPGA CPU cores, and I would describe all of them as FSMs. It's possible that newer CPUs wouldn't qualify because e.g. they rely on metastable circuits for randomness, power-monitoring, etc. but most of it should be a FSM and the exceptions aren't anything like "infinite execution paths".
> Like I have said...
Yes, you are repeating yourself without addressing the issue that the ability to verify does not, by itself, confer any trust. Even if we accept your conclusion, it does not mean the other risks are inconsequential.
Yes, you are repeating yourself without addressing the issue that the ability to verify does not, by itself, confer any trust. Even if we accept your conclusion, it does not mean the other risks are inconsequential.
I think his point is the most consequential issue is the RNG, which to me makes a sort of sense.
You can never be truly secure and eliminate all potential concerns (what if there are invisible people with nanotech in your house - not a known concern, you can always manufacture some artificial concern), so you try to address concerns in an order of priority.
This seems like a very reasonable thing to do, in fact everyone does it - it is why we even bother to call anyone "paranoid" to begin with, i.e. we have our own list of concerns and try to address what we can...
You can never be truly secure and eliminate all potential concerns (what if there are invisible people with nanotech in your house - not a known concern, you can always manufacture some artificial concern), so you try to address concerns in an order of priority.
This seems like a very reasonable thing to do, in fact everyone does it - it is why we even bother to call anyone "paranoid" to begin with, i.e. we have our own list of concerns and try to address what we can...
[deleted]
Deniable backdoors are a much bigger risk than reproducible backdoors.
I trust my hardware manufacturers to be afraid of putting a backdoor into their chips if a binary captured via network surveillance could be used to show that a backdoor existed. This would be devastating to their business. Therefore, I trust them to not do anything that risks this occurring.
This is why people were so uneasy when internally-accessible unique serial numbers were added to the microcode engines of Intel processors.
I trust my hardware manufacturers to be afraid of putting a backdoor into their chips if a binary captured via network surveillance could be used to show that a backdoor existed. This would be devastating to their business. Therefore, I trust them to not do anything that risks this occurring.
This is why people were so uneasy when internally-accessible unique serial numbers were added to the microcode engines of Intel processors.
You can trust a chip to correctly do cryptographic computations by comparing with another, more trusted system (an FPGA, if you want to go to absurd lengths).
You can protect yourself against faulty key generation by generating the key offsite or on a HSM.
However, a flaw in a RNG that allows a third party (hello NSA) to break cryptography - you cannot defend from that, you can't even detect it.
You can protect yourself against faulty key generation by generating the key offsite or on a HSM.
However, a flaw in a RNG that allows a third party (hello NSA) to break cryptography - you cannot defend from that, you can't even detect it.
> However, a flaw in a RNG that allows a third party (hello NSA) to break cryptography - you cannot defend from that, you can't even detect it.
You always put bad randomness through enough calls of one way functions that reversing them is computationally infeasible for your adversary for the lifetime of the secret.
You always put bad randomness through enough calls of one way functions that reversing them is computationally infeasible for your adversary for the lifetime of the secret.
Deterministic functions do not increase entropy, bad entropy in is bad entropy out.
[deleted]
A datacenter scenario seems like a good fit for a centralized source of entropy, like a server with a dedicated high quality entropy source (maybe some kind of geiger counter/nuclear decay based source?). Very early in the boot process query the entropy server for a truly random seed and go from there to initialize your random algorithm, kind of like NTP and network time sources. Security would be something to pay attention to as you wouldn't want an attacker to ever get control of providing entropy.
Assuming you fully trust your PRNG algorithm, you really only need to do this once, generate a seed, then hash it with the current time(Assuming you have a trusted source), and whatever other entropy you have, plus the untrusted hardware RNG.
A backdoored RNG is unlikely to ever repeat patterns, that would be obvious, so it should be trustworthy enough to create a unique number.
It also probably, but not definitely can't phone home without someone noticing(Unless it can target specific people who aren't looking), and if it can, it can also send anything else it wants anyway.
An insecure but unique seed hashed with a secret machine specific value should be safe, it's not like they can manipulate the final value without having a way to break the hash, right?
You could even reuse the secret between machines as long as the attacker doesn't know it and everything else in the hash is unique.
Whatever network boot thingy or ansible job could provision random seeds when it updates the OS.
A backdoored RNG is unlikely to ever repeat patterns, that would be obvious, so it should be trustworthy enough to create a unique number.
It also probably, but not definitely can't phone home without someone noticing(Unless it can target specific people who aren't looking), and if it can, it can also send anything else it wants anyway.
An insecure but unique seed hashed with a secret machine specific value should be safe, it's not like they can manipulate the final value without having a way to break the hash, right?
You could even reuse the secret between machines as long as the attacker doesn't know it and everything else in the hash is unique.
Whatever network boot thingy or ansible job could provision random seeds when it updates the OS.
> A datacenter scenario seems like a good fit for a centralized source of entropy
"One ring to rule them all" is the quote my inner security sense immediately reaches for
"One ring to rule them all" is the quote my inner security sense immediately reaches for
Purity spiral
Well, Cloudflare uses lava lamps.
https://www.cloudflare.com/de-de/learning/ssl/lava-lamp-encr...
https://www.cloudflare.com/de-de/learning/ssl/lava-lamp-encr...
They don’t use them (read the details); they could fall back to using them. And it’s a stupid publicity stunt. And even then, they would use them via an ipcam - something probably way less secure than any rdrand or lava lamp.
It is and it isn't, in a sufficiently catastrophic scenario they might help for real.
Note also most people have never seen a real lava lamp, only digital reproductions, like the one in Day of the Tentacle. Not the same thing.
Note also most people have never seen a real lava lamp, only digital reproductions, like the one in Day of the Tentacle. Not the same thing.
There are many other more practical sources of random number generation, including ones that are non-deterministic due to quantum effects. SGI did it for fun, and obviously someone at Cloudflare was a fan.
I'm also confused by the second statement. You believe that more people have seen lava lamps in video games and similar than ones in person, or photos/videos of real ones? This seems unlikely to me.
I'm also confused by the second statement. You believe that more people have seen lava lamps in video games and similar than ones in person, or photos/videos of real ones? This seems unlikely to me.
Yes as a matter of fact I do believe people see lava lamps in digital media more often than in real life. I am one example of such a person. Lava lamps are an American thing largely, so if you want to see them you need to bring one from America or go to America to see it. What is the alternative? Lava lamp in the media, where you can look at it many times, but it is always a rerun.
The lava lamps are completely impractical. You'd get randomness of equal quality for orders of magnitude less energy by turning the lamps off and putting a lens cap over the webcam they use to record them.
i am pretty sure radioctive decay is random, and it's not metaphysical
Ah, but is your sample still live enough to be "cryptographic grade" random? Is the hardware that measures the source and the software that reports it subject to any periodicity that you don't know about but your attackers might?
(Some) People who study this often get lost down the rabbit hole and come out thinking the universe is deterministic.
(Some) People who study this often get lost down the rabbit hole and come out thinking the universe is deterministic.
Any distribution with a sufficient amount of entropy can be turned into "cryptographic-grade" randomness source using randomness extractors [1]. These work independently of any outside factors that might be trying to sneak signal (e.g. periodicity) into the noise -- as long as you can prove there's sufficient entropy to start with, you're good to go.
[1] https://en.wikipedia.org/wiki/Randomness_extractor
[1] https://en.wikipedia.org/wiki/Randomness_extractor
Low-intensity radiation is random enough, but it's slow: your device is necessarily twiddling thumbs between a detected event and the next, and entropy is mostly proportional to the number of events (for example, almost n bits from what of 2^n identical units is hit by the next particle).
Once you get 16-48ish bytes depending on paranoia you can just rely on crypto
Or, it's what one of my ex-NSA buddies told me: we almost never break the encryption, we break the implementation, because that's where the errors are.
The same can assuredly apply to capturing entropy.
The same can assuredly apply to capturing entropy.
100% this. WEP WiFi was an infamous old example. The encryption was solid but the implementation was poor and could be easily broken.
If you zoom in enough there is noise everywhere. Thermal noise across a resistor is particularly easy to measure [0]. Purists might want a nuclear decay event[1], or even a cosmic ray detection[2] but the more complex the apparatus the more shenanigans can occur.
For hyper important entropy, humans must invest in a macroscopic and very slow spectacle - a publicly prepared experiment broadcast live to a large audience. [3]
0 - https://analog.intgckts.com/noise/thermal-noise-of-a-resisto...
1 - https://en.wikipedia.org/wiki/Schr%C3%B6dinger%27s_cat
2 - https://www.youtube.com/watch?v=gwIGnATzBTg&t=479s
3 - https://www.youtube.com/watch?v=Bup0TcbQeVs
For hyper important entropy, humans must invest in a macroscopic and very slow spectacle - a publicly prepared experiment broadcast live to a large audience. [3]
0 - https://analog.intgckts.com/noise/thermal-noise-of-a-resisto...
1 - https://en.wikipedia.org/wiki/Schr%C3%B6dinger%27s_cat
2 - https://www.youtube.com/watch?v=gwIGnATzBTg&t=479s
3 - https://www.youtube.com/watch?v=Bup0TcbQeVs
Macroscopic stuff can possibly be faked with special effects. Verifiable randomness would be best done with a public record. You could have multiple companies provide numbers and hash them together so that all of them would have to collude to manipulate it.
Like cloudflare's beacon thing.
However lotteries are mostly just entertainment like any other gambling, and the balls are part of the show, so they would need some other spectacle.
Like cloudflare's beacon thing.
However lotteries are mostly just entertainment like any other gambling, and the balls are part of the show, so they would need some other spectacle.
Faking a result with special effects applies to each and every source of randomness. It is in essence the last irreducible threat model as Descartes once noted.
For those that want an (additional) source of entropy, the FSF offers[1] a USB HWRNG[2] that uses ADC quantization noise. It seems to be simple and clever enough to get the job done. True to FSF form the source is available if you want to adapt it to your own MCU. The data provided by mine passed all the randomness quality tests I could throw at it.
I don't know if it's still maintained or not, but the developer proposed a public entropy pool[3] which looks interesting. Full disclosure: I haven't looked at it closely enough to understand how the trust model works.
[1]: https://shop.fsf.org/storage-devices/neug-usb-true-random-nu... [2]: https://www.gniibe.org/memo/development/gnuk/rng/neug.html [3]: https://www.gniibe.org/memo/development/kun9be4/idea.html
I don't know if it's still maintained or not, but the developer proposed a public entropy pool[3] which looks interesting. Full disclosure: I haven't looked at it closely enough to understand how the trust model works.
[1]: https://shop.fsf.org/storage-devices/neug-usb-true-random-nu... [2]: https://www.gniibe.org/memo/development/gnuk/rng/neug.html [3]: https://www.gniibe.org/memo/development/kun9be4/idea.html
The problems you mentioned are not related to PCs or systems with motherboards like you are thinking. Every not-too-ancient PC CPU has been able to gather sufficient entropy just from cycle timing jitter. The problem is with old, simple embedded systems (and actually just emulations of said systems).
As many of these comments show, it's easy to come up with creative and probably effective sources of entropy.
The problem is knowing when you've collected enough to (re)seed your random bit generator.
Entropy sources usually have failure modes that result in predictable data in the output. The entropy source has to work even when someone is using an arc welder nearby or puts popcorn in the microwave.
Assuming kernel memory stays secret, collecting entropy should only be a problem during boot.
But distro maintainers aggressively optimize boot times, so there's a little time to spend collecting entropy at boot. Systems usually save a bit of entropy on the hard drive across boots, but that has its own issues. Unfortunately, first boot is when the SSH keys are generated, so that's kind of the worst-case scenario.
The problem is knowing when you've collected enough to (re)seed your random bit generator.
Entropy sources usually have failure modes that result in predictable data in the output. The entropy source has to work even when someone is using an arc welder nearby or puts popcorn in the microwave.
Assuming kernel memory stays secret, collecting entropy should only be a problem during boot.
But distro maintainers aggressively optimize boot times, so there's a little time to spend collecting entropy at boot. Systems usually save a bit of entropy on the hard drive across boots, but that has its own issues. Unfortunately, first boot is when the SSH keys are generated, so that's kind of the worst-case scenario.
They already do have; see Intel's implementation on Ivy Bridge :
https://www.electronicdesign.com/resources/article/21796238/...
(See https://news.ycombinator.com/item?id=2947936 from 2011 but the original article link seems to have gone)
(See https://news.ycombinator.com/item?id=2947936 from 2011 but the original article link seems to have gone)
Here is a test of Linux' random number generator by Germany's national ITSEC body, BSI: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publicat...
Generally speaking, a lot of proposed sources of "randomness" may not be as random as people think. And off-the-shelf hardware may be compromised/influenced by governemnts (see the NSA-NIST scandal).
For safe communication (one-time pad), you need plenty of truly random numbers, not pseudo-random ones.
It would therefore be good to have an open source source of entropy as a USB device, e.g. based on radioactive decay of some harmless but unstable isotope. There are companies offering such devices, but again I would not trust any of them but prefer people build their own from open hardware specs (it is likely that these vendors are infiltrated by intelligence agencies the same way as Swiss-based Crypto AG was - https://en.wikipedia.org/wiki/Crypto_AG).
Generally speaking, a lot of proposed sources of "randomness" may not be as random as people think. And off-the-shelf hardware may be compromised/influenced by governemnts (see the NSA-NIST scandal).
For safe communication (one-time pad), you need plenty of truly random numbers, not pseudo-random ones.
It would therefore be good to have an open source source of entropy as a USB device, e.g. based on radioactive decay of some harmless but unstable isotope. There are companies offering such devices, but again I would not trust any of them but prefer people build their own from open hardware specs (it is likely that these vendors are infiltrated by intelligence agencies the same way as Swiss-based Crypto AG was - https://en.wikipedia.org/wiki/Crypto_AG).
Radioactive decay isn't the only source of quantum noise. Johnson-Nyquist kTC noise on a capacitor is another quantum source of noise, for instance.
PCs are not where problems with entropy generally are a large issue. For starters, many CPUs have inbuild hardware entropy sources (although not everybody trusts them)
[deleted]
There are good entropy sources (as others have indicated)
But just because there are good entropy sources on physical hardware doesn't mean the overwhelming majority of system instances are inheriting those sources well (and not just virtual machines/cloud processing)
6 years ago I wrote about haveged, truerand, and twuewand[0] (specifically in the context if improving the entropy pool for a heavy Java app)
There are also dedicated USB dongles ... but again: they don't help much (if at all) for hosted instances (containers, VMs, etc)
--------------
[0]https://antipaucity.com/2016/04/01/improve-your-entropy-pool...
But just because there are good entropy sources on physical hardware doesn't mean the overwhelming majority of system instances are inheriting those sources well (and not just virtual machines/cloud processing)
6 years ago I wrote about haveged, truerand, and twuewand[0] (specifically in the context if improving the entropy pool for a heavy Java app)
There are also dedicated USB dongles ... but again: they don't help much (if at all) for hosted instances (containers, VMs, etc)
--------------
[0]https://antipaucity.com/2016/04/01/improve-your-entropy-pool...
I think VIA [1] did this on some of their mini-ITX boards with embedded CPUs. I seem to recall a contemporary review saying that they used electrical noise to implement an RNG, a fact which is corroborated [2] here:
> Nehemiah stepping 3 and higher offers an electrical noise-based random number generator (RNG) that produces good random numbers for different purposes.
[1] https://en.m.wikipedia.org/wiki/VIA_PadLock [2] http://www.logix.cz/michal/doc/article.xp/padlock-en
> Nehemiah stepping 3 and higher offers an electrical noise-based random number generator (RNG) that produces good random numbers for different purposes.
[1] https://en.m.wikipedia.org/wiki/VIA_PadLock [2] http://www.logix.cz/michal/doc/article.xp/padlock-en
I had an idea many years ago about using those cheap tv tuner cards that were briefly somewhat popular in PCs as an entropy source. If it could reliably tune to a dead channel I imagine it would be a good source of quality entropy.
Many years ago I have indeed used this method, which has the advantage of a very high rate for the random bits.
There is no need to tune to a dead channel. Instead of connecting a TV cable or antenna, it is enough to connect a coaxial resistive terminator on the TV input connector. Then all the channels are dead.
Unfortunately this is a dead technology, so I have abandoned it after I retired my last motherboard with PCI connectors.
You can do something similar with the audio microphone input, but the TV tuners had a much higher bandwidth and a much higher sensitivity. For good results with the microphone input you need to make an analog noise generator, instead of using just a resistor, as it was enough for a TV tuner.
There is no need to tune to a dead channel. Instead of connecting a TV cable or antenna, it is enough to connect a coaxial resistive terminator on the TV input connector. Then all the channels are dead.
Unfortunately this is a dead technology, so I have abandoned it after I retired my last motherboard with PCI connectors.
You can do something similar with the audio microphone input, but the TV tuners had a much higher bandwidth and a much higher sensitivity. For good results with the microphone input you need to make an analog noise generator, instead of using just a resistor, as it was enough for a TV tuner.
>For good results with the microphone input you need to make an analog noise generator, instead of using just a resistor, as it was enough for a TV tuner.
Is this true? If you crank the gain on the cheap mic amplifier that comes with basically any laptop or motherboard, you'll get a ton of noise. Yes, the high bits will be correlated between samples, but if you XOR all the bits in a sample - or multiple samples - together, that ought to be a pretty solid random bit, no? You just need to make your XOR-ing "window" span at least 1 bit's worth of entropy in the stream. It's not megabytes per second, but it's a lot better than having the user wiggle the mouse, surely?
Is this true? If you crank the gain on the cheap mic amplifier that comes with basically any laptop or motherboard, you'll get a ton of noise. Yes, the high bits will be correlated between samples, but if you XOR all the bits in a sample - or multiple samples - together, that ought to be a pretty solid random bit, no? You just need to make your XOR-ing "window" span at least 1 bit's worth of entropy in the stream. It's not megabytes per second, but it's a lot better than having the user wiggle the mouse, surely?
You could still do it with a USB capture card or an SDR. Analog capture certainly isn't dead though it might be a little expensive.
Yes, the only problem is the price.
Analog TV tuners were very cheap. Now it no longer makes sense to use an expensive analog capture board for a RNG.
There are much cheaper solutions.
For no more than $10, you can make a RNG using the ADC of either a microcontroller board with USB interface or of an audio USB dongle or of the microphone connector of the motherboard audio.
Analog TV tuners were very cheap. Now it no longer makes sense to use an expensive analog capture board for a RNG.
There are much cheaper solutions.
For no more than $10, you can make a RNG using the ADC of either a microcontroller board with USB interface or of an audio USB dongle or of the microphone connector of the motherboard audio.
Using a radio receiver as a source of entropy opens you to a rather obvious attack channel.
If you replace the radio signal source at the radio receiver input with a shielded resistive terminator, you no longer have any attack channel (because now the radio receiver has only an output, but no input).
For this purpose, radio receivers are just very sensitive amplifiers. Any very sensitive amplifier will output noise when its input is terminated on a resistor, both amplified resistor noise and additional noise from sources internal to the amplifier.
When you use much less sensitive amplifiers than radio receivers, e.g. audio amplifiers, a resistor at the input may be not enough and you must put there a source of greater noise, e.g. an avalanche breakdown diode (a.k.a. Zener diode).
For this purpose, radio receivers are just very sensitive amplifiers. Any very sensitive amplifier will output noise when its input is terminated on a resistor, both amplified resistor noise and additional noise from sources internal to the amplifier.
When you use much less sensitive amplifiers than radio receivers, e.g. audio amplifiers, a resistor at the input may be not enough and you must put there a source of greater noise, e.g. an avalanche breakdown diode (a.k.a. Zener diode).
Serious question, I don't know much about this - why is it hard to generate a random number? I don't really understand this conversation about needing better entropy.
because a lot of work has gone into making digital systems as deterministic as possible. there's noise everywhere in the real world, but by thresholding voltage values and operating on clock ticks, digital systems are largely impervious to it.
if you run the same program twice, you get the same result. this is the wonderful result of all that work... but now there's no noise so there's no randomness.
random number generators are actually just mathematical functions that produce a stream of output with a flat distribution given a fixed input. the simplest ones give the exact same output given the same input. (sometimes this is exploited in debugging of algorithms that make use of randomness, like monte carlo methods).
newer hardware has hardware support for generating random numbers using analog phenomena, but older hardware doesn't always have this. there are some clever hacks in the kernel that make use of noise found in the clocks that drive the digital system, as well as sampling from a variety of external sources (interrupts from things like network activity, or keyboard/mouse, or other hardware).
the problem here is that they want good randomness early in the boot process when a lot of those interrupts aren't being generated (because the hardware hasn't started), there's no hardware support for randomness, and the clock noise trick doesn't work.
my guess is that they'll probably add a few more random (hah) hacks to try and generate noise when there's no peripherals although the article states that they're going out and trying to fix userland by adding a program that saves/restores some randomness for each boot.
if you run the same program twice, you get the same result. this is the wonderful result of all that work... but now there's no noise so there's no randomness.
random number generators are actually just mathematical functions that produce a stream of output with a flat distribution given a fixed input. the simplest ones give the exact same output given the same input. (sometimes this is exploited in debugging of algorithms that make use of randomness, like monte carlo methods).
newer hardware has hardware support for generating random numbers using analog phenomena, but older hardware doesn't always have this. there are some clever hacks in the kernel that make use of noise found in the clocks that drive the digital system, as well as sampling from a variety of external sources (interrupts from things like network activity, or keyboard/mouse, or other hardware).
the problem here is that they want good randomness early in the boot process when a lot of those interrupts aren't being generated (because the hardware hasn't started), there's no hardware support for randomness, and the clock noise trick doesn't work.
my guess is that they'll probably add a few more random (hah) hacks to try and generate noise when there's no peripherals although the article states that they're going out and trying to fix userland by adding a program that saves/restores some randomness for each boot.
but. enough with this computer stuff. here's the really interesting question: are living creatures deterministic machines?
there's so much random noise in the environment that it is extremely hard to answer.
moreover, we know that early development of sensorimotor systems is driven by random noise. we learn to control our bodies by being stimulated by environmental noise, attempting to use our effectors (muscles), observing how that works out, correcting errors and then improving on it.
what gives rise to consciousness? i'd argue the randomness from the noise in our environments.
there's so much random noise in the environment that it is extremely hard to answer.
moreover, we know that early development of sensorimotor systems is driven by random noise. we learn to control our bodies by being stimulated by environmental noise, attempting to use our effectors (muscles), observing how that works out, correcting errors and then improving on it.
what gives rise to consciousness? i'd argue the randomness from the noise in our environments.
The needs for random numbers vary by application. I'm satisfied with the Johnson noise generated by a resistor, feeding an a/d converter, for testing audio circuits. I only need a sampling rate of a few tens of kHz. For applications like encryption, what's important is not just each number in isolation, but ensuring that sequences of random numbers have required properties that make it hard to guess a number in the sequence from its predecessors. Or to guess that two different sequences come from the same computer. You might need to generate sequences at a rate that make it hard to do with purely physical random sources.
And you need to be assured that a sequence meets those needs without being able to test it to exhaustion, which means it has to be provable from inspection of the algorithm and original sources of entropy. At least, provable enough for the application. ;-)
And you need to be assured that a sequence meets those needs without being able to test it to exhaustion, which means it has to be provable from inspection of the algorithm and original sources of entropy. At least, provable enough for the application. ;-)
I think the challenge is in generating random numbers that no one else can guess. I could be way off, but I think its the initial setup that is the sticking point, because if you can't get a good random number as your seed then your 'random' numbers stop being random.. because they can be predicted.
I'm no scientist, but it is intuitive to me that a machine ultimately run by rules of precise and discrete voltage would have trouble here. It seems silly because it feels so basic to us meatspace dwellers, but you can't build up something so precisely and demand it to follow our instructions, and then just be like "ok forget about all that."
That said I do also understand why it is relatively easy to make PRNGs. But that is just dissimulation, its just making instructions eat their own tail.
That said I do also understand why it is relatively easy to make PRNGs. But that is just dissimulation, its just making instructions eat their own tail.
It's really hard to get a signal that doesn't have a pattern.
For entropy sources that measure the environment, are there attacks where the attacker manipulates the environment? For example, when the source is measuring the temperature, an attacker could alter the temperature near the sensor to create more predictable random numbers?
Related: And does software detect if a sensor is broken or a poor source on entropy? Like if it broke and locked itself on to the same constant temperature reading?
Related: And does software detect if a sensor is broken or a poor source on entropy? Like if it broke and locked itself on to the same constant temperature reading?
That's why you only use the least significant digits of any number that comes from a sensor.
So if the temperature changes from 65.78614329 degrees to 66.24667182 degrees, you don't take 65 and 66, you take 329 and 182. Those digits are most likely to be random noise and not something an attacker can manipulate at will. Even if the analog part of the sensor is stuck at the same temperature as in your example, the digital reading will probably fluctuate around that value with plenty of random digits.
So if the temperature changes from 65.78614329 degrees to 66.24667182 degrees, you don't take 65 and 66, you take 329 and 182. Those digits are most likely to be random noise and not something an attacker can manipulate at will. Even if the analog part of the sensor is stuck at the same temperature as in your example, the digital reading will probably fluctuate around that value with plenty of random digits.
> you don't take 65 and 66, you take 329 and 182.
you take all of them and run it through an appropriate extractor. it is very easy for ADC error to have structure and bias.
you take all of them and run it through an appropriate extractor. it is very easy for ADC error to have structure and bias.
[deleted]
I guess this is why "gpg --generate-key" asks you to bang randomly on your keybaord and wiggle your mouse, lol.
Yeah this is absolutely unnecessary. Maybe it wasn't before I was born, I'm not that old, but good ol' gnupg is still holding on to the concept of running out of entropy. See also putty doing the mouse wigglies for a private key.
Nobody answered the real answer: there's simply no need. Existing solutions work good enough for most people, and it's dirt cheap.
Extra sensors cost extra money, and people not are willing to pay for no visible benefit to them.
Extra sensors cost extra money, and people not are willing to pay for no visible benefit to them.
You can use a cell phone camera as a TRNG, there are plenty of papers ie
https://ieeexplore.ieee.org/document/7132901
https://ieeexplore.ieee.org/document/7132901
Interesting photonics opportunity here: could you produce a single photon slit-lamp on a chip for entropy production? Not sure you can do better than that.
We should use the white noise or turbulence generated by our PC fans as entropy sources. Brownian motion is one of the best entropy sources we have.
Given the day this was posted on I was half expecting it to be a proposal to add radiation sources as a standard computer component
> simple GPS
Excuse me, but when did pinging multiple satellites thousands of kilometres away (in orbit) become simple?
Excuse me, but when did pinging multiple satellites thousands of kilometres away (in orbit) become simple?
1. GPS doesn't "ping" multiple satellites. It's the other way around. Multiple satellites are constantly transmitting their times, and any receiver can listen in and figure out their location based on that.
2. regardless of how much technology/research went into developing the GPS, it's still fairly simple to access from a software point of view. A CPU may have millions/billions of transistors that are intricately placed, but that doesn't mean using your CPU to add two numbers can't be described as "simple".
2. regardless of how much technology/research went into developing the GPS, it's still fairly simple to access from a software point of view. A CPU may have millions/billions of transistors that are intricately placed, but that doesn't mean using your CPU to add two numbers can't be described as "simple".
I guess I'm just amazed that GPS is now considered simple.
You probably have a supercomputer in your pocket. Self driving cars have started service around me. Engineering builds on its own success and many techniques/solutions get standardized and commoditized. Today’s hard is tomorrow’s simple (and conversely yesterday’s simple can become today’s hard as techniques are forgotten or we lose old ways of doing things).
Because PC's weren't, from the beginning of its history, desgined for security scenarios.
Isn’t that what a Secure Enclave is for? I believe it has a TRNG, a true random number generator.
That true random number generator needs entropy sources: it's the client, not the server.
[deleted]
Will quantum computing solve this issue?
No, but Intel's RDSEED and friends rely on quantum electrical noise in conventional circuits to provide true randomness. (Intel uses kTC reset noise from a capacitor or pair of capacitors on the CPU core die, IIRC.)
Quantum computers cost millions of dollars, and are worse random sources than a component that costs a penny. Simply put, no, quantum computers will not solve this.
RNGs in actually existing classical computers are already "quantum". A true classical-physics-only computer would be deterministic.
They do have lots of sensors that can be used... We have bad defaults and a not-very-skillful usage of said hardware. On workstations there are lots of options. In datacenters, there could be some dedicated hardware for it somewhere - and an skillful usage of said entropy being imported into each rack unit.
Is this assumption correct, that adding a magnetometer, accelerometer, simple GPS, etc to a motherboard would improve its entropy gathering? Or is there a mathematical/cryptographical rule that makes the addition of such sensors useless?
Do smartphones have better entropy gathering abilities? It seems like phones would be able to seed a RNG based on input from a variety of sensors that would all be very different between even phones in the same room. Looking at a GPS Android app like Satstat (2) it feels like there's a huge amount of variability to draw from.
If such sensors would add better entropy, would it really cost that much to add them to PC motherboards?
----
(1) https://news.ycombinator.com/item?id=30848973
(2) https://mvglasow.gitlab.io/satstat/ & https://f-droid.org/en/packages/com.vonglasow.michael.satsta...