Analysis of a strong Random Number Generator

Almost all cryptographic protocols depend on random (unpredictable) values to create keys, cookies, tokens, initialisation vectors, and so on. The Linux (as well as other Unix flavours) kernel provides a character device as a source for randomness. This device represents the essential part needed by various cryptographic protocol implementations for a secure operation (conditional security), therefore it needs special attention from security experts.

This paper will give an extract of results taken from analysing the input sources used by Linux' PRNG implementation. The statistical entropy of each source and of the whole pool is calculated to get a better picture of the entropy quality during the boot--process and to spot entropy overestimation by the kernel. Observation taken by process show a repeating behaviour for different system startups. This can be used by an attacker to create profiles and to simulate a more complex system. Even observations of the events generated by the block-device show timing patterns between different boot--sequences. To dispel doubts of developers to add untrusted sources, two kinds of untrusted sources, low-quality and malicious source, were examined. It will be shown that low--quality sources are not able to reduce the entropy in the pool that already exists but can lead to an overestimation. A more dangerous situation exists with the presence of a malicious source which is theoretically able to led the mixing algorithm produce a stream of zeros.

The goal of this work is not to show a practical attack against the random device but to provide more transparency and to ease further analysis.