Entropy generator with 100 kB/s throughput

Hi crypto hackers,

[1] patch at http://www.chronox.de/jitterentropy-0.1.tar.gz

The Linux kernel RNG which we all use via /dev/random or /dev/urandom received a lot of merits over the long years it exists. In particular it was subject to countless researches and assessments and was determined to deliver appropriate entropy to the caller.

However, we all know that the RNG also has deficiencies, which makes the appropriate use not entirely clear to everybody. In the past we heard about weak keys in embedded systems and the like. It is not the RNG's fault, but rather the problem of designers of such systems. Nonetheless, things could be easier with the use of the Linux RNG . In particular I met the following shortcomings over the years:

* /dev/random is regarded as high-quality RNG as it is constantly reseeded, but suffers from its blocking nature

* there is no in-kernel equivalent for /dev/random -- i.e. how can you really
seed the DRNG that is present in the kernel crypto API with high quality entropy?

* at boot time the data /dev/random or /dev/urandom spits out is questionable
which requires a reseed during reboot. Also, that seed file must first be written, which may not be trivial in all circumstances. For example, in embedded systems or live CDs, this may be a challenge. Or what about
system
outages -- there is no clean shutdown and no new seed file.

* in virtual environments (i.e. the Linux kernel operates as guest), /dev/random does not have access to all the devices to collect entropy.

* when generating the key for full disk encryption configuration, there may be
limited entropy in the entropy pools

* random.c contains complex processing which enlarges the device event processing for every event

In the patch, I try to provide an entropy collector without these shortcomings.
The patch offers an entropy generator based on CPU timing jitter. The entropy
collector has the following properties:

* it does not maintain any state and therefore does not need any seed

* it delivers entropy on demand with a throughput of about 100 kB/s and does not block -- it performs a synchronous entropy generation for the caller

* it should work well in virtualized environments

* the heart of the entropy collector is about 10 lines of code and does not use cryptography

* an array of statistical test suites pass the output of the entropy collector
(again, the output is not mangled with cryptography)

The design and concepts are documented in source code comments.

The source code is available at [1]. The code can be compiled as kernel module
as well as user space application. In case the code finds its way to the kernel, the user space code will be removed -- currently it remains to ease the analysis. To compile as kernel module, just run make. To compile as user space application, run make -f Makefile.user. Note, the user space part can also
be used in user space libraries to avoid /dev/random.

Is such entropy collector of interest for the kernel? Do you see weaknesses in the design or its implementation?

In a recent discussion about the Linux RNG Theodore Ts'o indicated that in the long run, he would like to see an RNG based on AES (see http://lkml.org/lkml/2012/12/15/162).

In addition to the entropy collector, the kernel module also includes a link to the kernel crypto API X9.31 DRNG based on AES. Two instances of the DRNG are maintained. The first instance is reseeded once in a while (after 1024 bytes
of random data) with the CPU jitter entropy. The second is reseeded with 16 bytes of entropy when 16 bytes are read from the DRNG. The first DRNG therefore
is a fast delivering DRNG which is information theoretical weaker than the second DRNG (which is much slower, but the information theoretical entropy equals about 1 bit per 1 bit of output).

For testing purposes, debugfs interface files are implemented to read from the entropy collector and the two DRNGs. The test mode is triggered with the parameter "insmod jitterentropy.ko testmode=1". The interface files are /sys/kernel/debug/jitterentropy/[seed|drng|strong-drng].

Detailed design description is given as comments in the source code file.

Thanks
Stephan

You're not mangling the output with cryptography, but you are doing some mangling in jitterentropy_cpu_jitter().

So let's be clear about what the heart of your entropy source is:

You're getting the nanoseconds out of clock_gettime(CLOCK_REALTIME), and then mixing it using XOR and a ROL(3) into a 64-bit buffer, and interspersing the calls to clock_gettime() with schedule().

So what a code breaker at the NSA would probably try to do first is to measure is whether there is any kind of bias or non-entropy in the nanoseconds returned by CLOCK_REALTIME after calls to schedule(). If they can find any kind of bias, they can use that to calculate what kind of patterns or non-random bits might end up showing up after you do your non-cryptographic mangling.

For that reasons, what I would suggest doing first is generate a series of outputs of jitterentropy_get_nstime() followed by schedule(). Look and see if there is any pattern. That's the problem with the FIPS 140-2 tests. Passing those tests are necessary, but *NOT* sufficient to prove that you have a good cryptographic generator. Even the tiniest amount of post-processing, even if they aren't cryptographic, can result in an utterly predictable series of numbers to pass the FIPS 140-2 tests.

Regards,

- Ted

In fact, Stephan's 'xor and shift a counter' design, even with zero input entropy (a counter incrementing at a constant rate), passes FIPS and a surprising fraction of dieharder tests (though some of the tests, such as diehard_count_1s_str, have this generator dead to rights); it also gives an ent entropy well in excess of 7.9999 bits per byte. This means it's hard to be confident that the entropy measured by ent is coming from the input entropy as opposed to the (exceedingly minimal-seeming on the surface!) amount of mixing done by the xor-and-shift...

It appears the entropy counted is equal to the log2 of the difference between successive samples (minus one?), but even if you have a good argument why the ones bit is unpredictable it doesn't seem an argument that applies as strongly to the weight-128 bit.

When the jitterrand loop runs 10 times, the LSB of that first loop has only gotten up to the 30th bit, so there are 20+ MSBs of the register that have not yet had bits rolled into them that are 'entropic' under the definition being used.

Finally, in the 'turbid' random number generator
(http://www.av8n.com/turbid/), the author develops a
concept of hash saturation. He concludes that if you have a noise source with a known (or assumed!) entropy and a has function that is well-distributed over N bits, you'd better put in M > N bits of entropy in order to be confident that the output register has N bits. He appears to suggest adding around 10 extra bits of randomness, or 74 bits randomness for a 64-bit hash, relatively indepently of the size of the hash. This design gathers only 64 bits if you trust the input entropy calculation, which according to the hash saturation calculation means that the output will only have about 63.2 bits of randomness per 64 bits output.

Here's my 'absolutely zero entropy' version of the jitter random algorithm as I understand it:

#include <stdint.h>
#include <unistd.h>

const uint64_t dt = 65309;
uint64_t t, r;

static inline uint64_t rol64(uint64_t word, unsigned int shift)

{
    return (word << shift) | (word >> (64 - shift));
}

uint64_t jitterrand() {
    int i;
    // each sample from the 'stuck counter' will be accounted as 7 bits of
    // entropy, so 10 cycles to get >= 63 bits of randomness
    for(i=0; i<10; i++) {
        t += dt;
        r = rol64(r ^ t, 3);
    }
    return r;
}

int main() {
    while(1) {
        uint64_t val = jitterrand();
        ssize_t res = write(1, &val, sizeof(val));
        if(res < 0) break;
    }
    return 0;
}

// Jeff

On 10.02.2013 02:57:51, +0100, Jeff Epler <[email protected]> wrote:

Hi Jeff,

I am totally on your side that passing the tests is a necessary prerequisite for a good RNG but by no means a proof that the RNG produces entropy.

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.

Why are you mentioning 128 bit? The pool I try to fill is 64 bit and it is filled with at least 16 * 9 clock measurements and an equal amount of code in-between due to the schedule call.

If you apply this argument to my suggested code, after executing the 16 loops in jitterentropy_cpu_jitter once, you rolled up to bit 48 (3 * 16). Now, you have at least 9 invocations of this loop of 16. This implies you rolled over the pool buffer several times.

I am not sure how that applies to the suggested code. The entropy source just generates raw entropy without using a hash. The entropy then is used to seed a DRNG. The so-called "strong DRNG" is initially seeded with 48 bytes out of my entropy source. After generating 16 bytes of output, it is reseeded with another 16 bytes of entropy. And after reaching 1024 bits of output, it is also re-keyed.

Only the "regular DRNG" is reseeded after 1024 bytes of output and rekeyed after 1MB of output.

Only those two DRNGs are supposed to be interface for a user to obtain random data.

Note: reseeding and rekeying are not yet implemented in the kernel crypto API, but can easily be added.

Thanks
Stephan

| Cui bono? |

OK, my original reading of the mixing code was not accurate. This time around, I started with the original posted tarball and turned the use of the CPU clock into a very simple and clearly bad "clock" that will provide no entropy.

@@ -270,12 +270,13 @@
 typedef uint64_t __u64;
 
 static int fips_enabled = 0;
-#define jitterentropy_schedule sched_yield()
+#define jitterentropy_schedule (0)
 static inline void jitterentropy_get_nstime(__u64 *out)
 {
-       struct timespec time;
-       if (clock_gettime(CLOCK_REALTIME, &time) == 0)
-               *out = time.tv_nsec;
+        static __u64 t = 0;
+        const __u64 delta2 = 257;
+        static __u64 delta;
+        *out = (t += (delta += delta2));
 }
 
 /* note: these helper functions are shamelessly stolen from the kernel :-) */

This give a generator that has Entropy = 7.999907 bits per byte and fails 6 in 10000 FIPS 140-2 tests. It also passes some (but not all) dieharder tests.

Jeff

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.

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

One paper that seems to show there is some randomness in such measurements is McGuire, Okech & Schiesser "Analysis of inherent randomness of the Linux kernel",
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

They do two clock calls with a usleep() between, take the low bit of the difference and pack them unmixed into bytes for testing. Their tests show over 7.5 bits of entropy per byte, even with interrupts disabled. The same paper shows that simple arithmetic sequences give some apparent entropy, due to TLB misses, interrupts, etc.

There are lots of caveats in how this should be used and it is unclear how much real entropy it gives, but is seems clear it gives some.

My own program to feed into random(4) is based on such things:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

HAVEGE also uses them
http://www.irisa.fr/caps/projects/hipsor/
& there is a havegd daemon for Linux
http://www.issihosts.com/haveged/

random(4) also mixed in timer data at one point, which seems the correct thing for it to do. Later I heard something about that code having been removed. What is the current status?

On 10.02.2013 19:50:02, +0100, Theodore Ts'o <[email protected]> wrote:

Hi Ted,

...

Given all your doubts on the high-precision timer, how can you reasonably state that the Linux kernel RNG is good then?

The data from add_timer_randomness the kernel feeds into the input_pool is a concatenation of the event value, the jiffies and the get_cycles() value. The events hardly contains any entropy, the jiffies a little bit due to the coarse resolution of 250 or 1000 Hz. Only the processor cycles value provides real entropy.

Now you start doubting that with arguments that the resolution of that processor cycle timer is very coarse. If this is the case, why shall I trust random.c, especially considering the measurements observable events like key strokes, mouse movements, interrupts (network cards). Only if you have a high-precision time stamp, entropy can be derived from these events.

Moreover, I cannot understand your comments on VMs -- on x86, the timer depends on the rdtsc instruction which should be available on current CPUs and is callable from user space. Hence, there should be no obstacle to use this instruction within a VM and get a good reading.

Note, I will make measurements about the distribution of the timer values and will come back to you.

Thanks
Stephan

| Cui bono? |

There are multiple sources of entropy, though. There are reasons not to fully trust any -- key strike statistics can be predicted if the enemy knows the language, the enemy might be monitoring the network. there is no keyboard or mouse on a headless server, a diskless machine has no disk timing entropy and one with an SSD or intelligent RAID controller very little, .... However, with multiple sources and conservative estimates, it is reasonable to hope there is enough entropy coming in somewhere.

It is much harder to trust a system with single source of entropy, perhaps impossible for something that is likely to be deployed on the whole range of things Linux runs on, from a cell phone with a single 32-bit CPU all the way to beowulf-based supercomputers with thousands of multicore chips.

Moeove, random(4) has both a large entropy pool (or three, to be more precise) and strong crypto in the mixing. If it /ever/ gets a few hundred bits of real entropy then no-one without the resources of a major government and/or a brilliant unpublished attack on SHA-1 can even hope to break it.

In the default Linux setup, it gets few K bits of
reasonably good entropy from the initialisation
scripts, so attacks look impossible unless the
enemy already has root privileges or has
physical access to boot the machine from
other media & look at Linux storage.

Because we're measuring intervals that are substantially larger than "CPU jitter". (i.e., inputs from keyboards and mice, interrupts from hard drives and networks, etc.)

Jiffies is defined by 250HZ (4ms) on modern Linux kernels, at least for x86 systems. Average seek times for common HDD's are 10ms, with full-stroke seek times being roughly twice that, and seek times perhaps 50% slower for laptop/mobile HDD's, and 50% faster for high-end server drives. So that's enough to get maybe a bit or two worth's of entropy for HDD interrupts.

(Yes, this does imply that the entropy estimator for /dev/random is probably overestimating the entropy in a number of cases; in general, it's actually pretty difficult to measure entropy accurately in an automated way.)

The problem is one of correctness versus performance. (The TSC is unsynchronized across different CPU cores, and the guest OS has no idea when it gets switched to running on a different core on the host CPU.) As a result, on many/most VM's the TSC is emulated or paravirtualized. For example, see:

http://old-list-archives.xen.org/archives/html/xen-devel/2009-08/msg01103.html

for a discussion of the issues involved.

Regards,

- Ted

On 09.02.2013 19:06:29, +0100, Theodore Ts'o <[email protected]> wrote:

Hi Ted,

thank you for the review.

Correct.

I thought I have countered such possibility already with the following 2 concepts:

1. Before entropy is extracted from the pool, at the minimum 9 * 16 clock measurements (we have 16 rounds in jitterentropy_cpu_jitter and at least 9 rounds in jitterentropy_gen_entropy due to the entropy calculation and the limit of 7 bits of entropy per round) are fed into the pool with the strong possibility of more. The number of measurements mixed into the pool depends on the amount of entropy the heuristic applies to the time needed to perform the 16 rounds of measurements and the previous delta.

2. The entropy heuristic is measuring the delta of deltas to calculate the entropy -- and thus implicitly how often the 16 clock measurements are applied. With the use of deltas of deltas (i.e. kind of the 2nd derivation of the absolute time measurements), the code implies 0 bit of entropy for evenly spaced time measurements (i.e. no jitter) and time measurements with a too coarse timer.

Note, I am not using FIPS 140-2 tests as there are none. I try to use the tests NIST and the German BSI would require when you come along with an RNG for validation. In addition, I use the dieharder test suite with its tons of tests.

Thank you very much for the suggestions. I will perform the suggested test.

On the other hand the entropy generator is intended to serve as a seed source for the DRNGs. One of the goals I tried to achieve is ease of use without the possibility to misuse the implementation. With that in mind, for the kernel implementation, I guess jitterentropy_read_entropy should not be exported with EXPORT_SYMBOL and should be static.

This change implies that in the kernel only the DRNGs are accessible where the strong DRNG (jitterentropy_strong_drng) should conceptually be as strong as blocking_pool (without the blocking nature) and the regular DRNG (jitterentropy_reg_drng) is conceptually the equivalent to nonblocking_pool which is guaranteed to be reseeded.

Thanks
Stephan

Apologies if this is misthreaded, I had to hand-craft the headers.

What is this "pool" if it's not "state"?

And, from looking at jitterentropy_entropy_calc(), it seems to think that the [source producing the] following sequence of timestamps:

1000, 1010, 1030, 1050, 1060, 1080, 1090, 1110, 1120, ... i.e. with absolutely metronomic deltas of 10, 20, 10, 20, 10, 20, ...

has 4 bit of entropy per reading. I hope I don't have to explicitly say that it clearly it has 0 bits of entropy.

Entropy harvesting is quite hard - entropy estimation is unimaginably harder. Phil

"In a world of magnets and miracles" 
-- Insane Clown Posse, Miracles, 2009. Much derided.
"Magnets, how do they work"
-- Pink Floyd, High Hopes, 1994. Lauded as lyrical geniuses.

On 21.02.2013 15:07:12, +0100, Phil Carmody <[email protected]> wrote:

Hi Phil,

There is no state between calls. Of course, you need a scratchpad to do calculations.

I can always hand-craft some deltas that the entropy heuristics come up with a positive value although there is none. You can make the same statement for the entropy calculation of random.c. So, that example is not applicable. I am working on showing that the jitter has entropy. I will come back.

This is a statement that does not make sense. You CANNOT per definition calculate entropy! The entropy calculation shall ensure that the collector in the worst case is called as often to make sure that there is enough entropy. In other circumstances, it shall just save time!

Ciao
Stephan

| Cui bono? |

But in general you need a buffer. It is quite easy to construct scenarios where several K bits of entropy are needed very -- for example, reboot an IPsec gateway the supports a few dozen tunnels and needs a few hundred bits to rekey each. Without state, it is quite difficult to demonstrate that you can meet such requirements. Given a reasonable size of buffer, some saved random data and the assumption that the enemy does not already have root on your server, it is trivial.

I think that has already been shown. See the McGuire et al. paper I cited earlier in the thread and the HAVEGE papers. Of course it needs more analysis to be sure we have really good estimates of that entropy, but it seems clear there is some at any rate.

Yes.

The question is not /calculating/ it, but /estimating/ it. That is a perfectly reasonable thing to do, and it is done in most generators. It is a hard problem, though, and requires care in both design and implementation.

Also, in some designs it is possible to get very close to calculating entropy. The Turbid generator, for example, uses physical measurements of sound card properties plus arguments from standard circuit physics to prove a lower bound on the Johnson noise that must exist in the circuit.

the hash, you get a provable lower bound on output entropy.

That's assuming you're talking to a real physical sound card, however. Suppose you have a set up where the user is running one or more VM's on their desktop, and the VM (possibly with some assist from PulseAudio) is multiplexing the host sound card and doing upmixing and/or downmixing as part of its multiplexing magic?

Would the Turbid generator be able to detect this situation, and would its entropy estimates be correct? Even if they are correct, the fact that another VM might be getting the same stream of inputs, unbeknownst to the Turbid generator, might mean that an adversary might have access to the "entropy" being generated by the PulseAudio stream....

(And yes, there is the same potential issue with the current /dev/random sampling what it thinks is hardware noise generation from network and hdd interrupts; the point is that entropy collection in the VM is *hard* and extremely error-prone. In the end you're probably better off using paravirtualization for /dev/random and trust the Host OS to give you good randomness. After all, if you don't trust the Host OS, you're fundamentally screwed anyway....)

- Ted

I'm so sorry, something went terribly wrong with gmail/thunderbird :-(

2013/2/22 Nick Kossifidis <[email protected]>:

GPG ID: 0xEE878588
As you read this post global entropy rises. Have Fun ;-)
Nick