The MASM Forum

General => The Laboratory => Topic started by: AW on April 13, 2018, 01:14:49 AM

Title: on-chip random numbers
Post by: AW on April 13, 2018, 01:14:49 AM
Reference:
https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide

This is a fast essay on the subject matter :
Code: [Select]
includelib \masm32\lib64\msvcrt.lib
printf PROTO :PTR, :VARARG
includelib \masm32\lib64\kernel32.lib
ExitProcess PROTO :DWORD
LIMIT equ 10

.data
fmt db "Random value %u: %llu",10,0
msg1 db "64-bit pseudo random numbers seeds using RDSEED",10,0
msg2 db 10,"64-bit high-quality random numbers using RDRAND",10,0

.code

main proc
        sub rsp, 28h
; Verify support for rdseed and rdrand
; rdrand
mov eax, 1
cpuid
bt ecx, 30
jnc exit
; rdseed
mov eax, 7
xor ecx, ecx
cpuid
bt ebx, 18
jnc exit

mov rcx, offset msg1
call printf

mov r15d, 1 ; generate from 1 to LIMIT seeds for pseudo-random number generator
@@:
rdseed r8 ; store a 64-bit random seed in destination register
jnc @b ; retry if no seed available in the entropy condioner
mov rcx, offset fmt
mov rdx, r15
call printf
inc r15d
cmp r15, LIMIT
jbe @b

; high-quality random numbers
mov rcx, offset msg2
call printf

mov r15d, 1 ; generate from 1 to LIMIT high-quality random numbers
@@:
rdrand r8 ; store a 64-bit high-quality number in destination register
jnc @b ; retry if no valid number available yet
mov rcx, offset fmt
mov rdx, r15
call printf
inc r15d
cmp r15, LIMIT
jbe @b
exit:
mov rcx, 0
call ExitProcess
main endp

end

Output:
64-bit seeds for pseudo random number generator using RDSEED
Random value 1: 11271964044411198033
Random value 2: 14819904872933026051
Random value 3: 11734536593662125914
Random value 4: 10178806003817372157
Random value 5: 16507044168887200704
Random value 6: 17015068959861677558
Random value 7: 9330418827117195449
Random value 8: 18272815394612035461
Random value 9: 1625390651447534182
Random value 10: 1624657990116424887

64-bit high-quality random numbers using RDRAND
Random value 1: 9866148806316864898
Random value 2: 13381141406723372343
Random value 3: 15942791537508244642
Random value 4: 11939218512590708444
Random value 5: 16677724538897210232
Random value 6: 13506647463992344196
Random value 7: 12752478826357554567
Random value 8: 373324759560139517
Random value 9: 12406571025380030795
Random value 10: 4471555834226138872

Title: Re: on-chip random numbers
Post by: felipe on April 14, 2018, 02:08:18 AM
I downloaded the masm64sdk. I renamed the masm32 folder temporarily (don't want another partition) and i created a folder named masm32. There i putted (unzipped) all the files and i run makeall.bat.Every went ok. I have the build tools of visual studio 2017. Which are accessed in convenient cmds each with a particular purpose and with the environment variables ok for that cmd "session". So i assembled your nice demo (or full program, sorry  :redface:) with this command: ml64 /c test.asm. Everything ok, a test.obj was created. Then i linked with this command: link test.obj /ENTRY:main /SUBSYSTEM:CONSOLE. And everything was ok, a test.exe was created. Then i run this nice demo (full program too  :biggrin:) but it seems like the source flow was directly to the exit label. Which means i have an Intel without that nice capacity. Hey, but the program and article was great informative  :greenclp:. I even now have the masm64sdk. Thanks a lot aw27. (And hutch).  :icon14: :icon14: :greenclp:
Title: Re: on-chip random numbers
Post by: hutch-- on April 14, 2018, 02:58:05 AM
felipe,

From memory a software random produces better results than the Intel instruction. There are two algos, irand and seed_irand, set the seed first then call irand.
Title: Re: on-chip random numbers
Post by: AW on April 14, 2018, 03:08:29 AM
@felipe
Nothing i can do to help you. :(

@hutch
Your statement does not make any sense to me, unless you have inside information.
Title: Re: on-chip random numbers
Post by: hutch-- on April 14, 2018, 09:31:12 AM
Been a while since I did the test pieces on rdrand but there was a lot of documentation on the net of problems with rdrand including back doors from the NSA and others. The Linux guys among others refused to trust it by itself and opted for software random algos. My own testing with ENT showed rdrand was OK but that a software implimentation was often better and there was no risk of a back door. The action with a decent random algo is a good seeding technique that does what you require, either impossible to reproduce OR a seeding technique that is unique for a special purpose that IS reproducible.
Title: Re: on-chip random numbers
Post by: Ascended on April 14, 2018, 10:34:06 AM
Interesting read Hutch.  :t

Would this work on AMD chips also (seeing as AMD is always trying to keep compatible with Intel)?

The hardware implementation would have to be faster to execute wouldn't it?
Title: Re: on-chip random numbers
Post by: hutch-- on April 14, 2018, 11:57:45 AM
Its probably easier to do a test piece, if its a late model AMD, it probably has RDRAND but its a reasonably late Intel mnemonic so I would not expect it on older hardware. I tested in with this 6 core Haswell that I am using as it is late enough to have the instruction. It works and would be useful but it was nothing exciting in either speed or randomness and there is the potential risk of a back door to help the NSA to break encryption.
Title: Re: on-chip random numbers
Post by: Ascended on April 14, 2018, 12:03:23 PM
Yeah, it's pretty bad the backdoor 'in chip' state of affairs at the moment.
Title: Re: on-chip random numbers
Post by: hutch-- on April 14, 2018, 12:23:03 PM
felipe,

Try this one out on your computer, it test if RDRAND is available and if it is, it runs it.
Title: Re: on-chip random numbers
Post by: AW on April 14, 2018, 02:11:00 PM
I have not much faith on what people write about when they are unable to produce proofs.
And there is no proof whatsoever, only speculation.
I have done a lot of work on randomness in the past, namely I have a software called Ramdon Labs in my website. It can also retrieve true ramdom data from Random.org. I verified that most times data generated by artifitial means,  namely by CryptoMT or Crypto API, scores better in the tests than true random data from ramdom.org.
Of course, we can question whether the data from ramdon.org is indeed true random and in the end we can question everyting.
On the other hand, there are very good pseudo-random number generators, there are no doubts about that. But the secret does not lie in the seed! For example, with Mersenne Twister the next state can be found with the knowledge of only 624 previous states, even though the period is 219937.
The real problem is about having good sources of entropy, and since this is really difficult, the so-called cryptographically secure pseudo-random number generators add obfuscation on top of obfuscation, for example rotating bits or xoring them or xoring and rotating or swapping them or any other conceivable way. But they are not true random number generator, only very good at making almost impossible to find what the next number will be.
Title: Re: on-chip random numbers
Post by: hutch-- on April 14, 2018, 04:12:20 PM
I have long been a fan of "ENT" as a pseudo random algorithm is about as useful as its tests show. Many of the older common ones are very poor in their characteristics. The notion of what random is effects the evaluation of results, sub sonic rumbling of the universe is well respected, microphoned wind turbulence scores well, depending on your sense of humour, a recorded policy speech by whatever politician you wish to nominate or even our Kylie would probably do the job but "random" semantically  means without order which in turn means unpredictable and this is where it becomes useful in encryption.

I have seen the use of pseudo random generators for many simpler tasks, card shuffling, making an array non ordered for constructing trees and of course some games use them but it is in the field of encryption that high powered random number generators need to perform. The seed can be a weak point if its range is small enough and if the pseudo random generator has a low repeat rate it can be broken with enough computer grunt so decent algorithms and highly unpredictable seeds make sense, QWORD sized seeds tend to make guessing or brute forcing a seed a lot more difficult.
Title: Re: on-chip random numbers
Post by: jj2007 on April 14, 2018, 05:41:37 PM
I have long been a fan of "ENT" as a pseudo random algorithm is about as useful as its tests show.

And we have some experience with it, see e.g. Monte Carlo Simulation with RDRAND (32 bit) (http://masm32.com/board/index.php?topic=2441.msg25678#msg25678). The tests started 8 years ago with Alex' algo. (http://www.masmforum.com/board/index.php?topic=11679.msg122831#msg122831) ENT and Diehard play also a role in the CAcert results (http://www.cacert.at/cgi-bin/rngresults) - over 3,000 algos tested. With Ctr F, you may find inside the page your favourite random generator- it's fun to see some big names fail miserably, e.g. Excel 2013 function RAND(). Searching for FORTRAN or BASIC yields also some goodies ;)
Title: Re: on-chip random numbers
Post by: AW on April 14, 2018, 08:03:48 PM
There is another aspect, rdseed produces multiplicative brute-force prediction resistance numbers, and rdrand additive brute-force prediction resistance numbers. This mean that we can multiply and add them together obtaining high-quality random numbers with any number of digits we want.
Title: Re: on-chip random numbers
Post by: Siekmanski on April 15, 2018, 12:40:45 AM
If you want real random data, connect a radio tuner to your computer and tune between 2 stations and record the data.  :bgrin:
Title: Re: on-chip random numbers
Post by: felipe on April 15, 2018, 04:31:37 AM
felipe,

Try this one out on your computer, it test if RDRAND is available and if it is, it runs it.
Code: [Select]

RDRAND not supported
Press any key to exit ....
:(
Probably my i5 is from an old generation. Still has good features: hyper-threading, vm support and others...
Title: Re: on-chip random numbers
Post by: Raistlin on April 17, 2018, 03:21:25 PM
From what I've read, RdRand is pretty fast (requests in the nanosecond ranges) and reasonably "secure" for cryptographic use.
The compatibility issue however is of more concern for generic implementations. I will be adding its detection to my hardware enumerator/system profiler in any case.

@hutch : https://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html   
<-This is where the NSA tried to alter RdRand to make it less random

Just for interest, anyone worked with hle/rtm (Transactional Synchronization Extensions) CPUID functions (Multi threading) ?
CPUID function 7 -> EBX bits : 4 and 11

Instructions: XACQUIRE,LOCK,XRELEASE,XBEGIN,XEND,XABORT   
Title: Re: on-chip random numbers
Post by: Raistlin on April 18, 2018, 03:28:53 PM
Never-mind - found some more information. Let me share, this looks promising to say the least.

https://www.felixcloutier.com/x86/XACQUIRE:XRELEASE.html  (Hardware Lock Elision) HLE / TSX

https://www.scss.tcd.ie/Jeremy.Jones/CS4021/transactional%20memory.pdf (Restricted Transactional Memory) RTM
Title: Re: on-chip random numbers
Post by: AW on April 18, 2018, 06:35:06 PM
Quote
Just for interest, anyone worked with hle/rtm (Transactional Synchronization Extensions) CPUID functions (Multi threading) ?
Probably not, given the amount of zero byte locking files databases continue to spill over.
Title: Re: on-chip random numbers
Post by: Raistlin on April 18, 2018, 07:27:49 PM
@aw27 - I was thinking of using TSX/HLE for our multi-threaded IOCP servers.
We could potentially eliminate the Critical sections (my case) / Semaphore (your case)
mechanisms that currently steal valuable clock cycles. Seems less clunky as well.
Title: Re: on-chip random numbers
Post by: AW on April 18, 2018, 08:19:10 PM
You may try, but listen to the silence of Intel....
What I mean is that according to the grapevine and the errata, TSX is not yet free of bugs.

Errata:
https://www.intel.com/content/dam/www/public/us/en/documents/specification-updates/desktop-6th-gen-core-family-spec-update.pdf
Title: Re: on-chip random numbers
Post by: AW on April 18, 2018, 10:53:49 PM
In addition, I could not find any processor able to support either RTM or HLE.  :(
I run also the Intel emulator without success.  :(

Code: [Select]
includelib \masm32\lib64\msvcrt.lib
printf PROTO :PTR, :VARARG
includelib \masm32\lib64\kernel32.lib
ExitProcess PROTO :DWORD

.data
nortm db "RTM not supported",10,0
nohle db "HLE not supported",10,0

.code


main proc
sub rsp, 28h
; Are RTM & HLE supported?
mov eax, 7
mov ecx, 0
cpuid
bt ebx, 11
jc hle
mov rcx, offset nortm
call printf
hle:
bt ebx, 4
jc exit; supported
mov rcx, offset nohle
call printf

exit:
mov rcx, 0
call ExitProcess

main endp

end

And MASM does not recognize any of the instructions XACQUIRE,LOCK,XRELEASE,XBEGIN,XEND,XABORT.

So, it is a whole fantasy.
Title: Re: on-chip random numbers
Post by: Raistlin on April 19, 2018, 02:59:15 PM
D@mn!t  - oh well. That is strange though, TSX/HLE has been around since 2014 (Haswell).
 
Title: Re: on-chip random numbers
Post by: hutch-- on April 19, 2018, 05:11:18 PM
Rudi,

Thanks for the link, its an interesting read and gives you every good reason to avoid anything that is well known in the field of encryption as it is probably compromised before it hits the market. Its the normal response, if the good guys (sic) can use it, the bad guys can as well. Any of the big players already know this and I imagine that any of them already have very big computer grunt for breaking anything that relies on the key bit size.

The stupid part is that anyone who seriously needs to encrypt data is not using crap like this, they are using their own techniques and this goes for fruitcakes like the Islamic State, spies of any of the government agencies, truly big business and folks doing secret research on some massive range of subjects. Security agencies grabbing at information are not doing it for security reasons, they are doing it for control and clandestine theft of technology.
Title: Re: on-chip random numbers
Post by: AW on April 23, 2018, 07:52:52 PM
D@mn!t  - oh well. That is strange though, TSX/HLE has been around since 2014 (Haswell).
Oh yeah, d@mn!t:
https://www.youtube.com/watch?v=AIXUgtNC4Kc
Title: Re: on-chip random numbers
Post by: Raistlin on April 24, 2018, 03:01:03 PM
 :greenclp:
Title: Re: on-chip random numbers
Post by: K_F on April 27, 2018, 08:32:03 PM
Oh yeah, d@mn!t:
https://www.youtube.com/watch?v=AIXUgtNC4Kc
So sad.. but that's representative of the state that SA has descended to..  :lol:
Title: Re: on-chip random numbers
Post by: AW on April 27, 2018, 10:27:59 PM
It is difficult for Raistlin to do TSX/HLE assembly language in there.  :(
Title: Re: on-chip random numbers
Post by: zedd151 on May 07, 2018, 03:12:59 AM

....Try this one out on your computer, it test if RDRAND is available and if it is, it runs it.


Code: [Select]
Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size
of this 80000000 byte file by 0 percent.

Chi square distribution for 80000000 samples is 232.44, and randomly
would exceed this value 75.00 percent of the times.

Arithmetic mean value of data bytes is 127.5112 (127.5 = random).
Monte Carlo value for Pi is 3.140695879 (error 0.03 percent).
Serial correlation coefficient is 0.000011 (totally uncorrelated = 0.0).

That's all folks
Press any key to exit ....

Processor   AMD A6-9220e RADEON R4, 5 COMPUTE CORES 2C+3G, 1600 Mhz, 2 Core(s), 2 Logical Processor(s)    :biggrin:

Title: Re: on-chip random numbers
Post by: AW on May 13, 2018, 01:25:04 AM
After scratching my head looking for the reasons the Intel emulator does not properly identify TSX instructions I found that the answer lies in a mysterious switch that we only know about in the extended help.
So, if I do: "sde -help" in the command line, nothing surfaces about TSX. But if I do "sde -long-help" it is all there.

Now, if I have a file called tsx.exe with TSX instructions, I can make the emulator run as if it had an Haswell CPU (before TSX being disabled in the Haswell CPU  :lol: ). Well, it appears that in real life, TSX instructions are currently disabled in all recent CPUs, except some server models, but someday all will be back to normal and we all will be more happy with those TSX instructions.

This is my reviewed TSX identification snippet, tested on the emulator.

Code: [Select]

includelib \masm32\lib64\msvcrt.lib
printf PROTO :PTR, :VARARG
includelib \masm32\lib64\kernel32.lib
ExitProcess PROTO :DWORD

.data
nortm db "RTM not supported",10,0
rtm db "RTM supported",10,0
nohle db "HLE not supported",10,0
hle db "HLE supported",10,0

.code

main proc
sub rsp, 28h
; Are RTM & HLE supported?
mov eax, 7
mov ecx, 0
cpuid
bt ebx, 11
jc rtmsup
mov rcx, offset nortm
call printf
jmp short skiprtmsup
rtmsup:
mov rcx, offset rtm
call printf
skiprtmsup:
bt ebx, 4
jc hlesup
mov rcx, offset nohle
call printf
jmp short exit
hlesup:
mov rcx, offset hle
call printf

exit:
mov rcx, 0
call ExitProcess

main endp

end

I was also badmouthing MASM for not recognizing any of the instructions XACQUIRE,LOCK,XRELEASE,XBEGIN,XEND,XABORT. Actually, it does recognize, I was not using the correct syntax.



Title: Re: on-chip random numbers
Post by: felipe on May 13, 2018, 01:09:37 PM
Nice program aw27, i like your style, thanks for sharing:

Code: [Select]
C:\masm32\xxx>xxx
RTM not supported
HLE not supported

C:\masm32\xxx>

 :icon14:
Title: Re: on-chip random numbers
Post by: AW on May 13, 2018, 07:57:55 PM
I could not find any notebook with a CPU supporting IntelĀ® TSX-NI, even within the most expensive ones.
I could however find desktops, and not necessarily within the most expensive, supporting it.
Since I will need to buy a desktop in the near future I will add this requirement.