<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jun 28, 2017 at 3:36 PM, iang <span dir="ltr"><<a href="mailto:iang@iang.org" target="_blank">iang@iang.org</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
I would say precisely the reverse.  If you're a security expert you have a good chance in hell of doing a good PRNG.  If you're a user you have no chance.<br></blockquote><div><br></div><div>/dev/urandom is far too slow for something like OpenSSL. getrandom()/getentropy() are faster, but still slower than can be done in-process. While "use use /dev/urandom" is good advice, that's not a good trade-off imo for a project that is already heavily focused on cryptography.  </div><div><br></div><div>For example, If you're doing something like TLS1.1, and generating a random IV for every CBC record sent, then this is very significant. Or if you're doing a lot of ECDSA is another case.  There can also be quality issues with the implementations of /dev/urandom on some platforms; for example if you desire prediction resistance, not all /dev/urandom implementations provide it.</div><div><br></div><div>This was the motivation for including our own in-process DRBG in s2n. We want extreme performance, and also don't want to outsource so critical a part of our security model. In case it's useful, here's the design we use and some discussion on why:</div><div><br></div><div>In s2n, every every thread gets two RNGs: </div><div><br></div><div>  <a href="https://github.com/awslabs/s2n/blob/master/utils/s2n_random.c">https://github.com/awslabs/s2n/blob/master/utils/s2n_random.c</a></div><div><span style="color:rgb(36,41,46);font-family:SFMono-Regular,Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;white-space:pre"> </span><span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(111,66,193);font-family:SFMono-Regular,Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;white-space:pre">s2n_get_public_random_data()</span><br></div><div><font color="#6f42c1" face="SFMono-Regular, Consolas, Liberation Mono, Menlo, Courier, monospace"><span style="font-size:12px;white-space:pre"> </span></font><span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(111,66,193);font-family:SFMono-Regular,Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;white-space:pre">s2n_get_private_random_data()</span></div><div><br></div><div>under that slight veneer, each is a instantiation of a DRBG:</div><div><br></div><div>  <a href="https://github.com/awslabs/s2n/blob/master/crypto/s2n_drbg.c">https://github.com/awslabs/s2n/blob/master/crypto/s2n_drbg.c</a></div><div><br></div><div>The DRBG is AES_CTR DRBG from the NIST SP800-90A standard. Each is initially seeded from /dev/urandom, and then reseeded using RDRAND on each invocation, to provide prediction resistance. </div><div><br></div><div>To provide fork-safety, accesses to the DBRGs are guarded with a memory value that is zeroed on fork (we use pthreads_atfork, and <span style="color:rgb(36,41,46);font-family:SFMono-Regular,Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;white-space:pre">MAP_INHERIT_ZERO</span><span style="color:rgb(36,41,46);font-size:12px;white-space:pre"><font face="arial, helvetica, sans-serif"> to provide that guarantee). </font></span></div><div><span style="color:rgb(36,41,46);font-family:SFMono-Regular,Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;white-space:pre"><br></span></div><div><span style="color:rgb(36,41,46);font-size:12px;white-space:pre"><font face="arial, helvetica, sans-serif">Reasoning:</font></span></div><div><br></div><div><font color="#24292e" face="arial, helvetica, sans-serif"><span style="font-size:12px;white-space:pre"><b>Why AES_CTR DRBG?</b></span></font></div><div><span style="color:rgb(36,41,46);font-size:12px;white-space:pre"><font face="arial, helvetica, sans-serif">We focus heavily on testing in s2n, and so we had a very strong preference for using an algorithm that comes with test vectors and could formally verify. NIST 800-90 is a good place to start, but </font></span></div><div><span style="color:rgb(36,41,46);font-size:12px;white-space:pre"><font face="arial, helvetica, sans-serif">obviously there's the whole DUAL_EC debacle. </font></span></div><div><span style="color:rgb(36,41,46);font-size:12px;white-space:pre"><font face="arial, helvetica, sans-serif"><br></font></span></div><div><span style="color:rgb(36,41,46);font-size:12px;white-space:pre"><font face="arial, helvetica, sans-serif">In researching the basic foundation algorithms to use, I found these papers (and more) very helpful:</font></span></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><a href="https://pdfs.semanticscholar.org/136e/9214b3637a84b9accb32f7b6176f047c403a.pdf">https://pdfs.semanticscholar.org/136e/9214b3637a84b9accb32f7b6176f047c403a.pdf</a><br></font></div><div><font face="arial, helvetica, sans-serif"><a href="https://www.cs.cmu.edu/~kqy/resources/thesis.pdf">https://www.cs.cmu.edu/~kqy/resources/thesis.pdf</a><br></font></div><div><font face="arial, helvetica, sans-serif"><a href="https://eprint.iacr.org/2006/379.pdf">https://eprint.iacr.org/2006/379.pdf</a><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Reading those, and mailing list archives me, convinced me of the simplicity and security the HMAC and AES_CTR DRBGs, each being as secure as the primitive they use. I also was lucky enough to attend the HACS workshops at RWC, where we had working groups on RNGs each year. The conversations there were great and very helpful.  </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">My conclusion was that HMAC has some security edges on AES_CTR (My colleague Matt Campagna's paper is a good guide on that) ... but these turn out not to be relevant when using Prediction Resistance. So I went with AES_CTR, with PR, because it was measurably faster on our hosts (we have AES-NI and SHA acceleration). </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Having test vectors greatly increased my confidence in the correctness of the implementation, and they were easy to incorporate:</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><a href="https://github.com/awslabs/s2n/blob/master/tests/unit/s2n_drbg_test.c">https://github.com/awslabs/s2n/blob/master/tests/unit/s2n_drbg_test.c</a><font face="arial, helvetica, sans-serif"><br></font></div><div><br></div><div>the NIST spec also provides a declarative definition that we were able to translate into SAW and Cryptol easily:</div><div><br></div><div><a href="https://github.com/awslabs/s2n/tree/master/tests/saw/spec/DRBG">https://github.com/awslabs/s2n/tree/master/tests/saw/spec/DRBG</a><br></div><div><br></div><div>and so we now actually formally verify that the s2n DBRG code is equivalent to what's in the spec. Further increasing my confidence that we at least get that right.  I'm not aware of any /dev/urandom has a similar level of proof or confidence. </div><div><br></div><div>With the 800-90A AES_CTR, we mix in RDRAND on every invocation, making it unpredictable. More importantly though, this also greatly increases the amount of work that certain kinds of hardware backdoor (like a compromised CPU) would have to perform to produce a deterministic output. Such a backdoor would need to inspect the present state of the DRBG, run through AES, in order to predict the output that would be produced from a known RDRAND output.  That's a neat property, though obviously not a general defense against hardware backdoors (like just reading the output registers or memory). </div><div><br></div><div><b>Why two RNGs per-thread?</b></div><div>The worst kind of failure for an RNG is to expose secrets. Algorithmic weaknesses and implementation errors can lead to predictable or duplicate RNGs outputs. It's a total disaster if RNG output used in an IV (which is often public) compromises the RNG output used for a shared-secret.  So they are kept very separate, as a defense in depth. </div><div><br></div><div>The per-thread part is a performance consideration, to avoid locking. </div><div><br></div><div><div><font color="#24292e" face="arial, helvetica, sans-serif"><span style="font-size:12px;white-space:pre"><b>Anything else useful?</b></span></font></div><div><font color="#24292e" face="arial, helvetica, sans-serif"><span style="font-size:12px;white-space:pre">I like BoringSSLs approach too, which is based on ChaCha20 and RDRAND (or was when I looked), but didn't adopt it because there's no good spec to work a proof from, and performance was comparable for our use-case. </span></font></div></div><div><font color="#24292e" face="arial, helvetica, sans-serif"><span style="font-size:12px;white-space:pre"><br></span></font></div><div><font face="arial, helvetica, sans-serif"><font color="#24292e"><span style="font-size:12px;white-space:pre">In looking at other userspace RNGs, I did see that some use getpid() and getppid() as fork-safety guards. These provide some more protection, but do cost a little, and it turns out they aren't effective on Linux (libc can lie about getpid()) - so we don't include those. I wish Linux had </span></font><font color="#24292e"><span style="font-size:12px;white-space:pre">MAP_INHERIT_ZERO , to avoid pulling in pthreads. </span></font></font></div><div><font face="arial, helvetica, sans-serif"><font color="#24292e"><span style="font-size:12px;white-space:pre"><br></span></font></font></div><div><font face="arial, helvetica, sans-serif"><font color="#24292e"><span style="font-size:12px;white-space:pre">We do call /dev/urandom to seed initially, and found that EINTR can happen more than we expected. We ended up adding exponential backoffs (see s2n_random.c) to avoid tight spinning loops in some cases. Never would have predicted that happening. </span></font></font></div><div><br></div><div><br></div></div>-- <br><div class="gmail_signature">Colm</div>
</div></div>