Random unsigned 64 bit integers

[Marat1961 17]

3 minutes ago, julkas said:

It's open source code, you can improve it or open issue.

The fact that the project is free, under the Apache-2.0 License.
Your project should have a link to the project whose code you are using.

 

By the way, then there was no question of mine either.

[Arnaud Bouchez 407]

On 10/23/2020 at 4:50 PM, Mahdi Safsafi said:

Not so ! 

Short answer : 0 is not granted to be a random value on all architectures.  

Long answer : https://software.intel.com/content/www/us/en/develop/blogs/rdrand-do-i-need-to-check-the-carry-flag-or-can-i-just-check-for-zero.html

I know this.
The comment is correct in the context of our code base, of course, not absolutely.
Returning 0 and returning a not random value (i.e. checking the carry flag) won't hurt in our mORMot code base, since RDRAND is never used directly as random source, just as entropy source.

 

Of course, in the context of the OP question, RDRAND is not a good idea, since it will work only one a set of machines.
I clearly stated that in my answer.

Edited October 25, 2020 by Arnaud Bouchez

[Arnaud Bouchez 407]

On 10/23/2020 at 8:03 PM, Kas Ob. said:

don't use the full block in getting a random number

This is a very good advice.
Of course, since AES is a permutation algorithm, only using a part of the output is as secure as XORin it.

 

But since we use AES-CTR, I don't see how it may be unsecure in our case:
- we can't get the Random output feed from attackers (if they can, then we have more trouble than our PRNG)

- AES-CTR is crypto secure by itself so even if we get the output feed, we won't be able to guess the key, even in the context of a PRNG.

 

On 10/23/2020 at 8:03 PM, Kas Ob. said:

use the other half to generate the next state

Here I am confused.
If you don't strictly use AES-CTR, but reinject the other half into the generator, you are changing the block chaining mode for something else.

AES-CTR is proven, I don't know if some tweaked algorithm may be safe.
By changing the CTR increment using some bits of the previous AES result? If it is odd, add 1, otherwise add 2?

 

I will read the pdf, anyway.
And change our source code don't avoid the XOR.

Thanks again for the feedback.

Edited October 25, 2020 by Arnaud Bouchez

[Guest]

20 minutes ago, Arnaud Bouchez said:

But since we use AES-CTR, I don't see how it may be unsecure in our case:

It is secure, i said to convert it to "bad ass one", it still has weak points, two to be exact, both are hard to perform an attack against but they are still valid.

1) Backtracking or called lack of forward security ( it been named many things), this about if current state had been compromised or disclosed, can you read the past state? with simple AESCTR yes you can.

2) Future prediction, this valid if current state had been compromised again for the current state then CTR mode will make the life easier to predict or test against next state, this is valid collision attack and using CTR will give attacker an shorter method to test about key (although it is not a key) for current state and the next one, this is one example.

 

Let that pdf alone, it is very hard to process, the math there is complicated but the figure 4 is brilliant to show prediction path aka attacked leakage path, so in very simple and naive way to explain it, draw a horizontal line in the middle of that finite group, and will see that these paths lost had their values, as they become short insufficient to build on, again this is very simple way to explain, and at page 8 the author suggested to use two initialization vectors instead of one (IV0 and IV1) for the same reason, and that is interesting way to secure the initialization from the seed, now when i suggested cut in half, the other half which can't be used to build paths on, but will be used in next state, means the same uniformly ratio of noise will be mixed in parallel (not in threading means) but for a side attack it will be seen the same noise from two parts with no way to distinguish the source.

 

I would suggest that you have look at "NIST SP 800-90A" https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final and specially about that part, referring to "8.8 Prediction Resistance and Backtracking Resistance" page 23, that does have nice explanation and better than ever i can write in English.

And another paper which is very valuable one, as it does target developer more than mathematician, it also does compare its proposed algorithm against few other PRNGs and CPRNGs, a rare and hard to find comparison, yet it is a little bit biased, but the author has his rights.

https://www.researchgate.net/publication/328091514_Randen_-_fast_backtracking-resistant_random_generator_with_AESFeistelReverie 

Make notice of the benchmark and how PCG perform against the proposed algorithm "Randen", in the end of the paper there is the algorithm, also there is this https://github.com/google/randen

 

Hope you like that and find it helpful in answering your points.

 

ps:

1 hour ago, Arnaud Bouchez said:

AES-CTR is proven, I don't know if some tweaked algorithm may be safe.
By changing the CTR increment using some bits of the previous AES result? If it is odd, add 1, otherwise add 2?

It might, but on other hand it is still in range of predictable addition value, i would prefer to use published, vetted and peer reviewed papers to build.

And the point is going around the following, if an attack is possible to perform with 1 addition, two adding two might be harder but then again adding 3 is better and 4 even better, where to stop?, lets jump to best value to add, it is half of a block, that wasn't disclosed !

[julkas 12]

20 hours ago, Marat1961 said:

It would be helpful to know the domain of application (DDD).

Domain of application - number theory algorithms (Pollard Rho, Brent, ...)

[julkas 12]

I have created Rosetta code entry for Object Pascal - http://www.rosettacode.org/wiki/Pseudo-random_numbers/Splitmix64#Object_Pascal

[Mahdi Safsafi 225]

7 hours ago, Arnaud Bouchez said:

I know this.
The comment is correct in the context of our code base, of course, not absolutely.
Returning 0 and returning a not random value (i.e. checking the carry flag) won't hurt in our mORMot code base, since RDRAND is never used directly as random source, just as entropy source.

Unfortunately, I’m not in a position to discuss your internal design for the great mORMot library. So literally I’m just going to speak theoretically.

You used a DRNG instead of PRNG(LCG or whatever) -because you wanted a true RNG- to initialize an entropy source(ES) right ? What I’m seeing here is that your implementation breaks two fundamental rule of RNG : uniform distribution and unpredictable sequence ! How ? by counting 0 as TRN. This technically makes your ES vulnerable for backdoor !  

- An attacker may predicate 0 just because he knows that when RDRAND fails, it returns 0.

- What if he is knowing how to make RDRAND fail ? Now your ES is filled with zeros ! Intel didn’t describe all the circumstances that may lead to a failure. All what we know for now is a failure is expected if RN is not available didn’t pass the self-test ? In fact many people questioned Intel intentions when it putted some pressure on Linux kernel to use RDRAND/RDSEED … Eventually many concluded that a 3rd party (NSA?) was involved and may predicate/influence the output !!! Just google for the reason why the Linux kernel chipped out RDRAND/RDSEED.

 

If you permit me, I’d like to give some suggestions:

- Change the implementation by checking for CF and doing 10 time attempt when CF=0. I believe this will cost nothing compared to the additional security you get. BTW, that’s what Intel recommends:

Quote

 

5.2.1 Retry Recommendations

It is recommended that applications attempt 10 retries in a tight loop in the unlikely event

that the RDRAND instruction does not return a random number. This number is based on

a binomial probability argument: given the design margins of the DRNG, the odds of ten failures in a row are astronomically small and would in fact be an indication of a larger

CPU issue.

 

- Add another (optional) way to initialize the ES : e.g : CSPRNG, OS random data.

 

[Arnaud Bouchez 407]

1 hour ago, Mahdi Safsafi said:

If you permit me, I’d like to give some suggestions:

- Change the implementation by checking for CF and doing 10 time attempt when CF=0. I believe this will cost nothing compared to the additional security you get. BTW, that’s what Intel recommends:

- Add another (optional) way to initialize the ES : e.g : CSPRNG, OS random data.

You are right. The code I posted in this thread is indeed useless. You can't trust RDRAND to return some random values. It was a bad idea.

 

It is never used as unique source of entropy in mORMot. Just as part of a lot of entropy gathering.
Here is the documentation of mORMot about the initialization of our cryprographic AES-based PRNG:

 

    /// retrieve some entropy bytes from the Operating System
    // - entropy comes from CryptGenRandom API on Windows, and /dev/urandom or
    // /dev/random on Linux/POSIX
    // - this system-supplied entropy is then XORed with the output of a SHA-3
    // cryptographic SHAKE-256 generator in XOF mode, of several entropy sources
    // (timestamp, thread and system information, SynCommons.Random32 function)
    // unless SystemOnly is TRUE
    // - depending on the system, entropy may not be true randomness: if you need
    // some truly random values, use TAESPRNG.Main.FillRandom() or TAESPRNG.Fill()
    // methods, NOT this class function (which will be much slower, BTW)
    class function GetEntropy(Len: integer; SystemOnly: boolean=false): RawByteString; virtual;
 

https://github.com/synopse/mORMot/blob/ecc375adc96e5b78d63dd58a88418874a0f622d8/SynCrypto.pas#L1114

 

And about RDRAND, when mORMot checks the CPUID, it also runs RDRAND and if it fails to return random values, it unset its internal flag, and it will never be used, and not used as entropy.

It is even worse on AMD, which can have CF=1 but always return 0 or -1 !!!

 

So in practice, mORMot seems to follow your wise suggestions.
My answer in this thread, and my RDRAND use was confusing, for sure.
🙂

Edited October 25, 2020 by Arnaud Bouchez

[Fr0sT.Brutal 900]

On 10/23/2020 at 4:56 PM, Anders Melander said:

Most of them. You're scaling a 31-bit integer value in the approximate range 0..X-1 to the range 0..2^64-1

No. I'm scaling a 8-bit float value in the approx range 0.0..1.0 to the range 0..2^64-1

Actually parameterless Random generates such value already (I wasn't aware of that overload). Even though Random doesn't include the high boundary of specified range, rounding will produce this value

[Anders Melander 1782]

3 minutes ago, Fr0sT.Brutal said:

No. I'm scaling a 8-bit float value in the approx range 0.0..1.0 to the range 0..2^64-1

Storing a 31-bit value in a 64-bit intermediary doesn't magically produce more distinct values. You'll still have at most 2^31 distinct values.

[Marat1961 17]

On 10/23/2020 at 10:33 PM, Marat1961 said:

Hastily sketched. Perhaps for everything to work correctly, we need to implement multiplication of 64-bit numbers.

Since the most significant digits of the result are not used, there seems to be no difference which multiplication is signed or unsigned.

I was tormented by vague doubts, in the end I wrote several tests and did not find any difference when performing multiplication operations for the lower digits of the result.

 

The test code can be viewed here.
https://en.delphipraxis.net/topic/3763-multiple-two-uint64-modulo/?tab=comments#comment-31938

[Tommi Prami 130]

This seems interesting Random number generator algorithm, don't have any authority to actually prove it tough.

https://www.pcg-random.org/

 

There is some Delphi implementation at https://github.com/LUXOPHIA/LUX IT is way too complex if you only need one algorithm. Also one 32 bit version at https://github.com/mpodvin/PCG32-Random.

Dunno how it is going to compare with https://bitbucket.org/egrange/dwscript/src/master/Source/dwsRandom.pas if someone knows, I would be happy to learn.

 

-Tee-  

Edited February 12, 2021 by Tommi Prami
Typo fixed