minor formatting of a footnote: { } was missing
[ach-master.git] / src / 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 A good source of random numbers is essential for many crypto
7 operations. The key feature of a good random number generator is the
8 non-predictability of the generated numbers. This means that hardware
9 support for generating entropy is essential.
10
11 \todo{Other architectures, BSD, Windows?}
12
13 Hardware random number generators in operating systems or standalone
14 components collect entropy from various random events mostly by using
15 the (low bit of the) time an event occurs as a entropy source. The
16 entropy is merged into an entropy pool and in some implementations there
17 is some bookkeeping about the number of random bits available.
18
19 \subsection{When random number generators fail}
20
21 Random number generators can fail -- returning predictable non-random
22 numbers -- if not enough entropy is available when random numbers should
23 be generated.
24
25 This typically occurs for embedded devices and virtual machines.
26 Embedded devices lack some entropy sources other devices have, e.g.:
27
28 \begin{itemize}
29 \item No persistent clock, so boot-time is not contributing to the
30     initial RNG state
31 \item No hard-disk: No entropy from hard-disk timing, no way to store
32     entropy between reboots
33 \end{itemize}
34
35 Virtual machines emulate some hardware components so that the
36 generated entropy is over-estimated. The most critical component that
37 has been shown to return wrong results in an emulated environment is the
38 timing
39 source\footnote{\url{http://jakob.engbloms.se/archives/1374},\url{https://polarssl.org/tech-updates/security-advisories/polarssl-security-advisory-2011-02}}.
40
41 Typically the most vulnerable time where low-entropy situations occur is
42 shortly after a reboot. Unfortunately many operating system installers
43 create cryptographic keys shortly after a
44 reboot\footnote{\url{https://factorable.net/weakkeys12.extended.pdf}}.
45
46 Another problem is that OpenSSL seeds its internal random generator only
47 seldomly from the hardware random number generator of the operating
48 system. This can lead to situations where a daemon that is started at a
49 time when entropy is low keeps this low-entropy situation for hours
50 leading to predictable session
51 keys\footnote{\url{https://factorable.net/weakkeys12.extended.pdf}}.
52
53 \subsection{Linux}
54
55 On Linux there are two devices that return random bytes when read, the
56 \verb+/dev/random+ can block until sufficient entropy has been collected
57 while \verb+/dev/urandom+ will not block and return whatever (possibly
58 insufficient) entropy has been collected so far.
59
60 Unfortunately most crypto implementations are using \verb+/dev/urandom+
61 and can produce predictable random numbers if not enough entropy has
62 been
63 collected\footnote{\url{https://factorable.net/weakkeys12.extended.pdf}}.
64
65 Linux supports the injection of additional entropy into the entropy pool
66 via the device \verb+/dev/random+. On the one hand this is used for
67 keeping entropy across reboots by storing output of /dev/random into a
68 file before shutdown and re-injecting the contents during the boot
69 process. On the other hand this can be used for running a secondary
70 entropy collector to inject entropy into the kernel entropy pool.
71
72 \subsection{Recommendations}
73
74 To avoid situations where a newly deployed server hasn't enough
75 entropy it is recommended to generate keys (e.g. for SSL or SSH) on
76 a system with enough entropy available and transfer the generated keys
77 to the server.  This is especially advisable for small embedded devices
78 or virtual machines.
79
80 For embedded devices and virtual machines deploying additional userspace
81 software that generates entropy and feeds this to kernel entropy pool
82 (e.g. by writing to \verb+/dev/random+ on Linux) is recommended. Note
83 that only a process run as root can update the entropy counters in the
84 kernel, each non-root user-process can feed entropy to the pool but
85 cannot update the
86 counters\footnote{\url{https://en.wikipedia.org/wiki/dev/random}}.
87
88 For Linux the \verb+haveged+
89 implementation\footnote{\url{http://www.issihosts.com/haveged/}} based on the
90 HAVEGE\footnote{\url{http://www.irisa.fr/caps/projects/hipsor/scripts/down.php?id=13781296\&ext=.pdf}}
91 strong random number generator currently looks like the best choice. It
92 can feed its generated entropy into the kernel entropy pool and recently
93 has grown a mechanism to monitor the quality of generated random
94 numbers\footnote{\url{http://www.issihosts.com/haveged/ais31.html}}. The
95 memory footprint may be too high for small embedded devices, though.
96
97 For systems where -- during the lifetime of the keys -- it is expected
98 that low-entropy situations occur, RSA keys should be preferred over DSA
99 keys: For DSA, if there is ever insufficient entropy at the time keys
100 are used for signing this may lead to repeated ephemeral keys. An
101 attacker who can guess an ephemeral private key used in such a signature
102 can compromise the DSA secret key.
103 For RSA this can lead to discovery of encrypted plaintext or forged
104 signatures but not to the compromise of the secret
105 key\footnote{\url{https://factorable.net/weakkeys12.extended.pdf}}.