/dev/random and linux security issues (kinda long)

[aluminumsulfate at earthlink.net]

Greetings,

I just discovered something VERY DISTURBING about /dev/{u,}random in
Linux....  Despite what the man page for urandom says, the data from
/dev/random is REALLY not very random at all.  Many googleable pages
on entropy gathering will tell you what the man page says: that
/dev/random will block until the kernel has enough entropy to return
data.  THIS IS FALSE!!!  FALSE FALSE!

Data retrieved from /dev/random (and /dev/urandom, for that matter)
show *very* uneven digit distributions when displayed in base 95.  I
was doing this to generate crypto keys and noticed (yes, visually!)
that the keys conspicuously lacked entropy.  If you can tell a key
isn't random by just looking at it... well, you'd be better off
banging your head against the keyboard and recording the
keystrokes....  Anyway, the data obtained /dev/{u,}random devices
SHOULD NOT be used for cryptographic purposes.

But, unfortunately, that's not the worst of it.  To add hopelessness
to lies, there doesn't appear to be ANY mechanism, built into Linux,
to harvest entropy from your kernel!  There are some userspace
entropy-gathering daemons, and lots of PRNGs under /lib, but nothing
that harvests entropy from network/disk/timer interrupts/etc.  Is it
just me or does that mean the kernel (and, more generally, GNU/Linux)
are missing some *seriously important* functionality?!!

One depressing implication of this is that most crypto software (i.e.
GPG, SSL, etc.) are relying, in fact, on cryptoinsecure entropy
sources!  So, all those keys and certificates we've published might
not be as secure as we thought....

I found this problem on kernel 2.4.20.  If you want to see if this
problem exists on your machine, I've included some (rather short) perl
scripts at the end of this message.  Feel free to check my code. (I've
gone through examples using bc and gotten the same results, so I don't
think there are any errors in my math.)

On a related note, the use of cryptographic filesystems was mentioned
(in another thread) as a possible way to prevent intruders from
modifying files (e.g. rootkit checkers) on a compromised host.  This
is not completely accurate.  It is possible for an attacker to modify
an encrypted filesystem in useful ways without posessing the key.
Filesystems encrypted in CBC mode (the kernel default) are vulnerable
to this kind of attack, which is a result of various mathy things
involved in CBC mode encryption.  Using some form of EPCFB mode cipher
may prevent this kind of attack.  But, AFAIK, there is no (working)
way to use that kind of cipher in kernelspace.  So, even CBC-encrypted
filesystems on a compromised host cannot be trusted.

Here comes the code...

<---cut here--->
#!/usr/bin/perl

# read MSB-first 8-bit bytes from STDIN and print its value as a decimal integer
use bignum;

$bits = 8;
while (read STDIN,$bite,1) {
	$val = $val * (1<<$bits);
	$val += ord $bite;
}
print "$val\n" if ($val ne "");

<---cut here--->
#!/usr/bin/perl

# read a decimal integer from STDIN and return its value, in base 95, on stdout
# this uses the printable ASCII characters, in order, as the digits of base 95
# input and output are both MSDF

use bignum;

$line = <>;
$line =~ /^([0-9]+)/;
$dec = "$1"; # quotes NECESSARY

$base = 95;
while ($dec) {
 $digit = $dec % $base;
 # this int is necessary because BigInt tries to be too smart
 $dec = int($dec / $base);
 $result = chr($digit + 32) . "$result";
}

# /me thinks BigInt may have some coercion bugs in it...
print "$result\n" if ($dec eq "0");

<---cut here--->