8 ms·

Things like this, i.e. getting random numbers from some real-world process that is supposedly perfectly random, come up every now and then and I keep repeating:

• Kuinox 7y ago
  There is specialized hardware to generate a lot of RNG.
  • hannob 7y ago
    Yeah, e.g. quantum based RNGs. Which are also pretty useless.
    • Kuinox 7y ago
      They are useful in some cases. But it's not for everyone.
  • DonHopkins 7y ago
    Silicon Graphics developed a specialized hardware random number generator in 1997, covered under U.S. Patent 5,732,138: "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system." https://en.wikipedia.org/wiki/Lavarand https://en.wikipedia.org/wiki/Lavarand https://www.wired.com/2003/08/random/ https://www.wired.com/2003/08/random/ https://patents.google.com/patent/US5732138A/en https://patents.google.com/patent/US5732138A/en
• max_ 7y ago
  This is one question I have always come across when working with crypto systems. Why is it impossible for one to have an algorithm that generates true cryptographically secure random numbers?
  • hannob 7y ago
    > Why is it impossible for one to have an algorithm that generates true cryptographically secure random numbers? The answer alternates between "it's not" and "depends on how exactly you define algorithm". With algorithms we usually talk about deterministic instructions. In such a sense an algorithm can't create random numbers, because it'll always output the same thing with the same input. But give a few random inputs (which there are usually plenty in any complex enough system) we can build an algorithm that will take these random inputs and output an endless, secure stream of random numbers. Which is what every modern operating system does. You don't need any magic external random number source for that, just use what your OS gives you.
    • max_ 7y ago
      Interesting. What "degree of complexity" in the system is a "complex enough system"?
      • hannob 7y ago
        Good questoin, it's hard to give a definite answer, but usually "if it has a harddrive and a network card you're unlikely to have any problem". Rule of thumb: Normal Desktops and Servers are unlikely to be problematic. Really the only realistic problem is that if you generate a cryptographic key right after booting the device and if the device is something like a router. Look here [1] for some research on that. That scenario can be avoided by newer APIs (newer linux kernels have the getrandom system call for that) that only will spit out random numbers once the RNG has been initialized with enough randomness - but in return you may get services blocking at boot. [1] https://factorable.net/ https://factorable.net/
  • espadrine 7y ago
• ArtWomb 7y ago
  Simple boson sampling, if you can get a technique that maps photons to RNGs in "O(1)" fashion, could conceivably provide a high-throughput infinite source of highly-entropic randomness. And it's probably only needed in <<< %1 of use cases ;) But understanding how Nature computes randomness is quite enlightening. Just yesterday morning on a hike I saw some long spikey ice crystals recently formed on a creek bed and the patterns were more aesthetically pleasing than any geometric computer art. In the example regarding crystallization, it is an absolute mystery how the nucleating solid particles will choose their exact equilibrium compositions out of the infinite range of possibilities. And then communicate that quantity to the far reaches of the liquid-solid forming interface!
  • enkid 7y ago
    Nature doesn't compute random numbers, it has underlying processes either random or so opaque as to be effectively random.
    • wongarsu 7y ago
      Except for quantum mechanics. We can compute probabilities perfectly, but the actual outcome of any one event (e.g. the destination of any one photon) is unpredictable. Any attempts to explain quantum mechanics as being deterministic require faster-than-light communication and are generally seen as unlikely [1] (unless we are in a simulation and there's a global random number generator, of course). You can buy PCIe cards exploiting this for random number generation [2] 1: https://en.wikipedia.org/wiki/Hidden-variable_theory https://en.wikipedia.org/wiki/Hidden-variable_theory 2: https://www.idquantique.com/random-number-generation/products/quantis-random-number-generator/ https://www.idquantique.com/random-number-generation/product...
      • sysbin 7y ago
        What's your definition of unpredictable & random? I'm interested because you write off quantum mechanics as unlikely to be deterministic. When everything being deterministic is more realistic and from scientific understanding of systems working in nature. Contrary to determinism would be true magic. Having a force without any cause. That just feels like lack of understanding.
• rini17 7y ago
  So you insist "solves no real problem" and in the very next sentence you name few such problems :)
  • hannob 7y ago
    Erh no. I say it doesn't solve real problems and then I list real problems with RNGs that aren't solved by it.
    • TallGuyShort 7y ago
      How would a device based on natural stochastic processes not solve boot entropy? I thought that was exactly how such devices were used now, except most users don't even have one.
      • mistercow 7y ago
        I think the point is that cheaply manufactured devices based on natural stochastic processes are already a solved problem, and a new wacky process involving chemistry doesn't bring anything worthwhile to the table.
        • rini17 7y ago
          Here Hanno rejected all hardware devices: > None of that is solved by any form of physics or chemistry based RNG.
    • rini17 7y ago
      Boot entropy? That is neatly solved by HWRNG. Bugs/insecurity? These are indeed better with HWRNG. HWRNG are more likely to fail catastrophically (that is easy to detect if you don't use whitening) and easier to physically audit (there are much simpler options than this contrived crystallization device). Algoritmic RNGs are more likely to fail undetectably and dangerously, and much harder to audit.
• thu2111 7y ago
  What we're reading here isn't an article intended for computer scientists. It's reporting some findings that may be of interest to chemists. The "true random numbers" thing was pretty clearly tacked on by someone who's heard a bit about encryption - enough to know it requires high quality randomness - but who isn't a computer scientist. They notice that these kinds of crystallisations are random and write a paper. Not really useful to most of us here on HN but no big deal and maybe interesting for other reasons. Now, your wider point isn't really true. Physics based RNGs are extremely useful. They can be embedded in CPUs which immediately solves several problems: 1. the "no entropy on first boot" problem for embedded devices and newly installed cloud hardware 2. the prevalence of bugs in software RNGs, often caused by attempts to optimise around performance problems elsewhere e.g. Debian, Android have both completely broken their crypto RNGs in the past. The complexity of managing entropy in virtualised environments with multiple levels of nesting (e.g. hypervisor, VM, processes) is quite extreme. HW RNG is simple because you go straight to the CPU, without any software in between. The level of validation on CPU circuits is vastly higher than for operating systems. e.g. back in 2006 a paper came out showing there were multiple vulns in the Linux kernel RNG: http://www.pinkas.net/PAPERS/gpr06.pdf http://www.pinkas.net/PAPERS/gpr06.pdf 3. Hardware RNGs can be extremely fast and generate huge quantities of randomness without any overhead. This matters in some cases like Monte Carlo simulation. 3. Most importantly, they can can be used by secure enclaves. The enclave use case isn't obvious so it's worth dwelling on. Technologies like SGX let us run software with a new and very strong threat model, namely, that everything outside the enclave is malicious. That means the kernel, the peripherals, the memory, the bus, system firmware like UEFI or SMM code. Everything. This is obviously very useful if you want to run calculations on other people's hardware without trusting them i.e. in the cloud. But for it to work the enclave must be able to generate encryption keys without relying on the kernel to have collected entropy for it (as we don't trust the kernel!). On Intel chips this is possible because there's a hardware, physics based RNG in the chip itself. The entropy is collected from a meta-stable oscillator circuit that is measuring thermal noise from the silicon itself. The circuit schematics are public and were audited by Cryptography Research Inc, who have a strong name in the field of hardware security. There's an article on the theory here: https://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator https://spectrum.ieee.org/computing/hardware/behind-intels-n... Of course AMD and ARM have something similar. Some people wonder if a CPU RNG can be trusted, but I think this concern is based in a mis-understanding of what modern CPU microcode is capable of. If your CPU is malicious then any output from your computer cannot be trusted. Enclaves let you do computations if other parts of the machine are malicious (with caveats) but ultimately, the CPU is the heart and brain of the device. Worrying about whether a hardware RNG is trustworthy is about as useful as worrying if any other part of the CPU is trustworthy: the answer may be 'no' but you have no way of knowing, and if you're worried about the US Government your only alternative is to switch to an ARM processor that was fabbed by a company without much exposure to the US. Not many of those are around.
• SAI_Peregrinus 7y ago
  That and a good entropy source can be had with 2 transistors: https://ieeexplore.ieee.org/document/7111269 https://ieeexplore.ieee.org/document/7111269 (no login copy http://www.chaotic-circuits.com/wp-content/uploads/2016/06/Simple-Two-Transistor-Single-Supply-RC-Chaotic-Oscillator.pdf http://www.chaotic-circuits.com/wp-content/uploads/2016/06/S...) Entropy generation isn't hard, even at boot, even on embedded systems (this circuit is cheap enough to stick on most boards if you really need it. Or there are $0.50 ICs that do this and a lot more!). And once you have the entropy, you feed it to your normal fast-key-erasure CSPRNG, and have effectively infinite quantities of random bits.
  • jdc 7y ago
    Interesting. This may be a dumb question, but I wonder what happens if you run an EDA simulation on this circuit. Would it still be random?
    • mattkrause 7y ago
      Chaotic systems are usually described as having "strong sensitivity to initial conditions", but this almost undersells them. Even incredibly small deviations from the simulation (measurement error, over/undervoltage conditions, floating point errors/rounding, probably even temperature fluctations) would be enough to alter the results. You can see some neat examples of this with double pendulums, which seem like they should be easy to predict/model, but are absolutely not! While this is popularly known as the "butterfly effect", but I recently learned it was originally called the much less poetic "sea gull effect".
    • SAI_Peregrinus 7y ago
      Yes, it's still chaotic. You'll get the same results every time with no parameter variation, but any variation creates dramatically different results. The circuit exploits sensitive dependence on initial conditions, things like temperature and manufacturing variations between the transistors. EDA simulators fix these conditions by default, but you can do things like iterate over a range of values for them, and see that the results change dramatically with each change in input.
• narrator 7y ago
  How about having multiple independent nodes receive a random number from an external source? Like the arrival of incoming gamma ray bursts or something? That would be useful for blockchain I imagine.
• eyegor 7y ago
  A fun thing that I haven't seen anyone try is to deliberately induce metastability into a small circuit. Anyone who's played with digital logic knows that underpowering/overclocking will lead to unpredictable behavior. Just build an oscillator and aim for an unstable clock speed (beyond the spec'd setup/hold delays) with an inadequate power source.
  • titzer 7y ago
    There are already hardware random number generator products that are better (https://en.wikipedia.org/wiki/Hardware_random_number_generator https://en.wikipedia.org/wiki/Hardware_random_number_generat...). A key point is to reduce energy consumption. Instead of aiming for an unstable clock speed (which requires a lot of power), it suffices to sample the very small leakage current from some circuit at high precision.
    • eyegor 7y ago
      Unstable clock speeds and power have zero relationship when you design the circuit. You can easily design something with a few transistors that will violate setup and hold times at 1-10mhz, which you can get out of a very low power crystal. You could even use an off the shelf mcu with a low nominal clock speed and just point a fast resonator at it. You can even make things unstable by giving it too slow of a clock speed. Most semiconductors don't want to hold a charge difference for very long.