Randomness in .NET

There are various situations when you need random data in your application. Maybe you want to mix the order of the returned items, or maybe you create nonces for your encrypted messages. Those two sample scenarios require different approaches, and while choosing a non-cryptographic PRNG works just fine in the first situation, using it in the latter is entirely wrong. You may be wondering what a non-cryptographic PRNG is. A PRNG, or pseudorandom number generator, is an algorithm for generating a sequence of numbers whose properties almost equal to the properties of sequences of random numbers. The way how the algorithm creates these sequences could be either cryptographically secure (cryptographic PRNG) or not (non-cryptographic PRNG). A non-cryptographic PRNG cares only about the uniform distribution of random bits and not about their predictability. As we will see in a moment, using the same seed twice in the Non-crypto PRNG, results in two sequences of bytes equal to each other. Cryptographic PRNGs, on the other hand, provide random bits but are also unpredictable. In the coming paragraphs, we will examine in detail the ways we use PRNGs in .NET.

Non-cryptographic PRNGs

System.Random is the .NET class which implements the non-cryptographic PRNG. As we can read in the docs:

The current implementation of the Random class is based on a modified version of Donald E. Knuth’s subtractive random number generator algorithm. For more information, see D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, third edition, 1997.

As a side note, there is a subtle bug in the implementation, which probably causes a statistical bias in the results. The discussion on GitHub and linked materials are an interesting read if you want to learn more.

The algorithm used in the .NET Core is the same as in the .NET Framework and, when seeded with the same value, returns the same sequences of numbers. There is a difference, however, when we use the default constructor.

The default seed value in the .NET Framework implementation is equal to the value of the Environment.TickCount property. Its resolution is limited to the resolution of the system timer (typically in the range of 10 to 16 ms). Thus, using Environment.TickCount has an unfortunate consequence if you create multiple instances of the Random class at once, for example, the code:

Action a = () => {
    var rnd = new Random();
    var n = rnd.Next();
    Console.WriteLine($"{Thread.CurrentThread.ManagedThreadId}: {n}");
};

for (int i = 0; i < 4; i++) {
    Task.Run(a);
}

Console.ReadKey();

will most probably return four times the same number. On my machine I got:

6: 1258418122
19: 1258418122
14: 1258418122
20: 1258418122

To resolve this problem you may share an instance of the Random class, but it requires locking, as Random is not thread-safe. Alternatively, you may pick a safe value for the seed parameter. If you wonder what the safe value could be, the .NET Core source code could help.

The default seed value in the .NET Core implementation is generated in two steps. Firstly, the runtime creates a new thread-local instance of the Random class (t_threadRandom) using as a seed the result of the call to the Next method of the global Random class instance (g_globalRandom). Secondly, the runtime calls the Next method of the thread-local instance to create the final seed value. The snippet from the .NET Core source code implementing this logic looks as follows:

public class Random
{
    public Random() : this(Random.GenerateSeed())
    {
    }
    ...
    private static int GenerateSeed()
    {
        Random random = Random.t_threadRandom;
        if (random == null)
        {
            Random obj = Random.s_globalRandom;
            int seed;
            lock (obj)
            {
                seed = Random.s_globalRandom.Next();
            }
            random = new Random(seed);
            Random.t_threadRandom = random;
        }
        return random.Next();
    }
    ...
    [ThreadStatic]
    private static Random t_threadRandom;

    private static readonly Random s_globalRandom = new Random(Random.GenerateGlobalSeed());
}

You may be curious what is the seed value of the global Random class instance. To create it, .NET Core uses a cryptographically secure PRNG (BCrypt on Windows, OpenSSL on *nix) and a byte array of length four. After the call, the bytes in the array contain random values, which are later converted to an integer and serve as the seed of the global Random class instance. Here is a simple diagram to show you the relations between various Random instances involved:

Predictability of System.Random

So we heard that System.Random is predictable, but what does this statement imply. Let’s write a simple application using the Random class:

using System;

namespace RandomApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var rnd = new Random();

            while (true)
            {
                Console.WriteLine($"Random: {rnd.Next()}");
                Console.ReadKey();
            }
        }
    }
}

Next, let’s start it and press any key three times. We should receive three random numbers on the output, in my case:

Random: 1926603654
Random: 1395823328
Random: 2012846163

Time to attach a debugger and record the internal state of the Random instance. We start by loading the SOS plugin and finding our Random class instance:

0:006> .loadby sos clr
0:006> !dumpheap -type System.Random
PDB symbol for clr.dll not loaded
c0000005 Exception in C:\Windows\Microsoft.NET\Framework\v4.0.30319\sos.dumpheap debugger extension.
      PC: 0965fa73  VA: 00000000  R/W: 0  Parameter: 00000000

0:006> !dumpheap -type System.Random
 Address       MT     Size
03302488 715735e4       20     

Statistics:
      MT    Count    TotalSize Class Name
715735e4        1           20 System.Random

0:006> !dumpobj 03302488
Name:        System.Random
MethodTable: 715735e4
EEClass:     711176d0
Size:        20(0x14) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
      MT    Field   Offset                 Type VT     Attr    Value Name
7152f2dc  40005e3        8         System.Int32  1 instance        3 inext
7152f2dc  40005e4        c         System.Int32  1 instance       24 inextp
7152f2a0  40005e5        4       System.Int32[]  0 instance 0330249c SeedArray

Let’s dump the values of the inext and inextp fields (offsets are from the dumpobj output):

0:006> dd 03302488+8 L1; * value of the inext field
03302490  00000003
0:006> dd 03302488+c L1; * value of the inextp field
03302494  00000018

We also need the SeedArray (we use the 8-byte offset to skip the Method Table and the field holding the size of the array):

0:006> dd 0330249c+0x8 L0n58
033024a4  00000000 72d5a386 533292e0 77f99853
033024b4  45b5249a 190a3cdd 67b95935 17dde999
033024c4  4d7130ad 7fc39353 6a5ff75e 1ce681e4
033024d4  670034ab 6229ac74 31884d2e 710e234f
033024e4  4aa52493 529dea8d 516824e7 042a117d
033024f4  38250b90 3e5d6df8 3d9b11b6 4cf87030
03302504  31143aa7 1c59b4e6 54f317f2 7ad6d9b5
03302514  3dfae557 5fc18116 0a0077ad 7fbddafe
03302524  314ad324 357ab207 51c07c7a 6ba2d338
03302534  4d9abfb5 52040a2d 7cead921 3c457bdb
03302544  29501b17 736e2a61 254e4277 33ef4a79
03302554  164801bb 2c0c82b5 549be47b 29f4ea82
03302564  2cf05185 2db171b0 05e747b2 6b2bc62d
03302574  779da6ef 1ca59b6c 19e4a90f 259e628b
03302584  00000000 7152f2dc

Having recorded those values, we are ready to write an “oracle” application:

var rnd = new Random();

var fld = rnd.GetType().GetField("inext", BindingFlags.NonPublic | BindingFlags.Instance);
fld.SetValue(rnd, 0x3);

fld = rnd.GetType().GetField("inextp", BindingFlags.NonPublic | BindingFlags.Instance);
fld.SetValue(rnd, 0x18);

var newSeedArray = new int[] {
0x00000000, 0x72d5a386, 0x533292e0, 0x77f99853,
0x45b5249a, 0x190a3cdd, 0x67b95935, 0x17dde999,
0x4d7130ad, 0x7fc39353, 0x6a5ff75e, 0x1ce681e4,
0x670034ab, 0x6229ac74, 0x31884d2e, 0x710e234f,
0x4aa52493, 0x529dea8d, 0x516824e7, 0x042a117d,
0x38250b90, 0x3e5d6df8, 0x3d9b11b6, 0x4cf87030,
0x31143aa7, 0x1c59b4e6, 0x54f317f2, 0x7ad6d9b5,
0x3dfae557, 0x5fc18116, 0x0a0077ad, 0x7fbddafe,
0x314ad324, 0x357ab207, 0x51c07c7a, 0x6ba2d338,
0x4d9abfb5, 0x52040a2d, 0x7cead921, 0x3c457bdb,
0x29501b17, 0x736e2a61, 0x254e4277, 0x33ef4a79,
0x164801bb, 0x2c0c82b5, 0x549be47b, 0x29f4ea82,
0x2cf05185, 0x2db171b0, 0x05e747b2, 0x6b2bc62d,
0x779da6ef, 0x1ca59b6c, 0x19e4a90f, 0x259e628b, 
0x00000000, 0x7152f2dc
};

fld = rnd.GetType().GetField("SeedArray", BindingFlags.NonPublic | BindingFlags.Instance);
fld.SetValue(rnd, newSeedArray);

while (true)
{
    Console.WriteLine($"Predicted RANDOM: {rnd.Next()}");
    Console.ReadKey();
}

As you can see in the listening, we restore the state of the Random class with the help of the reflection. Now, it’s time to test our code. After pressing space three more times in the original app I got:

Random: 1926603654
Random: 1395823328
Random: 2012846163
Random: 693858228
Random: 1142367466
Random: 1826783103

And in the “oracle” app:

Predicted RANDOM: 693858228
Predicted RANDOM: 1142367466
Predicted RANDOM: 1826783103

The last three values are equal which proves that our code works! 🙂 Another way of “guessing” the random number sequence would be to decrement the Environment.TickCount value till we receive the same number sequence as in the original application. This approach, of course, works only in the .NET Framework (as you remember .NET Core uses a different approach to the default seed generation). The code below presents the idea:

void Main()
{
    var rnd = new Random();

    var sequence = new int[20];
    for (int i = 0; i < sequence.Length; i++) {
        sequence[i] = rnd.Next();
    }

    Thread.Sleep(500);

    Console.WriteLine("Found seed: {0}", FindSeed(sequence));
}

// Define other methods and classes here
public int FindSeed(int[] sequence) {
    var seed = Environment.TickCount;

    bool invalid = true;
    while (invalid && seed > 0) {
        var rnd = new Random(--seed);

        invalid = false;
        for (int i = 0; i < sequence.Length; i++) {
            if (sequence[i] != rnd.Next()) {
                invalid = true;
                break;
            }
        }
    }

    return seed;
}

Cryptographic PRNGs

To get full randomness, cryptographic PRNGs use:

• a source of entropy, which is called a random number generator (RNG), and usually comes from the environment
• a cryptographic algorithm (PRNG) to produce high-quality random bits

PRNG generates random-looking bits using RNG, which is truly random. As PRNG is deterministic, without RNG, its output would be predictable. Cryptographic PRNG guarantees forward and backward secrecy – the previously generated bits are impossible to recover, and future bits are impossible to predict.

To create cryptographically secure random numbers in .NET (both Full and Core) we should use the RNGCryptoServiceProvider class. All implementations of this class rely on interop calls to native libraries. The .NET Framework on Windows uses the CryptGenRandom function, whereas the .NET Core on Windows uses the BCryptGenRandom function (a part of the Cryptography API: Next Generation) and on Linux the RAND_bytes function from the OpenSSL library.

RNGCryptoServiceProvider is generally a safer choice when you need to generate random bytes. Creating an instance of this class is expensive, so it’s better to populate a 400-byte array than call the constructor 100 times to populate a 4-byte array.

Conclusion

I hope you find this post informative. There is a lot more to say about random number generation, and you can find a chapter dedicated to it in any cryptographic book. A great example of such a book is “Serious Cryptography” by Jean-Philippe Aumasson. I am reading it right now and enjoying it. Also, last year Syncfusion published a free ebook “Application Security in .NET Succinctly” by Stan Drapkin which contains many recipes how to write secure code in .NET. It focuses mainly on the .NET Framework, but most chapters hold true for the .NET Core too.