Re: [PATCH] /dev/random: Insufficient of entropy on many architectures

[Thorsten Glaser]

Stephan Mueller <smueller <at> chronox.de> writes:

> And here the RNG theory breaks: a whitening function (crypto function) 
> like the used SHA1 does not add entropy. Thus, the SHA1 just spreads out 
> the entropy evenly over the output buffer. As entropy can be considered 

Thatâs why you also use a (faster, less powerful) mixing function
on input.

I was wondering: why not use Jenkinsâ one-at-a-time hash there?
Iâve worked with it a bit, and it has good avalanche behaviour;
I didnât measure any cycles though.

Basically, h be an uint32_t register (usually loaded from a
memory location and stored to one afterwards), then you do:

    (h) += (uint8_t)(b);
#ifdef with_mirabilos_changes
    ++(h);
#endif
    (h) += (h) << 10;
    (h) ^= (h) >> 6;

Iâm adding 1 after the first step (adding the byte) in order
to make even NUL bytes make up a difference.

Iâm toying with code that has 32 such uint32_t values, making
for a total of 128 Bytes of state, and when asked to add some
memory content into that pool, just distribute the bytes over
the values array, incrementing a counter.

(One could probably do something with cmpxchg to make that
lockless, but Iâm not doing any parallel programming myself.)

Then, every once in a while, youâd run the finish function
on every value, which is:

#ifdef with_mirabilos_changes
    (h) += (h) << 10;
    (h) ^= (h) >> 6;
#endif
    (h) += (h) << 3;
    (h) ^= (h) >> 11;
    (h) += (h) << 15;

My change here is because Jenkinsâ OAAT has good avalanche
except for the last input byte, so I just fake adding NUL
(which doesnât get avalanched so well, but doesnât matter)
to get the last actual data byte avalanched.

Then I write those finialised hash values back to the
128-Byte-buffer then I add that into the main pool using
a cryptographic (hash, or stream cipher rekey) function.
(In my case, arc4random, if someone wonders.)

> >It doesn't matter if you collect predictable data - it neither helps
> 
> Oh yes, it hurts, if you update the entropy estimator on those 
> predictable bits. Because then you get a deterministic RNG like 

Iâve seen Theodore apply exponential backoff to any estimation,
which is probably a good thing. But yes, you probably will want
to guess the entropy of the bytes added and not count things
where youâre not too sure of. (In the interrupt case, we have
jiffies, cycles and num, so weâd probably best estimate how
often interrupts are called, base a number of âtimingâ bits
on that, and account for num; this may very well be less than
8 bit âcreditedâ for a long and two u_int added to the pool,
but as long as you get that right and donât blindly credit
a byte as 8 bit, youâre safe. To quote the author of RANDOM.SYS
for DOS: âEvery bit counts.â It adds uncertainty to the pool,
at least by stirring around the already-existing entropy without
adding any new (creditable) entropy.)

bye,
//mirabilos

--
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/