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{http://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 \subsection{Linux}
  62
  63 \todo{Other architectures, BSD, Windows?}
  64
  65 On Linux there are two devices that return random bytes when read; the
  66 \verb+/dev/random+ can block until sufficient entropy has been collected
  67 while \verb+/dev/urandom+ will not block and return whatever (possibly
  68 insufficient) entropy has been collected so far.
  69
  70 Unfortunately most crypto implementations are using \verb+/dev/urandom+
  71 and can produce predictable random numbers if not enough entropy has
  72 been collected\cite{HDWH12}.
  73
  74 Linux supports the injection of additional entropy into the entropy pool
  75 via the device \verb+/dev/random+. On the one hand this is used for
  76 keeping entropy across reboots by storing output of /dev/random into a
  77 file before shutdown and re-injecting the contents during the boot
  78 process. On the other hand this can be used for running a secondary
  79 entropy collector to inject entropy into the kernel entropy pool.
  80
  81 %% specifics for libraries
  82 %% Openssl uses /dev/urandom. See the paper: https://factorable.net/weakkeys12.conference.pdf (section 5.2)
  83 %% What about other libs?
  84 %% What about other OSes?
  85
  86
  87 \subsection{Recommendations}
  88
  89 To avoid situations where a newly deployed server doesn't have enough
  90 entropy it is recommended to generate keys (e.g. for SSL or SSH) on
  91 a system with a sufficient amount of entropy available and transfer the generated keys
  92 to the server.  This is especially advisable for small embedded devices
  93 or virtual machines.
  94
  95 For embedded devices and virtual machines deploying additional userspace
  96 software that generates entropy and feeds this to kernel entropy pool
  97 (e.g. by writing to \verb+/dev/random+ on Linux) is recommended. Note
  98 that only a process with root rights can update the entropy counters in the
  99 kernel; non-root or user processes can still feed entropy to the pool but
 100 cannot update the counters\cite{Wikipedia:/dev/random}.
 101
 102 For Linux the \verb+haveged+
 103 implementation\cite{HAV13a} based on the HAVEGE\cite{SS03}
 104 strong random number generator currently looks like the best choice. It
 105 can feed its generated entropy into the kernel entropy pool and recently
 106 has grown a mechanism to monitor the quality of generated random
 107 numbers\cite{HAV13b}. The memory footprint may be too high for small
 108 embedded devices, though.
 109
 110 For systems where -- during the lifetime of the keys -- it is expected
 111 that low-entropy situations occur, RSA keys should be preferred over DSA
 112 keys: For DSA, if there is ever insufficient entropy at the time keys
 113 are used for signing this may lead to repeated ephemeral keys. An
 114 attacker who can guess an ephemeral private key used in such a signature
 115 can compromise the DSA secret key.
 116 For RSA this can lead to discovery of encrypted plaintext or forged
 117 signatures but not to the compromise of the secret key\cite{HDWH12}.