1 /** 2 * @license 3 * Copyright 2016 Google Inc. All rights reserved. 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.security.wycheproof; 18 19 import java.math.BigInteger; 20 import java.nio.ByteBuffer; 21 import java.security.GeneralSecurityException; 22 import java.util.Random; 23 24 /** 25 * A collection of utilities for testing random number generators. So far this util simply checks 26 * that random numbers are not generated by java.util.Random. Eventually we plan to add detection 27 * for other random number generators too. 28 * 29 * @author bleichen@google.com (Daniel Bleichenbacher) 30 */ 31 public class RandomUtil { 32 // Constants for java.util.Random; 33 static final long A = 0x5DEECE66DL; 34 static final long A_INVERSE = 246154705703781L; 35 static final long C = 0xBL; 36 37 /** Given a state of a java.util.Random object compute the next state. */ nextState(long seed)38 protected static long nextState(long seed) { 39 return (seed * A + C) & ((1L << 48) - 1); 40 } 41 42 /** Give the state after stepping java.util.Random n times. */ step(long seed, long n)43 protected static long step(long seed, long n) { 44 long a = A; 45 long c = C; 46 n = n & 0xffffffffffffL; 47 while (n != 0) { 48 if ((n & 1) == 1) { 49 seed = seed * a + c; 50 } 51 c = c * (a + 1); 52 a = a * a; 53 n = n >> 1; 54 } 55 return seed & 0xffffffffffffL; 56 } 57 58 /** Given a state of a java.util.Random object compute the previous state. */ previousState(long seed)59 protected static long previousState(long seed) { 60 return ((seed - C) * A_INVERSE) & ((1L << 48) - 1); 61 } 62 63 /** Computes a seed that would initialize a java.util.Random object with a given state. */ getSeedForState(long seed)64 protected static long getSeedForState(long seed) { 65 return seed ^ A; 66 } 67 getStateForSeed(long seed)68 protected static long getStateForSeed(long seed) { 69 return (seed ^ A) & 0xffffffffffffL; 70 } 71 72 /** 73 * Given two subsequent outputs x0 and x1 from java.util.Random this function computes the 74 * internal state of java.util.Random after returning x0 or returns -1 if no such state exists. 75 */ getState(int x0, int x1)76 protected static long getState(int x0, int x1) { 77 long mask = (1L << 48) - 1; 78 long multiplier = A; 79 // The state of the random number generator after returning x0 is 80 // l0 + eps for some 0 <= eps < 2**16. 81 long l0 = ((long) x0 << 16) & mask; 82 // The state of the random number generator after returning x1 is 83 // l1 + delta for some 0 <= delta < 2**16. 84 long l1 = ((long) x1 << 16) & mask; 85 // We have l1 + delta = (l0 + eps)*multiplier + 0xBL (mod 2**48). 86 // This allows to find an upper bound w for eps * multiplier mod 2**48 87 // by assuming delta = 2**16-1. 88 long w = (l1 - l0 * multiplier + 65535L - 0xBL) & mask; 89 // The reduction eps * multiplier mod 2**48 only cuts off at most 3 bits. 90 // Hence a simple search is sufficient. The maximal number of loops is 6. 91 for (long em = w; em < (multiplier << 16); em += 1L << 48) { 92 // If the high order bits of em are guessed correctly then 93 // em == eps * multiplier + 65535 - delta. 94 long eps = em / multiplier; 95 long state0 = l0 + eps; 96 long state1 = nextState(state0); 97 if ((state1 & 0xffffffff0000L) == l1) { 98 return state0; 99 } 100 } 101 return -1; 102 } 103 104 /** 105 * Find a seed such that this integer is the result of 106 * 107 * <pre>{@code 108 * Random rand = new Random(); 109 * rand.setSeed(seed); 110 * return new BigInteger(k, rand); 111 * }</pre> 112 * 113 * where k is max(64, x.BitLength()); 114 * 115 * <p>Returns -1 if no such seed exists. 116 */ 117 // TODO(bleichen): We want to detect cases where some of the bits 118 // (i.e. most significant bits or least significant bits have 119 // been modified. Often this happens during the generation 120 // of primes or other things. 121 // TODO(bleichen): This method is incomplete. getSeedFor(java.math.BigInteger x)122 protected static long getSeedFor(java.math.BigInteger x) { 123 byte[] bytes = x.toByteArray(); 124 if (bytes.length == 0) { 125 return -1; 126 } 127 ByteBuffer buffer = ByteBuffer.allocate(8); 128 int offset = bytes[0] == 0 ? 1 : 0; 129 if (bytes.length - offset < 8) { 130 int size = bytes.length - offset; 131 buffer.position(8 - size); 132 buffer.put(bytes, offset, size); 133 } else { 134 buffer.put(bytes, offset, 8); 135 } 136 buffer.flip(); 137 buffer.order(java.nio.ByteOrder.LITTLE_ENDIAN); 138 int x0 = buffer.getInt(); 139 int x1 = buffer.getInt(); 140 long state = getState(x0, x1); 141 if (state == -1) { 142 return -1; 143 } 144 return getSeedForState(previousState(state)); 145 } 146 147 /** Attempts to find a seed such that it generates the prime p. Returns -1 if no seed is found. */ getSeedForPrime(BigInteger p)148 static long getSeedForPrime(BigInteger p) { 149 int confidence = 64; 150 Random rand = new Random(); 151 int size = p.bitLength(); 152 // Prime generation often sets the most significant bit. 153 // Hence, clearing the most significant bit can help to find 154 // the seed used for the prime generation. 155 for (BigInteger x : new BigInteger[] {p, p.clearBit(size - 1)}) { 156 long seed = getSeedFor(x); 157 if (seed != -1) { 158 rand.setSeed(seed); 159 BigInteger q = new BigInteger(size, confidence, rand); 160 if (q.equals(p)) { 161 return seed; 162 } 163 } 164 } 165 return -1; 166 } 167 168 /** 169 * Checks whether p is a random prime. A prime generated with a secure random number generator 170 * passes with probability > 1-2^{-32}. No checks are performed for primes smaller than 96 bits. 171 * 172 * @throws GeneralSecurityException if the prime was generated using java.util.Random 173 */ checkPrime(BigInteger p)174 static void checkPrime(BigInteger p) throws GeneralSecurityException { 175 // We can't reliably detect java.util.Random for small primes. 176 if (p.bitLength() < 96) { 177 return; 178 } 179 long seed = getSeedForPrime(p); 180 if (seed != -1) { 181 throw new GeneralSecurityException( 182 "java.util.Random with seed " + seed + " was likely used to generate prime"); 183 } 184 } 185 } 186