GnuPG PRNG insecure?
dres at cs.tu-berlin.de
Thu Feb 7 20:11:01 CET 2002
Recently, out of curiosity, I looked at GnuPG's random number
generation and stumbled across something I think is problematic.
However, I'm not a cryptographer, nor do I have in-depth knowledge
on cryptographic secure pseudo random number generation.
That's why I ask people here to comment on this.
So read this with care; any or all of the things presented herein
may be totally wrong.
The problematic line that gave me headaches is in add_randomness()
in random.c, where the random noise gathered by the (system
dependant) different random code (rndlinux.c rndegd.c rndw32.c ..)
is added to our random pool:
rndpool[pool_writepos++] = *p++;
The problem I see with this is, that previous data in our random
pool is simply overwritten with new data. If our gathered data is
already random in a cryptographically secure sense, this is not a
problem per se. However, on non /dev/random systems such as win32
the system dependent random gather code simply puts much more "random"
noise (gathered from lots of different sources of varying quality)
into our pool, in the hope that the random pool code handles this
correctly (like whitening the buffer via use of a hash function etc.).
To further express this, imagine that the system-x random gatherer
is asked to add x bytes of random data into our pool. The gatherer
"decides" that to satisfy this demand he has to put out 2*POOLSIZE
of random noise containing not-that-much entropy. After POOLSIZE bytes
have been written, the code in random.c correctly whitens the buffer
using RIPEMD160. However, the next POOLSIZE bytes of random data (of
questionable quality) *overwrite* anything that was in the pool before,
destroying the valuable accumulated entropy.
(The worst case would be these last POOLSIZE bytes being all zeros.)
This depends on the quality of the environmental noise gatherer used,
but theoretically keys generated with GnuPG on systems lacking a good
random source are at risk.
As said, I'm not that experienced with PRNGs etc, but I think this
would do just fine:
rndpool[pool_writepos++] ^= *p++;
This will also harden the PRNG against attacks on systems which *do*
have a good random source (such as linux).
Furthermore, already collected entropy is not simply thrown away
(even if "used"), instead it is kept in full, still it is impossible
to guess the current state of the pool based on the previous one
(without knowledge of the actual random data). In short: this should
always increase the PRNGs quality.
Please Cc any replies, as I'm not subscribed.
Stefan Keller <dres at cs.tu-berlin.de>
More information about the Gnupg-devel