c# - .NET Framework: Random number generator produces repeating pattern

Question

EDIT: This is not a duplicate, and it's not a result of a naive misunderstanding of how to use a random number generator. Thanks.

I seem to have discovered a repeating pattern in the numbers generated by the System.Random class. I am using a "master" Random instance to generate a seed for a second "main" Random instance. The values produced by this main Random instance exhibit a repeating pattern. In particular, the 3rd number produced is very predictable.

The program below demonstrates the problem. Note that a different seed value is used each time through the loop.

using System;

class Program
{
    static void Main(string[] args)
    {
            // repeat experiment with different master RNGs
        for (int iMaster = 0; iMaster < 30; ++iMaster)
        {
                // create master RNG
            var rngMaster = new Random(iMaster + OFFSET);

                // obtain seed from master RNG
            var seed = rngMaster.Next();

                // create main RNG from seed
            var rngMain = new Random(seed);

                // print 3rd number generated by main RNG
            var ignore0 = rngMain.Next(LIMIT);
            var ignore1 = rngMain.Next(LIMIT);
            var randomNumber = rngMain.Next(LIMIT);
            Console.WriteLine(randomNumber);
        }
    }

    const int OFFSET = 0;
    const int LIMIT = 200;
}

I think this should produce random output, but the actual output on my box is:

84
84
84
84
84
84
84
84
84
84
84
...

Can anyone explain what's going on here? Changing the OFFSET and LIMIT constants changes the output value, but it's always repeating.

Answer 1

Welcome to the world of non cryptographically strong RNGs. Apparently the built in .NET RNG has a tendency to make the 3rd number it outputs 84 if you limit it to 0 to 200 for its outputs. Take a look at the following version of the program, it shows more of what is going on in the output.

class Program
{
    static void Main(string[] args)
    {
        Console.WindowWidth = 44;
        Console.WindowHeight = 33;
        Console.BufferWidth = Console.WindowWidth;
        Console.BufferHeight = Console.WindowHeight;

        string template = "|{0,-5}|{1,-11}|{2,-5}|{3,-5}|{4,-5}|{5,-5}|";
        Console.WriteLine(template, "s1", "s2", "out1", "out2", "out3", "out4");
        Console.WriteLine(template, new String('-', 5), new String('-', 11), new String('-', 5), new String('-', 5), new String('-', 5), new String('-', 5));

        // repeat experiment with different master RNGs
        for (int iMaster = 0; iMaster < 30; ++iMaster)
        {
            int s1 = iMaster + OFFSET;
            // create master RNG
            var rngMaster = new Random(s1);

            // obtain seed from master RNG
            var s2 = rngMaster.Next();

            // create main RNG from seed
            var rngMain = new Random(s2);

            var out1 = rngMain.Next(LIMIT);
            var out2 = rngMain.Next(LIMIT);
            var out3 = rngMain.Next(LIMIT);
            var out4 = rngMain.Next(LIMIT);
            Console.WriteLine(template, s1, s2, out1, out2, out3, out4);
        }

        Console.ReadLine();
    }

    const int OFFSET = 0;
    const int LIMIT = 200;
}

Here is the output

|s1   |s2         |out1 |out2 |out3 |out4 |
|-----|-----------|-----|-----|-----|-----|
|0    |1559595546 |170  |184  |84   |84   |
|1    |534011718  |56   |177  |84   |123  |
|2    |1655911537 |142  |171  |84   |161  |
|3    |630327709  |28   |164  |84   |199  |
|4    |1752227528 |114  |157  |84   |37   |
|5    |726643700  |0    |150  |84   |75   |
|6    |1848543519 |86   |143  |84   |113  |
|7    |822959691  |172  |136  |84   |151  |
|8    |1944859510 |58   |129  |84   |189  |
|9    |919275682  |144  |122  |84   |28   |
|10   |2041175501 |30   |115  |84   |66   |
|11   |1015591673 |116  |108  |84   |104  |
|12   |2137491492 |2    |102  |84   |142  |
|13   |1111907664 |88   |95   |84   |180  |
|14   |86323836   |174  |88   |84   |18   |
|15   |1208223655 |60   |81   |84   |56   |
|16   |182639827  |146  |74   |84   |94   |
|17   |1304539646 |31   |67   |84   |133  |
|18   |278955818  |117  |60   |84   |171  |
|19   |1400855637 |3    |53   |84   |9    |
|20   |375271809  |89   |46   |84   |47   |
|21   |1497171628 |175  |40   |84   |85   |
|22   |471587800  |61   |33   |84   |123  |
|23   |1593487619 |147  |26   |84   |161  |
|24   |567903791  |33   |19   |84   |199  |
|25   |1689803610 |119  |12   |84   |38   |
|26   |664219782  |5    |5    |84   |76   |
|27   |1786119601 |91   |198  |84   |114  |
|28   |760535773  |177  |191  |84   |152  |
|29   |1882435592 |63   |184  |84   |190  |

So there are some strong correlations between the first output of the master RND and the first few outputs of a second RNG that was chained off of the first. The Random RNG is not designed to be "secure" it is designed to be "fast", so things like what you are seeing here are the tradeoffs between being fast and secure. If you don't want things like this to happen you need to use a cryptographicly secure random number generator.

However just switching to a Cryptographic Random Number Generator (CRNG) is not enough you still need to be careful how you use the CRNG. A very similar problem happened with WEP wireless security. Depending on what IV was given in the header it was possible to predict what the seed value (the WEP key) for the random number generator was used to protect the connection. Although they used a CRNG (they used RC4) they did not use it correctly (you have to spit out a few 1000 iterations before the output becomes non predictable).