Re: Jetty Session ID Prediction
Chris Anley wrote:
Hi folks,
I've posted a paper that explains a little more here:
http://www.ngssoftware.com/research/papers/Randomness.pdf
Nice paper. I do notice an enumeration loop over 2^16 possible 16-bit
values. This can be improved as following (note: this is probably
already discussed in mathematic literature - i.e. I probably did not
invent it...):
Let us denote the initial state of the PRNG as 2^16*x1+y1, where x1 are
the leftmost 32 bits, and y1 are the rightmost 16 bits. x1 is known,
and y1 is not. Likewise, the next state is 2^16*x2+y2, where x2 is
known and y2 is not. Of course, I'm ignoring small issues such as sign,
the 7 possible base choices, etc. - my main focus is replacing the
innermost brute-force loop.
Now, the following holds (PRNG advance rule):
2^16*x2+y2 = 0x5DEECE66DL*(2^16*x1+y1)+0xBL (mod 2^48).
Rearranging, we have:
0x5DEECE66DL*y1 =2^16*x2+y2-0x5DEECE66DL*2^16*x1-0xBL (mod 2^48)
Let's further split y1 (a 16 bit quantity) into m*2^13+n (m is 3 bits, n is 13
bits), and re-arrange:
0x5DEECE66DL*n = -0x5DEECE66DL*2^13*m+2^16*x2+y2-0x5DEECE66DL*2^16*x1-0xBL
(mod 2^48)
Note that at the left hand side of the equation, we have an absolute
quantity < 2^48 (n<2^13, 0x5DEECE66DL<2^35). Enumerating over
all possible 8 values of m, we also know exactly the absolute value of
the right hand side, up to y2, so if we write that as Z+y2, where Z is
known (Z=-0x5DEECE66DL*2^13*m+2^16*x2-0x5DEECE66DL*2^16*x1-0xBL)
and y2 is not, applying mod 2^48 means ((Z mod 2^48) + y2 ) mod
2^48. Only if (Z mod 2^48) > 2^48-2^16 will y2 make a significant
difference, i.e. if (Z mod 2^48)>2^48-2^16 then we need to check for
two options: (Z mod 2^48) and (Z mod 2^48) - 2^48. For simplicity,
let's assume then that (Z mod 2^48) <=2^48-2^16, which means we can
write the following *absolute* equation:
0x5DEECE66DL*n = (Z mod 2^48) + y2
Taking modulo 0x5DEECE66DL we solve y2 (note that y2 is a 16 bit quantity, much
smaller than 0x5DEECE66DL):
y2= (-(Z mod 2^48)) mod 0x5DEECE66DL
If y2 is not a 16 bit quantity, then clearly m is incorrect.
Assuming a correct y2, we can find n by dividing:
n = ((Z mod 2^48) + y2) / 0x5DEECE66DL
And since we have m, we know y1=m*2^13+n.
To summarize, the proposed improvement is:
Enumerate over all 2^3=8 possible values of m, for each calculate
Z=(-0x5DEECE66DL*2^13*m+2^16*x2-0x5DEECE66DL*2^16*x1-0xBL)
and in rare (1:2^32) cases, enumerate two possible (Z mod 2^48) values, then
calculate
y2= (-(Z mod 2^48)) mod 0x5DEECE66DL (reject m's with y2>=2^16)
n = ((Z mod 2^48) + y2) / 0x5DEECE66DL
y1=m*2^13+n
This should be much faster than looping over 2^16 values.
-Amit