remove dangerously out-of-date Linux/haveged info
[ach-master.git] / src / theory / RNGs.tex
1 \section{Random Number Generators}
2 \label{section:RNGs}
3
4 % This section was authored by Ralf Schlatterbeck (Ralf Schlatterbeck <rsc@runtux.com>)
5
6 \epigraph{``The generation of random numbers is too important to be left to chance.''}{Robert R. Coveyou}
7
8
9 \begin{figure}[h]
10   \centering
11   \includegraphics[width=0.4\textwidth]{img/random_number.png}
12   \caption{xkcd, source: \url{https://imgs.xkcd.com/comics/random_number.png}, license: CC-BY-NC}
13   \label{fig:dilbertRNG}
14 \end{figure}
15
16
17
18 A good source of random numbers is essential for many crypto
19 operations. The key feature of a good random number generator is the
20 non-predictability of the generated numbers. This means that hardware
21 support for generating entropy is essential.
22
23
24 Hardware random number generators in operating systems or standalone
25 components collect entropy from various random events mostly by using
26 the (low bits of the) time an event occurs as an entropy source. The
27 entropy is merged into an entropy pool and in some implementations there
28 is some bookkeeping about the number of random bits available.
29
30 \subsection{When random number generators fail}
31
32 Random number generators can fail -- returning predictable non-random
33 numbers -- if not enough entropy is available when random numbers should
34 be generated.
35
36 This typically occurs for embedded devices and virtual machines.
37 Embedded devices lack some entropy sources other devices have, e.g.:
38
39 \begin{itemize*}
40   \item No persistent clock, so boot-time is not contributing to the
41     initial RNG state
42   \item No hard-disk: No entropy from hard-disk timing, no way to store
43     entropy between reboots
44 \end{itemize*}
45
46 Virtual machines emulate some hardware components so that the
47 generated entropy is over-estimated. The most critical component that
48 has been shown to return wrong results in an emulated environment is the
49 timing source~\cite{Eng11,POL11}.
50
51 Typically the most vulnerable time where low-entropy situations occur is
52 shortly after a reboot. Unfortunately many operating system installers
53 create cryptographic keys shortly after a reboot~\cite{HDWH12}.
54
55 Another problem is that OpenSSL seeds its internal random generator only
56 seldomly from the hardware random number generator of the operating
57 system. This can lead to situations where a daemon that is started at a
58 time when entropy is low keeps this low-entropy situation for hours
59 leading to predictable session keys~\cite{HDWH12}.
60
61 For systems where -- during the lifetime of the keys -- it is expected
62 that low-entropy situations occur, RSA keys should be preferred over DSA
63 keys: For DSA, if there is ever insufficient entropy at the time keys
64 are used for signing this may lead to repeated ephemeral keys. An
65 attacker who can guess an ephemeral private key used in such a signature
66 can compromise the DSA secret key.
67 For RSA this can lead to discovery of encrypted plaintext or forged
68 signatures but not to the compromise of the secret key~\cite{HDWH12}.