What is the practical impact of using System.Random which is not cryptographically random?

Question

I recently noticed a .NET software using PBKDF to derive an encryption key from a password string. This password string was dynamically generated using System.Random. Now, I know that System.Random is not really cryptographically random and should not be used for security purposes. Moreover, there are several flaws in .NET's implementation of System.Random.

But my question is this:

• What is the practical impact of using System.Random to create a password string and deriving a key from it. Is it really possible for us to reproduce the key at a later time? Are there feasible attacks that will allow me to deduce the random string generated in this context with high probability? Or is it the kind of vulnerability that can only be exploited in specific "lab" conditions or scenarios?

Answer 1

You asked for the practical impact, so the answer is that for \$120 I could probably have your entire password database done by tomorrow.

Here is your program, or something similar to it:

using System;
using System.Text;
using System.Security.Cryptography;

class Program {
    static void Main(string[] args) {
        byte[] pwd = new byte[128];
        byte[] salt = Encoding.ASCII.GetBytes("saltsalt");

        var rand = new Random();
        rand.NextBytes(pwd);
        Rfc2898DeriveBytes k = new Rfc2898DeriveBytes(pwd, salt, 1000);
        Console.WriteLine(System.Convert.ToBase64String(k.GetBytes(16)));
    }
}

We should spend a bit of time talking about your salt. I've assumed it's fixed. You'd usually randomly generate it - if you use a single System.Random instance for both the salt and the password then the attack is basically the same. If you're creating two System.Random instances, one after the other, then you're unlikely to gain anything given how the default seed is generated. If your salt is based on an incrementing counter or usernames or something, what I'm about to say only really applies to attacking a single password rather than an entire database. You should still be concerned either way.

I compiled this and ran it on my own machine, and it gave me the key IDWrj6Fd9c4kqJ6A2FHDEg==.

Let's try and break it! System.Random is well-documented: https://docs.microsoft.com/en-us/dotnet/api/system.random.-ctor?view=netframework-4.8. It uses a 32 bit integer key, and in fact if the key is negative the docs tell us that it actually uses the key's absolute value for some reason. Handy! That's only 31 bits! Let's break it with this program:

using System;
using System.Text;
using System.Linq;
using System.Security.Cryptography;

class Program {
    static void Main(string[] args) {
        byte[] target = System.Convert.FromBase64String("IDWrj6Fd9c4kqJ6A2FHDEg==");
        byte[] pwd = new byte[128];
        byte[] salt = Encoding.ASCII.GetBytes("saltsalt");

        for (int i = 0; i < Int32.MaxValue; i++){
            if (i % 1024 == 0) {
                Console.WriteLine(i);
            }
            var rand = new Random(i);
            rand.NextBytes(pwd);
            Rfc2898DeriveBytes k = new Rfc2898DeriveBytes(pwd, salt, 1000);
            if (k.GetBytes(16).SequenceEqual(target)){
                Console.WriteLine("pwnt");
                Console.WriteLine(i);
                Environment.Exit(0);
            }
        }
    }
}

How long will this take to run?

dnSpy is a handy tool for reverse-engineering C# applications, and we can use it to take a look at what the default constructor for System.Random does. Yours might be different, but in mine an unseeded System.Random sets the seed to Environment.TickCount, which is the number of milliseconds that have passed since the computer was booted up. I don't leave my computer running for more than a couple of hours at a time, so Environment.TickCount is probably not going to be any bigger than 36,000,000. Watching the keys go by, I'm trying about 14,336 keys per minute. 36000000/14336 = 2511 minutes to try all the feasible keys, so it should finish within about 40 hours.

40 hours of a crappy C# program on a laptop is not secure at all. Even if you picked your seed better, 2147483648/14336 = 149796 minutes, so about 2,400 hours. I suppose I could spend some time re-writing my trash-tier C# program so that it runs faster - it's definitely really slow and can be improved massively - but I don't care enough about your passwords to do that. It's easier to just run a few thousand instances starting at different seeds for an hour each.

Amazon will sell me CPU hours at around \$0.05 per hour so it'd cost me \$120, plus a bit of time and faff writing the code and getting it on their servers, to crack your entire password database. Probably less, since my laptop is likely slower than their compute nodes.

Most of the time here is spent actually computing the PBKDF2 function. PBKDF2 is pretty great and you should still use it - it's designed to be slow precisely so that attacks like this are inefficient. The \$120 estimate is based on using 1,000 iterations in your PBKDF2, which takes a couple of milliseconds per hash on my machine. You could make this attack cost \$1200 by just tuning that parameter to 10,000 instead, though a determined attacker would still happily pay that to get their hands on your users' data. If you wanted this attack to cost me $1,200,000, you could use 10,000,000 iterations! You'd also be wasting a couple of hours every time you wanted a password. I don't know what your application is doing, but if it's spending all that time computing hashes then it'd probably make more money mining Bitcoin or something.

Basing your password scheme on non-cryptographic random number generator isn't a very good idea. Use this one instead: https://docs.microsoft.com/en-us/dotnet/api/system.security.cryptography.rngcryptoserviceprovider.getbytes?view=netframework-4.8. If you were to instead generate 128 bytes from a CSPRNG, then this kind of brute force would start costing me several quadrillion dollars of compute time, which is a few hundred times the GDP of the entire planet. No organisation has anything close to this level of compute power.

Answer 2

From what you have described, it sounds like your system works as follows:

1. Consult the system clock to find a 32-bit seed $s$.
2. Use System.Random to generate a passphrase $p = G(s)$. (Here $G$ is shorthand for whatever computation happens inside System.Random.)
3. Hash the passphrase with PBKDF(2?) into output $x = H(p, \sigma)$, where $\sigma$ is a salt known to the adversary. (Here $H$ is shorthand for PBKDF2.)

4. Do other stuff with $x$. Let's assume you expose $x$ so that we can focus on what the adversary will do; the adversary wins if they can find $p$ or $s$ and predict everything else that is derived from them.

   (In practical terms, maybe you actually derive a key $k = H(p, \sigma)$ and then expose some other function $x = f(k)$ of $k$, but that doesn't substantively change the analysis—we can just fold $f$ into ‘$H$’ and go on as before.)

Let's set aside the flaws in the System.Random algorithm for the moment—there are only at most $2^{32}$ distinct outputs, so in the best case for the defender and the worst case for the attacker, there are $2^{32}$ distinct possible values of $p$, uniformly distributed.

A sensible adversary will probably treat $G$ and $H$ as black boxes and try to find $s$. The naive brute force approach is to enumerate every candidate 32-bit seed $s^*$ and check whether $x = H(G(s), \sigma)$. This costs about $2^{32}$ (four billion) times the cost of evaluating $G$, which is negligible (maybe a few hundred CPU cycles), plus the cost of evaluating $H$, which depends on the PBKDF2 parameters and dominates the cost.

You didn't specify what hash function or how many PBKDF2 iterations, but let's say you picked 1000 iterations of PBKDF2-HMAC-SHA256. My laptop computes about 5 000 000 SHA-256 hashes per second on a single CPU (measured by openssl speed sha256 with the 16-byte inputs), which is about 2 500 000 HMAC-SHA256 hashes per second, or about 2 500 password guesses per second. My laptop also has eight CPUs, so actually it can make about 20 000 guesses per second. With the naive brute force attack on PBKDF2-HMAC-SHA256 on the laptop I happen to be typing on, it should take about two days at my laptop's full power draw to find $s$ and $p$.

That's without any hardware acceleration: Intel's SHA-256 CPU instructions would presumably speed it up—and therefore reduce the cost—by a factor of about four, giving an answer in a few hours. The computation uses essentially no memory or data-dependent memory access patterns, so it can fruitfully be moved to a GPU for further speedups without even leaving the comfort of my personal laptop. Getting an answer in a few seconds is not hard to imagine if you have a modest cluster of GPUs to throw at the problem, like you could rent at Amazon.

In practice, the adversary actually probably doesn't just have one target $x = H(G(s), \sigma)$ to attack: they probably have many targets $x_1 = H(G(s_1), \sigma_1),$ $\dots,$ $x_t = H(G(s_t), \sigma_t)$ to attack, and they win if they break the first of any of the $t$ targets. (Once you get a foothold into a network, it is often easy to springboard from there to many other places in the network.) If you didn't choose a distinct salt $\sigma_i$ for each user, then an adversary could also reduce this (rather low!) cost by a factor of $t$ as long as they parallelize the attack $n \geq t^2$ ways, recovering the seed in the cost $2^{32}\!/t$ and in the time $2^{32}\!/nt$ by using a parallel rainbow table search[1].

Of course, this analysis is isolated from the rest of the details of your application. There may be other ways to break it. For example, if the adversary knows what time you seeded System.Random they can narrow the search space down considerably. If you have a distinct salt per user, how did you choose the salt? If you chose it from System.Random verbatim, it may be possible to recover the System.Random seed from the salt and find the passphrase without an even moderately expensive search at all.

---

What cryptographers will tell you is that if the password has high enough min-entropy, then your system will not be breakable in certain particular ways if you use certain cryptography.

What cryptographers will generally not do is lift a finger to break your pet project, because it's a lot of trouble to find a ‘feasible’ attack, and negligible reward—unless they actually get a specific reward from your system because they are the adversary trying to exploit your users, in which case they aren't going to share their findings with you.

Cryptographers only bother attacking real systems in the wild when they are particularly high-value, like TLS, and particularly many users might be at particularly high risk because of shoddy choices like RC4 that the engineers drag their feet about changing, despite the fact that RC4 was broken within 48 hours of its publication[2] and cryptanalysts kept finding worse[3] and worse[4] problems in it. That's why cryptanalysts bothered studying the specific use of RC4 in WPA and TLS[5][6][7], for example. The same thing happened with bespoke kooky constructions in SSH, TLS, and PGP[8].

Don't be the engineer responsible for making a shoddy cryptographic decision that will inspire cryptanalysts to poke holes in your system years down the road. Follow cryptographers' advice the first time around, to save the cryptanalysts' effort and to let them focus on cryptosystems that will be broadly used like NIST PQC, to improve security for everyone. If you're not sure whether the use of System.Random will ruin your security, assume that it will and promptly replace it by something better in order to give confidence to your users.

Answer 3

The official documentation for System.Random explicitly says it should not be used for generating passwords. It’s predictable, and seeded only from the system clock. This means System.Random has at most 20 bits of entropy to anyone who has a clock accurate to within a second.

Indeed, try creating two new instances in quick succession on different threads; they will produce the same output! I have encountered exactly this issue in an audit of real-world password reset code in a SaaS application. The same passwords were being sent to multiple users in the real world. You could predict those passwords easily if you guessed/knew that System.Random with base64 encoding was being used to generate reset passwords.

Answer 4

Some time ago (more than 5 years, I think) in a local forum one guy gave a "cryptographic challenge" to the community. He gave an encrypted string and a small piece of code that produced it. The goal was to find what the encrypted string was. The encryption key was based on System.Random(), which is the spot where it could be attacked.

At the time my work machine had a 4-core hyperthreaded CPU (so 8 logical CPUs). Simply splitting the search space among them allowed me to probe all possible 32-bit seeds within a few minutes. I think it was less than 10 minutes. This shocked even the person who gave the challenge.

So, if someone gets a hold of your code and can see how it's all done, and all they need to do to break it is to guess the output from System.Random(), they will be able to do so in less than an hour, simply by trying all seeds.

Answer 5

The practical impact is that if the attacker can determine the time when the password was created, they can feed that time as a seed to System.Random, and will get exactly the same password.

System.Random uses a time value with a precision of 1 second. Assuming password creation time is known down to a second (like a user registration date/time from a database), the password will be found instantly. If the creation time is known down to an hour, there are only 3600 seeds to try in order to find the password.

Additional knowledge about the system (e.g. knowing that password generation tasks run on a particular schedule) or flaws in the password generation algorithm (generating the same password for several date/time seeds) can further reduce the search space.

Answer 6

To aid the intuition, please consider my new password generation scheme "seems trustworthy until people inspect details" or "stupid." The way that stupid works is you throw a die and pick a password. If you throw 1, your password is "dhjousacbjlfswsgolFHfhjQPC." If you throw 2 it is "vmcseykogcsKcsNTLhczdg." And so on.

Those look like pretty good passwords to me! They are the sort of password that strength checks promise would hold up for a long time. Which they would, if an attacker started with "aaaaaaaaaaaaaaaaaaaaaa" and worked forward. But suppose that the attacker knows I am using stupid. They won't start with lots of as, they will start with dhjousacbjlfswsgolFHfhjQPC and will have the right answer within 6 guesses. What happens, essentially, is I started with a weak random number generator: a single die. No function I can possibly use will get more than 6 available options out of six available dice results.

The issue is the same for any weak random generator. Perhaps there are a few million start values instead of 6. But fundamentally, a million is not a big number for a computer to count to. All the attacker does is simulate System.Random with each of the possible million inputs, and they get a million possible outputs. That is a much smaller forest to hide in than you would expect from the fact that your passwords look long and random.