From aholtzma@ess4.engr.UVic.CA Tue, 26 Oct 1999 20:59:14 -0700
Date: Tue, 26 Oct 1999 20:59:14 -0700
From: Aaron Holtzman aholtzma@ess4.engr.UVic.CA
Subject: [Livid-dev] CSS key generation analysis

Since the css code is publically available, I'm going to make use
of my right to free speech in my country. It's amazing the amount
of fear that large multinational corporations can put into the
hearts of hackers :p

The first step of key generation does very little to protect
the integrity of the player keys. In fact, if you have one legit
key, you are just one forty bit hash function away from getting a
new player key.

First, some definitions and background. I'm going to focus on the
first stage of key generation (which is all that matters).

D[] - The disc key sector containing 409 five bit 'slots'
d - A plain text disc key that can be used in key generation step 2
d' - An encrypted disc key taken from D[] which corresponds to p
p - A plain text player key as it exists in the player code
p' - An encrypted player key generated as part of key generation step 1

The first stage key generation looks like this

p' = crypt_a(p); //This is the for(i=[0..5]){ k += LSFR + CRAP} loop
d = one_way_hash(d',p'); 

You would then use the resulting d to decrypt the title key in stage two 
and carry on your merry way. There are two interesting remarks to make at 
this point. One is that d is constant for a particular disc, regardless of which
player key you're using. Two, the generation is p' is completely pointless.
Since p' only depends on p, having p' is just as good as having p for our 
purposes.

Now if we have p_5 for example (where _N means corresponding to disc key 
offset N), we could run through the process using d_5' and p_5' and get
d (which is again the same for all player keys). All we need to do to get p_X'
(where X is any old offset from 0x05-0xA0 (1)(2)) is find an input to the one_way_hash
function that along with d_X' provides the output d. 

There are 2^40 possibile combinations of inputs, and I have code that
trys 17e6 potential hashes/second on a Celeron 366. This gives a max
search time of ~17 hours.

There is one caveat. The one way hash function is not a bijection. This means 
there may be many potential hash inputs that produce that right output. Only one 
is p_X', and to test the potential keys you need to use a different disc.

Code to perform this task is left as an exercise to the reader. Have fun.

cheers,
aaron

(1) I contend that there are only 32 player keys that are repeated up to
thirteen times in random slots (but the slots are the same between discs).
Slots 0x05-0xA0 are unrepeated, consecutive disc keys. On _some_ discs,
some of the repeat slots are filled with noise. If you don't believe me
take a look at the distribution of the disk key sector and decide for 
yourself.

(2) There is also the matter of the special 0x00 slot magic disc key. This
key plays a part in determining which player key to use (if a player has
more than one p). I haven't looked too closely at the math behind this
key, but I suspect that there are even more flaws to exploit here.