bugtraq - Re: Jetty Session ID Prediction

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Tue, 06 Feb 2007 19:53:04 +0200
From: Amit Klein <aksecurity@...il.com>
To: Chris Anley <chris@...software.com>
Cc: bugtraq@...urityfocus.com
Subject: 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