[Cryptech Tech] FIPS 140-2 test program

[Benedikt Stockebrand]

Hi Stephan and list,

I think we really have to sort out what I meant with "model":

Stephan Mueller <smueller at chronox.de> writes:

>>> - Shannon Entropy formula
>>
>>I'm not sure I really understand what they mean with that term, so I'm
>>not going to comment on this one right now.
>
> See http://en.wikipedia.org/wiki/Shannon_entropy -- the formula in the 
> definition section

I was afraid that's what was meant, but the underlying model here is
that the bits are generated independently (by flipping coins in the
textbooks).  That doesn't have to apply to an actual HWRNG/TRNG.

The easiest way to fool this is by using a discrete difference (or sum)
on the function, i.e. replace  x = (x_0,...x_(n-1)) 
with x' = (x_0 XOR x_1, x_1 XOR x_2, ... x_(n-2) XOR x_(n-1)).

If x is truly random, then so is x'.  But if x isn't then the test may
behave significantly different on inputs x and x'

>>> - Chi-Square Test
>>> - mean calculation
>>> - Simulation
>>
>>These tests all take an entirely arbitrary aspect and check for that
>>aspect only.  Fair enough, but why are these tests of any value?  Why
>>are they "better" than a test "Is a quote from the works of Shakespeare
>>encoded in EBCDIC"?  They are arbitrary, and as such only useful if
>>the underlying model matches the source of the data.
>
> That is the key here: there are NO tests you can make that *shows* you 
> have entropy. All you can do is make statistical tests to more and more 
> conclude your noise source *may* have entropy.

I didn't say that they "show" anything, but maybe I did some sloppy
wording somewhere.  Anyway, if you hypothetically applied all the
(enumerably infinite) possible tests, all inputs, and as such all
sources, are getting tested the same; the key is to choose "suitable"
tests for whatever source, and "suitability" depends on the way the
source works, i.e. it should model the way it works.

That's the problem with the finite selection of blackbox tests used in
all the general test suites.  They of course do have an implicit model
on which that selection is based, but this isn't generally made
explicit; even if it was, it wouldn't necessarily have to match the
source I want to test output from; if it isn't, then this becomes a
rather tedious excercise in reverse engineering ("reverse mathing"???)
of the underlying model.

>>With the chi square test for example: What is so special about an 8 bit
>>word size, statistically speaking?  Why not use a 65517 bit word size
>>instead?
>
> There is nothing about it. The word size however should correlate with 
> the blocksize of your RNG. If you generate 8 bits at a time, you apply 8 
> bits. If you generate 17 bits at one time, you apply 17 bits. [...]

Again, that's what I mean with "model".  Problem here is that ent and
such use 8 bits not because of the way the RNG under test works, but
because it's convenient to implement.

>>that?  And should it be big or little endian, which may make a huge
>>difference on the result of the test?
>
> The endianess matters little, because you look for patterns. If you have 
> patterns, you have them regardless how you look at your bits (big or 
> little endian).

Yes, but endianness is critical in such that the result of the test
depends heavily on it when it comes to some patterns.

>> [Dart target simulation]
>
> I am fine with your statement. Yet, the goal is to identify patterns. 
> Thus, such simulation thing at least helped me once to identify patterns 
> where all other calculations showed that there were none.

Sure, if the model behind that simulation somehow related to the source
of the data you wanted to test, that's fine.  And thanks to Occam's
razor that actually kind of works surprisingly often.

However, the closer we can model the test to the way the source works,
or is supposed to work, the more reliable the tests derived from it will
be.

> Again, all testing just wants to look for patterns. If you take the 
> output from a cipher with a known key, you *will* receive a 
> *patternless* data stream and all statistical tests will show thumbs up.

Well, not the tests that happen to do a decryption first.

> But then I go back to my initial statement: entropy is relative.

Sure!  Question is: What does it mean to us when we build a HWRNG?

> If you do not know that you used Shakespare + DES+ known key, the bit
> stream *looks* like white noise to you and you would assume it
> contains entropy (at least it is entropic to *you*). But somebody else
> with the foreknowledge on how the bit stream is generated does not
> consider it to contain entropy.

Exactly, and now we can apply that to the construction of a HWRNG: 

First we start with a noise source of some sort, and figure out the
properties of the output it generates.  When I chose the avalanche
effect in a reverse biased PN junction, I knew that entropy becomes
visible at the output when the junction enters (or leaves) breakdown
state, while everything else is rather deterministic; so that lead me to
the approach of measuring time between rising edges rather than doing
some fixed-interval sampling, to ensure that with every noise bit I get
I do get some entropy.  On the other hand, if I used a different noise
source this might not work (I guess it should work with a ring
oscillator, though).

Next step is to test the entire construction using statistical tests.
With the avalanche effect, the failure modes that I came up with made
the bitstream either slow down or stop entirely, so this design is kind
of failsafe (unless we start to worry about intentional manipulations,
which is an issue we have to address fundamentally differently).  With
the ring oscillator however, the situation here should be significantly
different, because these may actually fluctuate by the amount of jitter
they generate.

Again, is it getting clear what I mean with "model" here?

> No, it is not weird at all! Your point is very good to illustrate the 
> limitations of all "entropy test applications": it is not possible to 
> test entropy.

Right, but it is possible to probabilistically test a source of entropy
by passing its output through tests that have been derived from the
model of its inner workings.  Which is what we really need.


Cheers,

    Benedikt

-- 
Benedikt Stockebrand,                   Stepladder IT Training+Consulting
Dipl.-Inform.                           http://www.stepladder-it.com/

          Business Grade IPv6 --- Consulting, Training, Projects

BIVBlog---Benedikt's IT Video Blog: http://www.stepladder-it.com/bivblog/