2
\$\begingroup\$

I have the following code blocks that generate apparently random numbers by using thread timing variations.

I am looking for a general code review, and a specific focus on whether the results are "true random numbers".

For computers with more than two CPUs

#include<chrono>
#include<iostream>
#include<thread>
using namespace std;

#define Mili 7
#define Base 7
#define Thrs 2

typedef unsigned char      Num;
typedef unsigned long long Out;

volatile Out out,tmp;

void inline thr(Num const num){
 while(true)
  out=out*Base+tmp,tmp=tmp*Base+num;
}

int main(){
 thread ths[Thrs];
 for(Num i=0;i<Thrs;++i)
  ths[i]=thread(thr,i);
 this_thread::sleep_for(chrono::milliseconds(Mili));
 while(true)
  cout.write((char*)&out,sizeof(out));
}

For computers with two CPUs

#include<iostream>
using namespace std;

#define Base 7
#define Iter 53

typedef unsigned char      Num;
typedef unsigned long long Out;

volatile Out out,tmp;

int main(){
 for(Num i=0;i<Iter;++i)
  #pragma omp parallel for schedule(runtime)
  for(Num num=0;num<Iter;++num)
   out=out*Base+tmp,tmp=tmp*Base+num;
 while(true){
  #pragma omp parallel for schedule(runtime)
  for(Num num=0;num<Iter;++num)
   out=out*Base+tmp,tmp=tmp*Base+num;
  cout.write((char*)&out,sizeof(out));
 }
}

For computers with one CPU:

#include<chrono>
#include<iostream>
#include<thread>
using namespace std;

#define Nano 1
#define Mili 7
#define Base 7
#define Thrs 2

typedef unsigned char      Num;
typedef unsigned long long Out;

volatile Out out,tmp;

void inline thr(Num const num){
 while(true)
  out=out*Base+tmp,tmp=tmp*Base+num;
}

int main(){
 thread ths[Thrs];
  for(Num i=0;i<Thrs;++i)
   ths[i]=thread(thr,i);
 this_thread::sleep_for(chrono::milliseconds(Mili));
 while(true)
  cout.write((char*)&out,sizeof(out)),
  this_thread::sleep_for(chrono::nanoseconds(Nano));
}
\$\endgroup\$
  • \$\begingroup\$ I'm voting to close this question as off-topic. I've chosen "broken code"/"code not yet written", but I'm not sure that's the perfect close reason. The problem is, this question is asking "Does this code do what I want it to do?" On Code Review we expect askers to post questions that are working perfectly as they expect, and answerers will tell you how to improve the code. This is not where you come to verify that your result is accurate or get help improving your result (other than the gray-ish area of performance concerns). \$\endgroup\$ – nhgrif Jul 4 '15 at 13:24
  • \$\begingroup\$ @nhgrif I mostly disagree. That's a similar problem: Making the output more random instead of making it more performant. It's surely no perfect fit for this site and I'm rather sceptical concerning the algorithm, but answering one more question doesn't kill us. \$\endgroup\$ – maaartinus Jul 4 '15 at 13:33
  • \$\begingroup\$ It's probably worth noting that the user didn't intend to post his question here. It was migrated here, away from Computer Science, by a moderator there. I think a meta discussion might be worthwhile if you feel so inclined. I already think performance questions are gray-area enough. I think this one is just on the wrong side of that gray area. \$\endgroup\$ – nhgrif Jul 4 '15 at 13:35
  • \$\begingroup\$ @nhgrif: It was actually posted here first, which was deleted after this question arrived here. \$\endgroup\$ – Jamal Jul 8 '15 at 19:26
13
\$\begingroup\$

A true random number generator (TRNG) is a source of bits such that each bit has a probability of exactly 1/2 of being 1. Your code is obviously not a TRNG since its bias will heavily depend on the timing of operations.

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces bits which satisfy statistical tests designed to verify randomness. Your code is obviously not deterministic so it is not a PRNG.

What you have here is a source of entropy: a bit stream which is not fully deterministic. You're measuring the timing of your program which depends on the synchronization between wall time and the CPU, so you're using jitter as a source of entropy.

CPU jitter may be a potential source of entropy. This paper by Stephan Müller analyzes CPU jitter on an x86 CPU. It has acceptable statistical properties if done right. However, there is a far cry from having acceptable statistical properties to being a good entropy source. The Linux kernel maintainers debated whether to include Müller's code as an entropy source, and concluded against it. They found two problems:

  • Having good statistical properties is good enough for some applications, but it is not good enough for security. For security, unpredictability is necessary. Even a knowledgeable adversary must not be able to reproduce the output. That includes, for example, an adversary who has the exact same hardware running the exact same program.
  • The CPU, in fine, does not contain much if any actual physical source of entropy. At the physical level, it's pretty much a deterministic system, albeit an extremely complex one which is difficult to analyze fully. It's unclear whether the physical uncertainties are enough to reach macroscopic levels.

To make things worse (much worse!) your implementation of CPU jitter measurement is deeply flawed. CPU jitter randomness is based on the lack of synchronization between the real-time clock (RTC) and the CPU's clock. But your code doesn't go very far in this direction: it spends most of its time doing sleep_for()! sleep_for() is based on interrupts driven by the RTC, and so are context switches. Confronting the RTC with itself is fully predictable, so the only source of unpredictability is the timing of the few computations that you make.

I haven't made any mathematical analysis of your computations (what you do with out). The only reason I can see to use multiplication here is to exercise different parts of the CPU to increase jitter. You should document this kind of design choices.

An obvious potential problem with your function is that it's prone to short cycles. The transformation (out, tmp) → (out*Base+tmp, tmp*Base+num) has cycles; if you fall into them you'll emit repetitions for a while until the scheduler hits. Just for fun, I ran your code and inspected the output visually, which is degree 0 of statistical testing (serious statistical testing uses tools that run for hours). The single-CPU version emitted sequences of zeroes () now and then… that's an obvious failure.

0000c9f0  5c 4d 68 41 e1 95 77 a6  17 2e bb 7a c6 37 d6 27 
0000ca00  54 a4 7f f0 5f ee 5b fc  54 a4 7f f0 5f ee 5b fc 
*
0000cbb0  a1 48 55 36 71 47 4b 75  4f a1 8d c1 60 fc c8 f0 
0000cbc0  52 f5 22 43 e1 1a c0 4d  52 f5 22 43 e1 1a c0 4d 
0000cbd0  52 f5 22 43 e1 1a c0 4d  74 47 ad 9f bd ee 5f 90 
0000cbe0  74 47 ad 9f bd ee 5f 90  74 47 ad 9f bd ee 5f 90 
*
0000cc40  74 47 ad 9f bd ee 5f 90  e3 2e c7 50 a8 84 5a 1c 
0000cc50  fb ea 92 19 2f 6c 98 8e  0b 6a 7a 9a ac 59 87 03 
0000cc60  73 ac 9f 43 2f 52 ab e1  2b d8 86 ab 7b 97 98 fc 

(The first column is the offsets, then , all in hex. A * stands for a sequence of all-zero lines.)

On the programming side, you should initialize all variables. Leaving variables uninitialized doesn't increase entropy (they're predictable on a given platform), makes your program harder to analyze, and allows the compiler to optimize parts of your code away (for example, since you can't distinguish between a final value of out that was produced from a particular starting value, and a final value that was produced from a different starting value, the compiler is allowed to perform no computation until the first time the value of out is written to). Also note that operations like out=out*Base+tmp are not performed atomically, there can be a context switch between the time out is read and the time out is written to, in which case the work of the other thread(s) is be overwritten.

Note: sometimes “TRNG” is used to mean a source of entropy, which I discuss below. An actual RNG can be built on top of a source of entropy (preferably multiple independent sources) by seeding a PRNG with the source of entropy. By this very weak definition, you have a TRNG, but as we've seen one that's neither good nor new.

All in all, you seem to be trying to generate random numbers by flailing around in the dark. That doesn't work. Generating random numbers is very difficult. In order to be taken seriously, a random number generator needs to come with a detailed analysis, including rationales for each sources, collected statistical data, mathematical models, etc. Not a code dump. Showing that you did no research by demonstrating ignorance of common terminology doesn't help your credibility either.

\$\endgroup\$
  • \$\begingroup\$ Thank four your answer. You taught me a lot and I researched. According to your definitions, they are TRNG. The CPUs are physical sources of entropy. This implementation of CPU jitter confronts the CPU speed with the RTC. The multiplication has several purposes: Data races, prime number multiplication, entropy accumulation. To avoid large sequences of unchanged numbers, it is recommended to use higher priorities, shielded CPUs or low workloads. Variables are volatile, what means: No optimization. Atomically operations means: No data races. The codes were already hard analyzed. \$\endgroup\$ – ncomputers Jul 4 '15 at 21:20
  • 4
    \$\begingroup\$ @ncomputers.org Oooookay. Your comment shows that you don't understand arithmetic (“prime number multiplication”?? No, at no point!), entropy (“entropy accumulation” — again no), volatile (doesn't make anything atomic), atomicity (none of that in your program), common sense (“it is recommended to use …” — dude, your program would be one running among many, nobody wants to use their PC solely to generate random numbers). You really need to learn the basics. \$\endgroup\$ – Gilles 'SO- stop being evil' Jul 4 '15 at 21:30
  • \$\begingroup\$ I want to teach you a lot of things. Prime numbers are a base for cryptology and data encryption. Volatile tells the compiler, that the variable may change and should avoid some optimizations. That means: to initialize the variable is useless for optimization. Atomic accesses must be avoided to make these codes work. Atomic access -> no data races. No data races -> no true random numbers, no true random numbers -> pseudo-random numbers. Entropy accumulation \$\endgroup\$ – ncomputers Jul 4 '15 at 22:24
  • \$\begingroup\$ "nobody wants to use their PC solely to generate random numbers" I want to introduce you, heuristics. Let's start here \$\endgroup\$ – ncomputers Jul 4 '15 at 22:25
-4
\$\begingroup\$

This is an extract of the binary dump and refers to: void inline thr(Num const num)

mov    (out),%rdx        #read the value of out
mov    (tmp),%rcx        #read the value of tmp
lea    0x0(,%rdx,8),%rax #step 1: multiply out*7
sub    %rdx,%rax         #step 2: multiply out*7
add    %rcx,%rax         #add the value of tmp to out
mov    %rax,(out)        #save the result (out=out*7+tmp)
mov    (tmp),%rdx        #read the value of tmp
lea    0x0(,%rdx,8),%rax #step 1: multiply tmp*7
sub    %rdx,%rax         #step 2: multiply tmp*7
add    %rsi,%rax         #add the value of num
mov    %rax,(tmp)        #save the result (tmp=tmp*7+num)
jmp    beginning         #do it again

Defining a clock as a device with a rate of change through the time: A data race is the result of confronting two clocks and CPU time jitter is the confrontation of both clocks.

The CPU speeds change slightly due to their physical entropy caused by the execution of a single instruction, due to their energetic inefficiency.

When the entropy level is enough to activate the heatsink fan, then this entropy will be exchanged faster with the environment.

When executing two threads exactly at the same time in two different CPUs and when tmp=out=0, there can happen two cases:

Thread 0

mov    (out),%rdx        #rdx=0
mov    (tmp),%rcx        #rcx=0
lea    0x0(,%rdx,8),%rax #rax=0
sub    %rdx,%rax         #rax=0
add    %rcx,%rax         #rax=0
mov    %rax,(out)        #out=0
mov    (tmp),%rdx        #rdx=0
lea    0x0(,%rdx,8),%rax #rax=0
sub    %rdx,%rax         #rax=0
add    %rsi,%rax         #rax=0
mov    %rax,(tmp)        #tmp=0

Thread 1

mov    (out),%rdx        #rdx=0
mov    (tmp),%rcx        #rcx=0
lea    0x0(,%rdx,8),%rax #rax=0
sub    %rdx,%rax         #rax=0
add    %rcx,%rax         #rax=0
mov    %rax,(out)        #out=0
mov    (tmp),%rdx        #rdx=0
lea    0x0(,%rdx,8),%rax #rax=0
sub    %rdx,%rax         #rax=0
add    %rsi,%rax         #rax=1
mov    %rax,(tmp)        #tmp=1

Case #1

The relative speed between the two clocks is different than zero. CPU 0 executed the above instructions at a speed of: 2.1111111 GHz CPU 1 executed the above instructions at a speed of: 2.0999999 GHz Relative speed between the two clocks: 0,0111112 GHz

CPU 0 were faster and CPU 1 where slower. tmp=0 was written before tmp=1. Hence the final result is: tmp=1

Case #2

Relative speed between the two clocks is exactly zero.

CPU 0 executed the above instructions at a speed of: 2.1111111 GHz CPU 1 executed the above instructions at a speed of: 2.1111111 GHz Relative speed between the two clocks: 0 GHz

CPU 0 and CPU 1 wrote a different value at the same time, what put the last bit of tmp on a superposition state. It is 1 and 0 at the same time. This superposition may live for one planck time or until its value is read by thread 0, thread 1 or thread 2.

Thread 2

while(true)
  cout.write((char*)&out,sizeof(out));

It is also possible, that gravitational waves caused by the flow of energy inside the CPUs produce small time dilations.

Desynchronization

mov    (out),%rdx        #out may be changed by the other thread
mov    (tmp),%rcx        #tmp may be changed by the other thread
lea    0x0(,%rdx,8),%rax
sub    %rdx,%rax
add    %rcx,%rax
mov    %rax,(out)        #out may never be read
mov    (tmp),%rdx        #tmp may be changed by the other thread
lea    0x0(,%rdx,8),%rax
sub    %rdx,%rax
add    %rsi,%rax
mov    %rax,(tmp)        #tmp may never be read
\$\endgroup\$
  • \$\begingroup\$ These days, code is as likely to run inside a virtual machine as it is to run bare-metal. Do your claims hold for virtual CPUs? \$\endgroup\$ – 200_success Jul 8 '15 at 17:50
-5
\$\begingroup\$

This is a continuation of the last answer.

The thermodynamic entropy, produced by the CPUs energetic inefficiency, impacts on physical properties, such as size, due to the thermal expansion, and resistance, due to small variations of temperature. The results of the data races depends on the exact speed of the CPUs, which depends on the physical state of the CPUs.

The time is crucial to determine the result of a data race. When did thread 0 start to change the address 0x01? Which value had that memory address in that moment? Which was the state of thread 1? Which was the exact speed of thread 0 and thread 1? Which was the exact thermodynamic entropy of CPU 0 and CPU 1? Which was the exact conductance of each CPU circuit? Which was the exact frequency of computer's oscillators? Thanks to the uncertainty principle, these questions are theoretically impossible to answer. The smallest attempt to check the CPUs states will change the CPUs states. It is possible to know which state had the CPU, but it is not possible to know the current state. It is possible to know what happened, but it is not possible to know what is happening. How are you going to know the exact position of each electron without changing its position?

This implementation of CPU jitter also depends on the exact speed of the CPU. The jitter deviation occurs when the real speed of the CPU is confronted with the real time clock of the PC. The randomness happens when one or both rates of change have small variations, impacting on the amount of iterations of the linear congruential generator before the number is read. In other words, the randomness occurrs thanks to small changes of the relative speed between two clocks. One is supposed to have always the same speed, the real time clock, while the other changes slightly with the simple action of making the CPU execute one single instruction.

The thermodynamic entropy is used to produce informatic entropy.

\$\endgroup\$
-10
\$\begingroup\$

These codes generate true random numbers because:

  1. They implement a linear congruential generator, which generate pseudo-random numbers.
  2. Unpredictable data races upgrades the pseudo-randomness into true-randomness.
  3. CPU time jitter upgrades the pseudo-randomness into true-randomness.

The CPUs are physical sources of entropy. Due to their energetic inefficiency, when executing a single instruction, they produce entropy, which is finally exchanged to the environment through the heatsink. This entropy impacts on the results of time jitter and data races.

To predict a number it is required to know the complete current state of the whole system, what is impossible thanks to the uncertainty principle.

(Naming the version for more than two CPUs normal, for two CPUs openmp and for one CPU paused)

The normal and paused versions offer better results when they are executed with higher priority, low workloads or by shielded CPUs, because this avoids, that the numbers remain unchanged for large sequences.

The quality of them differ:

  • normal.cpp: Offers the best performance and generate true random numbers thanks to data races.
  • openmp.cpp: Offers a high-performance alternative for computers with two CPUs, which also generate true random numbers thanks to data races.
  • paused.cpp: Offers the best quality despite the lowest performance. This generate true random numbers thanks to data races when is executed by at least two CPUs and time jitter by one or more CPUs.

The numbers are like cats of Schrödinger's paradox. They are undefined until they are read.

References

CPU Time Jitter Based Non-Physical True Random Number Generator

Software Random Number Generation Based on Race Conditions

\$\endgroup\$
  • 1
    \$\begingroup\$ To anyone who might want to delete this answer: Being wrong and being an answer are two different things. There is no real reason to delete this answer. \$\endgroup\$ – Simon Forsberg Jul 4 '15 at 21:26
  • \$\begingroup\$ @SimonAndréForsberg They delete it, because they want to avoid the spread of knowledge. The answer is here. \$\endgroup\$ – ncomputers Jul 4 '15 at 21:31
  • 4
    \$\begingroup\$ 1. This code does not implement a LCG (it would only do that if the thread wasn't interrupted). 2. The data races are predictable. 3. That's 2 using the name I just taught you. 4. There is no “uncertainty principle” involved in the operation of a CPU. \$\endgroup\$ – Gilles 'SO- stop being evil' Jul 4 '15 at 21:32
  • 1
    \$\begingroup\$ @ncomputers.org This answer has 1 delete vote, three are needed. I don't think it will be deleted, but be prepared for downvotes. And no one is delete-voting for preventing the spreading of knowledge. People are down-voting however because they're trying to prevent wrong knowledge. \$\endgroup\$ – Simon Forsberg Jul 4 '15 at 21:35
  • 4
    \$\begingroup\$ I've voted to undelete this answer; I would suggest to combine your posts into a single one, and delete the others. \$\endgroup\$ – Mathieu Guindon Jul 8 '15 at 19:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.