java/com/google/security/wycheproof/RandomUtil.java

/**
 * @license
 * Copyright 2016 Google Inc. All rights reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.security.wycheproof;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.security.GeneralSecurityException;
import java.util.Random;

/**
 * A collection of utilities for testing random number generators. So far this util simply checks
 * that random numbers are not generated by java.util.Random. Eventually we plan to add detection
 * for other random number generators too.
 *
 * @author bleichen@google.com (Daniel Bleichenbacher)
 */
public class RandomUtil {
  // Constants for java.util.Random;
  static final long A = 0x5DEECE66DL;
  static final long A_INVERSE = 246154705703781L;
  static final long C = 0xBL;

  /** Given a state of a java.util.Random object compute the next state. */
  protected static long nextState(long seed) {
    return (seed * A + C) & ((1L << 48) - 1);
  }

  /** Give the state after stepping java.util.Random n times. */
  protected static long step(long seed, long n) {
    long a = A;
    long c = C;
    n = n & 0xffffffffffffL;
    while (n != 0) {
      if ((n & 1) == 1) {
        seed = seed * a + c;
      }
      c = c * (a + 1);
      a = a * a;
      n = n >> 1;
    }
    return seed & 0xffffffffffffL;
  }

  /** Given a state of a java.util.Random object compute the previous state. */
  protected static long previousState(long seed) {
    return ((seed - C) * A_INVERSE) & ((1L << 48) - 1);
  }

  /** Computes a seed that would initialize a java.util.Random object with a given state. */
  protected static long getSeedForState(long seed) {
    return seed ^ A;
  }

  protected static long getStateForSeed(long seed) {
    return (seed ^ A) & 0xffffffffffffL;
  }

  /**
   * Given two subsequent outputs x0 and x1 from java.util.Random this function computes the
   * internal state of java.util.Random after returning x0 or returns -1 if no such state exists.
   */
  protected static long getState(int x0, int x1) {
    long mask = (1L << 48) - 1;
    long multiplier = A;
    // The state of the random number generator after returning x0 is
    // l0 + eps for some 0 <= eps < 2**16.
    long l0 = ((long) x0 << 16) & mask;
    // The state of the random number generator after returning x1 is
    // l1 + delta for some 0 <= delta < 2**16.
    long l1 = ((long) x1 << 16) & mask;
    // We have l1 + delta = (l0 + eps)*multiplier + 0xBL (mod 2**48).
    // This allows to find an upper bound w for eps * multiplier mod 2**48
    // by assuming delta = 2**16-1.
    long w = (l1 - l0 * multiplier + 65535L - 0xBL) & mask;
    // The reduction eps * multiplier mod 2**48 only cuts off at most 3 bits.
    // Hence a simple search is sufficient. The maximal number of loops is 6.
    for (long em = w; em < (multiplier << 16); em += 1L << 48) {
      // If the high order bits of em are guessed correctly then
      // em == eps * multiplier + 65535 - delta.
      long eps = em / multiplier;
      long state0 = l0 + eps;
      long state1 = nextState(state0);
      if ((state1 & 0xffffffff0000L) == l1) {
        return state0;
      }
    }
    return -1;
  }

  /**
   * Find a seed such that this integer is the result of
   *
   * <pre>{@code
   * Random rand = new Random();
   * rand.setSeed(seed);
   * return new BigInteger(k, rand);
   * }</pre>
   *
   * where k is max(64, x.BitLength());
   *
   * <p>Returns -1 if no such seed exists.
   */
  // TODO(bleichen): We want to detect cases where some of the bits
  //   (i.e. most significant bits or least significant bits have
  //   been modified. Often this happens during the generation
  //   of primes or other things.
  // TODO(bleichen): This method is incomplete.
  protected static long getSeedFor(java.math.BigInteger x) {
    byte[] bytes = x.toByteArray();
    if (bytes.length == 0) {
      return -1;
    }
    ByteBuffer buffer = ByteBuffer.allocate(8);
    int offset = bytes[0] == 0 ? 1 : 0;
    if (bytes.length - offset < 8) {
      int size = bytes.length - offset;
      buffer.position(8 - size);
      buffer.put(bytes, offset, size);
    } else {
      buffer.put(bytes, offset, 8);
    }
    buffer.flip();
    buffer.order(java.nio.ByteOrder.LITTLE_ENDIAN);
    int x0 = buffer.getInt();
    int x1 = buffer.getInt();
    long state = getState(x0, x1);
    if (state == -1) {
      return -1;
    }
    return getSeedForState(previousState(state));
  }

  /** Attempts to find a seed such that it generates the prime p. Returns -1 if no seed is found. */
  static long getSeedForPrime(BigInteger p) {
    int confidence = 64;
    Random rand = new Random();
    int size = p.bitLength();
    // Prime generation often sets the most significant bit.
    // Hence, clearing the most significant bit can help to find
    // the seed used for the prime generation.
    for (BigInteger x : new BigInteger[] {p, p.clearBit(size - 1)}) {
      long seed = getSeedFor(x);
      if (seed != -1) {
        rand.setSeed(seed);
        BigInteger q = new BigInteger(size, confidence, rand);
        if (q.equals(p)) {
          return seed;
        }
      }
    }
    return -1;
  }

  /**
   * Checks whether p is a random prime. A prime generated with a secure random number generator
   * passes with probability > 1-2^{-32}. No checks are performed for primes smaller than 96 bits.
   *
   * @throws GeneralSecurityException if the prime was generated using java.util.Random
   */
  static void checkPrime(BigInteger p) throws GeneralSecurityException {
    // We can't reliably detect java.util.Random for small primes.
    if (p.bitLength() < 96) {
      return;
    }
    long seed = getSeedForPrime(p);
    if (seed != -1) {
      throw new GeneralSecurityException(
          "java.util.Random with seed " + seed + " was likely used to generate prime");
    }
  }
}