[Cryptography] new PRNG family

[Ray Dillinger]

Well, I don't mean to be dismissive, but rounding means information loss
from your generator, and every time you lose information from
your generator you get a halfbit closer to being in a known state.

To put it another way, your generator will gravitate fairly quickly
onto cycles where there is no rounding at all (more precisely onto
cycles where the rounding happens in the same direction every time
through the cycle).

Every possible state leads into one of those cycles, but only some
of your states are actually *ON* one of those cycles.

That means an adversary looking at a stream of output doesn't have
to consider most of the states your generator could be in.  If he
assumes it's in one of the states that is on a cycle, he'll be right
unless your machine happens to be on one of its first few hundred outputs.

So the question becomes, how much of your state is useless for purposes
of security?  There is a way to at least guess.  If every state has
exactly one successor, but some states have multiple predecessors,
then you have at least as many states with no possible predecessors.
Those are "leaf nodes" in a state diagram, and you have to find a
way to identify them.

Then initialize your generator and run it forward past a few
hundred points where you lose information to rounding, then try
running from the state you reach, backward along all those paths.
What you will probably discover is that within a  dozen such
decision-point branchings, the vast majority of possible paths
that could have led to the reached state, will be shown to begin
in leaf nodes that could not have been reached from any state.

Then you can form an estimate at least of the ratio of unreachable
to reachable states.  Every state along a path that begins in a
leaf node state is unreachable.  Every state along a path that
begins in a branching node beyond which both paths are unreachable,
is also unreachable.  States you have actually traversed, may or
may not be reachable.  You should assume that the first N states
you traversed, where N is the length of the longest unreachable
path you've discovered, were on an unreachable path.

This matters because the ratio of unreachable to reachable states
is likely to be very large.  If it turns out that most of your
possible states are unreachable, then your generator necessarily
has much shorter cycles than it could, because none of those
unreachable states are on the cycles.  And we still haven't
considered how much the periods are shortened by the states
being divided up among multiple cycles  or how to tell how
many different cycles there are.

This is all general statistics, not real analysis of the specifics
of your particular generator.

				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/20141204/e95497c4/attachment.sig>