[147709] in cryptography@c2.net mail archive
Re: [Cryptography] /dev/random is not robust
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Thu Oct 17 13:59:26 2013
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <526018F0.9040802@borg.org>
Date: Thu, 17 Oct 2013 13:53:11 -0400
To: Kent Borg <kentborg@borg.org>
Cc: tytso@mit.edu, cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============1522197149293583540==
Content-Type: multipart/alternative; boundary="Apple-Mail=_646C7EFE-047F-4EC7-8EAC-20216C998CF9"
--Apple-Mail=_646C7EFE-047F-4EC7-8EAC-20216C998CF9
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=us-ascii
On Oct 17, 2013, at 1:05 PM, Kent Borg <kentborg@borg.org> wrote:
> But is this something that /dev/urandom might do better? Should =
blocking be added to /dev/urandom immediately after boot until some =
reasonable threshold has been reached at least once? Or on first boot =
are common distributions restoring a bad seed file and /dev/random can't =
tell? Arrgh, I am starting to think that the RNG is the wrong place to =
fix it.
>=20
> Should RNGs attempt to detect uninitialized states and refuse to run?
One answer to this question appears in the FIPS standards for RNG's. At =
times, they've required a continuous on-line test of the numbers being =
generated, with automatic shutdown if the test fail. These requirements =
almost certainly came from the hardware background of the FIPS =
standards. For hardware, certain failure modes - stuck at 0/stuck at 1 =
are the most obvious; short cycles due to some internal oscillation may =
be another - are extremely common, and worth checking for. For =
software-based deterministic PRNG's, such tests are mainly irrelevant - =
code doesn't develop such failures in the field. As the FIPS standards =
were adjusted for a more software-based world, the requirement for =
on-line testing was dropped.
Looking through some old messages on the subject here on the =
Cryptography list, I found one from Francois Grieu back in July of 2010:
> The Smart Card industry uses True RNG a lot. There, a common line of
> thought is to use:
> - a hardware RNG, which raw output (perhaps biased) is directly
> accessible for testing purposes (only), so that the software can check
> it in depth at startup and from time to time to ascertain that it is =
at
> least generating a fair amount of entropy
> - followed by appropriate post-processing in hardware (so as to gather
> entropy at all time), acting as a mixer/debiaser:; e.g. something =
LFSR-based
> - followed by a crude software test (e.g. no bit stuck)
> - optionally followed by software postprocessing (the subject is
> debated; this software has to be proven to not include weakness, and =
the
> hardware + crude software test is certified to eliminate such =
weakness,
> so why bother, some say)
>=20
> There is a standard, known as AIS31, on evaluating True RNG, which
> de-facto enforces the first three steps
> =
<https://www.bsi.bund.de/cae/servlet/contentblob/478130/publicationFile/30=
270/ais31e_pdf.pdf>
> which references
> =
<https://www.bsi.bund.de/cae/servlet/contentblob/478152/publicationFile/30=
275/ais20e_pdf.pdf>
More recently, David Johnston, who I gather was involved in the design =
of the Intel on-chip RNG, commented in a response to a question about =
malfunctions going undetected:
> That's what BIST is for. It's a FIPS and SP800-90 requirement.
Of course, with generators like the Linux /dev/random, we're in some =
intermediate state, with hardware components that could fail feeding =
data into software components.
My own view on this is that there's no point in testing the output of a =
deterministic PRNG, but the moment you start getting information from =
the outside world, you should be validating it. You can never prove =
that a data stream is random, but you can cheaply spot some common kinds =
of deviation from randomness - and if you're in a position to "pay" more =
(in computation/memory) you can spot many others. You have no hope of =
spotting a sophisticated *attack*, and even spotting code bugs that =
destroy randomness can be hard, but it's hard to come up with an example =
of an actual real-world hardware failure that would slip through. So =
you might as well do the testing.
-- Jerry
--Apple-Mail=_646C7EFE-047F-4EC7-8EAC-20216C998CF9
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=us-ascii
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><div><div>On Oct 17, 2013, at 1:05 PM, Kent Borg <<a =
href=3D"mailto:kentborg@borg.org">kentborg@borg.org</a>> =
wrote:</div><blockquote type=3D"cite">But is this something that =
/dev/urandom might do better? Should blocking be added to =
/dev/urandom immediately after boot until some reasonable threshold has =
been reached at least once? Or on first boot are common =
distributions restoring a bad seed file and /dev/random can't tell? =
Arrgh, I am starting to think that the RNG is the wrong place to =
fix it.<br><br>Should RNGs attempt to detect uninitialized states and =
refuse to run?<br></blockquote></div>One answer to this question appears =
in the FIPS standards for RNG's. At times, they've required a =
continuous on-line test of the numbers being generated, with automatic =
shutdown if the test fail. These requirements almost certainly =
came from the hardware background of the FIPS standards. For =
hardware, certain failure modes - stuck at 0/stuck at 1 are the most =
obvious; short cycles due to some internal oscillation may be another - =
are extremely common, and worth checking for. For software-based =
deterministic PRNG's, such tests are mainly irrelevant - code doesn't =
develop such failures in the field. As the FIPS standards were =
adjusted for a more software-based world, the requirement for on-line =
testing was dropped.<div><br></div><div>Looking through some old =
messages on the subject here on the Cryptography list, I found one from =
Francois Grieu back in July of =
2010:</div><div><br></div><div><blockquote type=3D"cite"><span =
style=3D"font-family: monospace; ">The Smart Card industry uses True RNG =
a lot. There, a common line of</span><br style=3D"font-family: =
monospace; "><span style=3D"font-family: monospace; ">thought is to =
use:</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">- a hardware RNG, which raw output =
(perhaps biased) is directly</span><br style=3D"font-family: monospace; =
"><span style=3D"font-family: monospace; ">accessible for testing =
purposes (only), so that the software can check</span><br =
style=3D"font-family: monospace; "><span style=3D"font-family: =
monospace; ">it in depth at startup and from time to time to ascertain =
that it is at</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">least generating a fair amount of =
entropy</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">- followed by appropriate =
post-processing in hardware (so as to gather</span><br =
style=3D"font-family: monospace; "><span style=3D"font-family: =
monospace; ">entropy at all time), acting as a mixer/debiaser:; e.g. =
something LFSR-based</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">- followed by a crude software test =
(e.g. no bit stuck)</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">- optionally followed by software =
postprocessing (the subject is</span><br style=3D"font-family: =
monospace; "><span style=3D"font-family: monospace; ">debated; this =
software has to be proven to not include weakness, and the</span><br =
style=3D"font-family: monospace; "><span style=3D"font-family: =
monospace; ">hardware + crude software test is certified to eliminate =
such weakness,</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">so why bother, some say)</span><br =
style=3D"font-family: monospace; "><br style=3D"font-family: monospace; =
"><span style=3D"font-family: monospace; ">There is a standard, known as =
AIS31, on evaluating True RNG, which</span><br style=3D"font-family: =
monospace; "><span style=3D"font-family: monospace; ">de-facto enforces =
the first three steps</span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; "><</span><a =
href=3D"https://www.bsi.bund.de/cae/servlet/contentblob/478130/publication=
File/30270/ais31e_pdf.pdf" style=3D"font-family: monospace; =
">https://www.bsi.bund.de/cae/servlet/contentblob/478130/publicationFile/3=
0270/ais31e_pdf.pdf</a><span style=3D"font-family: monospace; =
">></span><br style=3D"font-family: monospace; "><span =
style=3D"font-family: monospace; ">which references</span><br =
style=3D"font-family: monospace; "><span style=3D"font-family: =
monospace; "><</span><a =
href=3D"https://www.bsi.bund.de/cae/servlet/contentblob/478152/publication=
File/30275/ais20e_pdf.pdf" style=3D"font-family: monospace; =
">https://www.bsi.bund.de/cae/servlet/contentblob/478152/publicationFile/3=
0275/ais20e_pdf.pdf</a><span style=3D"font-family: monospace; =
">></span></blockquote><br></div><div>More recently, David Johnston, =
who I gather was involved in the design of the Intel on-chip RNG, =
commented in a response to a question about malfunctions going =
undetected:</div><div><br></div><div><blockquote type=3D"cite"><span =
style=3D"font-family: monospace; ">That's what BIST is for. It's a FIPS =
and SP800-90 requirement.</span><br style=3D"font-family: monospace; =
"></blockquote></div><div><br></div><div>Of course, with generators like =
the Linux /dev/random, we're in some intermediate state, with hardware =
components that could fail feeding data into software =
components.</div><div><br></div><div>My own view on this is that there's =
no point in testing the output of a deterministic PRNG, but the moment =
you start getting information from the outside world, you should be =
validating it. You can never prove that a data stream is random, =
but you can cheaply spot some common kinds of deviation from randomness =
- and if you're in a position to "pay" more (in computation/memory) you =
can spot many others. You have no hope of spotting a sophisticated =
*attack*, and even spotting code bugs that destroy randomness can be =
hard, but it's hard to come up with an example of an actual real-world =
hardware failure that would slip through. So you might as well do =
the testing.</div><div><br></div><div><div> =
=
=
-- =
Jerry</div></div><div><br></div></body></html>=
--Apple-Mail=_646C7EFE-047F-4EC7-8EAC-20216C998CF9--
--===============1522197149293583540==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============1522197149293583540==--
