2
$\begingroup$

Similar questions have been asked regarding use of time in true random number generation, but I'd like to consider using time as just one source of entropy, complementing others.

True random number generation relies on the mensuration of some physical stochastic process. Electrons avalanche across depletion boundaries in essentially one dimension. Polarised photons move in two dimensions, whilst rolled dice move in three. All are potential sources of entropy whose measure in up to three dimensions is used to generate random numbers.

However space is four dimensional. Rolling a 6 might be random, but isn't it even more precise to say it was a 6 at 7.49 am? Some people say that as time is known it is unsafe to use as a source of entropy. On my machine, Java can measure relative time to a precision of 350ns from boot time. Allowing for a realistic boot duration variation of 10s, that allows for 7.5 decades of resolution. Who can tell when my machine was booted? It might have been on for a year, so 7.5 decades of resolution is a conservative estimate. And what if the numbers aren't consumed immediately, but cached somewhere ageing them? Bytes resulting from such a generator obviously have no associated time stamp. This then adds at least another 7.5 zeros to the number of combinations of entropy, and consequently increases security.

When measuring a physical property, isn't it just as important to record when a voltage was measured as is the number of volts? The voltage is measured relative to a reference voltage, and surely it can be measured relative to boot time? After all, /dev/random uses timings for it's cryptographically secure output.

Supplemental:

After some testing, I found that the simple Java function 

System.nanoTime() & 0xff

can generate entropy at a rate of 1.4mb/s surprisingly. It varies in as still uncertain ways correlated with the system load.

Also, there seems to be a great effect when such entropy (call it Relativity) is mixed with another source. So again based on experiments, the following was found (but I think requires further study - seems to exhibit behaviour reminiscent of superposition)...

H(weak source) = 0.039%

H(Relativity) = 2.2%

H(weak source XOR Relativity) = 32%

If Relativity is therefore combined with physical measurements, this seems to be low lying fruit, especially in an entropy deficient environment.

|improve this question
$\endgroup$
  • $\begingroup$ Why true random number generators in particular? They're not particularly useful for cryptography, and aren't generally guaranteed to be cryptographically secure in the first place. $\endgroup$ – SAI Peregrinus Aug 30 '15 at 7:23
  • $\begingroup$ Regarding your supplemental information, that does not seem likely to be true entropy. You at least need to look at the distribution of those low bits. Cf. add_timer_randomness in the Linux kernel for an example of estimation through deltas (the comments in the beginning of the file are good). $\endgroup$ – otus Sep 1 '15 at 7:44
  • $\begingroup$ Also, see CPU Time Jitter Based Non-Physical True Random Number Generator for an attempt at generating entropy from timers without user input. (The function I linked above is only called on physical user input.) $\endgroup$ – otus Sep 1 '15 at 7:48
  • $\begingroup$ @SAIPeregrinus Assuming that your comment is serious, aren't true random numbers one of the Holy Grails of cryptography? Don't understand what you mean by your phrase regarding cryptographic security of them. $\endgroup$ – Paul Uszak Sep 3 '15 at 2:00
  • $\begingroup$ @otus I use the term entropy in the way Shannon originally defined it. It's a measure of the rate of information production. It's not random numbers. Clearly some form of extraction needs to be performed to get random numbers. This is exactly the underlying principle of your Jitter paper. $\endgroup$ – Paul Uszak Sep 3 '15 at 2:11
6
$\begingroup$

Who can tell when my machine was booted?

Anyone who observed it go on, at least. That could include someone sniffing your wlan traffic. However, if the computer in question is a shared server, anyone with access can probably call uptime.

After all, /dev/random uses timings for it's cryptographically secure output.

In setups where timing information is included (in a way that counts entropy), the thing being timed is supposed to be unknowable. For example, the least significant bits of when a physically present user presses a key.

In theory, even that isn't necessarily unknown (e.g. wireless keyboard), but since there is additional variation in how long it takes until the kernel knows about it and the entropy estimate is quite pessimistic, it is assumed to be.

However, in my opinion the most important thing to keep in mind is that you only need the TRNG to produce something like 256 bits on output. Use that to seed a CSPRNG and you can produce more output than you could ever use.

So if you have a truly random process, measuring the non-time values should be enough to quickly collect the required amount of entropy. You can throw time values into the entropy extractor if you like, but you don't need to credit them with entropy if you get enough anyway.

|improve this answer
$\endgroup$
4
$\begingroup$

I'll formalize things a bit, because I think it is then easier to understand what is going on.

Definitions. A random variable $X$ is defined by a set of possible events $(x_1,...,x_n)$ and the probabilities of these events $P(x_1),...,P(x_n)$, and its entropy is defined as$$H(X):=-\sum_{i=0}^n P(x_i)\cdot \log_2(P(x_i)) \mbox{ bits}.$$ When all events have the same probability (=uniform distribution)$$P(x_1)=P(x_2)=...=P(x_n)=1/n$$then you have the maximal entropy $$H(X)= \log_2(n) \mbox{ bits}.$$

Back to your example. The above means that the entropy you get from your boot duration is not only dependent on the possible events {350ns,700ns,...,10s}, but also on the probabilities of these events $P(350\mbox{ns}),P(700\mbox{ns}),...,P(10\mbox{s})$.

If all of your $n=10/0.000000350\approx 28571428$ possible boot times had the same probability, you'd have an entropy of $$\log_2 (28571428)\approx 24.77 \mbox{ bits}$$ However, I expect that most of your boot times will be around the mean of 5s, so you will have less entropy.

Physical sources of randomness. As you mention in your question, there are many possible sources of randomness you can use. E.g., you can measure voltages, the boot time, movements of the mouse, key strokes... Typically, a randomness extractor is used to obtain a uniform distribution from such non-uniform physical sources.

Some source will allow to generate random bits faster than others. A possible problem I see with your boot time is that it doesn't happen very often. If you go for mouse movements or key strokes, you will be able to generate random bits faster.

|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Mouse movements and key strokes may not happen at all, e.g. on headless servers. Precise network timings probably always happen, but are slightly dangerous as they may be influenced by outside parties. That's why a TRNG is for me a prime requirement for CPU's, if only to use it as additional seed. A boot at least always happens... $\endgroup$ – Maarten Bodewes♦ Aug 30 '15 at 16:09
  • $\begingroup$ @MaartenBodewes Even network timings that aren't influenced or observed by outside parties may not be ideal, since modern NICs use interrupt coalescence where an interrupt is only sent to the operating system at fixed (predictable) intervals, or after every n received packets instead of at each packet. $\endgroup$ – forest Feb 6 at 5:52

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.