Announcement

Collapse
No announcement yet.

BCryptGenRandom Output

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • BCryptGenRandom Output

    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.

  • #2
    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

    Comment


    • #3
      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

      Comment


      • #4
        Originally posted by Jerry
        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.

        Comment


        • #5
          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.
          Code:
          #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

          Comment


          • #6
            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).

            Code:
            [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]
            Ribeiro Alvo
            Member
            Last edited by Ribeiro Alvo; 12 Feb 2021, 05:06 PM. Reason: Bug fix as suggested by David on post #9

            Comment


            • #7
              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.

              Comment


              • #8
                David, Hi

                Originally posted by David Roberts View Post

                ...
                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.

                Comment


                • #9
                  Originally posted by Ribeiro
                  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.

                  Code:
                  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!

                  Comment


                  • #10
                    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.

                    Comment

                    Working...
                    X