[Cryptography] new PRNG family

[Ray Dillinger]

On 12/03/2014 01:46 AM, Andreas Briese wrote:
> 
> Maybe someone on the list likes to investigate and publish with me about a new (chaotic) family of PRNG based on logistic maps? 
> 
> https://github.com/AndreasBriese/breeze
> 

It is interesting, but you're relying on the exact format of
floating point numbers, correctness of the hardware implementation
of operations on them (*cough* FDIV bug *cough*), and rounding
modes which you must control exactly in order for your code to
work the way you think it will. Honestly, these are things
that vary much *less* from system to system and machine to
machine than they used to, but they are still a cause for
concern.  I would worry about using an FP-based generator on
any platform other than the one it had been developed and
tested on, or even on any platform where the default rounding
mode can be set with a system call.

Anyway, I don't want to get sufficiently elbows-deep in float
format and representation to do that analysis.  But if you want
to analyze this, Here are some things to check for.

Given your assumptions about IEEE float representation and
the default rounding mode, you already know that each state
has a unique successor.  Now try to prove that each state also
has a unique predecessor -- ie, for each total state your
generator can be in, there is only one possible prior state
which could have produced it. If the unique-predecessor
property is not true, then one of the predecessor states
(along with all of its predecessors, etc) is not on any cycle,
and that is bad.  You want as many states as possible - in
fact, all of them - to be on cycles.

A cycle is a set of states, each leading to the next in sequence.
Because you have a finite number of states, and each state has a
unique successor, every traversable path through the states of
your generator must eventually comes back to whatever state you
started in if your starting state is even *ON* a cycle - which
it probably won't be if your states don't have unique predecessors.
That is why the unique-predecessor property is important.  States
that aren't on cycles are unreachable, and don't count toward
security. Ideally, every possible state is on the same huge cycle.
If your generator has several equal-length cycles, then no keys
are weaker than others - but none of them is as strong as it would
be if all the states were on the same cycle. If it turns out that
some cycles are much shorter than others, your PRNG will have a
class of weak keys for every such short cycle.

How many bits of state does your generator have?  That is, let
S be the number of valid, reachable states your generator can
be in.  Log2(S) is the number of bits of state your generator
has.  IE, if you map all the valid states to numbers, you
would need this many bits to represent a number that size.

If your adversary knows your PRNG's state, the game is all over
because it's deterministic.  You're producing pseudoentropy with
no input of real entropy.  And each output reveals state to
the adversary.

Your objective is that your generator should change its
state faster than the bits it reveals allow an adversary to
determine the state.  By the time an opponent sees a bit,
the bit should be a function of every part of your state.
And every part of your state should depend on that bit
(or on the transition that produced it) by the time he
has seen enough further bits to reveal that state.

For a generator with N bits of state, it takes N+1 bits of
output for an analyst with Godly computer power to determine
the total state.  But most analysts have merely mortal compute
power at their disposal, and if they can explain the most
recently observed N-1 bits of output in terms of any of
2^128 or more starting states which they would have to check
through one at a time, the N+1 bit isn't going to do them
any good.

The security of a PRNG fails when an adversary doesn't have
to check all those possible prior states one at a time. For
example, in an LFSG, each output tells an adversary a whole
bit about the future state of the generator which won't
change until another output reveals what it's being
replaced with, so after he's seen N+1 bits of output he
knows all of the current and therefore all future states.

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/20141203/a9004b67/attachment.sig>