[Cryptography] Construction of cryptographic software.

[Ray Dillinger]

On 12/02/2014 03:41 PM, Paul Grubbs wrote:
> It would be awesome if you could add this to
> https://cryptocoding.net/index.php/Cryptography_Coding_Standard ! I'm sure
> they'd really appreciate your contribution.


Thank you both for that pointer.  I wasn't aware that it existed.

I observe that they say don't use the Mersenne Twister.  My response
is don't use it for a secure generator because it's not.  However, it is
an excellent source of bytes to mask with the output of a secure
deterministic sequence generator (the sort of thing that's used for a
stream cipher).  Not because it will make a secure PRNG any less
predictable, but because of the mathematical property that it provably
generates every possible output sequence 19937 bits long or less.

MT - or the LFSG it's based on, skipping MT's trivially reversible
output scrambling function as a feature that consumes CPU energy while
adding no security, sequentially generates every last bit pattern of
that length or less.  So, sooner or later, masking bytes from it will
match up with your secure PRNG to produce absolutely every output that
length or less.

This is a little bit important, because many SPRNGs have not very
much state, and a generator with not very much state will have much
shorter unproduceable sequences.

As an example, Rivest's new pseudorandom generator, Spritz (which is an
update of RC4) has a 256-element permutation, plus 3 bytes of state.  A
256 element permutation is about 1683-and-a-fraction bits of state
(because 2^1683 < 256! < 2^1684) and adding 24 more for the bytes gives
us 1707 bits.  So because it has only 1707 bits of state, it can only
start in 2^1707 different states, and there are provably sequences a
minimum of 1707 bits long that it absolutely cannot produce, because
math.  Because it is a CSPRNG, and must keep at least half its state
hidden from attackers, it's a good bet though I can't prove it, that
there are shorter sequences that it cannot produce, if its states are
distributed over several "orbits" or cycles.

Mask it with the output of an LFSG that has exactly one cycle and
provably goes through every permutation of its possible states on one
orbit, like the Mersenne twister, and suddenly, without losing the
security or nonlinearity of the SPRNG, you jump from sequences of no
more and probably considerably less than 1707 bits length being
impossible, and having it be very difficult to genuinely know exactly
how long the sequences that can't be produced are, to EVERY sequence of
19937 bits or less guaranteed to be a possible output.

This doesn't only matter if the CSPRNG eventually gets sufficiently
broken that an adversary can *TELL* which sequences of outputs are
impossible and use that information to attack a system.  It matters when
we consider the security of a set of 4096-bit keys for an asymmetric
crypto system.  If all the keys were generated by a CPRNG like Spritz,
and I know that there are only 2^1707 possible states that Spritz can
start in, then there are 2^1707, not 2^4096, possible output sequences
that could have been considered as key candidates.  With most of those
being eliminated by prime search or whatever, the field can be a lot
thinner than the 2^4096 would lead you to believe, and the odds of
collisions, birthday paradoxes, etc and the effect of those things on
security, have to be realistically adjusted.

				Bear


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141202/af58d250/attachment.sig>