The $48$-bit state $s_i$ evolves per a Linear Congruential Random Number Generator, with modulus $n=2^{48}$, multiplier $a=\mathtt{5DEECE66D}_{16}$, and additive constant $b=\mathtt B_{16}$; that is $s_i=(a\cdot s_{i-1}+b)\bmod2^{48}$. We are given the OR $r_i$ of its two upper bits for $i\in[1,81]$, or equivalently the $81$ booleans $s_i\ge2^{46}$. Our goal is to find $s_0$: if the Java default generator was explicitly seeded, $s_0\oplus a$ is the low-order 48 bits of the given long
seed.
The $81$ givens yield about $-81\left(\frac14\log_2(\frac14)+\frac34\log_2(\frac34)\right)\approx65.7$ bit of information, which should be typically ample to pinpoint a single $48$-bit seed.
A most brute force solution to the problem enumerates all the $s_0$ in $[0,2^{48})$, and for increasing $i$ computes the $s_i$ and eliminates a candidate $s_0$ as soon as there's a mismatch between a bit $r_i$ and the condition $s_i\ge2^{46}$. That's feasible, and particularly easy to distribute on multiple threads/CPUs/GPUs/FPGAs. The rest of this answer illustrates the NSA saying (popularized by Bruce Schneier): Attacks always get better; they never get worse.
Notice that we can compute for $z\in[-81,81]$ the $48$-bit constants $a_z$ and $b_z$ such that $s_{i+z}=(a_z\cdot s_i+b_z)\bmod2^{48}$. We have
$$\begin {align}
a_0&=1&b_0&=0\\
a_{z+1}&=a\cdot a_z\bmod2^{48}&b_{z+1}&=(a\cdot b_z+b)\bmod2^{48}\\
a_{-1}&=a^{-1}\bmod2^{48}=\mathtt{DFE05BCB1365}_{16}&b_{-1}&=a_{-1}\cdot (-b)\bmod2^{48}\\
a_{z-1}&=a_{-1}\cdot a_z\bmod2^{48}&b_{z-1}&=a_{-1}\cdot (b_z-b)\bmod2^{48}
\end{align}$$
This allows computing directly any $s_j$ from any $s_i$, by taking $z=j-i$. That's put to use in the following optimizations:
- Pick an $i$ with $r_i=0$ and reorganize the search by walking $s_i$ in the interval to $[0,2^{46})$, then compute $s_0$ from $s_i$. That's a welcome gain by a factor of $4$.
- We most likely¹ can pick the above $i$ such that $r_i=r_{i+1}=0$. The condition $s_{i+1}<2^{46}$ (which must hold) changes rarely when incrementing $s_i$: it holds true for about $2^{46}/a\approx2791$ consecutive values, then is false for an interval about three times longer, that we can skip, giving a speedup by a factor next to $4$.
At that stage of optimization, we explore $2^{44}$ values of $s_i$. I guesstimate² we can run faster than $2^6$ cycles/value tested on a core of a modern x64 desktop CPU. With a single $2^2$-core CPU at $2^{31}$ Hz, that would be $2^{17}$ seconds (1.5 day for the full exploration), and half that on average.
We can do better, but be warned that premature optimization is the root of all evils (Donald Knuth). We most often are able to make good use of the fact that $a_{-67}$ is small: when we can find $i,z$ with $r_i=r_{i+1}+r_{i-67}=0$, that allows getting down to $2^{42}$ values searched at cost of a further sub-division of the search sub-intervals for $s_i$ into sub-sub-intervals of width $2^{46}/a_{-67}\approx394$.
We often are able to further subdivide at least once or even twice, each time gaining another reduction by a factor of $4$ of the number of $a_i$ to test. We want to explore the usefulness of such subdivision for each $s_{i+z}$ with $r_{i+z}=0$. The better choices have the highest width $\approx2^{46}/\min(a_z,2^{48}-a_z)$ for the interval of $a_i$ with $s_{i+z}<2^{46}$. In particular, we might be able to use that $2^{46}/a_{19}\approx60$ or $2^{46}/(2^{48}-a_{-12})\approx60$. But we'll quickly get hit by the law of diminishing returns.
Update: There must be better methods. Something at least quite close was studied by Alan M. Frieze, Johan Hastad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing Truncated Integer Variables Satisfying Linear Congruences, in SIAM Journal on Computing, 1988.
¹ In the very unlikely case (I'm not even sure it is possible) that there's no $i$ with $r_i=r_{i+1}=0$, the simplest of several possible fallbacks is to pick $i$ and $z$ with $r_i=r_{i+z}=0$ and the smallest $a_z$ possible; that will often be $z=-67$ or $z=19$. The reduction in number of $s_i$ scanned is the same, but we'll more often change sub-intervals.
² When $s_i$ increases in a sub-interval, we want to quickly update at least one $s_j$ that we'll always test. An update of $s_j$ cost one addition of $a_{j-i}$ and a mask³. We'll pick $j$ with $r_j=0$, which will leave only one out of $4$ values of $s_i$ needing more scrutiny. For these, we sequentially compute and test the many other $s_{i+z}$ that we could still have wrong, of course stopping at the first mismatch and first testing $z$ with $r_{i+z}=0$. Each additional $z$ requires a multiplication by $a_z$. If that's too costly, we'll want to maintain one or a few more $s_k$ by addition.
³ A simple micro-optimization maintains $2^{16}s_i$ over a $64$-bit variable, saving the masking. The comparison becomes against $2^{62}$, also implementable as a $62$-bit right shift and a test for zero.
SecureRandom
implementation which should always provide a cryptographically secure random number generator. This is aboutjava.util.Random
which is a small non-secure random generator. Beware thatRandom
also acts as an interface definition forSecureRandom
but thenext
method is overridden in (i.e. replaced for)SecureRandom
- so it doesn't apply there. $\endgroup$ – Maarten Bodewes♦ Jan 19 '20 at 13:48