Security

On entropy and randomness

Linux random number generation (RNG) is often a source of confusion to developers, but it is also a very integral part of the security of the system. It provides random data to generate cryptographic keys, TCP sequence numbers, and the like, so unpredictability as well as very strong random numbers are required. When someone notices a flaw, or a possible flaw in the RNG, kernel hackers take notice.

Recurring universally unique identifiers (UUIDs), as reported by the smolt hardware profiler client program, had some worried about problems in the kernel RNG. As it turns out, the problem exists in the interaction between Fedora 8 LiveCD installations and smolt – essentially the UUID came from the CD – but it sparked a discussion leading to some possible improvements. Along the way, some common misconceptions about kernel RNG were cleared up.

The kernel gathers information from external sources to provide input to its entropy pool. This pool contains bits that have extremely strong random properties, so long as unpredictable events (inter-keypress timings, mouse movements, disk interrupts, etc.) are sampled. It provides direct access to this pool via the /dev/random device. Reading from that device will provide the strongest random numbers that Linux can offer – depleting the entropy pool. When the entropy pool runs low, reads to /dev/random block until there is sufficient entropy.

The alternative interface, the one that nearly all programs should use, is /dev/urandom. Reading from that device will not block. If sufficient entropy is available, it will provide random numbers just as strong as /dev/random, if not, it uses the SHA cryptographic hash algorithm to generate very strong random numbers. Developers often overestimate how strong their random numbers need to be; they also overestimate how easy "breaking" /dev/urandom would be, which leads to programs that, unnecessarily, read /dev/random. Ted Ts'o, who wrote the kernel RNG, puts it this way:

There is still a bit of hole in all of this: how does a freshly installed system, with little or no user interaction, at least yet, get its initial entropy? When Alan Cox and Mike McGrath started describing the smolt problem, the immediate reaction was to look closely at how the entropy pool was being initialized. While that turned out not to be the problem, it did lead Matt Mackall, maintainer of the kernel RNG, to start thinking about better pool initialization. Various ideas about mixing in data specific to the host, like MAC address and PCI device characteristics were discussed.

As Ts'o points out, that will help prevent things like UUID collisions, but it doesn't solve the problem of predictability of the random numbers that will be generated by these systems.

Linux provides random numbers suitable for nearly any purpose via /dev/urandom. For the truly paranoid, there is also /dev/random, but developers would do well to forget that device exists for everything but the most critical needs. If one is generating a large key pair, to use for the next century, using some data from /dev/random is probably right. Anything with lower requirements should seriously consider /dev/urandom.

Comments (28 posted)

autofs: insecure default configuration

Comments (none posted)

e2fsprogs: integer overflows

Comments (none posted)

emacs: buffer overflow

Comments (none posted)

emul-linux-x86-qtlibs: arbitrary code execution

Comments (none posted)

firebird: arbitrary code execution

Comments (none posted)

heimdal: insufficient memory allocation

Comments (1 posted)

libnfsidmap: possible privilege escalation

Comments (none posted)

MySQL: privilege escalation

Comments (none posted)

nagios: cross-site scripting

Comments (none posted)

phpMyAdmin: information disclosure

Comments (none posted)

ruby-gnome2: format string vulnerability

Comments (none posted)

samba: stack-based buffer overflow

Comments (none posted)

xorg-x11-xfs: arbitrary code execution

Comments (none posted)

zabbix: privilege escalation

Comments (none posted)