5
$\begingroup$

From what I understand, a physical source of true randomness could be achieved with a multi-core processor, by using clock drift between two or more cores.

However, a processor is easier to manipulate than nuclear decay or thermal noise when it comes to true random number generation.

My questions are:

  1. Are there any attacks?
  2. Are any of them practical?

  3. Are there any steps that can be taken or conditions satisfied to prevent attackers from effectively manipulating the output of the processor?

  4. And finally, how easy is it to bias the cpu virtually compared to properly implemented and secure CSPRNG libraries offered, like java SecureRandom?

My last question is really subjective to different libraries but if you can provide examples and scenarios or comparisons of potential attack vectors it would really help me understand.

I am currently under the impression that using a CPU for a TRNG is about as good as a software based CS-PRNG, but I could be wrong.

$\endgroup$
  • 2
    $\begingroup$ The Poisson distribution in channel charge will make clocks jitter, but not if they have a stable source, ie: crystal oscillator. you can use a ring oscillator and easily see this effect; however, due to clock edges, I do not believe there is anyway in a standard processor to see the difference. To that effect, you should edit your question to be more specific. $\endgroup$ – b degnan Jun 14 '17 at 23:49
  • 5
    $\begingroup$ A TRNG is never used instead of a CSPRNG. They serve different purposes. A TRNG is used to seed a CSPRNG. A CSPRNG alone isn't enough to generate random data since it's reproducible. A hardware entropy source alone isn't enough to generate random data because all entropy sources have biases. $\endgroup$ – Gilles Jun 15 '17 at 0:05
  • 1
    $\begingroup$ @Gilles Not quite. A TRNG doesn't require a CSPRNG in the least. You can get perfectly unbiased random output from a TRNG with just extremely simple matrix multiplication. In fact, any TRNG + CSPRNG combo is highly suspect in my opinion as you'd shouldn't have a CSPRNG component. $\endgroup$ – Paul Uszak Jun 15 '17 at 2:17
  • 1
    $\begingroup$ @PaulUszak Your opinion goes against that of a vast majority of the crypto community, as well as basic math and physics. I'm certainly not going to accept an RNG that doesn't go through a CSPRNG in any security-conscious project. $\endgroup$ – Gilles Jun 15 '17 at 8:37
  • $\begingroup$ @Gilles Actually you'll find that it goes people whose opinions are given to them by NIST (which understandably is not allowed to sanction a pure TRNG). It certainly doesn't go against the maths and physics. You just don't understand entropy /TRNGs. ID Quantique do and make a happy living selling them without CSPRNGs inside. I build them too and they work pretty well. Why don't you frame this as a new question? $\endgroup$ – Paul Uszak Jun 15 '17 at 10:07
11
$\begingroup$

A TRNG is never used instead of a CSPRNG. They serve different purposes. A TRNG is used to seed a CSPRNG. A CSPRNG alone isn't enough to generate random data since it's reproducible. A hardware entropy source alone isn't enough to generate random data because all entropy sources have biases.

For any purpose that's related to security or cryptography, a random generator (CSRNG) is built by seeding a cryptographically secure pseudorandom generator (CSPRNG) with an entropy source, which is some physically obtained unpredictable, secret input. The CSPRNG whitens the entropy source.

The CSPRNG turns a small amount of data (typically a few thousands of bits) into an effectively endless stream of bits, and ensures that all the bits are independent. More precisely, a CSRNG must have the property that if an adversary sees all the output bits except one (but does not get to see the RNG's internal state), they have no clue what that hidden bit is: it could be either 0 or 1 and the adversary can only guess with a chance of success that's extremely close to $1/2$ — no more than $1/2+2^{-N}$ for a CSRNG with $N$-bit quality (e.g. $N=128$). A CSPRNG guarantees that property provided that its seed is sufficiently “varied”, in that the adversary can't guess the seed with a chance of success that's better than about $2^{-N}$.

A discretization of a physical phenomenon always has biases: some sequences of bits are more probable than others, due to characteristics of the physical phenomenon or to measurement errors. Using this as input to a CSPRNG destroys all the correlations between successive bits. The CSPRNG also has other benefits, including the ability of combining multiple phenomenons, with the safety that combining sources together never weakens the result (even if one of the sources turns out to be partially or totally known to the adversary, the quality of the resulting RNG is still at least as good as the other sources).


Now the real question is, is clock drift (jitter) useful as an entropy source? The answer is yes, it is used in practice. Fast Digital TRNG Based on Metastable Ring Oscillator by Vasyltsov et al. (2008) gives an overview of work in that domain in §2.

If you're an application writer, that's not something you need to care about. Entropy gathering is done by the operating system.

If you're a system integrator, you have to take care that your system has proper entropy sources. All modern PC processors (RDRAND) and smartphones (running iOS, Android or Windows) have hardware RNG (using phyiscal phenomenons that differ from chip to chip). Embedded devices are a very varied breed, some have good entropy sources, others don't; clock drift is often irrelevant in this realm because there aren't enough distinct clocks (unless one has been provided for the very purpose of generating entropy through drift, in which case the manufacturer will generally provide a some firmware or driver code to perform the required measurements).

Measuring clock drift is not trivial. You need to make sure that you're reading data from clocks that aren't synchronized. You need to give the system enough time to get initialized and then for the clocks to get out of synch. You need to beware of environmental parameters; for example some clocks may be effectively unpredictable at sufficiently high temperature but completely predictable at lower temperature. A good hardware RNG will provide a quality estimate. Statistical tests on an entropy source can sometimes help figure out whether it's operating correctly, but often the types of biases depend on the physical construction of the source and tests need to take this physical construction into account in order to be effective.

$\endgroup$
  • $\begingroup$ Re. Your Vasyltsov paper. A custom built FPGA ring oscillator isn't exactly cpu clock drift between different cores is it? $\endgroup$ – Paul Uszak Jun 15 '17 at 1:19
  • $\begingroup$ I agree with the answer but disagree with the bias comment. If I have an inverter, the noise power in saturation is $I^2= 2q I_{sat} \left(1+e^{\frac{-V_{ds}}{U_{T}}}\right) f$, where $f$ is set by the current bias of the opposing transistor. The arrival of electrons across the resistor is a Poisson process that is determined by the electron concentration, diffusion constant and length of travel. Furthermore, as we move out of saturation, one would expect more noise, up to a factor of 2. I am unclear of the source of the bias due to the random distribution of the charge arrival. $\endgroup$ – b degnan Jun 15 '17 at 1:34
  • $\begingroup$ @bdegnan Even if your process is perfect — which is not the case, there are always sources of noise that can introduce a systematic drift, and how sure are you that those sources are negligible to the desired scale? — the measurement apparatus has its own inaccuracies. $\endgroup$ – Gilles Jun 15 '17 at 8:38
  • $\begingroup$ @PaulUszak I see, there's a bit of field specific assumptions. The entropy is the pounding of keys. Regarding the physics, the noise power is set by current, and in a source follower-chain, it makes a very good random number generator. I should have been specific that I was applying this to near threshold oscillators, and not integrating the noise on a cap. I found that Intel does this similarly (the non-paywalled overview): spectrum.ieee.org/computing/hardware/… Thermal noise is pretty much all we have in silicon. $\endgroup$ – b degnan Jun 15 '17 at 10:20
  • $\begingroup$ @Gilles In a reference frame, you will always have chaos. As Paul mention, you can changed how random something is by changing the temperature; however, it's relative to sampling. In Silicon, we will always have noise, and it just becomes managing the seeds. I hit "freeze out", ie: I'm an insulator, well before I become noise free and super conducting. To your comment, you just design the noise system for quality you want. $\endgroup$ – b degnan Jun 15 '17 at 10:28
4
$\begingroup$

The biggest danger is an inherent feature of using clock drift inside a busy computer. It's very difficult to accurately estimate the rate of entropy generation. You can't rely on what you're going to get, therefore satisfying the golden rule of (entropy in) > (entropy out) becomes problematic.

You can actually just use one core to generate a good quantity of entropy as all cores interact. Simply fetch the system time, as in System.nanos in Java. Do this:-

print System.nanoTime() & 0xff

which will generate data like:-

206
84
183
130
70
18
14
60
181
185

This sequence of numbers is a bit unpredictable but varies according to what your machine is doing and the type of machine. And probably the weather.

A mass of this data looks like:-

entropy

You can clearly see structure. You can also see that the structure continuously changes across the image. You could see it even clearer if you could zoom in on the file. That change is the entropy component. For this exact image, entropy is about 14% equivalent to 280,000 bits, or 1.1 bits /byte. (Entropy measured via compression.) So 14% of the image continuously changes, whilst the remaining 86% is fixed, which kinda makes sense looking at it. That entropy collection rate is specific to my machine at the time I collected it whilst streaming trance music.

All this data is theoretically predictable, but in reality isn't as the inside of a Java machine is incredibly chaotic. An equivalence is chucking a die. Whist we understand all the inherent processes as the die tumbles, we can't predict the score. The computer's chaotic environment can be sampled to generate pure entropy simple by reading the time. It's just that the entropy rate is too difficult to predict due to the same chaotic circumstances. That's the danger. I got 14% this time. You'll very probably get something entirely different, especially if you listen to different music or a CD.

PS. Actually, a thermal noise TRNG is easy to manipulate. All you have to do is put your hand on it and warm it up. The bias and entropy rate will change then.

PPS. Java's SecureRandom effectively uses the technique I've explained above to seed itself. It times the rate of different threads which are perturbed by exactly the things that affect System.nanos.

$\endgroup$
  • 1
    $\begingroup$ Hah! Now I if I can figure out your favourite tracks I can steal your private keys! Take that! :P $\endgroup$ – immibis Jun 15 '17 at 11:38
  • 2
    $\begingroup$ Note that System.nanoTime() "provides nanosecond precision, but not necessarily nanosecond resolution (that is, how frequently the value changes)—no guarantees are made except that the resolution is at least as good as that of currentTimeMillis()." Taking the least significant byte is not guaranteed to give you any entropy. Worth reading: "Nanotrusting the Nanotime", which has some pointers on how to benchmark your System.nanoTime() resolution. $\endgroup$ – Luis Casillas Jun 15 '17 at 17:28
  • 1
    $\begingroup$ thermal noise (johnson) is quantum-based and not deterministic; hand warming should do nothing. $\endgroup$ – dandavis Jun 15 '17 at 18:47
  • $\begingroup$ @dandavis In the classical interpretation, don't the atoms wobble more when they get warmer? Ergo the noise increases... $\endgroup$ – Paul Uszak Jun 15 '17 at 20:43
  • 1
    $\begingroup$ @PaulUszak: the quantum noise is very undersampled already, so a rate adjustment won't affect it within the specified operational thermal range. i can fill a canteen in a modest brook at the same rate as i could in the amazon... pachinko is apt: you can't catch them all. $\endgroup$ – dandavis Jun 15 '17 at 22:31
4
$\begingroup$

"However, a processor is easier to manipulate than nuclear decay or thermal noise when it comes to true random number generation."

This assumption is wrong (if you mean it would be easier to use a CPU than another source), since TRNGs use other sources much more often than clock drift. If you are trying to make an auditable random number you need the whole thing in a black box that doesn't do anything besides accept in entropy and output random numbers. You can't use some CPUs you already have because they may influence the random number.

Are there any attacks?
Maybe
Are any of them practical?
Maybe
Prevention?
Put the two CPUs in an isolated box running some known dummy program with known inputs, then realize it would be cheaper to replace them with some other source of entropy.

$\endgroup$

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.