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