Nondeterministic Random Number Generation

• Download source (no EXE) - 101.8 KB
• Download source - 101.8 KB

Introduction

The provided C# WPF .NET solution generates truly random numbers in a nondeterministic manner. These are most useful in cryptography and help protect against side-channel attacks. Although this solution was developed targeting an Intel multi-processor, targeting a machine with a single processor may produce different results.

What is a random number sequence?

For example (as the editor was kind enough to point out):

"314159......." is an example of the output from a deterministic routine for producing random numbers (if indeed, it is using an algorithm for producing digits of the value of pi). Most random number generators are of these types; they use a specific mathematical formula and usually require a "seed" value (quite commonly the system timer is used).

What are the problems with using deterministic routines for producing random values? In cryptography, if the algorithm used is already known, then the random values can be reproduced just by knowing what the initial seed of the generator is. Why is this a problem? Well, it's quite common to use random number generators for generating secret "keys".

So how do we create nondeterministic random values? Quite simply, we have to resort to either non-algorithmic approaches (such as white noise sampling) or producing our own nondeterministic algorithm.

From the Wiki article:

"A concurrent algorithm can perform differently on different runs due to a race condition."

Here, I present a class which does just that:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace randTesting
{
    /// <summary>
    /// Random byte generator
    /// </summary>
    public class RandomBytes
    {
        static volatile int v = 0;
        /// <summary>
        /// Creates the requested number of random bytes
        /// </summary>
        /// <param name="count"></param>
        /// <returns></returns>
        public static List<byte> GenerateBytes(int count)
        {
            List<byte> resbytes = new List<byte>();
            List<Thread> threadList = new List<Thread>();

            //get the number of processors on this os
            var pcount = Environment.ProcessorCount == 1 ? 2 : Environment.ProcessorCount;

            //initialize our bit value
            v = 1;

            //create a few threads
            for (int i = 0; i < pcount; i++)
            {
                var ts = new ThreadStart(mashup);
                var thd = new Thread(ts);
                thd.Start();
                threadList.Add(thd);
            }

            //wait on them to start up
            while (threadList.Any(a => a.ThreadState != ThreadState.Running));

            string bts = "";

            while (count > 0)
            {
                System.Threading.Thread.Sleep(5);
                int res = 0;
                if (v == 1) res = 1;
                bts += res;
                if (bts.Length == 8)
                {
                    int val = 0;
                    for (int x = 0; x < 8; x++)
                    {
                        val += (int)(Math.Pow((double)2, (double)x) * int.Parse(bts.Substring(x, 1)));
                    }
                    bts = "";

                    //add the byte value
                    resbytes.Add((byte)val);
                    count--;
                }
            }

            //thread cleanup
            threadList.ForEach(thd =>
                {
                    try
                    {
                        thd.Abort();
                    }
                    catch { }
                });

            return resbytes;
        }

        static void mashup()
        {
            while (true)
            {
                v *= -1;
            }
        }
    }
} 

Background

I've often wondered about the ability of a computer to generate truly random values. One approach that came to mind was to cause the processors to constantly "fight" over the same shared memory until paused and read. This is known as creating a "race condition". If sufficient amount of time is allowed to pass, the value in the shared memory location should be unknown, or random, since only the OS controls how much time is allotted to each processor.

Using the Code

The RandomBytes.cs file contains method "GenerateBytes" which returns the specified number of random bytes requested.

var bytes = RandomBytes.GenerateBytes(20);

Here's an example of 100 random bytes generated using this call:

220,252,230,230,105,62,1,101,143,95,78,243,215,3,95,45,66,33,160,29
114,147,147,39,12,68,249,95,59,225,86,237,95,190,91,79,160,214,169,105
29,218,77,54,12,246,244,101,204,158,95,169,249,104,41,128,251,33,79,20
124,247,207,53,216,129,222,74,161,214,247,94,179,229,103,22,184,213,14,132
43,15,130,147,207,27,77,47,196,111,143,94,197,177,67,65,81,202,126,157
51,176,166,171,137,111,227,171,151,206,150,218,23,37,74,37,20,95,204,226

Points of Interest

1. The pause (of 5 milliseconds) while looping and sampling the variable (v) might need to be adjusted depending on the speed of the target machine.
2. This processor: Intel Core I7, 2201 Mhz, 4 Cores
3. Used to seed deterministic (or pseudo random number generators)
4. Aperiodic
5. Poor Efficiency

A lot of people seem confused by all of the different random number generators available - and with good reason, too. Most RNGs (and apparently, some GUID generators) work by seeding themselves (a.k.a. conditioning) with a nondeterministic number generator and then are used to produce deterministic values (for a more efficient and perfect distribution). For the nondeterministic part, most use the mashing of a high speed timer and/or X and Y movements of the mouse. Some even use hashing of screen captures.

Also, I get a lot of questions about what Microsoft does. So, as for Microsoft's cryptographic random number generator:

http://en.wikipedia.org/wiki/CryptGenRandom[^]

Notice that the algorithm (or DETERMINISTIC) part isn't even published. However, the timer mashing (or NONDETERMINISTIC) part is clearly hinted at.

Thank you everybody for your comments and for helping me build a better article.

Some References

• http://www.random.org/randomness/
• http://en.wikipedia.org/wiki/Nondeterministic_algorithm
• http://en.wikipedia.org/wiki/Race_condition