New Random Number Generator for encryption
in [Cryptography]
|
Prev: Scalable Key Cryptography - The Universal Model.
Next: New Generation Lossless Data Representations
From: Lev Dymchenko on 12 Aug 2010 08:19 On Aug 12, 4:09 pm, jbriggs444 <jbriggs...(a)gmail.com> wrote: > 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.- Hide quoted text - > > - Show quoted text - Yes exactly. Interesting that standard tests do not catch it. But if we rearrange sequence so first bits will be generated by first particle, second block of bits by second particle and so on this course appeared in some test. For odd dimensions. I will present later research of quality of trajectories of particles. In short, even dimensions from 6 show good quality. Probably better auxiliary rng could help too. It has some performance room to use different auxiliary rng.
From: Lev Dymchenko on 12 Aug 2010 08:21 On Aug 12, 4:19 pm, Lev Dymchenko <levdymche...(a)gmail.com> wrote: > On Aug 12, 4:09 pm, jbriggs444 <jbriggs...(a)gmail.com> wrote: > > > > > > > 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.- Hide quoted text - > > > - Show quoted text - > > Yes exactly. Interesting that standard tests do not catch it. But if > we rearrange sequence so first bits will be generated by first > particle, second block of bits by second particle and so on this > course appeared in some test. For odd dimensions. I will present later > research of quality of trajectories of particles. In short, even > dimensions from 6 show good quality. Probably better auxiliary rng > could help too. It has some performance room to use different > auxiliary rng.- Hide quoted text - > > - Show quoted text - *source
From: orz on 12 Aug 2010 17:45 While I'm at it, there seems to be some people here familiar with cryptographic number generation. Over in sci.crypt.random-numbers I have a thread about an RNG I recently wrote that I'm looking for commentary on, particularly with regards to cryptographic security. No one is showing up there to comment except one guy who complains about everything but doesn't talk about the algorithm, so I'm hoping someone from sci.crypt will take a glance at it. It's very similar to RC4 but the state is not required to be a permutation and the RC4 indirection-based output hashing is replaced with a very low quality entropy mixing pool, which is also mixed in with the array. It's fairly fast, but the security is highly questionable because the amount of entropy I'm return from the entropy pool each call is a tiny bit greater than the amount going in, and the return value is a very simple function of the entropy pool state. And probably other flaws I haven't realized. The main RNG I've been using as a yardstick is ISAAC... it's a tiny bit faster than ISAAC (which, to my knowledge, is one of the fastest CSPRNGs around) on my computer, and (I think... hard to say for sure) dramatically lower in bias, but probably no better in security (and my analysis suggests that ISAAC is already not the greatest CSPRNG in terms of security). Anyway, back to the regularly scheduled program: TestU01 Crush STILL hasn't finished on this. It's been like 2 and a half days or something I think. I may kill it if it doesn't finish before too terribly long. I'm guessing that what's going on in terms of performance on statistical tests is that the total number of particles the % chance of collision and the quality of the internal RNG are the most important things for performance on statistical tests. Because it interleaves particles, very large numbers of particles mean that related bits are very far apart in the bitstream, which makes correlations extremely hard to detect. The BCFN test might be able to detect that, but only if it had a ton of data to work on, and this is too slow to give it that much data. Some more tests, on smaller sizes. All of these tests use random_fracobj as the underlying RNG. For these runs the tests enabled are the standard 3 (BCFN-13, Gap-16, and DC6:9x1Byte:1) plus OFPF-13+4. For these tests, it was run at all power of 2 lengths up to 128 MB, and continually longer runs were made after that for as long as any of the 4 enabled tests had suspicious results (ie p-values in excess of .99 or so). size 2, dimensions 9, saturation 1/3 (170 particles) 1401 seconds / GB fails OFPF-13+4 at 256 KB size 3, dimensions 9, saturation 1/3 (6561 particles) 1322 seconds / GB passes tests up through 256 MB size 3, dimensions 8, saturation 1/3 (2187 particles) 1115 seconds / GB fails OFPF-13+4 at 128 MB size 3, dimensions 7, saturation 1/3 (729 particles) 1103 seconds / GB fails OFPF-13+4 at 16 MB size 3, dimensions 6, saturation 1/3 (243 particles) 957 seconds / GB fails OFPF-13+4 at 2 MB size 3, dimensions 5, saturation 1/3 (81 particles) 921 seconds / GB fails OFPF-13+4 at 64 KB fails DC6:9x1Byte:1 at 64 MB (p-value for DC6 was 10**-3 at 8 MB, 10**-4 at 16 MB, and 10^-4 at 32 MB, finally crossed the failure threshold at 64 MB... possibly it should have failed at 16 or 32 MB but got really lucky) size 3, dimensions 4, saturation 1/3 (27 particles) 787 seconds / GB fails OFPF-13+4 at 16 KB fails DC6:9x1Byte:1 at 4 MB fails Gap-16 at 8 MB fails BCFN-13 at 16 MB size 4, dimensions 4, saturation 1/3 (85 particles) 771 seconds / GB fails OFPF-13+4 at 128 KB fails DC6:9x1Byte:1 at 32 MB fails BCFN-13 at 128 MB fails Gap-16 at 256 MB size 4, dimensions 5, saturation 1/3 (341 particles) 877 seconds / GB fails OFPF-13+4 at 2 MB fails BCFN-13 at 256 MB size 4, dimensions 6, saturation 1/3 (1365 particles) 922 seconds / GB fails OFPF-13+4 at 32 MB size 4, dimensions 7, saturation 1/3 (1365 particles) 1058 seconds / GB passed all size 6, dimensions 3, saturation 1/3 (72 particles) 731 seconds / GB fails OFPF-13+4 at 64 KB fails BCFN-13 at 128 KB fails DC6:9x1Byte:1 at 32 MB fails Gap-16 at 32 MB at this point in testing I enabled some more DC6 parameterizations targeting medium-range correlation: size 6, dimensions 4, saturation 1/3 (432 particles) 760 seconds / GB fails OFPF-13+4 at 4 MB size 6, dimensions 4, saturation 1/3 (2592 particles) 848 seconds / GB fails OFPF-13+4 at 128 MB Now, varying saturation a bit to try looking at constant numbers of particles: (by saturation I mean the ratio of particles to possible locations for particles) size 4, dimensions 5, saturation 1/4 (256 particles) 825 seconds / GB fails OFPF-13+4 at 2 MB fails BCFN-13 at 128 MB size 8, dimensions 3, saturation 1/2 (256 particles) 811 seconds / GB fails OFPF-13+4 at 512 KB fails BCFN-13 at 512 KB fails DC6:5x8Byte:11 at 8 MB fails DC6:9x1Byte:1 at ??? MB (it passed up till 16 MB, gave a very suspicious result on 16 MB (p=10^-5), barely failed at 32 MB (p=10^-6), gave a moderately suspicious result at 64 MB (p=10^-4), gave a very suspicious result 128 MB (p=10^-6), and solidly failed at 256 MB (p=0). Admittedly the failure threshold for this one is a little high, but it's not *that* high... it's just went berzerk here) size 4, dimensions 5, saturation 1/2 (512 particles) 1047 seconds / GB fails OFPF-13+4 at 1 MB fails BCFN-13 at 256 MB size 8, dimensions 4, saturation 1/8 (512 particles) 644 seconds / GB fails OFPF-13+4 at 16 MB size 16, dimensions 3, saturation 1/8 (512 particles) 595 seconds / GB fails BCFN-13 at 1 MB fails OFPF-13+4 at 32 MB I was hoping a clear picture would emerge, like more collisions = less long range correlation. Unfortunately, I'm not seeing any clear patterns like that at the moment.
From: Greg Rose on 12 Aug 2010 21:12 In article <b0b2aee0-25a3-48e5-b805-2e5def988d62(a)s24g2000pri.googlegroups.com>, orz <cdhorz(a)gmail.com> wrote: >[...] The main RNG I've been using as a yardstick is >ISAAC... it's a tiny bit faster than ISAAC (which, to my knowledge, is >one of the fastest CSPRNGs around) on my computer, and (I think... >hard to say for sure) dramatically lower in bias, but probably no >better in security (and my analysis suggests that ISAAC is already not >the greatest CSPRNG in terms of security). A nit about your terminology: the "CS" is short for "cryptographically secure", and ISAAC is not thought to be secure, as you acknowledge above. You seem to be talking about a stream cipher kind of thing, so I would expect you would get more comments and scrutiny here than in s.c.random-numbers. Is this the same multi-dimensional automata thingy that has been discussed recently? Greg. --
From: orz on 12 Aug 2010 22:53
On Aug 12, 6:12 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > In article <b0b2aee0-25a3-48e5-b805-2e5def988...(a)s24g2000pri.googlegroups..com>, > > orz <cdh...(a)gmail.com> wrote: > >[...] The main RNG I've been using as a yardstick is > >ISAAC... it's a tiny bit faster than ISAAC (which, to my knowledge, is > >one of the fastest CSPRNGs around) on my computer, and (I think... > >hard to say for sure) dramatically lower in bias, but probably no > >better in security (and my analysis suggests that ISAAC is already not > >the greatest CSPRNG in terms of security). > > A nit about your terminology: the "CS" is short for > "cryptographically secure", and ISAAC is not thought > to be secure, as you acknowledge above. > > You seem to be talking about a stream cipher kind > of thing, so I would expect you would get more > comments and scrutiny here than in > s.c.random-numbers. Is this the same > multi-dimensional automata thingy that has been > discussed recently? > > Greg. > -- This discussion would be better moved to the thread in sci.crypt.random-numbers (titled "proposed cryptographic RNG"), as it's unrelated to the RNG proposed in this thread (this thread is about the automata thingymabob). I did not find any commenters in sci.crypt.random-numbers except the aforementioned one, though perhaps that's because I do not (and can not) offer a serious proof of security for that algorithm. I do not believe that ISAAC is unworthy of the moniker CSPRNG, merely that it would require significantly less computation power and math to crack than most of the eCrypt profile 1 CSPRNGs. I believe that that is a reasonable tradeoff for the speed that ISAAC offers, and that ISAAC fills a useful niche among CSPRNGs despite its relative weakness. I believe that it fills a reasonable niche among non-crypto PRNGs as well - prior to the algorithm I just posted in sci.crypt.random-numbers, I was unaware of any PRNG as fast as ISAAC in software that had appeared to have lower bias - to my knowledge that algorithm I posted is the only one today; the algorithms coming out of the academic non-crypto PRNG community seem rather anemic in comparison, at least on empirically measurable grounds. I am aware that some fraction of the academic crypto community holds ISAAC in contempt (Jean-Phillipe Aumasson made that clear in his paper, but then his paper was sufficiently flawed that I see no reason to put any faith in his opinion on the matter) for not offering any proof of security and partially short-circuiting the normal route to acceptance via a cash bounty. My impression is that the engineering crypto community does not share that contempt. Regardless, so far as I know no one has come remotely close to collecting that bounty, though I suspect it to be (barely) possible to do so with present day computing power. |