**Next message:**Olof Johansson: "Re: [PATCH 11/14] ARM: ux500: remove irq_base property fromplatform_data"**Previous message:**Olof Johansson: "Re: [PATCH 1/1] ARM: tegra: Fix build error w/ ARCH_TEGRA_114_SOCw/o ARCH_TEGRA_3x_SOC"**In reply to:**Theodore Ts'o: "Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput"**Next in thread:**Stephan Mueller: "Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

On Sat, Feb 09, 2013 at 01:06:29PM -0500, Theodore Ts'o wrote:

>

>

>

>

>

>

>

>

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

--

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/

**Next message:**Olof Johansson: "Re: [PATCH 11/14] ARM: ux500: remove irq_base property fromplatform_data"**Previous message:**Olof Johansson: "Re: [PATCH 1/1] ARM: tegra: Fix build error w/ ARCH_TEGRA_114_SOCw/o ARCH_TEGRA_3x_SOC"**In reply to:**Theodore Ts'o: "Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput"**Next in thread:**Stephan Mueller: "Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]