<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Nov 12, 2014 at 2:21 PM, Jerry Leichter <span dir="ltr"><<a href="mailto:leichter@lrw.com" target="_blank">leichter@lrw.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">On Nov 12, 2014, at 12:45 PM, Bill Cox <<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>> wrote:<br><div><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><font color="#000000">...</font>However, a small correlation is OK.  We can just subtract any measurable correlation from the estimated entropy per source.</div></div></div></div></blockquote>It's not so simple.  Correlation and entropy in an active attack environment don't play well.</div><div><br></div><div>Suppose you had source R1.  I use R1 delayed by one bit as a second source R2.  Any correlation between R1 and R2 is an autocorrelation at length 1 of R1 with itself - one of the things we would presumably check for to begin with, and it's something even fairly simple RNG's would be expected to attain.  And yet if someone learns either R1 or R2, there is no randomness left.  Also, the combined entropy had better be exactly that of R1 (or R2) or we could bootstrap arbitrarily high entropy out of any source by simply combining itself with itself at different lags.  (Note that what I'm suggesting outputs bits at the same rate as R1.  If you actually used two successive bits of R1 to generate one bit of output, you would have gained entropy per output bit.)</div><div><br></div><div>This is one of those situations (common in tests for RNG's) where if we *find* something (correlation), we know the RNG is bad; but if we fail to find it, we haven't really learned anything.</div><span class="HOEnZb"><font color="#888888"><div><div>                                                        -- Jerry</div><div><br><br></div></div></font></span></div></blockquote><div><br></div><div>This certainly is true for CPRNGs, where finding any correlation is deadly to the algorithm.  However, SFAIK, there is no such thing as a hardware RNG that generates data that is undetectably non-random.  There are always correlations.  They all require "whitening" before the data can be used for crypto.  Some of the less impressive TRNGs whiten before you can see the data, without giving you access to the raw data from the entropy source.  This destroys any chance of verifiability.<br><br></div><div>There are many ways to do whitening.  For example, I used to use the parity of 80 sequential bits from a zener noise based RNG as the output, and that passed the old diehard tests.  However, I wasted most of the entropy in whitening.  A better solution would is to try and get a good estimate of the entropy, and compress it just enough through a cryptographic sponge to get it where it needs to be.<br><br></div><div>Some TRNGs, like Turbid, have provable levels of average entropy output.  That's helpful in whitening.  The Turbid paper showed that you don't need to compress entropy much through the sponge to have undetectable levels of non-randomness.  It's pretty cool.<br></div></div><br>Bill<br></div></div>