[Cryptography] The Crypto Pi

[ianG]

On 25/01/2015 14:27 pm, Ben Laurie wrote:
> On 18 January 2015 at 14:50, Ralf Senderek <crypto at senderek.ie> wrote:

>> But there is a problem with the randomness source on the beagle bone.
>> I've monitored the state of the kernel's entropy pool via /proc and
>> found that if you read 10 Bytes from /dev/random the entropy level
>> drops by 52 bits. A short time later reading another 10 Bytes the beagle
>> blocks for 54 seconds. Reading 20 bytes for the first time removes
>> 116 bit of entropy from the pool and the second read blocks for nearly
>> 70 seconds. The beagle bone needs 143 seconds to recover and to add
>> a 100 bits of entropy back to the pool. There's no rngd running.
>
> I'm not sure what "removing bits from the pool" really means -
> extracting n bits from a pool does not, IMO, remove n bits, or even
> any large fraction of n, from the pool.


It's interesting isn't it.  This whole entropy accounting idea seems to 
be an implausible base for computing, and as a practical matter, in our 
field of endeavour, isn't required.  The notion of cryptographic 
security is sufficient.

The notion that removing a bit also removes a bit of entropy appears to 
be a "bound" argument.  You can't "remove a bit of entropy."  It's 
clearly not entropy once you touch it, and because output is protected 
by hashes, etc, there is also no clear mathematical relationship between 
the entropy pool and the output of the RNG.

If a bit of entropy is touched or relied upon, then adding in another 
bit certainly overwhelms any reduction that might be imagined.  But 
because entropy is expensive this one-bit-equality leads to unreliable 
design (blocking), so it's a missed opportunity.

Meanwhile, from a security & attack perspective, there is a slightly 
more compelling argument that an attacker can copy the state at time N 
and roll it forward.  The "replace entropy after use" argument seems to 
mitigate that attack nicely.

All of this has led me to change the design around.  In my current RNG I 
don't keep a central pool at all, just a mixer that demands fresh 
entropy as required from all collectors.  The major rule then is that 
the collectors aren't allowed to block at all, and it this is a problem 
for them, they have to keep a pool, or return nix;  their choice.



iang



ps; talking about collecting entropy is fraught by definition.  We need 
a better language, but I guess we're stuck with it for now.  I like John 
Denker's version which is 'surprisal'.