[Cryptography] new PRNG family

[Andreas Briese]

Am 06.12.2014 um 04:48 schrieb Tom Mitchell <mitch at niftyegg.com>:

> 
> 
> On Fri, Dec 5, 2014 at 11:30 AM, Ray Dillinger <bear at sonic.net> wrote:
> 
> 
> 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:
> >
>  ....
> This is a degenerate "generator" because we lose
> 
> Any generator needs to be very cautious with impossible
> state and results.

Regarding distribution patterns I did test all breeze variants (beside excessive NIST runs) 
on 256 bucket distribution of output and visual patterns (rgba from output) but found no flaws.   

> 
> Consider a RNG (true or pseudo) if an analysis discovers that
> a set of results is never generated than this can become a 
> problem.
> 
> Consider a lottery where a consortium can identify a block of
> picks that automated quick picks never generate.   By playing
> in that space alone the odds of sharing a result are vastly reduced
> and thus increasing the return on investment.
> 



> Same for key generation. If key generation fails to apply with 
> an even hand to all possibilities in key space then the key space exploration
> to crack open the data is reduced a little or a lot.   Agencies might
> try and  use alternative generators to make their key space less
> vulnerable than a common public keyspace.
> 
> Rounding has the potential of introducing inequities in the computation.
> 
> Theft and other abuses are possible.    Decades ago I was playing with
> calculating PI with a RNG based on some log and floating point mumble
> foo.   Code from the book compiled and ran... Then to make the exercise 
> visible I began to plot the hits inside and outside the unit circle.
> The pixels that turned on filled the screen except for arks of omission.
> These systematic omissions might be the locus of winning tickets
> in an illegal game and the rest of the space could be "sold" with
> no payout risk.     I was living in Reno and working with folk that at
> one time did work to validate electronic games.   Interesting discussions
> followed...  
> 
> The problem of RNGs is difficult.
> Consider how difficult it would be to demonstrate that all possible
> outcomes are possible and that impossible outcomes are a do
> not care.   

As far as i can tell, distribution is not the problem of this generator. You might argue, that if 
something is flawed - distribution will be flawed too, but  i have no indicator that this is in
fact the case here. That should have shown up in testing but didn't. I tested salsa20/8 in 
parallel with NIST-suite and beside always passing the test-suite with the breeze code that 
is published at github, i got even less p<0.05 than salsa did.

Period length might be a problem (see Persohn & Povinelli (2012) http://povinelli.eece.mu.edu/publications/papers/chaos2012.pdf about float 32bit). 
I think i have handled this (see my comments at the github site), but  i need to prove that, which becomes hard.
 
I had most of my companies equipment (3 i7 /     2 i5 /   2 XEON  /   4 dualcore imacs ) running for 10 consecutive days to test up to 10GB output with NIST,  and beside testing for innerState repetitions and found no flaws. 

Nonetheless i can not test the generator (not even the small breeze128)  as a whole for all possible outputs. 
Therefore i will step back and try to assess, if and in case how often a single logistic map 

while(x>0 && x<1){
nx = x-1
nx = nx * 3.9 * nx
x = 1-nx
}

produces the same state twice.  I did this when i started this project, but hadn't recorded it for statistical analysis. 
I'll keep you updated.

Andreas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141206/ec3857bc/attachment.html>