[cryptography] Tossing randomness back in?

Marsh Ray marsh at extendedsubset.com
Tue Apr 19 00:55:29 EDT 2011


On 04/18/2011 09:26 PM, Sandy Harris wrote:
> In many situations, you have some sort of randomness pool
> and some cryptographic operations that require random
> numbers. One concern is whether there is enough entropy
> to support the usage.
>
> Is it useful to make the crypto throw something back
> into the pool? Of course this cannot replace real new
> entropy, but does it help?

_If_ one is doing everything fundamentally right in the CSRNG I think 
that it does not help.

> If you are doing IPsec with HMAC SHA-1, for example,

Then we should expect you to have sufficient entropy in the pool to make 
brute force impractical forever (say 128 bits) and for you to be 
extracting your random stream from it through an effective one-way function.

You do not need to decrement the entropy estimate of the pool as you 
generate random numbers from it. If you believe the entropy of the pool 
decreases as you generate output from it, then either your starting 
entropy was much too small or you don't believe in the one-way-ness of 
your extraction function.

In other words, /dev/random should be a symlink to /dev/urandom.

> SHA gives a 160-bit hash and it is truncated to 96 bits
> for the HMAC.
> Why not throw the other 64 bits into the
> pool?

The costs are:

   - Code complexity. More chance something could go wrong.

     This was pointed out today:
     https://twitter.com/bleidl/status/60111957818212352
     It looks to me like a bad bug in the code which decremented
     the entropy estimate that may have caused the pool to
     go largely unused altogether.

   - Performance.

The benefit is:

   ?   Very hard to quantify, except that it comes in proportion to
       the degree to which other very important parts of the system
       are broken.
       How much do you credit for these bits that you put back in?

> In other cases, you might construct something to
> derive data for the pool. You do not need a lot.
> Each keying operation uses a few hundred bits
> of randomness

I don't think that these bits of randomness are "consumed" in a 
well-constructed system.

IIRC, Peter Gutmann was using the term "computational entropy" to refer 
to the entropy seemingly generated within the hash function. But I don't 
think he was willing to go all the way to conclude that the pool entropy 
was nondecreasing.

I know that I'm probably disagreeing with an old textbook with this, but 
these recommendations do need to be re-evaluated from time to time.

Some things have quietly changed over the last few years:

* We know more about hash functions. MD5 is seriously busted but still 
no one has yet calculated even a second preimage. SHA-1 has one foot in 
the grave too, but has no published collisions. The only published 
attacks on SHA-2 don't seem serious enough to mention. The SHA-3 contest 
is more an attempt to improve flexibility and performance than a need to 
improve security over SHA-2.

* We learned to expect and rely on related-key and known-plaintext 
resistance from our block ciphers. We also must learn to rely on the 
fundamental properties of our hash functions. In constructions like 
HMAC, the attacker is presumed to know the plaintext and the resulting 
MAC. An insufficiency in the one-wayness of the underlying hash function 
threatens the key directly. So if your hash function is weak in that 
respect, then you probably have bigger problems.

* Computers are attacked in different ways now. The threats to a CSRNG 
on a virtual server in a cloud provider data center are much different 
than those of a barely-networked PC running PGP years ago. Once pwned, 
we can no longer trust the computer again until it has been completely 
reformatted, and perhaps even including the firmware. In the past we 
might have hoped that a self-reseeding PRNG could "recover" its 
security. But today most compromises seem to put the attacker in a 
position to inject malware into the running kernel code itself. There's 
no recovery from that.

* An attacker may be able to force the generation of output from the 
CSPRNG. What do you do when its entropy drops to zero? Block? Now the 
bad guy can easily DoS your apps and they will simply move to using some 
other non-blocking RNG.

Still your cloud server provider could disclose the contents of your 
virtual memory somehow, so periodic stirring (with a one-way function of 
course) and catastrophic reseeding could be useful. But the reseeding is 
only to help mitigate an uncontrolled state disclosure, not because the 
entropy in the pool has significantly depleted. Even if you did 
experience such a memory disclosure, you'd probably be more worried 
about the private and session keys that had been leaked directly.

I would love to hear about an example, but I don't think a 
well-constructed CSPRNG with even a 100 bit pool size has ever been 
compromised due to entropy-depletion effects.

Last I looked at OpenSSL, it's CSPRNG would accumulate 70 or so bytes of 
real entropy in its pool and generate an arbitrary amount of output from 
that.

- Marsh



More information about the cryptography mailing list