New Random Number Generator for encryption
in [Cryptography]
|
Prev: Scalable Key Cryptography - The Universal Model.
Next: New Generation Lossless Data Representations
From: Greg Rose on 11 Aug 2010 20:55 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 11 Aug 2010 21:34 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 11 Aug 2010 18:12 "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 11 Aug 2010 22:26 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 11 Aug 2010 22:31
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. |