Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

From: Theodore Ts'o
Date: Sun Feb 10 2013 - 13:50:19 EST


On Sun, Feb 10, 2013 at 01:46:18PM +0100, Stephan Mueller wrote:
>
> However, the CPU has timing jitter in the execution of instruction. And
> I try to harvest that jitter. The good thing is that this jitter is
> always present and can be harvested on demand.

How do you know, though, that this is what you are harvesting?
Depending on the hardware and CPU that you are using, CLOCK_REALTIME
might be quantized in no more than 4ms intervals. Even on systems
with a TSC register, the TSC register has all sorts of effects which
can limit its granularity, and in fact is generally quantized as a
multiple of the bus cycles. Intel states that the quantization
effects mean that for timing purposes, you can't really accurately
time anything under 1000 cycles. So at that point, you're not
measuring CPU timing jitter, but something else; perhaps the frequency
beats between the CPU clock and the bus clock. Also, consider what
might happen if you are booted on a VM; at that point, I can pretty
much guarantee that whatever you are measuring, it will almost
certainly _not_ be from CPU timer jitter. It may be some very
hard-to-predict pattern generated from the timing interactions of the
host OS scheduler and the guest OS's scheduler, but that does _not_
necessarily mean that there is true randominess which you are getting.

After all, if I give you a sequence of numbers which is generated by
encrypting a counter with a secret AES key which only I know, that
does _not_ mean that you have a strong cryptographic random number
generator. If you use that sequence to generate session keys, I will
be able to break all of your encrypted traffic. The mere fact that
the sequence of numbers is one which passes pretty much all RNG tests,
whether they be FIPS 140, or the BSI tests, or the dieharder tests,
and just because _you_ can't figure out the pattern, does not mean
that therefore the sequence is random.

> I am not sure how that applies to the suggested code. The entropy source
> just generates raw entropy without using a hash.

And what's your proof that your entropy source really is an entropy
source?

After all, I can claim that the dice rolls are random based on the
chaotic air movements influencing how the die spins through the air.
The fact that there are chaotic air movements isn't the question. The
question is whether or not the die is perfectly balanced. If the die
is weighted unevenly, the fact that there are all sorts of subtle
chaotic effects which could be influencing the roll of the dice is
utterly irrelevant.

Similarly, if the time stamp counter, even though supposedly it is
giving you granularity measured in nanoseconds, is in fact getting
granularized somewhere in the hardware in in the thousands of cycles,
even if there are apparently many digits of precision, does not mean
that you actually have that many significant digits.

Regards,

- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/