 |
AutoHotkey Community
Let's help each other out
|
| View previous topic :: View next topic |
| Author |
Message |
Laszlo
Joined: 14 Feb 2005
Posts: 4517
Location: Boulder, CO
|
 Posted: Wed Oct 05, 2005 12:27 am Post subject: More secure random numbers |
 |
|
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. | Code: | 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. |
|
| Back to top |
|
 |
Chris
Site Admin
Joined: 02 Mar 2004
Posts: 10667
|
| Posted: Wed Oct 05, 2005 1:10 am Post subject: |
|
|
| Quote: | | 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. |
|
| Back to top |
|
|
shimanov
Joined: 25 Sep 2005
Posts: 610
|
| Posted: Wed Oct 05, 2005 1:26 am Post subject: |
|
|
An example of dual-use technology. It should be banned!
All jokes aside, this a good demonstration of using an existing resource.
| Quote: | 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? |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4517
Location: Boulder, CO
|
| Posted: Wed Oct 05, 2005 3:44 am Post subject: |
|
|
| Chris wrote: | | 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.
| Chris wrote: | | 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.
| Chris wrote: | | 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.)
| Chris wrote: | | ...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.
| shimanov wrote: | | 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. |
|
| Back to top |
|
|
shimanov
Joined: 25 Sep 2005
Posts: 610
|
| Posted: Wed Oct 05, 2005 5:10 am Post subject: some information on uuid/guid |
|
|
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):
| Code: |
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 |
|
| Back to top |
|
|
shimanov
Joined: 25 Sep 2005
Posts: 610
|
| Posted: Wed Oct 05, 2005 5:30 am Post subject: |
|
|
| Laszlo wrote: | | 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.
| Laszlo wrote: | | 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
| Code: |
Loop 8
r := (r + (*(Address+A_Index) ^ *(Address+A_Index+8)))/256.0
|
versus
| Code: |
Loop 16
r := (r + (*(Address+A_Index)))/256.0
|
In either case, r is always a rational number less than one. |
|
| Back to top |
|
|
Chris
Site Admin
Joined: 02 Mar 2004
Posts: 10667
|
| Posted: Wed Oct 05, 2005 3:23 pm Post subject: |
|
|
| Laszlo wrote: | | 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.
| Quote: | | 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.
| Quote: | | 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.
Last edited by Chris on Tue Feb 21, 2006 2:54 am; edited 1 time in total |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4517
Location: Boulder, CO
|
| Posted: Wed Oct 05, 2005 4:45 pm Post subject: |
|
|
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: | Code: | 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 | Code: | Loop 16
r := (r + (*(Address+A_Index)))/256.0 |
gives the same result as | Code: | 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. |
|
| Back to top |
|
|
Dewi Morgan
Joined: 03 Oct 2005
Posts: 183
|
| Posted: Thu Oct 06, 2005 12:35 am Post subject: |
|
|
Laszlo wrote:
| Quote: | | 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.
| Quote: | | 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.com/java/other/article.php/10936_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. |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4517
Location: Boulder, CO
|
| Posted: Thu Oct 06, 2005 4:13 am Post subject: |
|
|
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. |
|
| Back to top |
|
|
Leon
Joined: 27 Aug 2007
Posts: 179
|
| Posted: Wed Oct 24, 2007 8:40 pm Post subject: |
|
|
@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
| Quote: | 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? |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4517
Location: Boulder, CO
|
| Posted: Wed Oct 24, 2007 9:19 pm Post subject: |
|
|
Those functions were in Shimanov's post. However, AHK evolved since then, so I'd write the script now as: | Code: | 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
} |
|
|
| Back to top |
|
|
Leon
Joined: 27 Aug 2007
Posts: 179
|
| Posted: Wed Oct 24, 2007 9:33 pm Post subject: |
|
|
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 |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4517
Location: Boulder, CO
|
| Posted: Wed Oct 24, 2007 9:48 pm Post subject: |
|
|
| Laszlo wrote: | | 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. |
|
| Back to top |
|
|
Leon
Joined: 27 Aug 2007
Posts: 179
|
| Posted: Wed Oct 24, 2007 10:00 pm Post subject: |
|
|
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? |
|
| Back to top |
|
|
|
|
You can post new topics in this forum
You can reply to topics in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Register
Profile
Log in to check your private messages
Log in
