Enumerating values from a linear congruential generator java Random()

Sergey Unk

8/11/23, 6:47 AM

During my research on a java application, I discovered that the nextInt(64) function of the java.Random() class is used to generate the encryption key.

The key size is 16 bytes. I know that this generator is not recommended because it is vulnerable. Especially in this case, the value of each byte of the key is selected from a short range from 0x0 to 0x40.

I already got acquainted with the fact that it is possible to predict the next values of the generator using the previous values. But in my case meyan has no data about the previous values (The key is encrypted and I don't have access to its values), so here we are talking about iterating over the key values. I don't understand how can I use the data that each next value depends on the previous one (oldseed parameter)?

protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
}

How to reduce the number of enumeration for such a 16-byte key?

0 + 0

cryptanalysis

random-number-generator

brute-force-attack

pseudo-random-function

key-generation

fgrieu

8/11/23, 7:13 AM

Are the 16 bytes obtained with next(6) meaning you are using " from 0x0 to 0x40" to mean in [0, 0x40-1] ? Then hint: assume a single thread during key generation, and simplify accordingly what this code does. Then find which bits of the seed have an influence on the 16-byte key. Conclude how many such 16-byte keys there can be, and how to enumerate them. Perhaps, investigate how the seed is chosen, which may allow to enumerate the actual key much faster.

Sergey Unk

8/11/23, 8:27 AM

@fgrieu there is no next(6) - nextInt(64) is used. This means each byte of the 16 digit key is a number in the range [0;63] (decimal system)

fgrieu

8/11/23, 8:42 AM

That's clearer, and key bytes are from 0x0 to 0x3F included. Revised hints in light of the above: understand how `nextInt(64)` uses `next(31)`, and why `nextInt(64)` is precisely equivalent to `next(6)`. Then assume a single thread during key generation, and simplify the question's code accordingly. Find which bits of the seed have an influence on the 16-byte key. Conclude how many such 16-byte keys there can be, and how to enumerate all of them at feasible cost. Perhaps, investigate how the seed is chosen, which may allow to enumerate the actual key much faster.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Enumerating values from a linear congruential generator java Random()

TH: การแจกแจงค่าจากตัวสร้างความสอดคล้องเชิงเส้น java Random()

RO: Enumerarea valorilor dintr-un generator liniar congruențial java Random()

RU: Перечисление значений из линейного конгруэнтного генератора java Random()

VI: Liệt kê các giá trị từ một trình tạo đồng dư tuyến tính java Random()

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.