[Cryptography] Uncorrelated sequence length, was: A TRNG review per day

David Leon Gil coruus at gmail.com
Sat Oct 25 09:02:51 EDT 2014

On Sat, Oct 25, 2014 at 5:51 AM, Bill Cox <waywardgeek at gmail.com> wrote:
> On Fri, Oct 24, 2014 at 7:32 PM, David Leon Gil <coruus at gmail.com> wrote:
>> The current provable-security bounds on recovering from state
>> compromise require anywhere from 2KiB to 20 KiB of input entropy to
>> recover from "state compromise". See section 5.3 of
>> http://www.cs.nyu.edu/~dodis/ps/prematureNext.pdf
>> So, perhaps some applications would want a fairly large amount of entropy.

> However, I just went and looked a bit at random.c.  I would have to look a
> *lot* harder to feel confident I am reading it right, but at first glance,
> it's mixing function, _mix_pool_bytes does not satisfy my assumptions above.
> It does not appear to be a cryptographically secure hash function.  It
> simply stirs data in the pool weakly, counting on lots of entropy data to
> make that OK.

That's fully accurate. (In fact, an earlier paper by Dodis points out
that /dev/random is broken at present:
http://www.cs.nyu.edu/~dodis/ps/rng.pdf )

> This seems insecure to me, but I suppose there are probably reasons for the
> Linux kernel to weakly mix the input entropy rather than performing a secure
> hash.

No good reasons; OSX (and some BSDs?), for example, uses Schneier's
Fortuna RNG, which is cryptographically sensible.

> If I were writing that code, I'd turn Blake2b into a sponge (similar
> to Lyra2), and would only mix in entropy once I'd collected at least 256
> bits worth.  That way, the state becomes secure again on every update.

That would be better than what the Linux kernel is doing...

I believe that some folks are working on code to fix /dev/random, but
it's a fair amount of work to write / get merged.

> Can I use a simple hack to insure the Linux entropy is secure after every
> write to /dev/random?  I am thinking of force-feeding it 4096 bits from the
> Keccac sponge, rather than just 512 bits like I do now.  Is my reading of
> random.c's mixing accurate?  Will this hack insure that the entropy pool is
> securely refreshed?

Not sure.

More information about the cryptography mailing list