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?


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.
