Created
September 4, 2016 15:43
-
-
Save DinisCruz/828a23e607c1eab6b66c866e7f3a37c9 to your computer and use it in GitHub Desktop.
Java test that confirms how Random().nextInt() values can be predicted
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import org.junit.Test; | |
import java.util.ArrayList; | |
import java.util.Random; | |
import static org.junit.Assert.assertEquals; | |
import static org.junit.Assert.assertTrue; | |
public class Vulnerability_Weak_Crypto { | |
@Test | |
public void confirmThatBasedOnTwoValuesThirdCanBeDiscovered() | |
{ | |
Random random = new Random(); // insecure use of Random() class | |
int value_One = random.nextInt(); // get four values | |
int value_Two = random.nextInt(); // first two are used to predict the | |
int value_Three = random.nextInt(); // next two | |
int value_Four = random.nextInt(); | |
ReplicatedRandom hackedRandom = new ReplicatedRandom(); // ReplicatedRandom extends Random | |
boolean foundSeed = hackedRandom.replicateState(value_One, value_Two); // feed first two to ReplicatedRandom | |
assertTrue(foundSeed); // confirm that seed (of random) was found | |
assertEquals(hackedRandom.nextInt(), value_Three); // confirm that we are now able to predict the next | |
assertEquals(hackedRandom.nextInt(), value_Four); // two values (as created by random.nextInt() ) | |
} | |
} | |
// based on code from https://github.com/fta2012/ReplicatedRandom | |
// see detailed explanation in http://franklinta.com/2014/08/31/predicting-the-next-math-random-in-java/ | |
// see issue I originally had https://github.com/fta2012/ReplicatedRandom/issues/4 | |
class ReplicatedRandom extends Random { | |
// Replicate the state of a Random using two consecutive values from its nextInt | |
public boolean replicateState(int firstNextInt, int secondNextInt) { | |
return replicateState(firstNextInt, 32, secondNextInt, 32); | |
} | |
// Replicate the state of a Random using two consecutive values from its nextFloat | |
public boolean replicateState(float firstNextFloat, float secondNextFloat) { | |
return replicateState((int)(firstNextFloat * (1 << 24)), 24, (int)(secondNextFloat * (1 << 24)), 24); | |
} | |
public boolean replicateState(int nextN, int n, int nextM, int m) { | |
// Constants copied from java.util.Random | |
final long multiplier = 0x5DEECE66DL; | |
final long addend = 0xBL; | |
final long mask = (1L << 48) - 1; | |
long upperMOf48Mask = ((1L << m) - 1) << (48 - m); | |
// next(x) is generated by taking the upper x bits of 48 bits of (oldSeed * multiplier + addend) mod (mask + 1) | |
// So now we have the upper n and m bits of two consecutive calls of next(n) and next(m) | |
long oldSeedUpperN = ((long)nextN << (48 - n)) & mask; | |
long newSeedUpperM = ((long)nextM << (48 - m)) & mask; | |
// Bruteforce the lower (48 - n) bits of the oldSeed that was truncated. | |
// Calculate the next seed for each guess of oldSeed and check if it has the same top m bits as our newSeed. | |
// If it does then the guess is right and we can add that to our candidate seeds. | |
ArrayList<Long> possibleSeeds = new ArrayList<Long>(); | |
for (long oldSeed = oldSeedUpperN; oldSeed <= (oldSeedUpperN | ((1L << (48 - n)) - 1)); oldSeed++) { | |
long newSeed = (oldSeed * multiplier + addend) & mask; | |
if ((newSeed & upperMOf48Mask) == newSeedUpperM) { | |
possibleSeeds.add(newSeed); | |
} | |
} | |
if (possibleSeeds.size() == 1) { | |
// If there's only one candidate seed, then we found it! | |
//System.out.println("found seed: " + possibleSeeds.get(0)); | |
setSeed(possibleSeeds.get(0) ^ multiplier); // setSeed(x) sets seed to `(x ^ multiplier) & mask`, so we need another `^ multiplier` to cancel it out | |
return true; | |
} | |
if (possibleSeeds.size() >= 1) { | |
System.out.println("Didn't find a unique seed. Possible seeds were: " + possibleSeeds); | |
return false; | |
} else { | |
System.out.println("Failed to find seed!"); | |
} | |
return false; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment