From: Lev Dymchenko on
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
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
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
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
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.