New Random Number Generator for encryption
in [Cryptography]
|
Prev: Scalable Key Cryptography - The Universal Model.
Next: New Generation Lossless Data Representations
From: Mok-Kong Shen on 12 Aug 2010 06:24 unruh: > When you have a choice of a bunch of secure PRNG, why in the world would > you pick an insecure one for any reason? Lacking knowledge of OP's work, I can't say anything specific to his PRNG. But, as I said, a statistically good PRNG could be used as a component of a scheme. If the combined result turns out to be fine and efficient, why should one deny its merits from the very beginning? BTW, I was in my earlier post only suggesting that OP take a look of Marsaglia's work to see if he could eventually get some good ideas from that. M. K. Shen
From: orz on 12 Aug 2010 06:25 I started up more statistical testing... this time I tried enabling a few extra types of tests and lowering the quality settings on MDWP to force a failure. TestU01 Crush still hasn't finished yet. mdwpobj<random_fracobj,vector2t,point2t> (size 20, saturation 1/3) 662 seconds / GB fails test "OFPF-13+4" at 256 KB fails test "BCFN-13" at 4 MB fails test "Rare:5x8Byte:4" at 8 MB fails test "DC6:9x1Byte:1" at 64 MB mdwpobj<random_fracobj,vector3t,point3t> (size 20, saturation 1/3) 682 seconds / GB fails test "BCFN-13" at 8 MB fails test "OFPF-13+4" at 128 MB mdwpobj<random_fracobj,vector4t,point4t> (size 20, saturation 1/3) 830 seconds / GB passed this set through 2 GB so far and from earlier testing with fewer tests: mdwpobj<random_fracobj,vector5t,point5t> (size 20, saturation 1/3) 1018 seconds / GB passes "BCFN-13", "DC6:9x1Bytes:1", and "Gap-16" (those 3 make up my standard set of tests) up through 16 GB The implication seems clear: the number of dimensions has a huge impact on output quality. Unfortunately, it also had an impact on performance. test key: BCFN-13: A test I generally have enabled (ie part of my standard set), this mostly checks for long range linear patterns in the data. Meaning it's good at finding flaws in large fibonacci-style RNGs that have insufficient non-linearity. OFPF-13+4: A test I generally have disabled because it is too slow and not all that good. This checks for short-range patterns that don't align with byte boundaries. It's supposed to find flaws in RNGs that produce 1 bit at a time or something like that. Rare:5x8Byte:4: A test I generally have disabled because it's not all that good. This test focus on areas where many 0s or 1s are returned in a single 64 bit (aligned) block. DC6:9x1Byte:1: A test I generally have enabled (ie part of my standard set), this mostly checks for short range linear patterns in the data. Meaning it's good at finding flaws in small state RNGs that have insufficient non-linearity. For reference, comparing that to some test RNG algorithms, selected because they fail in finite time but represent a variety of types of algorithms, arranged in order of increasing output quality: lcg32_16 A basic LCG, almost identical to a typical libc rand(), m=2**32, only the upper 16 bits of the result are used fails standard set at 128 MB (1 MB with common transforms) fails 6 tests in SmallCrush sclcg64_32 A combination of an LCG (m=2**32-1, poorly chosen multiplier) with a low-quality non-LCG multiplication based RNG, 32 bit output fails standard set at 128 GB (4 MB with common transforms) passes SmallCrush, fails 5 tests in Crush bin48_16 A simple RNG based upon basic maths (addition, xor, constant shifts), 48 bits of state, 16 bits returned fails standard set at 16 MB fails 1 test in SmallCrush, 11 tests in Crush sapparot A simple RNG based upon basic maths, see http://www.literatecode.com/2004/10/18/sapparot/ fails standard set at 128 MB passes SmallCrush, passes Crush, BigCrush not yet tried mwlc A simple multiplication based RNG. fails standard set at 1 GB passes SmallCrush, passes Crush, BigCrush not yet tried mwc4691 A large state fibonacci-style algorithm proposed by Marsaglia, used in his combination-RNG KISS4691 fails standard set at 1 GB, possibly with common transforms (my notes are unclear) passes SmallCrush, passes Crush, passes BigCrush (the full KISS4691 does not fail any normal tests, but it does fail correlation tests between different seeds in some cases after 4 GB) mm A fibonacci-style RNG, x[n] = x[n-24] + x[n-55] w/ 32 bit values but using only the upper 16 bits of each result fails standard set at 16 GB (2 GB with common transforms) passes SmallCrush, passes Crush, BigCrush not yet tried lcg64_32 A basic LCG, m=2**64, only the upper 32 bits are used fails standard set at 512 GB (2 GB with common transforms) passes SmallCrush, fails 4 tests in Crush mt19937_untempered A simple but large GFSR, the Mersenne Twister with the final output hashing (aka tempering) removed fails standard set at 16 GB (8 GB with common transforms) passes SmallCrush, fails 2 tests in Crush, fails 2 tests in BigCrush fran A (vastly?) reduced strength variant of RC4 fails standard set at 32 GB passes SmallCrush, fails 1 tests in Crush, BigCrush not yet tried clcg96_32 A combination of 2 LCGs, m1=2**64, m2=2**32-1, the multiplier on the 2nd was poorly chosen fails standard set at 512 GB (32 GB with common transforms) passes SmallCrush, fails 1 tests in Crush, BigCrush not yet tried ibaa8x4 A vastly reduced strength variant of IBAA (which is in turn a predecessor to ISAAC, though apparently higher quality than ISAAC) fails standard set at 128 GB passes SmallCrush, passes Crush, BigCrush not yet tried isaac32x16 A reduced strength variant of ISAAC (uses array size 16 instead of array size 256) fails standard set at 16 TB w/ common transforms (does not fail w/o transforms) passes SmallCrush, passes Crush, passes BigCrush Assuming normal speed RNGs, standard set of tests takes 15-25 seconds / GB, standard set with common transforms takes 20-90 seconds / GB, and standard set with full transforms takes 200-250 seconds / GB. (transforms were not used here, as they are not intended to be use on RNGs that produce 1 bit at a time) Assuming normal speed RNGs, SmallCrush takes 9-15 seconds, Crush takes 30-60 minutes, and BigCrush takes 5-7 hours. That's on a 3 GHrz Core 2 Duo.
From: Lev Dymchenko on 12 Aug 2010 07:58 On Aug 12, 12:52 pm, "Joseph Ashwood" <ashw...(a)msn.com> wrote: > "Lev Dymchenko" <levdymche...(a)gmail.com> wrote in message > > news:09124ddb-8255-48d6-b32c-7c8b2ab25784(a)p7g2000yqa.googlegroups.com... > > > Joseph Ashwood > > > "It works easily in this case becase there is a known counter > >> involved, from past the counter is only a single round. > > " > > > If counter is known, it does not necessary mean that attack is > > successful. > > You really should try to understand what I say. The foundation criteria was > building how to mount a differential attack on a pRNG. I gave the method I > used to model it as a block cipher with a chaining mode. I'm not giving the > details of the attack because it is a simple attack, but it is important > that, if you are going to build a good pRNG, you need to learn how to find > the attacks yourself. Once you understand how to mount a differential > cryptanalytic attack, the attack is easy to see. You just need to read up on > differential attacks until you understand them. > Joe Did you actualy perform such attack on this rng or just talking? I researched this attack and found interesting results, I will present later. You are missed good test results in rng article, and you missed something else about your attack.
From: Lev Dymchenko on 12 Aug 2010 08:04 Yes, low dimensions is no good, though better auxiliary rng could improve them a bit. It is interesting to test small cube size with high dimension. Also if data fits in CPU cache, speed is much better.
From: jbriggs444 on 12 Aug 2010 08:09
On Aug 11, 10:26 pm, Lev Dymchenko <levdymche...(a)gmail.com> wrote: > On Aug 12, 2:12 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote: > > > > > > > "Mok-Kong Shen" <mok-kong.s...(a)t-online.de> wrote in message > > >news:i3tkjq$ofn$03$1(a)news.t-online.com... > > > > Joseph Ashwood wrote: > > > >> ........ It is extremely weak against differential > > >> attacks. > > > > A question quite OT: Could you give a pointer to a good > > > (easy to understand) paper on differential attacks on PRNGs? > > > I don't know of any convenient reference. I actually modeled it as a 1-bit > > block cipher in CTR mode. I used the internal counter (I.e. the label for > > the particles and a loop count) as the plaintext, the pRNG output is the > > ciphertext, from there it is a fairly standard block cipher differential > > attack. It works easily in this case becase there is a known counter > > involved, from past the counter is only a single round. > > Joe > > I researched this attack just now and got interesting results. In > short, this attack is not successful, even if counter is known. You > only need not to select odd cube dimension. I will explain it on > update to rng article.- Hide quoted text - > > - Show quoted text - Yes, that's obvious. With an odd number of dimensions, the number of cells "one generation away" from a starting cell that have even parity are not equinumerous with the cells one generation away that have odd parity. For instance, in three dimensions (a 3x3x3 cube centered on the starting position) there are: 6 cells at the centers of the cube faces (odd parity) 12 cells at the centers of the cube edges (even parity 8 cells at the corners of the cube (odd parity) --- 26 cells total (2^3 - 1 = 26) That would be a 14 to 12 bias. In four dimensions the score is 40 to 40. So this potential source of bias appears to be avoided. |