Security is hard. In a current project I saw some code that created some access tokens based on a random number generator - .NET’s Random class. The code used an instance of Random stored in static field and I got curious:

If you have such a long living Random instance, could you predict the random values after generating a few of them?

It turns out, it is possible. And you only need to read 56 55 “random” values to predict all future values.

The following code predicts 10 (or any other number if you change the constant) values generated by random.Next() after reading 55 values (done in Prepare()).

public class RandomBreaker
{
  static void Main()
  {
    var random = new Random();

    int[] seedArray;
    int inext;
    int inextp;

    Prepare(random, out seedArray, out inext, out inextp);

    for (int x = 0; x < 10; x++)
    {
      int predictedRandomValue = PredictNextRandomValue(
        seedArray,
        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 void Prepare(
      Random random,
      out int[] seedArray,
      out int inext,
      out int inextp
    )
  {
    const int INTERNAL_ARRAY_SIZE = 56;
    const int INEXTP_START = 21;

    seedArray = new int[INTERNAL_ARRAY_SIZE];

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

    inext = INTERNAL_ARRAY_SIZE - 1;
    inextp = INEXTP_START;
  }

  // Implementation mirrors:
  // http://referencesource.microsoft.com/#mscorlib/system/random.cs,100
  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;
  }
}

Notes:

• To be able to predict the values, one needs to know exactly how Random internally works. This code was run against .NET Framework 4.5.2. If Microsoft ever decides to change the implementation, the prediction won’t work anymore.
• If Next(maxValue) was used instead of Next(), the prediction would become much harder as Next(maxValue) basically divides the range 0 to int.MaxValue into maxValue buckets. It then calls Next() and checks in which bucket the returned value resides. The number of this bucket is then returned. The “worst” case here is Next(1) which will return either 0 or 1. In this case, each value is based on any of 1,000,000,000 numbers - which makes it very hard (but probably not impossible) to find the original value.