I didnt know what to expect. It was a lot lower than the claimed 250 terabit/second. The fastest I have ever gotten bits out of dedicated hardware is only about 500 b/s. Now. I didn't try very hard, but I didn't think anything in the gigabit range was possible on a single chip.
I got something like 200Mb/s using RF noise and FPGA. I am not qualified to make any strong statements about quality of the resulting random bit stream.
The published one is significantly shorter which surprised me (6 pages vs 14 pages), but it does claim a different rate in the final paper "All these test results certify the randomness of our parallel random bits generated at a cumulative rate of 2 Tb/s × 127 = 254 Tb/s".
There’s really no true seed unless you have some sort of quantum system. Many are based on sources of noise and are actually somewhat slow. Small IoT devices often have poor generation.
A fast source of high quality numbers available to every computer is still an open problem.
I don't understand why we dont, at this point, have a specific module built into every processor or motherboard whose purpose is to serve as a simple entropy source. It's bizarre to me that this isn't built into the architecture standards.
However it's difficult to be sure it hasn't been backdoored, so it's not advisable to use it directly for cryptographic purposes. Worse, as DJB explains, it's hard to mix a potentially backdoored random number generator with other random numbers in a secure fashion: http://blog.cr.yp.to/20140205-entropy.html
That "malicious hardware RNG" scenario has always seemed odd to me. The idea is that it's going to spy on the contents of your entropy pool (or on your entropy sources, or both) and then generate malicious random bits to exactly cancel out what's in your pool, leaving you with all zeros or something like that. My question is, if you have the capability to pull off an attack like that, wouldn't you probably also have the capability to do much worse things? Like just reading and writing arbitrary memory?
1) Hardware has severe limitations on what you can actually implement, because implementing complex behavior with small numbers of low-level logic gates is really difficult.
2) You really don't want to get caught when the evidence of the attack is baked into the hardware itself.
Under those constraints, a very subtle attack on an entropy pool could be both easier to implement, and much harder to notice, than an obvious attack of just flipping some "root access bits" or backdooring the key generation directly. It's quite difficult to prevent those kinds of attacks from being detected by debuggers, under the constraints of a hardware implant.
In particular, remember that the mechanism where the backdoored RNG can observe state might be a deliberate leak, implemented by the programmer of the RNG pool, working with the people doing the hardware implant. In that scenario, they want something subtle so it'll pass code audits.
If you haven't already, I'd really suggest trying out some FPGA development. Basically, everything is done with fixed-function state machines, and abstractions and complex behaviours are really difficult to implement directly. I'd say FPGA design in comparison to, say, assembly, is similar to the difference in abstraction power between assembly and Python.
If your goal is 10/10 perfection, nothing will work.
If your goal is 9/10 or less, then you only need to generate a couple hundred bits once. You can quickly create "a fast source of high quality numbers" even if your initial seed generator can only do a dozen kilobytes per second.
Hardware implementors not bothering is something I would put under a different category.
This is basically what the Infinite Noise[1] project does.
Speed is limited by the speed of a gain stage and a comparator, and can run in excess of 100 Mbit/second per second with high performance components. Cheap solutions with CMOS quad op-amps can run at 8Mbit/second.
This implementation uses Keccak-1600 with cryptographically secure reseeding of more than 400 bits of entropy at a time, overcoming a trickle in/out problem present in the GNU/Linux /dev/random system. Users who need many megabytes per second of data for use in cryptography can set the outputMultiplier as high as they like, which causes Keccak to generate outputMultiplier*256 bits per reseeding by the Infinite Noise TRNG.
The purpose of the "randomart" visual hash of the key fingerprint is to let you quickly check that you've got the right key, because you recognise it, or can compare it by eye somewhat easily.
If it didn't have structure to the pattern then it would defeat the purpose.
Imagine blasting this sequence down to huge numbers of consumers, and letting independent nodes coordinate on intervals in the sequence in order to establish secure one time communications.
The bit rate is so high it would be impossible to reproduce the pad despite having access to the full random bit stream, because you couldn't possibly store the historic stream for future analysis even if you could eventually determine the past communication's interval.
This is an interesting idea. I see two limitations and I'm curious how they could be overcome:
1. The peers must communicate to decide in advance which intervals to use. If those communications are encrypted with the shared stream using previously exchanged intervals, then the security of each session depends on the previous session. Breaking one session also breaks all future sessions.
2. Attackers can capture and save samples of the random bit stream and test intercepted communications against those samples. They won't get all of the victim communications, but they will get some. Combined with the chaining problem above, this could let them eventually crack all established streams.
About 1: the peers don't have to communicate in advance.
They can just both do random sampling, and later on only use the overlap. That wastes a lot of bits, but requires no up-front communication.
About 2: obviously you wouldn't just use straight one-time pad, but use the random bits to arrive at a shared key.
With made up numbers: both parties sample randomly until they have eg 10k bits in common, then hash that down to eg 256 bits they need for a shared key.
If they use a decent hashing scheme, the only requirement for its security is that they share at least about 256 bits that the attacker has not seen. (It doesn't matter how many common bits the attacker has seen, only how many Eve hasn't seen.)
21 comments
[ 4.2 ms ] story [ 58.0 ms ] threadI wonder who would need more than that.
https://arxiv.org/abs/2004.07157
(Dunno the differences between the preprint and the published one. The preprint claims 100tb/s.)
A fast source of high quality numbers available to every computer is still an open problem.
However it's difficult to be sure it hasn't been backdoored, so it's not advisable to use it directly for cryptographic purposes. Worse, as DJB explains, it's hard to mix a potentially backdoored random number generator with other random numbers in a secure fashion: http://blog.cr.yp.to/20140205-entropy.html
1) Hardware has severe limitations on what you can actually implement, because implementing complex behavior with small numbers of low-level logic gates is really difficult.
2) You really don't want to get caught when the evidence of the attack is baked into the hardware itself.
Under those constraints, a very subtle attack on an entropy pool could be both easier to implement, and much harder to notice, than an obvious attack of just flipping some "root access bits" or backdooring the key generation directly. It's quite difficult to prevent those kinds of attacks from being detected by debuggers, under the constraints of a hardware implant.
In particular, remember that the mechanism where the backdoored RNG can observe state might be a deliberate leak, implemented by the programmer of the RNG pool, working with the people doing the hardware implant. In that scenario, they want something subtle so it'll pass code audits.
If you haven't already, I'd really suggest trying out some FPGA development. Basically, everything is done with fixed-function state machines, and abstractions and complex behaviours are really difficult to implement directly. I'd say FPGA design in comparison to, say, assembly, is similar to the difference in abstraction power between assembly and Python.
If your goal is 10/10 perfection, nothing will work.
If your goal is 9/10 or less, then you only need to generate a couple hundred bits once. You can quickly create "a fast source of high quality numbers" even if your initial seed generator can only do a dozen kilobytes per second.
Hardware implementors not bothering is something I would put under a different category.
Speed is limited by the speed of a gain stage and a comparator, and can run in excess of 100 Mbit/second per second with high performance components. Cheap solutions with CMOS quad op-amps can run at 8Mbit/second.
This implementation uses Keccak-1600 with cryptographically secure reseeding of more than 400 bits of entropy at a time, overcoming a trickle in/out problem present in the GNU/Linux /dev/random system. Users who need many megabytes per second of data for use in cryptography can set the outputMultiplier as high as they like, which causes Keccak to generate outputMultiplier*256 bits per reseeding by the Infinite Noise TRNG.
[1]: https://github.com/waywardgeek/infnoise
https://www.crowdsupply.com/13-37/infinite-noise-trng
Honestly, I tried generating an ssh key and I thought the pictogram would look like static on an old tv set, but it didn't look measurably different.
Maybe a better measure might have been timing it?
If it didn't have structure to the pattern then it would defeat the purpose.
Even those that are not cryptographically secure.
The bit rate is so high it would be impossible to reproduce the pad despite having access to the full random bit stream, because you couldn't possibly store the historic stream for future analysis even if you could eventually determine the past communication's interval.
1. The peers must communicate to decide in advance which intervals to use. If those communications are encrypted with the shared stream using previously exchanged intervals, then the security of each session depends on the previous session. Breaking one session also breaks all future sessions.
2. Attackers can capture and save samples of the random bit stream and test intercepted communications against those samples. They won't get all of the victim communications, but they will get some. Combined with the chaining problem above, this could let them eventually crack all established streams.
They can just both do random sampling, and later on only use the overlap. That wastes a lot of bits, but requires no up-front communication.
About 2: obviously you wouldn't just use straight one-time pad, but use the random bits to arrive at a shared key.
With made up numbers: both parties sample randomly until they have eg 10k bits in common, then hash that down to eg 256 bits they need for a shared key.
If they use a decent hashing scheme, the only requirement for its security is that they share at least about 256 bits that the attacker has not seen. (It doesn't matter how many common bits the attacker has seen, only how many Eve hasn't seen.)