Tech Insider					   Technology and Trends


			   USENET Archives


Electronic mail:			      World Wide Web:
   tech-insider@outlook.com		         http://tech-insider.org/

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

			   USENET Archives


Notice
******

The materials and information included in this website may only be used
for purposes such as criticism, review, private study, scholarship, or 
research.


Electronic mail:			      World Wide Web:
   tech-insider@outlook.com		         http://tech-insider.org/