CODEWITHSUNDEEP
c#.netsecurityrandom
Sebastian Krysmanski
Sebastian Krysmanski

Reputation: 8394

Can Random.Next() be predicted from its outputs

Having this (simplified) C# class:

public static class RandomValue
{
    private static readonly Random s_random = new Random();

    public static int GetRandomValue()
    {
        lock (s_random)
        {
            return s_random.Next();
        }
    }
}

Is it possible to predict the next value of GetRandomValue() by looking at the values generated by this method?

Assumptions (for the sake of the question):

I'm asking because I've seen some code using a similar approach to generate some kind of access tokens. This code was not written by me and I would probably have used one of .NET's crypto random classes. I'm just curious whether this is still sufficiently secure.

Upvotes: 4

Views: 1855

Answers (1)

Sebastian Krysmanski
Sebastian Krysmanski

Reputation: 8394

Based on kennytm's comment I created a proof of concept on how to to "break" Random. It may be a little rough around the edges but it shows that you only need 55 values to predict the next one (and every value after that).

The following code first reads 55 values from a single Random instance and then predicts the next 10 values:

public class Program
{
    static void Main(string[] args)
    {
        const int INTERNAL_ARRAY_SIZE = 56;
        const int INEXTP_START = 21;

        var internalArray = new int[INTERNAL_ARRAY_SIZE];

        var random = new Random();

        // Read 56 values.
        for (int x = 0; x < INTERNAL_ARRAY_SIZE - 1; x++)
        {
            internalArray[x + 1] =  random.Next();
        }

        int inext = INTERNAL_ARRAY_SIZE - 1;
        int inextp = INEXTP_START;

        // Predict the next 10 values.
        for (int x = 0; x < 10; x++)
        {
            int predictedRandomValue = PredictNextRandomValue(internalArray, ref inext, ref inextp);
            int officialRandomValue = random.Next();

            if (officialRandomValue == predictedRandomValue)
            {
                Console.WriteLine("Yes, they're the same.");
            }
            else
            {
                Console.WriteLine("No, they're different.");
            }
        }
    }

    private static int PredictNextRandomValue(int[] seedArray, ref int inext, ref int inextp)
    {
        const int MBIG =  int.MaxValue;

        int retVal;
        int locINext = inext;
        int locINextp = inextp;

        if (++locINext >= 56) locINext = 1;
        if (++locINextp >= 56) locINextp = 1;

        retVal = seedArray[locINext] - seedArray[locINextp];

        if (retVal == MBIG) retVal--;
        if (retVal < 0) retVal += MBIG;

        seedArray[locINext] = retVal;

        inext = locINext;
        inextp = locINextp;

        return retVal;
    }
}

Upvotes: 11

Related Questions