Oh no, not another PRNG

[dodicat]

This is purely pre processed.

Code: Select all

#lang "fb"

for x as long=1 to 5
next x
#ifdef x 
print "OK",x,__FB_LANG__ 
#else
print "NOT OK",__FB_LANG__ 
#endif


#lang "fblite"

sleep 

With the rnd code, the last call to rnd determines the future method, (not the previous, so not exactly like a preprocessor command). The #lang "fblite" determines the language (last call to the pre processor).
I was going to keep a pointer to rnd 1,5 and a pointer to the twister, and concatenate them into a 64 bit generator and test that out in practrand.
Practrand likes a good mix up, I might have got a winner, who knows?
Regarding the thread's title, If I had got a winner it would have been yet another PRNG, so what's the problem?

[deltarho[1859]]

The pointer, @Rnd, is the same regardless of which FB generator is used - it is simply a pointer to the Rnd function. When we get to Rnd it then determines which generator to use, and we will now get different pointers.

When we concatenate two random numbers we get a random number. So, concatenating 5 and 3 should give a better randomness. However, throughput will hit the deck as 3 is about 350 times faster than 5.

If you want to use cryptographic numbers, for their quality of randomness, then use CryptoRndII which is faster than MT.

I am sorry, dodicat, but I reckon that you are flogging a dead horse here.

Added: BTW, when using two different generators the practice is to XOR the results. Research has shown that the resulting randomness is improved but costing throughput.

[jj2007]

when using two different generators the practice is to XOR the results. Research has shown that the resulting randomness is improved but costing throughput.

That's what I do with my file encryptor, see http://masm32.com/board/index.php?topic=8649.0
Do you think there is any difference between XORing two 32-bit PRNGs and using one 64-bit generator?

[deltarho[1859]]

Do you think there is any difference between XORing two 32-bit PRNGs and using one 64-bit generator?

That is a strange comparison. If the 64-bit generator is a LCG then that will fail PractRand at 8KB.

[jj2007]

Your algos push PractRand to its limits. That is probably important for scientific experiments - and I'd like to see a simple example where that matters.

My interest is slightly different. To encrypt a file,
- take a password and turn it into a 32-bit seed
- load the file into a buffer
- xor the buffer using a 32-bit PRNG
- save the buffer

To decrypt,
- use the known password to generate the seed
- load the file into a buffer
- xor the buffer using a 32-bit PRNG
- save the buffer

That is pretty straightforward, but a brute force attack would start from the assumption that the first 4 bytes of the encrypted file are (for example) Chr("PK", 3, 4) - all zip files start with this DWORD. Since a 32-bit PRNG will have a period close to 2^32, all you have to do is generate 4GB of 32-bit numbers until you find the one that matches. After about 9 seconds, your encrypted file is cracked...

Now, if you use the same PRNG for a second sequence, with a different seed, and you xor everything twice, then it takes twice as long to encrypt the file but 2^32 times as long to decrypt because you must find two matching slots in two sequences. That makes it 1200 years instead of 9 seconds.

My question is if one would see exactly the same effect using one 64-bit PRNG instead of two 32-bit PRNGs.

The PRNG I use is home-brewn, simple and almost 4 times as fast as PCG32. It is very good according to the ENT suite but fails PractRand at 128 kBytes. For the time being, I will stick to this one, also because with Microsoft's built-in stuff you can never be sure that there isn't a little backdoor...

[deltarho[1859]]

@jj2007

- take a password and turn it into a 32-bit seed

One method is to take a password and inject entropy by hashing it many times. If the password is 'password' and it is subject to 500ms of crunching, how long will it take to crack the password? Answer: 500ms. You need to use a strong entropy seed in the first place. A 128-bit random seed is not gong to get broken anytime soon. You will not remember it so put it into a password manager.

I see what you are getting at now with regard one 64-bit PRNG.

This is my answer: 2^32 x 2^32 = 2^64

It is very good according to the ENT suite but fails PractRand at 128 kBytes.

The first four metrics of the ENT suite are to do with distribution uniformity and not randomness - only the last metric, Serial Correlation Coefficient, has anything to do with randomness. If randomness is an issue then we should use PractRand.

but fails PractRand at 128 kBytes

With your task I don't think that matters. What does matter is cryptographic security and PRNGs don't have that.

In any event, I am totally against home-brewed encryption. I say that because every cryptographer on the planet will say the same.

With regard Microsoft there was only one API which was of concern. From MSDN: "Windows 10: Beginning with Windows 10, the dual elliptic curve random number generator algorithm has been removed." They don't say why but people like Bruce Schneier know why.

[deltarho[1859]]

Your algos push PractRand to its limits. That is probably important for scientific experiments - and I'd like to see a simple example where that matters.

I didn't address that.

I don't concern myself whether it matters or not - I would leave that to a user of random numbers to tell me whether it matters or not. I mentioned in the Warming up PRNGs Pascal's Wager. I use it with regard choosing a generator. If I use a fast good quality generator then I don't have to concern myself with speed or quality. I used xoroshiro128** with UEZ's Fireworks. Fireworks uses dodicat's Regulator so using a faster generator isn't going to make a blind bit of difference. Fireworks uses many random numbers. Top quality random numbers will not make a blind bit of difference. Using xoroshiro128** was done quickly. Some applications will benefit from a faster generator. Some will benefit from better quality random numbers. If I use xoroshiro128** or one of my other generators which "push PractRand to its limits" then I will be covered by Pascal's Wager.

[jj2007]

- take a password and turn it into a 32-bit seed

One method is to take a password and inject entropy by hashing it many times. If the password is 'password' and it is subject to 500ms of crunching, how long will it take to crack the password? Answer: 500ms.

Sorry, but that doesn't make much sense. The password translates to a DWORD, and that is one slot in your 2^32 PRNG "ring". So you cannot crack the password without knowing at least one DWORD of the actual xor'ed data. I quoted the PKxx sequence as an example - if the original file was a zip file, then indeed you need (max) 2^32 trials to find the seed that opens the rest of the ring. That takes 9 seconds on my trusty old Core i5. Or 1200 years in case of two PRNGs.

[deltarho[1859]]

That takes 9 seconds on my trusty old Core i5. Or 1200 years in case of two PRNGs

Chances are that no one will have the slightest interest in breaking your code but if they did they would not use a trusty old Core i5 would they? At the moment a super computer cannot break 96 bits of entropy. 2^32 x 2^32 x 2^32 = 2^96. That is three PRNGs. That will reduce your "4 times as fast as PCG32" to "1 times as fast as PCG32". In which case you could use xoroshiro128** which has a state vector of 128 bits. A cryptanalyst may say: "I am not going to try and brute force that but I can see three open doors with a gale blowing through them. "Where?" you may say with a response of "There, there and there". "Oh, dear" you may say, "I didn't see them". "Why should you", the cryptanalyst may say, "you are not a cryptanalyst".

Anyway, have a look 'Memo to the Amateur Cipher Designer' and 'Snake Oil'. The first was written in 1998 and the second in 1999 but make as much sense as they did then.

I have some home-brewed encryption. They were fun to write. Do I use any of them? Nope. My Encrypternet application uses AES, RSA, SHA256 and ECDSA all of which have been 'hammered' by cryptanalysts over the years. Every component has 128-bit security. It has a limited life span because RSA and ECDSA will be dead in the water when quantum computers hit the streets.

[jj2007]

Maybe I am just a bit dumb... let's take a simple example:
- you have a buffer with encrypted data that contains two DWORDs: AAAABBBB
- you know that AAAA was originally Chr("PK", 3, 4)
- both DWORDs were xor'ed twice with the same PRNG, using different seeds
- how can you determine in a short time the original value of BBBB?

[deltarho[1859]]

At first glance I haven't got a clue, but I will kick it around. I remember a few years ago a cryptographer said something like "If you haven't got a PhD in cryptography then you cannot call yourself a cryptographer". I thought that he was being very arrogant but as the years went by I realized that he wasn't. Cryptographers are an exceptional class of people. However, there are others who are even more exceptional, and they are cryptanalysts. I can imagine a cryptanalyst looking at your problem and saying "Come on boys, that is easy" and then shows us how it can be done. We would just look at each other and be totally taken aback at what we had just seen and thinking that we wouldn't have come up with that in twenty years. There are two types of cryptanalyst: White Hats and Black Hats. White Hats are those who contact Microsoft, and others, and advise them of security issues. Black Hats are those who are responsible for Patch Tuesday existing. Some Black Hats have been 'deradicalized' and now work for the NSA. This may explain why the NSA has been, how can I put it, a little naughty sometimes, to say the least.

Anyway, like I said, I will kick it around but don't hold your breath.

[jj2007]

I will kick it around but don't hold your breath.

Thanks, I am really curious if there is a shortcut that I am not able to see.

[deltarho[1859]]

I had to go out for a while, but when I got back I knocked this out. It looks OK but you may see a flaw - often spotted with another pair of eyes.

I am going to use 'A XOR B XOR B = A'

Let us say the original DWORDS were PK3Aabcd

We go through our two sets of 4 gigs of random numbers until we get

PK34 XOR W0X0Y0Z0 XOR W1X1Y1Z1 = AAAA where W0X0Y0Z0 and W1X1Y1Z1 are from sequence 0 and sequence 1 respectively.

Let W0X0Y0Z0 and W1X1Y1Z1 be the next random number in sequence 0 and sequence 1.

BBBB = abcd XOR W0X0X0Z0 XOR W1X1Y1Z1

So, abcd = BBBB XOR W0X0X0Z0 XOR W1X1Y1Z1

and so on.

This operation will take at most 2^32 x 2^32 iterations which was to be expected; the expectation being 2^31 x 2^31 = 2^62.

Come to think of it, this is how the enigma machine was broken when a German used the same salutation each day, the keys changed daily. The early challenge at Bletchley was to break the code before the end of the day. Interestingly most of the staff were not cryptanalysts - just a bunch of people with very unusual talents.

[jj2007]

This operation will take at most 2^32 x 2^32 iterations

And that would take how much time?

[deltarho[1859]]

And that would take how much time?

You already gave me a figure of 1200 years - that has not changed.