Re: Good enough for crypto?

> 
> For the record, I said that there might be
> cryptographic problems with using LFSRs for
> filtering. Since details of your filtering system
> are not forthcoming, I'm not able to say, one way
> or the other, whether there are such problems or
> not. But adding a couple of gates to make it
> nonlinear certainly couldn't hurt.

As I mentioned near the beginning of this thread, I will answer any
and all questions as clearly and completely as possible.  We intend to
keep nothing secret, unlike many companies like VIA or M-Systems that
make extreme claims about their "true" random bit rates but do not
reveal exactly how they obtain such extraordinary amounts of entropy. 
As a note, we were commissioned to analyze the theoretical entropy
source for the Intel TRNG - the only company that did reveal
sufficient technical detail to do so - and we determined their random
bit-rate claims are well founded; even conservative.

The exact structure of our "stirring" function has been posted in two
or three messages in this thread, but for convenience I will reiterate
with additional details.  If this is not adequate, I will post the
source code.

First let me say that there are two purposes for the stirring
function.  The first is to "correct" the slight defects in the
statistical properties that occur in any non-deterministic RNG.  These
arise from autocorrelation, which is a function of the transfer
function of the entropy source and all the electronics that transform
the measurement into a binary bit; and from inevitable biases in the
measurement and drift in the electronics.

The second is to take an input sequence of bits that has an average
entropy/bit < 1.0 and produce an output sequence that has entropy ~
1.0/bit.  This can only be accomplished by reducing the number of
output bits by at least (1.0-H) times the number of input bits.

Without respect to entropy content, the statistical properties are
corrected in the following way:  A serial shift register is programmed
with taps at certain intervals.  The lengths of the intervals must be
relatively prime, and for greatest effect, 2 is excluded from any
factor of interval length.  The total length of the register is
naturally the sum of all the intervals.  There is no limit to the
number of intervals nor, therefore to the total register length.  We
generally use about 5 intervals with a total length of around 200.  An
example is 29, 31, 37, 41 and 43 for a total of 181.  The bits from
each of these taps are all XOred together with a bit from the input
sequence.  The resultant bit is taken as a bit in the output sequence
and it is then also shifted into the shift register.  The corrector is
self-seeding in that the beginning state is not important and will
typically be all 0's.  The corrector is initialized by passing through
it a true random sequence of length at least 5 times the shift
register length before any output bits are taken.

The basic theory of the corrector is that when any two (or more)
sequences are XOred together, the statistical properties of the
resultant sequence are at least as good, and usually better than, the
properties of the better (statistically) of the original sequences. 
The statistical properties of the sequence produced by the XOr
function and fed back into the shift register are bootstrapped to
exceedingly high quality by the continously recursive nature of the
corrector.  Since this is also the output sequence, its statistical
properties are equally good.  This statistical corrector works so well
that an input sequence that is biased to .99/.01 will output a
sequence that will easily pass DIEHARD tests.

The second purpose of producing an output sequence with statistical
entropy approaching 1.0 is accomplished simply by decimating the bits,
that are taken as part of the output sequence, by an appropriate
amount.  All other functions of the corrector continue for each input
bit, but some of the output bits are discarded.  If, for example, the
average entropy/bit of the input sequence were 0.6, only every second
XOr output bit would be used in the output sequence.  In this way,
approximately 1.2 bits of entropy would be consumed to produce each
output bit.  Of course, a more conservative approach would be to take
every fourth bit, thus consuming 2.4 bits of entropy for each output
bit.  Setting the output bit-rate for the generator readily allows
this choice.

Describing the exact theoretical details of how entropy is distributed
between partially correlated and/or biased bits when they are mixed
and decimated is a little beyond the scope of this thread.  It is also
beyond the stated purpose of describing the stirring function used in
the ComScire PCQNG TRNG.  For the purpose of this description when I
refer to entropy in a sequence or bit, I use the term as it is
typically used, not in the more precise way that I have mentioned in
this thread.

 
> What I didn't say was that your system as a whole
> wasn't just fine. As far as I can tell, it will
> deliver plenty of good random bits for any
> application. But that isn't what I or the other
> commenters have been commenting upon. We've been
> trying to point out that keeping the precise
> details secret does not enhance your reputation in
> this community. That buzzwords like "infinitely
> recursive linear feedback shift registers" and
> especially "paranormal" lead to skepticism.

We generally would not use the word "paranormal," but we do not shy
away from mentioning experiments relating to affecting true random
sequences by directed intention.  Several of our generators are in use
at universities doing research on the subject.  In any case, this
certainly does not taint the quality of our generators being used for
other, more mainstream applications.

By the way, "infinitely recursive" was coined from infinite impulse
response (IIR) digital filters, which have an analogous property.  I
do agree that perhaps "continuously recursive" is more correct.

> 
> Anyway, you have a successful product, and to
> some extent deservedly so, so feel free to ignore
> my suggestion. I'll cope.
> 
> Greg.

I am sincere about revealing everything to the best of my ability.  If
I have left something out, just let me know.  I do want to point out
that this is not the usual policy for most companies that have spent a
lot of money and time developing products that are challenging, and
where the competition keeps most of their inner workings secret while
making unsupportable, exaggerated claims.

With regard,

Scott