Re: Good enough for crypto?

In article <[EMAIL PROTECTED]>,
Scott Wilber <[EMAIL PROTECTED]> wrote:
>As I mentioned near the beginning of this thread, I will answer any
>and all questions as clearly and completely as possible.
[much valuable detail snipped]

Thanks very much for that description. The
combination of the filtering LFSR and the
decimation should, indeed, ensure that the
sequence is sufficiently random for all purposes.

Is the decimation rate "user selectable" in any
sense? One of my nightmares is the user who just
wants to get a slightly higher bit rate and so
disables the decimation... Note that there must be
*some* decimation, otherwise an adversary who sees
all the output bits gets to do attacks based on
the autocorrelation you mentioned. Of course this
doesn't matter if the entropy rate is exactly 1,
but I doubt that this ideal is obtainable in
practice... there will always be an epsilon.

>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.

It's possible that I missed your descriptions in
other posts; sometimes our newsfeed is flaky and
I've been travelling. Anyway, thanks, that was
adequate for my purposes.

>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.

If you mentioned this decimation before and I
missed it, I apologise. Anyway, this was the first
I heard of it.

>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

Another important characteristic that you seem to
have missed is that these intervals should also
form a Full Positive Difference Set, also known as
a Golomb Ruler. As it happens, because you've
chosen large differences, you've managed that. See
Anderson's paper on "searching for the optimum
correlation attack" and subsequent work by Jovan
Golic.

>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.

Ahh, yes, but it's easy to fool diehard. As a
cryptographer, though, given the right 5 of the
previous 181 output bits, I would be able to
predict the next bit with 99% probability. This is
why some decimation is essential.

>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.

Yup. Thanks. See above for my question about
"setting".

Again, thanks for being forthcoming with the
details.

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au