Re: Entropy Pool Contents

[Kyle Moffett <mrmacman_g4@mac.com>]

On Nov 27, 2006, at 15:40:16, David Wagner wrote:
> Phillip Susi  wrote:
> > David Wagner wrote:
> > > Nope, I don't think so.  If they could, that would be a security  
> > > hole, but /dev/{,u}random was designed to try to make this  
> > > impossible, assuming the cryptographic algorithms are secure.

Actually, our current /dev/random implementation is secure even if  
the cryptographic algorithms can be broken under traditional  
circumstances.  Essentially /dev/random will refuse to output any  
more data well before enough could be revealed to predict the current  
pool state, such that it is fairly secure even in the event of total  
failure of the cryptographic primatives.

> > > After all, some of the entropy sources come from untrusted  
> > > sources and could be manipulated by an external adversary who  
> > > doesn't have any account on your machine (root or non-root), so  
> > > the scheme has to be secure against introduction of maliciously  
> > > chosen samples in any event.

The way the /dev/random pool works is that writes are always  
guaranteed to add entropy to the pool (or at least never remove it),  
even if someone runs "dd if=/dev/zero of=/dev/random".  The initial  
state for any given write is secure, and when hashing a random value  
for which a significant part of the state has not even been  
theoretically revealed with a known value, the result is still  
random.  Even beyond that, the random pool also hashes the current  
value of the cycle-counter or time of day into the pool with each  
call, adding a bit of extra entropy in any case.  The same hashing of  
the time of day also occurs on reads.

> > Assuming it works because it would be a bug if it didn't is a  
> > logical fallacy.  Either the new entropy pool is guaranteed to be  
> > improved by injecting data or it isn't.  If it is, then only root  
> > should be allowed  to inject data.  If it isn't, then the entropy  
> > estimate should increase when the pool is stirred.

Well, actually the entropy pool is guaranteed not to lose entropy  
when it is stirred with data, but the whole point is to ensure that  
no userspace program *ever* has enough knowledge of the state of the  
pool to even begin a theoretical attack against past or future random  
values.  As a result it is perfectly OK for programs to dump whatever  
data they want into the random pool as extra security for _itself_,  
but the kernel does not trust it as extra security for itself.  Only  
root may inject guaranteed entropy and even then only using a  
specific ioctl, but any program may stir up the entropy pool however  
much it likes.

> I am satisfied that it is safe to feed in entropy samples from  
> malicious sources, as long as you don't bump up the entropy counter  
> when you do so.  Doing so can't do any harm, and cannot reduce the  
> entropy in the pool.  However, there is no guarantee that it will  
> increase the entropy.  If the adversary knows what bytes you are  
> feeding into the pool, then it doesn't increase the entropy count,  
> and the entropy estimate should not be increased.

Exactly.

> Note that, in any event, the vast majority of applications should  
> be using /dev/urandom (not /dev/random!), so in an ideal world,  
> most of these issues should be pretty much irrelevant to the vast  
> majority of applications.  Sadly, in practice many applications  
> wrongly use /dev/random when they really should be using /dev/ 
> urandom, either out of ignorance, or because of serious flaws in  
> the /dev/random man page.

Precisely.  Personally I generate my random passwords using a little  
perl script reading from /dev/random (as opposed to /dev/urandom) but  
that's more due to personal paranoia than any practical reason.

When generating long-term cryptographic private keys, however, you  
*should* use /dev/random as it provides better guarantees about  
theoretical randomness security than does /dev/urandom.  Such  
guarantees are useful when the random data will be used as a  
fundamental cornerstone of data security for a server or network  
(think your root CA certificate or HTTPS certificate for your million- 
dollar-per-year web store).

Cheers,
Kyle Moffett

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/