[Cryptography] new PRNG family

Ray Dillinger bear at sonic.net
Fri Dec 5 14:30:32 EST 2014



On 12/04/2014 11:30 PM, Andreas Briese wrote:
> 

> i would like to put in my words, would you please indicate, if i am on the right track:
> 
> looking at one log map:
> 
> 1. the log map calc can have a number $nI$ of inputs that result in $nO$ outputs - need to assess both.

Yes.  Actually, for starters just see if you can do it for a single
state.  Can you find all the different states that could be *immediate*
predecessors of any single state?

For example, if I have an integer "generator" with one word of
state, and the transition function is S=S/2 + 6, when I know
that the current state is S=9, then I know that the immediate
prior state was either S=15 or S=16.

But because there can be at most one cycle that includes the
current state, I know that therefore at least one of these
prior states (and all of its prior states, etc) is unreachable
(ie, not on any cycle).

Indeed, the above is an unfair example because S=S/2 + 6 has
only a single one-element cycle - at 6.  So even the current
state, where S=9, is not reachable on any cycle.

This is a degenerate "generator" because we lose a whole bit of
information due to rounding, *every* iteration, from every
possible state, until we have zero bits of state left when we
get to the cycle S=6.

Most generators - especially FP generators -- that people come
up with have a similar problem, though not that bad a case of
it.  There is some theoretically huge number of possible states
as measured by bits devoted to representing state information,
but as the generator iterates forward, its path is gradually
constrained by rounding errors as information is lost, until
finally it settles into a cycle where it approaches each
potential branching point on the cycle from the same single
prior state every time.

Often this stable cycle is shorter, by a factor of billions
or more, than the designer of the generator expected, because
of all the bits that have been lost due to rounding.  So
the *effective* state of the generator measured as log2(number
of states on a stable cycle) is much less than the number
of bits devoted to *representing* state.

To figure out how many bits you lose due to rounding, you
need to get some idea of how much effective state your
generator has.  So follow a path forward through a few
hundred such decision points, then try to go backward
along paths that *could* have led to the state you've
reached, and see how far you get on average before hitting
dead ends -- that is, states that no possible prior state
could have produced.  You don't have to find them all,
but try to get enough for statistical sampling.

If you can go backward through, say, ten (2-way) decision
points on an average path before hitting a dead end, that
means that at least 2^10 of your states are unreachable for
every state that is reachable.  That would mean your
generator's effective amount of state, for purposes of
security, is at least 10 bits less than the number of bits
required to enumerate the valid starting points.

It would also mean that every possible key or starting state
has at least 2^10 alias keys or starting states whose output
will converge within a few hundred transitions, to the same
point on the same cycle.  And finally it would mean that
your generator's cycle is shorter by a factor of 2^10 than
you might have hoped.

The bad news is that it's common for generators that people
design on their own to lose literally hundreds of bits of
state before settling onto their cycles.

The good news is that if you lose only three or six or ten,
and you've managed to get all the reachable states on the
same cycle, you're doing way better than most people's first
attempt.

				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/20141205/61cb346e/attachment.sig>


More information about the cryptography mailing list