304 lines
8.3 KiB
HTML
304 lines
8.3 KiB
HTML
|
<HTML
|
|||
|
><HEAD
|
|||
|
><TITLE
|
|||
|
>Random Numbers</TITLE
|
|||
|
><META
|
|||
|
NAME="GENERATOR"
|
|||
|
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
|
|||
|
REL="HOME"
|
|||
|
TITLE="Secure Programming for Linux and Unix HOWTO"
|
|||
|
HREF="index.html"><LINK
|
|||
|
REL="UP"
|
|||
|
TITLE="Special Topics"
|
|||
|
HREF="special.html"><LINK
|
|||
|
REL="PREVIOUS"
|
|||
|
TITLE="Authenticating on the Web"
|
|||
|
HREF="web-authentication.html"><LINK
|
|||
|
REL="NEXT"
|
|||
|
TITLE="Specially Protect Secrets (Passwords and Keys) in User Memory"
|
|||
|
HREF="protect-secrets.html"></HEAD
|
|||
|
><BODY
|
|||
|
CLASS="SECT1"
|
|||
|
BGCOLOR="#FFFFFF"
|
|||
|
TEXT="#000000"
|
|||
|
LINK="#0000FF"
|
|||
|
VLINK="#840084"
|
|||
|
ALINK="#0000FF"
|
|||
|
><DIV
|
|||
|
CLASS="NAVHEADER"
|
|||
|
><TABLE
|
|||
|
SUMMARY="Header navigation table"
|
|||
|
WIDTH="100%"
|
|||
|
BORDER="0"
|
|||
|
CELLPADDING="0"
|
|||
|
CELLSPACING="0"
|
|||
|
><TR
|
|||
|
><TH
|
|||
|
COLSPAN="3"
|
|||
|
ALIGN="center"
|
|||
|
>Secure Programming for Linux and Unix HOWTO</TH
|
|||
|
></TR
|
|||
|
><TR
|
|||
|
><TD
|
|||
|
WIDTH="10%"
|
|||
|
ALIGN="left"
|
|||
|
VALIGN="bottom"
|
|||
|
><A
|
|||
|
HREF="web-authentication.html"
|
|||
|
ACCESSKEY="P"
|
|||
|
>Prev</A
|
|||
|
></TD
|
|||
|
><TD
|
|||
|
WIDTH="80%"
|
|||
|
ALIGN="center"
|
|||
|
VALIGN="bottom"
|
|||
|
>Chapter 11. Special Topics</TD
|
|||
|
><TD
|
|||
|
WIDTH="10%"
|
|||
|
ALIGN="right"
|
|||
|
VALIGN="bottom"
|
|||
|
><A
|
|||
|
HREF="protect-secrets.html"
|
|||
|
ACCESSKEY="N"
|
|||
|
>Next</A
|
|||
|
></TD
|
|||
|
></TR
|
|||
|
></TABLE
|
|||
|
><HR
|
|||
|
ALIGN="LEFT"
|
|||
|
WIDTH="100%"></DIV
|
|||
|
><DIV
|
|||
|
CLASS="SECT1"
|
|||
|
><H1
|
|||
|
CLASS="SECT1"
|
|||
|
><A
|
|||
|
NAME="RANDOM-NUMBERS"
|
|||
|
></A
|
|||
|
>11.3. Random Numbers</H1
|
|||
|
><P
|
|||
|
>In many cases secure programs must generate ``random'' numbers that
|
|||
|
cannot be guessed by an adversary.
|
|||
|
Examples include session keys, public or private keys, symmetric keys,
|
|||
|
nonces and IVs used in many protocols, salts, and so on.
|
|||
|
Ideally, you should use a truly random source of data for random numbers,
|
|||
|
such as values based on
|
|||
|
radioactive decay (through precise timing of Geiger counter
|
|||
|
clicks), atmospheric noise, or thermal noise in electrical circuits.
|
|||
|
Some computers have a hardware component that functions as
|
|||
|
a real random value generator, and if it's available you should use it.</P
|
|||
|
><P
|
|||
|
>However, most computers don't have hardware that generates truly
|
|||
|
random values, so in most cases you need a way to generate random numbers
|
|||
|
that is sufficiently random that an adversary can't predict it.
|
|||
|
In general, this means that you'll need three things:
|
|||
|
<P
|
|||
|
></P
|
|||
|
><UL
|
|||
|
><LI
|
|||
|
><P
|
|||
|
>An ``unguessable'' state; typically this is done by measuring
|
|||
|
variances in timing of low-level devices
|
|||
|
(keystrokes, disk drive arm jitter, etc.)
|
|||
|
in a way that an adversary cannot control.</P
|
|||
|
></LI
|
|||
|
><LI
|
|||
|
><P
|
|||
|
>A cryptographically strong pseudo-random number generator (PRNG), which
|
|||
|
uses the state to generate ``random'' numbers.</P
|
|||
|
></LI
|
|||
|
><LI
|
|||
|
><P
|
|||
|
>A large number of bits (in both the seed and the resulting value used).
|
|||
|
There's no point in having a strong PRNG if you only have a few possible values,
|
|||
|
because this makes it easy for an attacker to use brute force attacks.
|
|||
|
The number of bits necessary varies depending on the circumstance, however,
|
|||
|
since these are often used as cryptographic keys, the normal rules of
|
|||
|
thumb for keys apply.
|
|||
|
For a symmetric key (result), I'd use at least 112 bits (3DES), 128 bits is
|
|||
|
a little better, and 160 bits or more is even safer.</P
|
|||
|
></LI
|
|||
|
></UL
|
|||
|
>
|
|||
|
Typically the PRNG uses the state to generate some values, and then
|
|||
|
some of its values and other unguessable inputs are used to update the state.
|
|||
|
There are lots of ways to attack these systems.
|
|||
|
For example, if an attacker can control or view inputs to the state
|
|||
|
(or parts of it), the attacker may be able
|
|||
|
to determine your supposedly ``random'' number.</P
|
|||
|
><P
|
|||
|
>A real danger with PRNGs is that most computer language libraries include
|
|||
|
a large set of pseudo-random number generators (PRNGs)
|
|||
|
which are <EM
|
|||
|
>inappropriate</EM
|
|||
|
> for security purposes.
|
|||
|
Let me say it again:
|
|||
|
<EM
|
|||
|
>do not use typical random number generators for security
|
|||
|
purposes</EM
|
|||
|
>.
|
|||
|
Typical library PRNGs
|
|||
|
are intended for use in simulations, games, and so on; they are
|
|||
|
<EM
|
|||
|
>not</EM
|
|||
|
> sufficiently random for use
|
|||
|
in security functions such as key generation.
|
|||
|
Most non-cryptographic
|
|||
|
library PRNGs are some variation of ``linear congruential generators'',
|
|||
|
where the ``next'' random value is computed as "(aX+b)<29>mod<6F>m"
|
|||
|
(where X is the previous value).
|
|||
|
Good linear congruential generators are fast and have useful statistical
|
|||
|
properties, making them appropriate for their intended uses.
|
|||
|
The problem with such PRNGs is that future values can be easily deduced
|
|||
|
by an attacker (though they may appear random).
|
|||
|
Other algorithms for generating random numbers quickly, such as
|
|||
|
quadratic generators and cubic generators, have also been broken
|
|||
|
[Schneier 1996].
|
|||
|
In short, you have to use cryptographically strong PRNGs to
|
|||
|
generate random numbers in secure applications - ordinary random number
|
|||
|
libraries are not sufficient.</P
|
|||
|
><P
|
|||
|
>Failing to correctly generate truly random values for keys has caused
|
|||
|
a number of problems, including holes in Kerberos,
|
|||
|
the X window system, and NFS [Venema 1996].</P
|
|||
|
><P
|
|||
|
>If possible, you should use system services
|
|||
|
(typically provided by the operating system) that are expressly designed
|
|||
|
to create cryptographically secure random values.
|
|||
|
For example,
|
|||
|
the Linux kernel (since 1.3.30) includes a random number generator, which
|
|||
|
is sufficient for many security purposes.
|
|||
|
This random number generator gathers environmental noise
|
|||
|
from device drivers and other sources into an entropy pool.
|
|||
|
When accessed as /dev/random, random bytes are only returned
|
|||
|
within the estimated number of bits of noise in the entropy pool
|
|||
|
(when the entropy pool is empty, the call blocks until additional
|
|||
|
environmental noise is gathered).
|
|||
|
When accessed as /dev/urandom, as many bytes as are requested are
|
|||
|
returned even when the entropy pool is exhausted.
|
|||
|
If you are using the random values for cryptographic purposes (e.g.,
|
|||
|
to generate a key) on Linux, use /dev/random.
|
|||
|
*BSD systems also include /dev/random.
|
|||
|
Solaris users with the SUNWski package also have /dev/random.
|
|||
|
Note that if a hardware random number generator is available and its
|
|||
|
driver is installed, it will be used instead.
|
|||
|
More information is available in the system documentation random(4).</P
|
|||
|
><P
|
|||
|
>On other systems, you'll need to find another way to get truly random results.
|
|||
|
One possibility for other Unix-like systems
|
|||
|
is the Entropy Gathering Daemon (EGD), which monitors system
|
|||
|
activity and hashes it into random values; you can get it at
|
|||
|
<A
|
|||
|
HREF="http://www.lothar.com/tech/crypto"
|
|||
|
TARGET="_top"
|
|||
|
>http://www.lothar.com/tech/crypto</A
|
|||
|
>.
|
|||
|
You might consider using a
|
|||
|
cryptographic hash functions (e.g., SHA-1) on PRNG outputs.
|
|||
|
By using a hash algorithm, even if the PRNG turns out to be guessable,
|
|||
|
this means that the attacker must now also break the hash function.</P
|
|||
|
><P
|
|||
|
>If you have to implement a strong PRNG yourself,
|
|||
|
a good choice for a cryptographically strong (and patent-unencumbered)
|
|||
|
PRNG is the Yarrow algorithm; you can learn more about Yarrow from
|
|||
|
<A
|
|||
|
HREF="http://www.counterpane.com/yarrow.html"
|
|||
|
TARGET="_top"
|
|||
|
>http://www.counterpane.com/yarrow.html</A
|
|||
|
>.
|
|||
|
Some other PRNGs can be useful, but many widely-used ones
|
|||
|
have known weaknesses that may or may not matter depending on your application.
|
|||
|
Before implementing a PRNG yourself, consult the literature, such as
|
|||
|
[Kelsey 1998] and [McGraw 2000a].
|
|||
|
You should also examine
|
|||
|
<A
|
|||
|
HREF="http://www.ietf.org/rfc/rfc1750.txt"
|
|||
|
TARGET="_top"
|
|||
|
>IETF RFC 1750</A
|
|||
|
>.
|
|||
|
NIST has some useful information; see the
|
|||
|
<A
|
|||
|
HREF="http://csrc.nist.gov/publications/nistpubs/800-22/sp-800-22-051501.pdf"
|
|||
|
TARGET="_top"
|
|||
|
>NIST publication 800-22</A
|
|||
|
> and
|
|||
|
<A
|
|||
|
HREF="http://csrc.nist.gov/publications/nistpubs/800-22/errata-sheet.pdf"
|
|||
|
TARGET="_top"
|
|||
|
>NIST errata</A
|
|||
|
>.
|
|||
|
You should know about the
|
|||
|
<A
|
|||
|
HREF="http://stat.fsu.edu/~geo/diehard.html"
|
|||
|
TARGET="_top"
|
|||
|
>diehard tests</A
|
|||
|
> too.
|
|||
|
You might want to examine
|
|||
|
the paper titled
|
|||
|
"how Intel checked its PRNG", but unfortunately that paper appears to be
|
|||
|
unavailable now.</P
|
|||
|
></DIV
|
|||
|
><DIV
|
|||
|
CLASS="NAVFOOTER"
|
|||
|
><HR
|
|||
|
ALIGN="LEFT"
|
|||
|
WIDTH="100%"><TABLE
|
|||
|
SUMMARY="Footer navigation table"
|
|||
|
WIDTH="100%"
|
|||
|
BORDER="0"
|
|||
|
CELLPADDING="0"
|
|||
|
CELLSPACING="0"
|
|||
|
><TR
|
|||
|
><TD
|
|||
|
WIDTH="33%"
|
|||
|
ALIGN="left"
|
|||
|
VALIGN="top"
|
|||
|
><A
|
|||
|
HREF="web-authentication.html"
|
|||
|
ACCESSKEY="P"
|
|||
|
>Prev</A
|
|||
|
></TD
|
|||
|
><TD
|
|||
|
WIDTH="34%"
|
|||
|
ALIGN="center"
|
|||
|
VALIGN="top"
|
|||
|
><A
|
|||
|
HREF="index.html"
|
|||
|
ACCESSKEY="H"
|
|||
|
>Home</A
|
|||
|
></TD
|
|||
|
><TD
|
|||
|
WIDTH="33%"
|
|||
|
ALIGN="right"
|
|||
|
VALIGN="top"
|
|||
|
><A
|
|||
|
HREF="protect-secrets.html"
|
|||
|
ACCESSKEY="N"
|
|||
|
>Next</A
|
|||
|
></TD
|
|||
|
></TR
|
|||
|
><TR
|
|||
|
><TD
|
|||
|
WIDTH="33%"
|
|||
|
ALIGN="left"
|
|||
|
VALIGN="top"
|
|||
|
>Authenticating on the Web</TD
|
|||
|
><TD
|
|||
|
WIDTH="34%"
|
|||
|
ALIGN="center"
|
|||
|
VALIGN="top"
|
|||
|
><A
|
|||
|
HREF="special.html"
|
|||
|
ACCESSKEY="U"
|
|||
|
>Up</A
|
|||
|
></TD
|
|||
|
><TD
|
|||
|
WIDTH="33%"
|
|||
|
ALIGN="right"
|
|||
|
VALIGN="top"
|
|||
|
>Specially Protect Secrets (Passwords and Keys) in User Memory</TD
|
|||
|
></TR
|
|||
|
></TABLE
|
|||
|
></DIV
|
|||
|
></BODY
|
|||
|
></HTML
|
|||
|
>
|