From: Greg Rose on
In article <i3uqla$eut$00$1(a)news.t-online.com>,
Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote:
>
>BTW, in case you are interested to compare your design with others,
>there is a PRNG by G. Marsaglia named Super KISS, which is claimed to
>have very large period and good statistical qualities. (You could
>Google to find it. I personally have unfortunately no knowldege of it.)

But it is cryptographically unsound, so not worth
mentioning in sci.crypt.

Greg.
--
From: orz on
On Aug 11, 4:37 am, Lev Dymchenko <levdymche...(a)gmail.com> wrote:
> On Aug 11, 3:07 pm, orz <cdh...(a)gmail.com> wrote:
> > I've cut & pasted your code in to my RNG experimentation code and set
> > it for testing using both TestU01 SmallCrush/Crush/BigCrush/Rabbit and
> > my own test suite (which is not yet published but should be available
> > on sourceforge within a week or so). Test results are not coming very
> > quickly though, as they expect a fair number of random bits and this
> > is producing them 1 at a time very slowly. I have not been very
> > impressed with Diehard or the NIST stuff or RaBiGeTe or ENT. I have
> > not tried Dieharder yet. The parameterization of MDWP that I'm
> > testing is the one used by default in your sample code:
> > mdwpobj<random_fracobj,vector5t,point5t>
> > Preliminary results say that MDWP output is significantly higher
> > quality than random_fracobj output, but that's not saying much as
> > random_fracobj is horrible. It passes SmallCrush; it passes Rabbit up
> > to 1 megabit so far; it passes my tests up to 1 GB so far (the last
> > may sound like a lot, but my tests are intended to be called on
> > multiple terrabytes for good RNGs - on faster RNGs I test 1 GB every
> > 20 seconds or so, while on this it took 20 minutes).
> > If you have a different parameterization you want testing focused on
> > let me know, but my CPU resources are very limited so not much total
> > testing will get done.
>
> > Since MDWP requires an internal RNG I'd compare it to an RNG
> > transforming wrapper like a Bays-Durham shuffle rather than to an
> > RNG. In terms of practical usage I don't really see a point to this
> > due to its extremely low speed, but it's possible this could be of
> > interest from a theoretical perspective. Conceivably this could be
> > optimized quite a bit, but there are RNGs that pass all bias tests
> > that are 700+ times faster than this, and cryptographically secure
> > RNGs that are 400+ times faster than this, so even with optimization I
> > doubt it will be truly competitive in speed.
>
> > I'd suggest taking a glance at RC4 btw. It's an RNG that's at heart
> > about an arrangement of a fixed set of things, with their positions
> > within that arrangement interacting over time. So in that way it's
> > vaguely analogous to this, though it bears no real resemblance any
> > physical system.
>
> Thanks. Lets see results. Yes, it is a bit slow, however, MDWP rng can
> have very big rand seed or encryption key with same performance. Even
> megabytes. Do you know other RNG with such big rand seed? Performance
> of the reference code is also dependent of compiler. I hope compiler
> could deal with templates effectively. It uses about 200-500 clocks on
> one bit on my system.

It has passed 16 GB of my standard test suite so far. I had to kill
that process to free up the CPU it's on for other stuff but if I get
some time later I'll restart it. If I restart it later I'll try to
enable a wider variety of tests than normal to since the RNG speed is
going to be the limiting factor no matter what. I might also try
reducing the quality settings to force a failure, then gradually
increasing them to measure at what rate the quality grows with size.

It still hasn't finished TestU01 Crush yet (and probably won't finish
until tomorrow), but I'm leaving that running as I only need one core
atm and I have no way of restarting TestU01 Crush without starting
over. Given the nature of your algorithm and its performance so far
on my tests I anticipate it passing Crush and probably BigCrush as
well. Though I won't be running BigCrush on it, as that would take
too long.

By "very big rand seed or encryption key with same performance" you
mean that it has a large statespace, takes a lot of initialization
data, and has an adjustable size. A fair number of CSPRNGs have pools
whose size can be set arbitrarily (though usually only to powers of 2)
and speeds that are independent of the pools size, though usually they
define a specific size as standard for that algorithm and rarely use
other sizes.
I think that you are not actually doing anything that a proper CSPRNG
would consider seeding in MDWP, instead relying on the internal RNGs
seeding function. Most widely used CSPRNGs include algorithms for
expanding keys (which are typically 8 to 256 bytes in size) out to the
full size of their secret states (which are often 1 KB or more in
size, though sometimes much smaller if they are based on cryptographic
hashes for instance), and go to extreme lengths to make sure that the
key expansion algorithm is very very high quality. I think they do
this because a few attacks on older CSPRNGs (like RC4) have succeeded
based upon weakness in the seed -> secret state expansion process.

On Aug 11, 9:46 am, "Cristiano" <cristiaN...(a)gmail.com> wrote:
> Lev Dymchenko wrote:
> > What sequence size do you suggest?
>
> I usually do: 1, 8, 16, 32, ... MBits up to 128 MBits for the last answer..
> I use 50 sequences.
>
> I wrote a multi-threaded version (still in beta) of RaBiGeTe for Windows
> which include the GUI (written with wxWidgets). If you are interested in
> that version, let me know.
>
> Cristiano

RaBiGeTe is still in development? I saw no updates since 2005 and
assumed it had frozen. Multi-threading RNG testing sounds like a
really good idea for this day and age. I'm working on a vaguely
similar package (though probably closer to TestU01, as it includes
RNGs and is intended to have the RNG output passed directly to the
tests without being written to disk first).
From: Joseph Ashwood on
"Mok-Kong Shen" <mok-kong.shen(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

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