Why use the C# class System.Random at all instead of System.Security.Cryptography.RandomNumberGenerator?

Question

Why would anybody use the "standard" random number generator from System.Random at all instead of always using the cryptographically secure random number generator from System.Security.Cryptography.RandomNumberGenerator (or its subclasses because RandomNumberGenerator is abstract)?

Nate Lawson tells us in his Google Tech Talk presentation "Crypto Strikes Back" at minute 13:11 not to use the "standard" random number generators from Python, Java and C# and to instead use the cryptographically secure version.

I know the difference between the two versions of random number generators (see question 101337).

But what rationale is there to not always use the secure random number generator? Why use System.Random at all? Performance perhaps?

Solution 1

Speed and intent. If you're generating a random number and have no need for security, why use a slow crypto function? You don't need security, so why make someone else think that the number may be used for something secure when it won't be?

Solution 2

Apart from the speed and the more useful interface (NextDouble() etc) it is also possible to make a repeatable random sequence by using a fixed seed value. That is quite useful, amongst others during Testing.

Random gen1 = new Random();     // auto seeded by the clock
Random gen2 = new Random(0);    // Next(10) always yields 7,8,7,5,2,....

Solution 3

First of all the presentation you linked only talks about random numbers for security purposes. So it doesn't claim Random is bad for non security purposes.

But I do claim it is. The .net 4 implementation of Random is flawed in several ways. I recommend only using it if you don't care about the quality of your random numbers. I recommend using better third party implementations.

Flaw 1: The seeding

The default constructor seeds with the current time. Thus all instances of Random created with the default constructor within a short time-frame (ca. 10ms) return the same sequence. This is documented and "by-design". This is particularly annoying if you want to multi-thread your code, since you can't simply create an instance of Random at the beginning of each thread's execution.

The workaround is to be extra careful when using the default constructor and manually seed when necessary.

Another problem here is that the seed space is rather small (31 bits). So if you generate 50k instances of Random with perfectly random seeds you will probably get one sequence of random numbers twice (due to the birthday paradox). So manual seeding isn't easy to get right either.

Flaw 2: The distribution of random numbers returned by Next(int maxValue) is biased

There are parameters for which Next(int maxValue) is clearly not uniform. For example if you calculate r.Next(1431655765) % 2 you will get 0 in about 2/3 of the samples. (Sample code at the end of the answer.)

Flaw 3: The NextBytes() method is inefficient.

The per byte cost of NextBytes() is about as big as the cost to generate a full integer sample with Next(). From this I suspect that they indeed create one sample per byte.

A better implementation using 3 bytes out of each sample would speed NextBytes() up by almost a factor 3.

Thanks to this flaw Random.NextBytes() is only about 25% faster than System.Security.Cryptography.RNGCryptoServiceProvider.GetBytes on my machine (Win7, Core i3 2600MHz).

I'm sure if somebody inspected the source/decompiled byte code they'd find even more flaws than I found with my black box analysis.

---

Code samples

r.Next(0x55555555) % 2 is strongly biased:

Random r = new Random();
const int mod = 2;
int[] hist = new int[mod];
for(int i = 0; i < 10000000; i++)
{
    int num = r.Next(0x55555555);
    int num2 = num % 2;
    hist[num2]++;
}
for(int i=0;i<mod;i++)
    Console.WriteLine(hist[i]);

Performance:

byte[] bytes=new byte[8*1024];
var cr=new System.Security.Cryptography.RNGCryptoServiceProvider();
Random r=new Random();

// Random.NextBytes
for(int i=0;i<100000;i++)
{
    r.NextBytes(bytes);
}

//One sample per byte
for(int i=0;i<100000;i++)
{   
    for(int j=0;j<bytes.Length;j++)
      bytes[j]=(byte)r.Next();
}

//One sample per 3 bytes
for(int i=0;i<100000;i++)
{
    for(int j=0;j+2<bytes.Length;j+=3)
    {
        int num=r.Next();
        bytes[j+2]=(byte)(num>>16);   
        bytes[j+1]=(byte)(num>>8);
        bytes[j]=(byte)num;
    }
    //Yes I know I'm not handling the last few bytes, but that won't have a noticeable impact on performance
}

//Crypto
for(int i=0;i<100000;i++)
{
    cr.GetBytes(bytes);
}

Solution 4

System.Random is much more performant since it does not generate cryptographically secure random numbers.

A simple test on my machine filling a buffer of 4 bytes with random data 1,000,000 times takes 49 ms for Random, but 2845 ms for RNGCryptoServiceProvider. Note that if you increase the size of the buffer you are filling, the difference narrows as the overhead for RNGCryptoServiceProvider is less relevant.

Solution 5

The most obvious reasons have already been mentioned, so here's a more obscure one: cryptographic PRNGs typically need to be continually be reseeded with "real" entropy. Thus, if you use a CPRNG too often, you could deplete the system's entropy pool, which (depending on the implementation of the CPRNG) will either weaken it (thus allowing an attacker to predict it) or it will block while trying to fill up its entropy pool (thus becoming an attack vector for a DoS attack).

Either way, your application has now become an attack vector for other, totally unrelated applications which – unlike yours – actually vitally depend on the cryptographic properties of the CPRNG.

This is an actual real world problem, BTW, that has been observed on headless servers (which naturally have rather small entropy pools because they lack entropy sources such as mouse and keyboard input) running Linux, where applications incorrectly use the /dev/random kernel CPRNG for all sorts of random numbers, whereas the correct behavior would be to read a small seed value from /dev/urandom and use that to seed their own PRNG.

View more solutions

Comments

[Macha]

Which would you rather type?

[Mark Sowul]

Too many people seriously use that as a justification for what they do (usually not out loud). Code is read more than it's written, who cares about trivial length differences?

[Mark Sowul]

But anyway why should you use cryptographic RNGs if you are not doing cryptography?

[cchamberlain]

@Macha, that's what aliases are for -> using R = System.Security.Cryptography.RandomNumberGenerator; R.Create();

[Lernkurve]

I very much like the intent argument.

[Lernkurve]

Thank you for demonstrating it with an actual test.

[Sergey Mirvoda]

it all about entropy generation and speed

[Lernkurve]

I read the Wikipedia article and some other Internet sources on entropy and entropy depletion, and I don't quite understand it. How can I be depleting the entropy pool when the random number generator is fed with system time, number of free bytes etc.? How can others use it as a attack vector to predict random numbers? Can you provide an easy example? Perhaps this discussion must be taken offline. en.wikipedia.org/wiki/Entropy_%28computing%29

[Luis Vito]

System time is not an entropy source, because it's predictable. I'm not sure about the number of free bytes, but I doubt it's a high-quality entropy source either. By sending more requests to the server, the attacker can cause the number of free bytes to decrease, making it partially deterministic. You application becomes an attack vector because by depleting the entropy pool, it forces the other, security-critical application to use less-random random numbers -- or wait until the entropy source is replenished.

[sisve]

And there's the BitConverter.ToInt32(Byte[] value, int startIndex) which may be easier to understand. ;)

[Aditya Sinha]

I think you are wrong about your magnitudes; sending financial data needs to be extremely quick; if your trading algorithm can get to the result 0.1ms quicker than the competition, you end up better in the queue of buy/sell/stop-loss/quote commands. 3 seconds is an eternity. This is why traders invest in insanely good computers. See the previous answer; Crypt.RNG takes only 0,0028 ms per new number; 0.0000028 seconds, so you are off by 9 orders of magnitude in terms of how much processing it takes, and also on how important speed is.

[Daniel James Bryars]

Ian Bell and David Braben used a random generator in the computer game Elite to create a vast list of planets and their attributes (size, etc), with very limited memory. This also relies on the generator creating a deterministic pattern (from a seed) - which the Crypto one obviously doesn't provide (by design.) There's some more information on how they did it here: wiki.alioth.net/index.php/Random_number_generator and the book "Infinite Game Universe: Mathematical Techniques" ISBN:1584500581 has a more general discussion on such techniques.

[Kristoffer L]

It should be noted that Random.GetNext is far from good at "spreading" the random numbers over the spectrum, especially in a threaded environment. I ran across this problem when writing a program to test different solutions to the Rand7 from Rand5 problem. In a quick threaded test just now of 100000 random numbers between 0 and 10, 82470 of the generated numbers were 0. I saw similar discrepancies in my previous tests. Crytpography random is very even in its distribution of numbers. I guess the lesson is to always test your random data to see that it is "random enough" for your needs.

[CodesInChaos]

@Kristoffer I think you misused Random. Let me guess: You created a new instance of the Random class for each number, which since it's seeded by a coarse timer will be seeded with the same value for an interval of about 1-16ms.

[Kristoffer L]

@CodeInChaos Not at all. I was merely running the test in a multi-threaded environment. It does not always screw up the resuls, but the outcome is quite unpredictable (in a bad way, even if we are talking about random. :P)

[BlueRaja - Danny Pflughoeft]

@CodesInChaos: Besides that, there is a race-condition with Random that causes it to return all 0's when the same object is used from multiple threads.

[BlueRaja - Danny Pflughoeft]

@KristofferL: See above comment, also see this answer

[supercat]

I understand that if one has a pseudo-random generator fed with e.g. a 32-bit seed, a brute-force attack will often be fairly easy; even a 64-bit seed may be subject to birthday attacks. Once the seed gets much larger than that, though, I don't quite see the risk. If one has a random generator which for each byte of output takes passes a 128-bit state through a block encryption algorithm and then outputs the bottom 8 bits, how could an attacker even with gigs of consecutive output bytes infer the state, absent weaknesses in the encryption algorithm itself?

[Roman Starkov]

Do keep in mind that MSDN does not guarantee this property to hold across .NET versions: "The implementation of the random number generator in the Random class is not guaranteed to remain the same across major versions of the .NET Framework."

[citykid]

Interesting, can confirm your finding: on my machine Next(1431655765) also gives 2/3 with any seeding. What is the magic of 1431655765? How did you arrive at this number?

[CodesInChaos]

@citykid Look at the number as hex or bits. It's magic arises from the dubious way Random uses to transform a 31 bit integer into a number with the specified upper bound. I forgot the details, but it's something like randomValue * max / 2^{31}.

[CodesInChaos]

My first guess is that you recreated Random too often. It should only be created once calling Next on that instance many times. Random is bad, but not that bad. Can you post a sample program along with a pair of seeds that exhibits this problem?

[Tim S.]

1431655765_10 = 1010101010101010101010101010101_2

[Traderhut Games]

The code would create a Random() at the beginning of each level (but it was a major problem with level 1 more than later ones) The code was roughly as follows:

[Traderhut Games]

Rnd = new Random ((uint)GameSeed); NextGameSeed = Rnd.Next (2000000000); Each level used a new Random that was created with a new seed - The Seed was saved for each level so I would be able to recreate the map, and also confirm the sequence of random seeds matched. This allows me to confirm that the game is a valid series of maps that have been solved and recreate the game.

[Traderhut Games]

And Initially, Random was created based on System.DateTime.Now.Ticks (or 0), and then the GameSeed was picked using the same call as the Rnd.Next() above. If I can't do this, then there is a serious issue with the seeding of the random number generator.

[phoog]

@romkyns MSDN does guarantee that the property will hold across .NET versions. The implementation may change, but the behavior of the class when constructed with the parameterized constructor is part of its contract, not its implementation (see msdn.microsoft.com/en-us/library/ctssatww(v=vs.110).aspx).

[Roman Starkov]

@phoog "As a result, your application code should not assume that the same seed will result in the same pseudo-random sequence in different versions of the .NET Framework." - I dunno, seems pretty clear to me. However, I wouldn't be surprised if they can't change it in practice without breaking existing programs, despite this warning.

[phoog]

@romkyns Yes, the specific repeatable sequence may change if you run your code on a different version of the framework. So, for example, a test might pass on one version of the framework and not another, but the behavior will be consistent within the context of a given framework. I understood your comment to mean that a future version of the framework might have an implementation where the same seed could give different sequences, and that isn't true -- or if it were, it would be a bug.

[ssss]

@phoog: You’re saying one thing and then the exact opposite of it. You’re contradicting yourself directly.

[phoog]

@Timwi what two things did I say that contradicted each other? I said that the behavior of identically-seeded Random objects must be the same according to the class's contract. I said this because I (mis-?) understood romkyn's comment to say that future implementations of Random might be such that identically-seeded objects could return different sequences. I also acknowledged that changing framework versions might cause a one-time change in the specific repeatable sequence returned. That's not the same as losing the property of repeatability altogether.

[Arsen Zahray]

Hm. So what implementation of Random for C# do you recommend using?

[spender]

...and it doesn't look like it will ever be possible to fix.

[Mike Dinescu]

this is not an answer to the original question!

[Traderhut Games]

It is, the answer is: There are no situations where calling Random() makes sense. Use the Crypto if you need random numbers for Cryptography or other situations that require highly random events. If you want a random sequence of numbers for a game or something - use some other algorithm - such as the one that I've suggested, do not call Random() as it is amazingly bad. (And can make your game seem dorky like it did mine.)

[user2864740]

If only System.Random did either.. oh, well.

[Mark Amery]

Holy cow, the non-uniformity of the distribution of Next(), demonstrated by you here, is a pretty spectacular bug - and still present today, 6 years after you first wrote up your findings. (I say "bug" rather than merely "flaw", because the docs claim that "Pseudo-random numbers are chosen with equal probability from a finite set of numbers". It ain't so, and your code here proves it.)

[Mark Amery]

You might think this is harsh, but -1 for posting results of a performance benchmark without including the code of the benchmark. Even if the performance characteristics of Random and RNGCryptoServiceProvider haven't changed in the last 8 years (which for all I know they might've), I've seen enough completely broken benchmarks used on Stack Overflow not to trust the results of a benchmark whose code isn't publicly available.

[Mark Amery]

@TraderhutGames wait, you generated your next seed to use from your previously-seeded Random() (specifically, by calling .Next(2000000000)) at the moment of creation, and were then surprised to get identical games happening in sequence? That's almost certainly going to happen if you use your seeding approach, regardless of the quality of your deterministic pseudo-random number generation algorithm; eventually, you're likely to hit some seed x such that new Random(x).Next(2000000000) == x, and then you're stuck with identical sequences forever.

[Traderhut Games]

The intent is that for the first Random() call it would generate a random series of numbers, so the first thing it did was generate the seed for the next level. The next level would seed with that seed. This gave me the ability to reproduce the exact same series of numbers, but that each game would be totally different. The problem was that seeding with a number from 0-2 billion would produce about the same set of numbers each time. The seed didn't seem to make all that much difference! I should have had a reproducible, but random series, but didn't.

[Traderhut Games]

I put a recommendation of a random number generator in my answer. The one from JPL written in 1984 hasn't been beat by anything I've seen (for a repeatable pseudo-random sequence that you don't use for cryptographic apps.) . You'd have to port it to C#, but that didn't take me long to do. The period is really long and one bit different in your seed results in a totally different sequence of numbers.

[MSeifert]

It seems like the link is down because Microsoft retired "connect".

[Sen Jacob]

I'm sure if somebody inspected the source/decompiled byte code >> Here you go. Reference source code of System.Random.

[Traderhut Games]

btw Mark: You are correct that you would have one chance in 2,000,000,000 that that seed would return the same seed that it was fed with, If someone plays 2 billion games and finds that seed, they win the game. Feel free to play it until you find it. And the next time I'll add code so if rnd(2000000000) = old_seed, then pick the next one.

[pepoluan]

Just to add to this old comment thread: System.Random is not really performant. There are PRNG implementations that are both more performant and statistically better than System.Random. For example, my XoshiroPRNG.Net implementation is both; it's available on nuget.org/packages/XoshiroPRNG.Net -- follow the link to the repo to see the performance benchmark code & results.