# Re: Jetty Session ID Prediction

*From*: Amit Klein <aksecurity@xxxxxxxxx>*Date*: Tue, 06 Feb 2007 19:53:04 +0200

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

**Follow-Ups**:**Re: Jetty Session ID Prediction***From:*Chris Anley

**References**:**Re: Jetty Session ID Prediction***From:*Chris Anley

- Prev by Date:
**rPSA-2007-0025-1 postgresql postgresql-server** - Next by Date:
**Re: Jetty Session ID Prediction** - Previous by thread:
**Re: Jetty Session ID Prediction** - Next by thread:
**Re: Jetty Session ID Prediction** - Index(es):