4
$\begingroup$

If I have a headless machine (no mouse movements, no keyboard presses, or user input), without any cryptography CSPRNG APIs, where can I collect entropy from?

$\endgroup$
  • 3
    $\begingroup$ Is that a theoretical or practical question? Almost all Unix-based systems have /dev/random. Windows typically has CryptGenRandom or RtlGenRandom. "Headless machine" is vague, PIC12, CS-1, OLCF-4? $\endgroup$ – fgrieu Nov 25 '19 at 16:32
  • 1
    $\begingroup$ Ala Paul's question, what else can you tell us about the environment? Is it x86-64? Modern Intel compatible architecture CPUs have the RDSEED instruction. If you trust that it has all the entropy you need. $\endgroup$ – Swashbuckler Nov 25 '19 at 18:45
  • 1
    $\begingroup$ No the question is rather, what entropy sources are there? I just don't want to outsource entropy collection (/dev/random or CryptGenRandom), but I want to see what sources there are. I'm not asking how to generate random numbers, rather what entropy sources there are. $\endgroup$ – 09182736471890 Nov 27 '19 at 21:50
  • 1
    $\begingroup$ I have not rejected all answers on hardware, see the accepted answer. The accepted answer successfully answers this question, with mention of hardware. $\endgroup$ – 09182736471890 Nov 28 '19 at 19:25
  • 1
    $\begingroup$ I realize you have accepted an answer, but it is rather confusing that you first summarily rejected all ‘hardware dependencies’ and then accepted an answer that is entirely about hardware dependencies! $\endgroup$ – Squeamish Ossifrage Nov 29 '19 at 6:25
7
$\begingroup$

I believe that on any CPU that you should be able to find at least two sources of noise with physically proven behaviors to create a purely random number. The first is through oscillator sampling, assuming that you have a fast clock and a slow clock. The second assumes that you have DRAM, and through the two-way shot noise in the channel, you should be able extract random bit flips in DRAM if you can control the timing.

Clock Sampling

The clock in a system is not a precise as you'd hope. Generally, you have a core clock that is generated through a PLL, and you also have some sort of realtime clock at 32.768kHz because that will overflow after bit-15 to give you a 1-second pulse. By sampling the fast clock with the slow clock, you can generate a series of bits; however, there's a few caveats:

  • oscillator jitter alone is not enough to create randomness
  • you can actually degenerate the randomness by trying to make it random if you have a poor circuit model.

As an x86 was mentioned (I know the least about this CPU btw), the time stamp counter combined with a 8254 on older machines or HPET on newer machines will get you a fast and a slow clock source. Michael S. McCorquodale dissertation should have a very good analysis on the clock jitter in both cases, or at least he did at this defense.

DRAM

If you can control the timing of the DRAM, you very likely could get a random noise source due to the fact that the noise in a semiconductor channel is a function two-way shot noise (and not classical Johnson Noise). Let's limit the scope to a single bit. You would have to put charge on the DRAM capacitor and then gradually delay the timing until that bit gave you a 1 or 0. The charge amplifier on the DRAM rows would also add to the noise, but I will ignore that component for now. Carver Mead and Rahul Sarpeshkar both use shot-noise in their neuromorphic engineering papers as a source for entropy on silicon neurons, and circuits people can derive it but I really don't know where an external reference is. The caveats:

  • DRAM timing control
  • assume that you are not near "freeze out" as the shot noise goes away.

I believe that either of these, combined with a hash, could be used as a means to generate a true random number as the noise sources are rooted in physics. You'll need to grab a cryptographer to take what I described to the next step.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, you don't need any form of cryptographic input to extract from your scheme. The numbers simply form as a result of non cryptographic extraction, such as Toeplitz or von Neumann (in appropriate circumstances). The hard bit is measuring and stabilising the $H_\infty$ rate. $\endgroup$ – Paul Uszak Nov 27 '19 at 21:49
  • $\begingroup$ You would have to put charge on the DRAM capacitor and then gradually delay the timing until that bit gave you a 1 or 0. – Surprisingly, at least for modern DRAM, different bits have different probabilities for decaying into a given bit, and those probabilities are not random nor secret. $\endgroup$ – forest Dec 8 '19 at 3:52
  • $\begingroup$ @forest I completely agree, but there's some context here. For a "bank", the decays are pretty close, and this is due how mismatch and lithography mess things up over area. In the scope of a single bit, you can do this. It's did the hand waving over the clocks. When I use DRAM for cache instead of SRAM, we have really good access to the clock that control timing. If I am using external DRAM, I have much less access to the controller registers. $\endgroup$ – b degnan Dec 8 '19 at 13:13
  • 1
    $\begingroup$ @PaulUszak I disagree as it's possible with anything with cache actually, and you just have to have access to the timers. You could achieve the same thing with SRAM read delays from the charge amps as there's a wait time. As someone who makes hardware, I can verify that there's a lot of registers that no one knows about outside the implementers of that hardware. I'm sure if you got the right *unix kernel programmer over for coffee, they'd tell you how to do it as they are familiar with what is given. $\endgroup$ – b degnan Dec 9 '19 at 19:40
  • 1
    $\begingroup$ @PaulUszak intel.com/content/dam/doc/datasheet/… 3.9.1 to 3.9.4 have what is needed. Sadly, you'd have to dedicate a whole DIMM to it form the looks of it, which would decrease your memory for the time of creating the random bits. Still, it's feasible in hardware. $\endgroup$ – b degnan Dec 9 '19 at 19:49
-3
$\begingroup$

Can entropy be gathered in a system without any hardware dependencies?

No. Not real entropy. There's probably some over-used cliche about trying to, but essentially you can't create Kolmogorov randomness without physical processes.

But there's a but. All computer algorithms execute on hardware, and that hardware is non deterministic at the pico scale. Hard to predict execution paths, indeterminate gate propagation delays and even electron travel times, amongst others can all produce randomness for harvesting. The haveged algorithm attempts this. Even simply reading the system clock repeatedly in a high level garbage collecting language [e.g. Java's System.nanoTime()] is non deterministic.

It's gets even more jittery if you can include a spinning disc drive in the loop somewhere. And don't forget that even virtualised discs are mounted on physical ones.

Are there any reliable entropy sources?

I suggest not very. All of the algorithms above have to execute alongside other code, some of which may be unknown, and certainly at unknown locations. It it difficult to quantify how much randomness your algorithm may have harvested, and that directly undermines the security confidence. And the concept of code portability/cross platform operation is at odds with a harvesting algorithm tied to particular hardware. So it's difficult to get 128 bits of Kolmogorov randomness in a firm timescale. You will have to use a large safety factor (say x100) in estimating min.entropy, but it's doable if speed isn't important. You'll be down to only tens of bits/s on something like an Arduino.


There are even more exotic techniques such as reading DRAM state transitions. There's a 2018 summary of DRAM based cryptographic primitives here, from TRNG and physical unclonable function (PUF) perspectives.

If your machine has some form of remote/comms access, then you can just fetch entropy over the comms port from a device that has it to spare.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ ‘essentially you can't create Kolmogorov randomness without physical processes’—This is not true. Kolmogorov randomness has nothing to do with physical processes (and not much to do with cryptography either); it may be hard to compute but a string's Kolmogorov complexity relative to some language is independent of any particular hardware you used to pick the string or execute the language. $\endgroup$ – Squeamish Ossifrage Nov 27 '19 at 23:38
  • $\begingroup$ @SqueamishOssifrage Pretty fundamental to cryptography actually. The reason it’s called Kolmogorov randomness is that it’s upstream of the typical (odd) definitions of (information) entropy here. This always rears it’s head with TRNGs and ye olde /dev/random thingie. And computational indistinguishability means it’s too easy to abuse as I show in my RDRAND analysis. It’s 99% certain that’s a high entropy source with low Kolmogorov randomness and thus a PRNG, not a TRNG. That’s why I use much clearer definitions. $\endgroup$ – Paul Uszak Nov 28 '19 at 1:44
  • 1
    $\begingroup$ The reason it's called Kolmogorov randomness is that it's based on Kolmogorov complexity—which, for a string and a language, is the length of the shortest program in that language that prints that string, an (uncomputable!) mathematical property not related a priori to probability or entropy—and it scratches an apparently common human itch to assign a notion of ‘randomness’ to a particular string—specifically, whether in a specific language there's a program shorter than the string to print it—even though it has nothing to do with uncertainty or adversaries or prediction or random processes. $\endgroup$ – Squeamish Ossifrage Nov 28 '19 at 3:01
  • 2
    $\begingroup$ Cryptography relies on ensuring the adversary doesn't know a secret key. If the adversary knows the key, it doesn't matter how long the shortest, say, Python program to print the key is—the Kolmogorov complexity of the key relative to the Python language—because the cryptography is hopelessly broken anyway. Maybe the shortest Python program is longer than the key itself—so the key has ‘Kolmogorov randomness’—but what's relevant to cryptography is the adversary's state of knowledge, which is a probability distribution on possible keys. $\endgroup$ – Squeamish Ossifrage Nov 29 '19 at 6:14
  • 1
    $\begingroup$ @SqueamishOssifrage That's grand, but this Q&A is about how to harvest entropy. And I've shown that quite conclusively. $\endgroup$ – Paul Uszak Nov 29 '19 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.