4 ms·

Why is it any better than a slow true random seed and pseudorandom numbers based on a secure hash function? I can't think of any application.

goalieca 6y ago
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.
- JulianMorrison 6y ago
  Also anything that expects to seed based on keyboard and mouse is not going to get much to seed from, in a widget attached to your wall.
- Enginerrrd 6y ago
  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.
  - petertodd 6y ago
    We do: https://en.wikipedia.org/wiki/RDRAND https://en.wikipedia.org/wiki/RDRAND 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 http://blog.cr.yp.to/20140205-entropy.html
    - oconnor663 6y ago
      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?
      - petertodd 6y ago
        There's two issues: 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.
    - Enginerrrd 6y ago
      Ah, I get it now. Thanks for the information.
- Dylan16807 6y ago
  I wouldn't say it's an open problem. 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.
magicalhippo 6y ago
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. [1]: https://github.com/waywardgeek/infnoise https://github.com/waywardgeek/infnoise
- m463 6y ago
  they sell usb dongles based on this on crowdsupply: https://www.crowdsupply.com/13-37/infinite-noise-trng 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?
  - azornathogron 6y ago
    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.
    - m463 6y ago
      Oh, I see now. I guess I confused it with some other software I used - I can't recall what - that showed some sort of randomness display.
      - eru 6y ago
        Any prng that's worth its salt should look totally random in almost any test to the human eye. Even those that are not cryptographically secure.

goalieca 6y ago

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.

JulianMorrison 6y ago
Also anything that expects to seed based on keyboard and mouse is not going to get much to seed from, in a widget attached to your wall.
Enginerrrd 6y ago
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.
- petertodd 6y ago
  We do: https://en.wikipedia.org/wiki/RDRAND https://en.wikipedia.org/wiki/RDRAND 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 http://blog.cr.yp.to/20140205-entropy.html
  - oconnor663 6y ago
    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?
    - petertodd 6y ago
      There's two issues: 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.
  - Enginerrrd 6y ago
    Ah, I get it now. Thanks for the information.
Dylan16807 6y ago
I wouldn't say it's an open problem. 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.

magicalhippo 6y ago

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. [1]: https://github.com/waywardgeek/infnoise https://github.com/waywardgeek/infnoise

m463 6y ago
they sell usb dongles based on this on crowdsupply: https://www.crowdsupply.com/13-37/infinite-noise-trng 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?
- azornathogron 6y ago
  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.
  - m463 6y ago
    Oh, I see now. I guess I confused it with some other software I used - I can't recall what - that showed some sort of randomness display.
    - eru 6y ago
      Any prng that's worth its salt should look totally random in almost any test to the human eye. Even those that are not cryptographically secure.