[Libre-soc-dev] [OpenPOWER-HDL-Cores] microwatt grows up LCA2021

[Paul Mackerras]

On Mon, Feb 08, 2021 at 10:42:16AM +0000, Luke Kenneth Casson Leighton wrote:
> On Saturday, February 6, 2021, Paul Mackerras <paulus at ozlabs.org> wrote:
> > On Sun, Jan 31, 2021 at 01:08:18PM +0000, Luke Kenneth Casson Leighton
> wrote:
> >> (context of link: analysis process for testing RNGs)
> >> https://github.com/betrusted-io/betrusted-soc/issues/13
> >>
> >> paul the last question asked, about the RNG, slapped wrist for saying it
> >> can be trusted to be secure! :)
> >
> > I took the question as a practical question, and as far as I recall I
> > didn't say anything absolute or theoretical.
> 
> i apologise, my literal-minded Asperger's jumped in with "eek!".  this does
> however highlight the possibility that someone might take your word for it,
> with obvious detrimental implications i won't outline.  that was my main
> concern.
> 
> >> mathematically, nobody can give guarantees (ever), in a nutshell the only
> >> thing you can say 100% is, "no nightmare scenario has occurred... so
> far".
> >
> > That's all you can say about any crypto system.  I personally would
> > rather trust an FPGA that I have programmed myself
> 
> ah now if you'd said that, i would not have freaked out :)  it's the
> addition of "i personally" that makes it an opinion, rather than a
> categorical-sounding (authoritative-sounding) "yes" that had me concerned.

Fair enough.  What I said probably came out a little different from
what I meant to say, given that I was answering a question off the
cuff.

> > and where the logic
> > is simple enough that it is highly unlikely that any
> > maliciously-introduced correlation could be present, than the HWRNG in
> > as ASIC where I have no idea what's really producing the numbers.
> 
> absolutely.  this is the exact same logic that had people backing Betrusted.
> 
> 
> >> ... but nobody, not ever, can make a categorical statement, "this
> >> cryptographic algorithm is secure".
> >
> > So, therefore you can never use any cryptographic device?
> 
> as you're no doubt aware, it's always an arms race.
> 
> every year either the creative intelligence increases or the brute-force
> resources increases.  either eliminates previously "secure" algorithms
> that, up until that point, everybody "knew" they were secure.
> 
> > All I said
> > about the microwatt RNG is that it would be reasonable to use it for
> > cryptography, and that still seems true to me.  I have run dieharder
> > for days on it without seeing any concerning results.
> 
> ah brilliant: that's critically important to add to the README / docs, and
> to future talks.  implication being:
> 
>   "don't take my word for it: here's the results of statistical tests"
> 
> i would actually really like to see those results.  and particularly STS
> ones.  link to STS source code at end of betrusted soc bug 13, above URL.
> 
> > If you know any
> > other good randomness tests, I could run them too.
> 
> CSRC NIST.gov's STS.  except do not bother with the Lempel-Zive test
> because it is flawed.  i explain why in the link betrusted-soc.
> 
> it's very important to run STS on both runs of 100,000 and on runs of
> 1,000,000.

Thanks for the pointer.  I have downloaded the tests and I'll compile
them up and run them on microwatt.

> also i recommend "ramping up", running the shorter quicker tests first,
> then the longer quicker tests, then the shorter longer tests and finally
> the ones that take several days.
> 
> any failure, any "weakness", *must* be viewed as catastrophic.
> 
> i cannot overemphasise how important that is.
> 
> btw one very important thing, it may be worthwhile to coordinate with
> Bunnie Huang regarding the FAILURE runs here:
> 
> https://github.com/betrusted-io/betrusted-wiki/wiki/TRNG-characterization
> 
> the marsaglia tests in particular have me concerned, they fail twice.

That's an interesting page.  The thing that stood out for me is that
he says his ring oscillators run at only 200 - 300 MHz.  The paper I
was working from showed oscilloscope traces from plumbing some of the
XOR outputs out to pins of the FPGA, from which it is clear that they
are oscillating at at least 500 - 1000 Mhz, though the limited output
pin bandwidth means you don't see all of the transitions.  I think I
will try plumbing out some bits to pins and looking at them with my
oscilloscope.

> the other thing is that, not having studied the dieharder source code, i do
> not know if it does tests-of-tests-of-tests.

I don't think it does statistics over all of the tests.  I thought
there were some tests that did statistics over the results from a
number of individual tests.

> STS does this: a histogram of p-values, followed by a p-value on that
> histogram.
> 
> the test-of-test-of-tests is absolutely essential to make sure that even
> the tests themselves do not have nonuniform (or uniform) suspicious
> characteristics.
> 
> example: if two runs produce identical output, the p-values look ok, right?
> so what's the problem, surely the p-value giving a PASS is ok, right?

That didn't happen with Microwatt's RNG.  In fact, occasionally a
result would show up as "weak", but then the same test run again would
usually give a different, stronger result.

> given the identical duplicated output this conclusion is obviously wrong
> but dieharder IN NO WAY noticed it - and that's where the histogram of
> p-values kicks in.  STS can be asked to run *thousands* of 100,000 bit
> tests, creating the required histograms of p-values in order to find these
> subtle flaws.

Well, in dieharder's defence, identical output would be what you would
expect for a PRNG with a given seed value.

> looking just at that output of dieharder i would say it is unlikely to be
> doing this and consequently is an inadequate test.
> 
> Cryptographic Statistical testing is REALLY complex and i bought 8 machines
> to run tests *non-stop* for six months when i was developing algorithms.
> 
> this is where i developed the incremental techniques so as to not waste
> time on week-long runs, only to find that a much shorter test only a few
> minutes long would have told me exactly the same information (failure).
> 
> again apologies for jumping up and down, i hope this gives you some insight
> into the rabbithole of cryptographic statistical testing that could easily
> suck away many months of your life in order to get a properly independently
> trustable answer.

Thanks for the detailed answer and the pointer to the STS tests.  I'll
post some results when I get them.

Paul.