BCryptGenRandom Output

[Jerry Wilson]

Does anyone know if BCryptGenRandom COULD create a value of zero? I don't want it to but do want to know if I need to check to detect if it does.

[Stuart McLachlan]

If it is generating random bits, which it is supposed to, any bit pattern should be equally possible including all 0s and all 1s.

Note that it can use different algorithms

[Jerry Wilson]

More specifically, could BCryptGenRandom fill a buffer with n number of bytes and all bytes (implying all bits in each byte) having a value of zero. Really, its an academic question since a line or two of code can be used to test the buffer with, virtually, no hit to app performance. According to Microsoft:

The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that standard.

SP800-90 is over 100 pages long so I'm trying to be lazy and skip reading that tome - hoping that someone else has

[David Roberts]

More specifically, could BCryptGenRandom fill a buffer with n number of bytes and all bytes (implying all bits in each byte) having a value of zero.

I cannot give a definitive answer to that but will say that if the answer is no then the output would not be random. The likelihood of a null buffer should be inversely proportional to n.

It is a bit like coin tossing. If 1,048,576 people, 2^20, tossed an unbiased coin twenty times then we should expect one to see either twenty heads or twenty tails. If only one person was involved, and they saw either twenty heads or twenty tails then we would have very strong evidence of a biased coin.

If your application prohibits a null buffer then a 'check and reject' mechanism will be mandatory.

Many people use Intel's RdRand without checking a potential failure. The chance of that is minuscule but not impossible. I allow six tries and if all fail I then revert to RtlGenRandom. I expect that scenario to never happen.

[David Roberts]

Here is a simple test using an Integer as a buffer.

The trial calls BCryptGenRandom 2^16 times. The integer could be zero on the first trial but that is highly unlikely. It could be zero on the 2^16th trial but that is equally unlikely. On average, we should get zero after 2^15, 2^16/2, trials; provided we have a perfect distribution uniformity.

So, I did 10,000 trials and got an average of 41,633.6572. That is 2^15.35 which isn't that far from 2^15. 10,000 trials isn't that large and a larger test should see us getting closer to 2^15.

With could do the same for a Dword buffer but then the average would be 2^31, so I wouldn't hold my breath on that test. Estimates vary but the chance of being struck by lightning in the UK is about 2^20 to 1 against.

I have done distribution uniformity tests on all my generators using a few more metrics than Formilab's Ent uses and found that BCryptGenRandom is one of the best and even beats Intel's RdRand but only just.

#Break On
#Compile exe
#Dim All
#Include "win32api.inc"
 
Function PBMain
Local hRand As Dword
Local Result As Integer
Local j, i, tot As Long
  BCryptOpenAlgorithmProvider(hRand, $$BCRYPT_RNG_ALGORITHM, $$Nul, 0)
  For j = 1 To 10000
    For i = 1 To 2^16
      BCryptGenRandom(hRand, VarPtr(Result), 2, 0)
      If Result = 0 Then Exit For
    Next
    tot += i
  Next
  Print tot/10000
  BCryptCloseAlgorithmProvider(hRand, 0)
  Waitkey$
End Function

[Ribeiro Alvo]

Jerry

Maybe this will answer you.

https://www.freebasic.net/forum/viewtopic.php?t=25393


Or use David's code, with the changes I made (I hope he doesn't mind).
This gives us more iterations, thus increasing the probability to find the value zero (0).

[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Break On[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Compile exe[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Dim All[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Include "win32api.inc"[/COLOR][/FONT][/FONT]

[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Function PBMain[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Local hRand As Dword[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Local Result As Integer[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Local j As QUAD[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]BCryptOpenAlgorithmProvider(hRand, $$BCRYPT_RNG_ALGORITHM, $$Nul, 0)[/COLOR][/FONT][/FONT]

[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]For j = 1 To 1152921504606846976  '2^60[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]BCryptGenRandom(hRand, VarPtr(Result), 2, 0)[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]If Result = 0 Then Exit For[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Next[/COLOR][/FONT][/FONT]

[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Print j [/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]BCryptCloseAlgorithmProvider(hRand, 0)[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Waitkey$[/COLOR][/FONT][/FONT]
[FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]End Function[/COLOR][/FONT][/FONT]

[David Roberts]

Hi Ribeiro

Since we are populating an integer, -2^15 to 2^15 -1, the chance of getting anywhere near 2^60 iterations before we see a zero is highly unlikely with the expected number of iterations being 2^15.

Perhaps I should have pushed 'i' beyond 2^16 a little but not as far as 2^60.

Your code only does one test - mine calculates an average of 10,000 tests.

It is worth noting that the theoretical average of 2^15 will not be obtained even if we did an infinite number of tests. BCryptGenRandom has an excellent distribution uniformity but it is not perfect.

Come to think of it my code may be one way of testing distribution uniformity. With a group test the generator which seems to be 'homing in' closer to an average 2^15 will be displaying the better distribution uniformity.

[Ribeiro Alvo]

David, Hi

...
Your code only does one test - mine calculates an average of 10,000 tests.
...

What is sought here is to know if this algorithm generates zeros.
This piece of code uses brute force to find zero.
For that to happen, an exhaustive search (a large number of iterations) will be necessary.
Even so, if a zero is never found, this does not prove that the generator produces them.
It is a matter of mathematical analysis to the generator in question.

[David Roberts]

For that to happen, an exhaustive search (a large number of iterations) will be necessary.

Point taken.

BTW, your code needs Print j and not Print i.

OK, try this.

Find the maximum minimum brute force value of j for 1000 trials.

It is better to use Log2.

A session takes about 11 seconds on my machine.

Function PBMain
Local hRand As Dword
Local Result As Integer
Local j As QUAD
Local i, lMax As Long
 
BCryptOpenAlgorithmProvider(hRand, $$BCRYPT_RNG_ALGORITHM, $$Nul, 0)
 
For i = 1 to 1000
  For j = 1 To 1152921504606846976  '2^60
   BCryptGenRandom(hRand, VarPtr(Result), 2, 0)
   If Result = 0 Then Exit For
  Next
  If j > lmax Then lMax = j
Next
Print Log2(lMax)
BCryptCloseAlgorithmProvider(hRand, 0)
Waitkey$
End Function

With five sessions, I get 18.8, 18.7, 19.1, 19.0, and 18.8.

So with an expected value of 2^15 we could find ourselves waiting until about 2^19 before a zero occurs; which is still less likely than being struck by lightning in the UK, but only half as much. Gulp!

[Ribeiro Alvo]

David

It looks like zeros are generated, which answers the question. However I only have version 5 of the PB Console and your code does not run on it.