3
$\begingroup$

I've seen it posted on different forms here and here that explain how java.util.Random library uses a linear congruential pseudorandom number generator which can be cracked using two values. Can this type of exploit go one level deeper and guess the nextByte data used to fill in the rest of a BigInteger value?

private static Random generator = new Random();

public static String uncrackableRandomNumber() {
    return new BigInteger(128, generator);
}

A snippet of the additional layer of byte generation using java.util.Random (rnd).

public BigInteger(int numBits, Random rnd) {
      this(1, randomBits(numBits, rnd));
  }

private static byte[] randomBits(int numBits, Random rnd) {
  if (numBits < 0)
    throw new IllegalArgumentException("numBits must be non-negative");
  int numBytes = (int) (((long) numBits + 7) / 8); // avoid overflow
  byte[] randomBits = new byte[numBytes];

  // Generate random bytes and mask out any excess bits
  if (numBytes > 0) {
    rnd.nextBytes(randomBits);
    int excessBits = 8 * numBytes - numBits;
    randomBits[0] &= (1 << (8 - excessBits)) - 1;
  }
  return randomBits;
}

The first two numbers are: 233458857748780331814340414981023411537 and 141610568161066839752374346774468879751, how can I determine the next number given only this information?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Yes its possible and easy. Hint: see what nextBytes does, use that to get two consecutive 32-bit outputs by the RNG, which allows to compute the full state. $\endgroup$ – fgrieu♦ May 7 at 6:23
  • $\begingroup$ @fgrieu Was hoping for a solution rather than a hint, but I'll read up on nextBytes. Glad to see the return of nextInt. $\endgroup$ – Todd Kennaday May 7 at 6:58
  • 1
    $\begingroup$ I (now) realize there's a recent Reddit with a similar question, under another name, stating that the purpose is breaking a 'web app'. While making the mistake of using the Java default RNG for security purpose is laughable, it's still my policy not to participate in attack of non-clearly-evil deployed crypto. While homework or CTF seems just as likely, neither of the three options is enticing me to give more than a hint. That's educative, again that's easy, just do it, you'll feel good. $\endgroup$ – fgrieu♦ May 7 at 8:31
1
$\begingroup$

Isn't the answer plainly yes by simple deduction? The BigInteger constructor is simply a linear function as: BigInt ~ F(LCG). Ergo if LCG is predictable, BitInt is too. It's not much deeper.

Could you do BigInt ~ F(SecureRandom)?

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.