Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

More secure random numbers


  • Please log in to reply
57 replies to this topic
Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
AHK's built in random number generator is seeded with a 32 bit number (timer), which usually does not take all the possible 2**32 values. In some cases it is problematic: at secure password or cryptographic key generation there are too few different initial values possible. Accessing the Windows built in generator of Globally Unique ID the value set is much larger.
SetFormat float, 4.18               ; needed for accurate computation with floats

MsgBox % GUID()                     ; 3 different GUID's
MsgBox % GUID()
MsgBox % GUID()

MsgBox % RandR()                    ; 3 random real numbers
MsgBox % RandR()
MsgBox % RandR()

Loop 10000
{
   f := RandI(0,9)                  ; random integers in [0,9]
   d%f% += 1                        ; histogram test
}
MsgBox %d0%`n%d1%`n%d2%`n%d3%`n%d4%`n%d5%`n%d6%`n%d7%`n%d8%`n%d9%`n

GUID()         ; 32 hex digits = 128-bit Globally Unique ID
{
   format = %A_FormatInteger%       ; save original integer format
   SetFormat Integer, Hex           ; for converting bytes to hex
   VarSetCapacity(A,16)
   DllCall("rpcrt4\UuidCreate","Str",A)
   Address := &A
   Loop 16
   {
      x := 256 + *Address           ; get byte in hex, set 17th bit
      StringTrimLeft x, x, 3        ; remove 0x1
      h = %x%%h%                    ; in memory: LS byte first
      Address++
   }
   SetFormat Integer, %format%      ; restore original format
   Return h
}

RandR()        ; 0 <= Random Real number < 1, from Globally Unique ID
{
   VarSetCapacity(A,16)
   DllCall("rpcrt4\UuidCreate","Str",A)
   Address := &A - 1
   r = 0
   Loop 8
      r := (r + (*(Address+A_Index) ^ *(Address+A_Index+8)))/256.0
   Return r
}

RandI(min,max) ; Random integer (< 53-bit) from Globally Unique ID
{
   VarSetCapacity(A,16)
   DllCall("rpcrt4\UuidCreate","Str",A)
   Address := &A - 1
   r = 0
   Loop 8
      r := (r + (*(Address+A_Index) ^ *(Address+A_Index+8)))/256.0
   Return min + Floor(r*(max-min+1))
}
GUID() gives a 128-bit (32 hex digit) Globally Unique ID value. RandR() returns a random real number between 0 and 1, while RandI(min,max) provides a random integer between min and max (inclusive). The calling example is a loop generating 10,000 random integers between 0 and 9, and the histogram values are shown. They have to be between 900 and 1,100 if the PC provides a good GUID generator. The script should work with Windows 2000 and up.

The GUID is not uniformly distributed in short sequences. To make the distribution nicer for random number generation the left and the right halves are XOR-ed together.

Chris
  • Administrators
  • 10727 posts
  • Last active:
  • Joined: 02 Mar 2004

AHK's built in random number generator is seeded with a 32 bit number (timer), which usually does not take all the possible 2**32 values.

The seed does vary between 0 and 2**32. Since it should wrap around back to zero every 7 minutes or so, it should vary uniformly. One common exception is if you have your script auto-start when the system boots: If your system always takes about the same amount of time to boot (say 30 seconds) this would cause the seed to be confined to a very limited range, and it wouldn't be as "random" as it could be.

Do you think the Random command should be re-seeded upon each use, or would that do more harm than good?

Is UuidCreate essentially a pseudo random number generator (the MSDN docs don't give much info)? If so, I was under the impression that pseudo random numbers aren't suitable for vital cryptographic purposes (in which case you probably intended the script for casual use only).

Thanks for posting this.

shimanov
  • Members
  • 610 posts
  • Last active: Jul 18 2006 08:35 PM
  • Joined: 25 Sep 2005
An example of dual-use technology. It should be banned!

All jokes aside, this a good demonstration of using an existing resource.

The GUID is not uniformly distributed in short sequences. To make the distribution nicer for random number generation the left and the right halves are XOR-ed together.

...

Loop 8
r := (r + (*(Address+A_Index) ^ *(Address+A_Index+8)))/256.0


Replacing "Loop 8" with "Loop 16" in RandI, produces a histogram with similarly uniform distribution. Why did you decide to XOR the two halves? Is there an advantage when the sample size is less than 10000?

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005

The seed does vary between 0 and 2**32. Since it should wrap around back to zero every 7 minutes or so, it should vary uniformly.

You wrote in another thread that the seed is the least significant 32 bits of the time measured in 100 ns intervals. What I meant is that if the fastest counter in the PC is slower than that (like in my PC it is updated only in every 280 ns) than not necessarily all the 2**32 values occur. Like at a counter period of 400 ns, the LS 2 bits are 0.

Do you think the Random command should be re-seeded upon each use, or would that do more harm than good?

Since the initialization uses a linear congruential generator, frequent reseeding would degrade the speed and the quality of the Mersenne Twister. What could be really useful is an option to seed the random number generator with a user supplied value. This would make scripts deterministic, useful for tests. If no explicit seeding was performed, the standard timer seed is to be used.

Is UuidCreate essentially a pseudo random number generator (the MSDN docs don't give much info)?

I don't know for sure. It looks like time is mixed in, so it has some physical entropy. I guess it from experiments with UuidCreateSequential, another function in the RTC dll. If you call it the first time in a process, it gives a value with a large difference from the value of the last time the same process was started and called this function. (Within the same instance of a process the Uuid values are incremented by 1.)

...pseudo random numbers aren't suitable for vital cryptographic purposes...

There are cryptographically secure (slow) pseudorandom number generators, which start from a secret seed (key). They are suitable for many crypto purposes, but not for all. Especially, security proofs often assume a truly random value, which need physical entropy. This does not prevent people to use secret seeded pseudorandom number generators for everything, and I have not heard of any successful attack exploiting this.

Replacing "Loop 8" with "Loop 16" in RandI, produces a histogram with similarly uniform distribution

After the 8th iteration the 64-bit precision of AHK is exhausted, and at the end only the last 8 bytes influence the result, so Loop 8 is the maximum which makes sense. I did some experiments, and the low order bits seemed to change slowly. To avoid problems when those bits are extracted and used, they get XOR-ed with the other half, which looked faster changing. However, I only spent a couple of hours with this, so it could be just a few unfortunate coincidences. The histogram test checks mostly the high order bits.

shimanov
  • Members
  • 610 posts
  • Last active: Jul 18 2006 08:35 PM
  • Joined: 25 Sep 2005
The value of using a uuid/guid for random number generation depends on what version is used. Apparently Windows 2000 and later use version 4, which require all fields to be generated from a "truly random" or "pseudo-random" source. Version 4 may contain up to 122 random bits. Of the 128 bits assigned, 4 contain version and 2 contain variant information.

I was not able to locate information on what algorithm and method Microsoft utilizes to generate their random numbers. Maybe there is a secret radioactive decaying source inside our system, of which no one is aware (possibly, inside the processor or memory -- that would explain the non-deterministic behavior, of which many people complain)?

Anyway... for the curious, the following code will display the decoded UUID (as generated by UuidCreate/UuidToString):

ERROR_SUCCESS			= 0
ERROR_OUTOFMEMORY		= 14

RPC_S_OK				:= ERROR_SUCCESS
RPC_S_OUT_OF_MEMORY		:= ERROR_OUTOFMEMORY

RPC_S_UUID_LOCAL_ONLY	= 1824
RPC_S_UUID_NO_ADDRESS	= 1739

VarSetCapacity( uuid, 16 )
result := DllCall( "rpcrt4.dll\UuidCreate", "uint", &uuid )

if ( result != RPC_S_OK )
	MsgBox, % result

status := DllCall( "rpcrt4.dll\UuidToStringA", "uint", &uuid, "uint", &ppUuid_text )

if ( status != RPC_S_OK )
{
	MsgBox, % result
	ExitApp
}

temp := ReadInteger( "uint", &ppUuid_text, 0 )
uuid_text := ReadString( temp, 0, 40 )

MsgBox, % uuid_text

DllCall( "rpcrt4.dll\RpcStringFreeA", "uint", &ppUuid_text )
return

TwosComplement( p_value, p_size )
{
	return, ( p_value^( 2**( p_size*8 )-1 ) )+1
}

ReadInteger( p_type, p_address, p_offset, p_hex=true )
{
	old_FormatInteger := a_FormatInteger

	if ( p_hex )
		SetFormat, integer, hex
	else
		SetFormat, integer, dec
	    
	if ( p_type = "int" )
	{
		sign := true
		size = 4
	}
	else if ( p_type = "uint" )
	{
		sign := false
		size = 4
	}
	else if ( p_type = "short" )
	{
		sign := true
		size = 2
	}
	else if ( p_type = "ushort" )
	{
		sign := false
		size = 2
	}
	else if ( p_type = "char" )
	{
		sign := true
		size = 1
	}
	else if ( p_type = "uchar" )
	{
		sign := false
		size = 1
	}
	else
		MsgBox, [ReadInteger] error: the type %p_type% is undefined!

	value = 0

	loop, %size%
		value := value+( *( ( p_address+p_offset )+( a_Index-1 ) ) << ( 8*( a_Index-1 ) ) )
	    
	if ( sign )
	{
		sign := ( *( p_address+p_offset+( size-1 ) ) ) >> 7
		
		if ( sign )
			value := -1*TwosComplement( value, size )
	}
	    
	SetFormat, integer, %old_FormatInteger%

	return, value
}

ReadString( p_address, p_offset, p_size )
{
	text=

	loop, %p_size%
	{
		address := p_address+p_offset+a_Index-1
	
		if ( *( address ) = 0 )
			break
		
		text := text Chr( *( address ) )
	}
	
	return, text
}

Relevant references:

Generating GUIDs
RFC 4122 - A Universally Unique IDentifier (UUID) URN Namespace
Yarrow - A secure pseudorandom number generator (Schneier)
RFC 1750 - Randomness Recommendations for Security

shimanov
  • Members
  • 610 posts
  • Last active: Jul 18 2006 08:35 PM
  • Joined: 25 Sep 2005

I did some experiments, and the low order bits seemed to change slowly. To avoid problems when those bits are extracted and used, they get XOR-ed with the other half, which looked faster changing.


Check my previous post for information concerning format and generation of UUIDs. It will explain your observations.

After the 8th iteration the 64-bit precision of AHK is exhausted, and at the end only the last 8 bytes influence the result, so Loop 8 is the maximum which makes sense.


I misstated my question. What do you gain if you use

Loop 8
      r := (r + (*(Address+A_Index) ^ *(Address+A_Index+8)))/256.0

versus

Loop 16
      r := (r + (*(Address+A_Index)))/256.0

In either case, r is always a rational number less than one.

Chris
  • Administrators
  • 10727 posts
  • Last active:
  • Joined: 02 Mar 2004

What I meant is that if the fastest counter in the PC is slower than that (like in my PC it is updated only in every 280 ns) than not necessarily all the 2**32 values occur.

I get it now. Thanks for clarifying.

What could be really useful is an option to seed the random number generator with a user supplied value.

Great suggestion. I will do this.

There are cryptographically secure (slow) pseudorandom number generators, which start from a secret seed (key).

Ah that makes perfect sense if the seed is secret and truly random. It's reminiscent of a one-time pad consisting of truly random numbers. As long as you use the pad only once and there is no physical theft/viewing of the pad, the message it encrypts is unbreakable.

Thanks!

Edit: The ability to reseed the random number generator has been added in v1.0.42.03. Thanks for suggesting it.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Printing 30 GUID's show that 4 bits (the first digit of the third block) are always the same. Also, the first 2 bits of the fourth block are always 10. These confirm shimanov's info about 6 fixed bits. I surrounded the DLL calls with a loop:
Loop 30

{

   result := DllCall("rpcrt4.dll\UuidCreate", "uint", &uuid )

   if ( result != RPC_S_OK )

      MsgBox, % result

   status := DllCall("rpcrt4.dll\UuidToStringA", "uint", &uuid, "uint", &ppUuid_text )

   if ( status != RPC_S_OK )

   {

      MsgBox, % result

      ExitApp

   }

   temp := ReadInteger("uint", &ppUuid_text, 0 )

   text := text "`n" ReadString( temp, 0, 40 )

}



MsgBox %text%
Concerning shimanov's question
Loop 16 

      r := (r + (*(Address+A_Index)))/256.0
gives the same result as
Loop 8 

      r := (r + (*(Address+8+A_Index)))/256.0
because the contribution of the earlier iterations underflows. (Actually, Loop 7 is the maximum sensible, with data type double.) XOR-ing two halves make each bit contribute to the final result. Also, if the fix bits do not overlap (they don't), the XOR-ed bytes have no fixed bits, so the result of the random number generators don't have fix bits.

Dewi Morgan
  • Members
  • 191 posts
  • Last active: Jun 07 2015 04:02 AM
  • Joined: 03 Oct 2005
Laszlo wrote:

Since the initialization uses a linear congruential generator, frequent reseeding would degrade the speed and the quality of the Mersenne Twister.

I have nothing to reply about this line. It was just so damn cool, in a geeky way, I just had to requote it.

This does not prevent people to use secret seeded pseudorandom number generators for everything, and I have not heard of any successful attack exploiting this.

The problem comes when people find out how your seed is generated. If you are distributing software to people then they can always find it out ("never trust the client!").

The most well known exploit of this weakness is the online poker shuffling problem http://www.developer... ... 6_616221_1 - because of this, most online poker sites now brag about their ridiculous levels of entropy/randomness, because that discovery rocked the online poker world, and really hurt their business.

Next most obvious is the exploit I listed in another thread, for guessing passwords on systems where many passwords are generated at the same time.

But it is often the case that you do not need access to the source to find how the seed is generated, or even to the compiled code, if you can obtain a large amount of output - especially if it's output with known timestamps.
Yet another hotkeyer.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
I was speaking about cryptographically secure pseudorandom number generators, seeded by a secret key. Dewi Morgan is right, of course, if the key is not secret (enough) or the software generator is insecure (from its output the seed or the next values could be deducted), then there is no security. Fortunately there are good generators and ways to keep a secret.

Thanks for the link, although what they write about pseudorandom number generators is very one sided, the introduction to cryptography is oversimplified, but the info about the poker shuffling is interesting.

Handling physical entropy is not easy, either. In casinos people have tried all kind of electromagnetic radiations to influence the electronic random number generators. If you could get close to one, you might be able to force them to generate a known pattern. Even if the entropy source is not electronic, like radioactive isotopes, the sensors are sensitive electronic devices susceptible to external influences.

Leon
  • Members
  • 179 posts
  • Last active: May 22 2008 02:41 PM
  • Joined: 27 Aug 2007
@Laszlo
In the second set of code u posted (link not working but: Wed Oct 05, 2005 4:45 pm)
when running the code I get

Error: Call to nonexistent function.
Specifically: ReadInteger("uint", &ppUuid_text, 0 )
---> 012: temp := ReadInteger("uint", &ppUuid_text, 0 )


Perhaps I am not supposed to run it on its own but instead integrate it into the code in your original post.
If so, how would I combine them?

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Those functions were in Shimanov's post. However, AHK evolved since then, so I'd write the script now as:
uuid := ppUuid_text := "1234567890123456"

Loop 30 {

   ErrorCheck( DllCall("rpcrt4.dll\UuidCreate", "uint", &uuid) )

   ErrorCheck( DllCall("rpcrt4.dll\UuidToStringA", "uint", &uuid, "uint", &ppUuid_text) )

   text .= ReadString( NumGet(ppUuid_text), 0, 40 ) "`n"

}

MsgBox %text%



ErrorCheck(code) {

   If (code) {  ; ERROR_SUCCESS = 0

      MsgBox Error %code%

      ExitApp

   }

}



ReadString( p_address, p_offset, p_size )  {

   i := p_address+p_offset

   Loop %p_size%

      If ( *i = 0 )

           break

      Else text .= Chr(*i++)

   Return  text

}


Leon
  • Members
  • 179 posts
  • Last active: May 22 2008 02:41 PM
  • Joined: 27 Aug 2007
I see.
Thanks Laszlo.
btw u realise the first digit in the 3rd block is always the same? unless that's is a very surreal co-incidence :)

Out of intereest, what could the reason for that be?
I don't see from the code what could cause it - not that i fully understand all of it

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005

4 bits (the first digit of the third block) are always the same. Also, the first 2 bits of the fourth block are always 10. These confirm shimanov's info about 6 fixed bits

MS fixed those bits for version info. This was the reason for XOR-ing the two halves: in the result there will be no constant bits.

Leon
  • Members
  • 179 posts
  • Last active: May 22 2008 02:41 PM
  • Joined: 27 Aug 2007
I think i see.
So after that (last) code it should be XOR-ed as in the first example?
So this last code is meant to be combined into the first code, am i right?