Criticism of a proposed floating point (cs)prng requested.
in [Cryptography]
|
Prev: Criticism of a proposed stream cipher requested.
Next: Question about pass phrase cracking through brute force
From: Francois Grieu on 4 Jun 2010 12:16 On 03/06/2010 20:24, Phoenix wrote: > The algorithm is: > > x_n+1 = FRAC( x_n ( x_n + b_n ) +c ) > > b=1,2,3�2048 > c=(0;1) > > I ask criticism on the safety, randomness quality, speed performance, > non linearity, crypto > analisys, Discrete Logarithm Problem (DLP), etc. > > For more go to: http://www.number.com.pt/index.html Let's replace the ambiguous notation x_n+1 by x{n+1} Define the integers k{n} = FLOOR( x{n}*(x{n}+b{n}) + c ) such that the recurrence becomes x{n+1} = x{n}*(x{n}+b{n}) + c - k{n} For all n x{n+1} = x{n} *(x{n} + b{n} ) + c - k{n} x{n+2} = x{n+1}*(x{n+1}+ 1 + (b{n}%2048) ) + c - k{n+1} By subtracting the two, it comes that (within rounding errors and possibly a mistake that can be fixed) y{n} = x{n+1}*(x{n+1}+2+(b{n}%2048))-x{n+2}-x{n}*(x{n}+b{n}) is an integer with absolute value no more than 2050. If the b{n} are known, from x{n} x{n+1} x{n+2} we can compute z{n} = FRAC(y{n}+2050.5) // 2050 is here to avoid sign issues If x{n} was a true Floating Point Random Number sequence uniformly distributed on [0..1[, then z{n} would be a (marginally worse) one. But with the Conjectured Cryptographically Secure PRNG proposed, z{n} will be close to 0.5, always within a few thousands EPSILON of the floating point type used. A plain statistical test of the standard deviation of z{n} over just a handful of values will immediately fail. If for some reason we had lost track of the b{n}, we can make that test for each of the 2048 possible b{n} at the start of the sample, and declare that the CSPRNG fails if one of the 2048 test fails (to a confidence level 2048 times tighter than for a single test). This illustrates that typically, a simple Floating-Point PRNG, if based on floating point calculations only, will fail a specially-crafted statistical test, and thus must not be considered a Cryptographically Secure PRNG. Fran�ois Grieu
From: Phoenix on 4 Jun 2010 12:32 On 4 Jun, 17:16, Francois Grieu <fgr...(a)gmail.com> wrote: > On 03/06/2010 20:24, Phoenix wrote: > > > The algorithm is: > > > x_n+1 = FRAC( x_n ( x_n + b_n ) +c ) > > > b=1,2,3 2048 > > c=(0;1) > > > I ask criticism on the safety, randomness quality, speed performance, > > non linearity, crypto > > analisys, Discrete Logarithm Problem (DLP), etc. > > > For more go to:http://www.number.com.pt/index.html > > Let's replace the ambiguous notation x_n+1 by x{n+1} > > Define the integers > k{n} = FLOOR( x{n}*(x{n}+b{n}) + c ) > such that the recurrence becomes > x{n+1} = x{n}*(x{n}+b{n}) + c - k{n} > > For all n > x{n+1} = x{n} *(x{n} + b{n} ) + c - k{n} > x{n+2} = x{n+1}*(x{n+1}+ 1 + (b{n}%2048) ) + c - k{n+1} > > By subtracting the two, it comes that (within rounding errors and > possibly a mistake that can be fixed) > y{n} = x{n+1}*(x{n+1}+2+(b{n}%2048))-x{n+2}-x{n}*(x{n}+b{n}) > is an integer with absolute value no more than 2050. > > If the b{n} are known, from x{n} x{n+1} x{n+2} we can compute > z{n} = FRAC(y{n}+2050.5) // 2050 is here to avoid sign issues > > If x{n} was a true Floating Point Random Number sequence uniformly > distributed on [0..1[, then z{n} would be a (marginally worse) one. > > But with the Conjectured Cryptographically Secure PRNG proposed, z{n} > will be close to 0.5, always within a few thousands EPSILON of the > floating point type used. A plain statistical test of the standard > deviation of z{n} over just a handful of values will immediately fail. > > If for some reason we had lost track of the b{n}, we can make that test > for each of the 2048 possible b{n} at the start of the sample, and > declare that the CSPRNG fails if one of the 2048 test fails (to a > confidence level 2048 times tighter than for a single test). > > This illustrates that typically, a simple Floating-Point PRNG, if based > on floating point calculations only, will fail a specially-crafted > statistical test, and thus must not be considered a Cryptographically > Secure PRNG. > > Fran ois Grieu Thanks Grieu, for your time. That is what I call a nice/usefull criticism here. I will study with carefull your post. Thanks again.
From: Maaartin on 4 Jun 2010 15:10 On Jun 4, 4:20 pm, Phoenix <ribeiroa...(a)gmail.com> wrote: > IEEE 754-2008 is sufficient for all areas of science, except for > crypto? The standard defines a lot of formats and a couple of modes. If *all* existing HW implemented it all and all compiler supported *all* of them, it would be nice, but this is obviously not the case. If there were a single choice which was both supported everywhere and the most efficient one, it could suffice. But there's none. Moreover, the most important and obundant HW is neither my nor your PC, but some tiny devices lacking FP at all. On Jun 4, 5:44 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Others may certainly have different opinions. I personally think though > that constraining communication partners to use hardware that produce > identical sequences isn't a too serious issue in many practical cases. It is. Just think about https, would you be happy if you couldn't access your bank just because of them using other HW? And what about secure email, etc.? > If your scheme turns out to be superior in security (and maybe also > processing efficiency) aspects, it would surely be a good contribution > to cryto in my humble view. There's no way how to show that something is secure except by a very time-consuming analysis by many good cryptographers. That's why there is only a couple of widely accepted ciphers, hashes, etc. Spending so much time on analysis of something not generally usable is loosing time.
From: Mok-Kong Shen on 4 Jun 2010 16:48 Maaartin wrote: > On Jun 4, 5:44 pm, Mok-Kong Shen<mok-kong.s...(a)t-online.de> wrote: >> Others may certainly have different opinions. I personally think though >> that constraining communication partners to use hardware that produce >> identical sequences isn't a too serious issue in many practical cases. > > It is. Just think about https, would you be happy if you couldn't > access your bank just because of them using other HW? And what about > secure email, etc.? Note the word "many" that I wrote. Consider e.g. the case where different branch officies of a firm are to confidentially communicate with one another. If that involves a PRNG that is based on computations in R, then almost surely the firm could afford to purchase compatible hardware, if not exactly identical hardware, for that purpose. In more general situations, Intel-compatible PCs are sufficiently "ubiquitous" and cheap, so that the problem in question could be considered to be practically solved, I would say. Certainly, if one partner uses Intel hardware and the other hardware from SUN, I don't know for sure but I guess there could be incompatibility problems. But that's outside of the "many" I meant. M. K. Shen
From: Phoenix on 4 Jun 2010 17:23
On 4 Jun, 20:48, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Note the word "many" that I wrote. Consider e.g. the case where > different branch officies of a firm are to confidentially communicate > with one another. If that involves a PRNG that is based on computations > in R, then almost surely the firm could afford to purchase compatible > hardware, if not exactly identical hardware, for that purpose. In > more general situations, Intel-compatible PCs are sufficiently > "ubiquitous" and cheap, so that the problem in question could be > considered to be practically solved, I would say. Certainly, if > one partner uses Intel hardware and the other hardware from SUN, > I don't know for sure but I guess there could be incompatibility > problems. But that's outside of the "many" I meant. M. K. Shen At this point, my question is: The incompatibility bettween i.e. (Intel/SUN) communications, is for all areas (Chemistry, Trigonometry, Biology, Geometry, etc) or only for crypto? If answer is only for crypto, what is the solution to pass accurate and compatible values in R from one system to another? |