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