From frank@funcom.com Wed, 27 Oct 1999 08:55:01 +0200 (CEST) Date: Wed, 27 Oct 1999 08:55:01 +0200 (CEST) From: Frank Andrew Stevenson frank@funcom.com Subject: [Livid-dev] Successfull attack on CSS algorithm Hi, I am a new member to this list, in fact I subscribed just today, in order to send this message, and answer to followups. My main interest in this is purely cryptographical, so I have little or no knowledge of the problems associated with CSS. What I have done is device an attack that will recover a CSS key with a complexity of 2^16 and as little as 6 known output bytes. This should reduce the keyrecovery time from ~17 hours to a fraction of a second. The CSS algorith is fataly flawed. A divide and conquer attack is possible by guessing the 16 unknown bits of LFSR1. LFSR1 is then clocked 4 times, and the known keystream bytes are then used to reconstruct the state of LFSR2. The whole cipher is then clocked another 2-6 times to validate the key. If the key is correct LFSR2 is clocked backwards 4 times to retrieve the initial state. The fine details can be found in the source code below. I hope this mail isn't too long, but I have included source for a complete cracker which works as follows: hippopotamus:~/pc/temp> scramble 3e 4c 13 2e 9c Doing encryption Keystate at start: 13e 4c 01385c2b output: 80 18 e2 cc c1 21 85 0d 9f 8c This produces the 10 first bytes of the keystream for the given key, and also dumps the initial keystate. hippopotamus:~/pc/temp> time scramble 80 18 e2 cc c1 21 85 0d 9f 8c Attempting crack Candidate: 13e 4c 01385c2b 0.090u 0.000s 0:00.10 90.0% 0+0k 0+0io 87pf+0w With 10 bytes as input, the initial state is here recovered in 1/10th of a second on a PPro200. frank ---------- The following is C code for the attack -------- /******************************************************** * * The Divide and conquer attack * * Deviced and written by Frank A. Stevenson 26 Oct 1999 * * ( frank@funcom.com ) * Released under the GPL license * ********************************************************/ [Code Removed] ----------- Following is a complete cracker ------------------- ------ compiles with VC++ / gcc linux, runs on x86 ----------- [Compressed File Removed] This sentence is unique in this respect; it can safely be attributed to my employer, Funcom Oslo AS. E3D2BCADBEF8C82F A5891D2B6730EA1B PGPmail preferred, finger for key There is no place like N59 50.558' E010 50.870'. (WGS84)
From andreas@andreas.org 27 Oct 1999 17:00:55 +0200 Date: 27 Oct 1999 17:00:55 +0200 From: Andreas Bogk andreas@andreas.org Subject: [Livid-dev] Successfull attack on CSS algorithm Frank Andrew Stevenson < frank@funcom.com> writes: > or no knowledge of the problems associated with CSS. What I have done > is device an attack that will recover a CSS key with a complexity of > 2^16 and as little as 6 known output bytes. This should reduce the > keyrecovery time from ~17 hours to a fraction of a second. Yery nice. Especially since the standard says that vts_01_0.vob has to start with: 00 00 01 ba 44 00 04 00 04 01 since the timecode is zero. Andreas -- "We should be willing to look at the source code we produce not as the end product of a more interesting process, but as an artifact in its own right. It should look good stuck up on the wall." -- http://www.ftech.net/~honeyg/progstone/progstone.html
From aholtzma@ess4.engr.UVic.CA Wed, 27 Oct 1999 08:40:27 -0700 Date: Wed, 27 Oct 1999 08:40:27 -0700 From: Aaron Holtzman aholtzma@ess4.engr.UVic.CA Subject: [Livid-dev] Successfull attack on CSS algorithm It would seem that Andreas Bogk (andreas@andreas.org) said: > Yery nice. Especially since the standard says that vts_01_0.vob > has to start with: > > 00 00 01 ba 44 00 04 00 04 01 > > since the timecode is zero. > This doesn't buy us much, as the encryption doesn't start until 128 bytes into the sector. This is well into the PES packet and high entropy land. Also, bytes 84,85, and 86 are used to salt the keystream generator. If you can find enough sectors with these bytes the same, you may be able to perform a correlation attack to recover the keystream. You'd have to look a bit closer at the frame statistics to determine if this is feasible. cheers, aaron
From philburr@usa.net 27 Oct 99 10:36:10 MDT Date: 27 Oct 99 10:36:10 MDT From: philburr@usa.net philburr@usa.net Subject: [Livid-dev] Successfull attack on CSS algorithm Although this may not be too useful for forcing the stream decryption key= unless a section is known unencrypted, this algorithm can be useful to br= ute the private player keys. Here's how: First, some conventions: d =3D disk key from the disk = d' =3D encrypted disk key p =3D private player key d' =3D CSStitlekey1(d, p); t =3D title key from disk t' =3D Needed Master Key t' =3D CSStitlekey2(t, d'); CSStitlekey1 and CSStitlekey2 are very similar. It is important to note the part of code that looks like this: for (i=3D9; i>=3D0; i--) key[CSStab0[i+1]] =3D k[CSStab0[i+1]]^CSStab1[key[CSStab0[i+1]]]^key[CSStab0[i]]; It should be noted here that this is a fairly useless function as far as the encryption is concerned. It is 1 to 1 and is completely reversibl= e. = Also, I should note here that key is the first argument to both functions and k is a function of the second argument(im). Or in other words, k =3D f(im). Now, as I said, that snippet of code is reversible. That is given that CSStitlekey2 modifies t to become t' and we know what t' is and what t is (I am assuming that 1 private/public= key set is known and t' has been found), it is very easy to calculate k. As I said that snippet of code is stupid and simply could have used a simple xor and would have been just as effective. Now given that we now know k, and we know the relationship between k and im is k=3Df(im) we need to reverse f(). Which is what the supplied code does. Now look at the f() for CSSdescramble() and note that it is very = similar the f() for CSStitlekey2() and CSStitlekey1(). It should be very easy (and I've done it) to modify the algorithm to reverse k for CSStitlekey1() and CSStitlekey2(). Now, the only problem is that given k has 5 elements and im has 5 elements, there are MULTIPLE POSSIBILITIES of im which will produce k. In fact, under these circumstances, there are on average about 256 possibilities according to my test runs. Now, given that there are 2 funcions (CSStitlekey1 and CSStitlekey2), given d (the disk key from th= e disk)there should be approximately 65536, O(2^16), possible d' keys (private player keys). Calculating them is very easy. But which to use? For that, one would probably need to run the algorithm= on multiple DVDs and compare the results and find the common keys and keep eliminating until there is only 1 left. I predict that brute forcin= g the private player keys will be fairly easy. cheers, Phil ____________________________________________________________________ Get free email and a permanent address at http://www.netaddress.com/?N=3D= 1
From aholtzma@ess4.engr.UVic.CA Wed, 27 Oct 1999 09:51:08 -0700 Date: Wed, 27 Oct 1999 09:51:08 -0700 From: Aaron Holtzman aholtzma@ess4.engr.UVic.CA Subject: [Livid-dev] Successfull attack on CSS algorithm It would seem that philburr@usa.net (philburr@usa.net) said: > > for (i=9; i>=0; i--) > key[CSStab0[i+1]] = > k[CSStab0[i+1]]^CSStab1[key[CSStab0[i+1]]]^key[CSStab0[i]]; > > It should be noted here that this is a fairly useless function as far > as the encryption is concerned. It is 1 to 1 and is completely reversible. Ummm...no. This is a one way hash function. If you think you can invert it, please do post the algorithm. cheers, aaron
From aholtzma@ess4.engr.UVic.CA Wed, 27 Oct 1999 11:03:45 -0700 Date: Wed, 27 Oct 1999 11:03:45 -0700 From: Aaron Holtzman aholtzma@ess4.engr.UVic.CA Subject: [Livid-dev] Successfull attack on CSS algorithm It would seem that Aaron Holtzman (aholtzma@ess4.engr.UVic.CA) said: > Ummm...no. This is a one way hash function. If you think you can > invert it, please do post the algorithm. > I stand corrected. Upon futher investigation you can reverse this function by building a tree of possible hash inputs back in time. I'm going to shut up now before I say anything else silly. cheers, aaron