CrackDiscKey() and possibility of improvement...

[Alan Goluban]

Hi.


I'm not sure whether this is an important issue, but the "libdvdcss" 
currently
doesn't take into account the possibility of multiple solutions for the disc
key hash (when DVDCSS_METHOD equals 'disc'), i.e. when using CrackDiscKey()
function.
I think the CrackDiscKey() shouldn't stop after finding the first 
"candidate",
but rather perform a full space search putting multiple candidates in a 
linked
list, for example. Somewhere later, the candidates should be used to decrypt
the title key, followed by the attempt to descramble the sectors. Only
then it is certain that the right disc (and title) key have been obtained
(if it would correctly descramble the sectors).

Currently, the CrackDiscKey() stops after finding a first candidate. I was
playing with my own version of CrackDiscKey() long time ago, but not in the
galaxy far, far away... ;)
I named that function disckey_hash_invert(). For 11 "real world" DVD 
disc key
hashes, it found 18 possible solutions (some hashes even have 3 solutions).
It's not a sample big enough to be statistically relevant, but it can be
roughly estimated that there are over 1.5 solutions per hash (maybe 
there is a
more detailed analysis on this issue that I'm unaware of).

What may be important is that the function I developed runs 2.5 times faster
than the current libdvdcss's implementation of CrackDiscKey() (on 
systems with
"enough" RAM so the swapping doesn't occur!).
Even more important, it doesn't require 64MB + 640KB of memory for 
tables - it
uses eight precomputed tables (of which one is p_css_tab1[]) using exactly
8000 BYTES in total. The code of the function is also roughly 2.5 times 
shorter.
Thus, it would run happily on C64 or even ZX-Spectrum. :-)

On a PIII at 1GHz/384MB PC it takes 4.83 seconds to find all possible 
solutions,
while CrackDiscKey() takes 12.24 seconds per one hash (compiled with 
gcc-3.2).
Things are drastically different on SS20 system with SuperSparc at 50Mhz 
and 64MB
of physical RAM; the disckey_hash_invert() takes 42.64 seconds per hash, 
while
CrackDiscKey() choked the machine and I was unable to invert even a 
single hash
due to disk swapping - I interrupted it after 35 minutes at iteration 765952
out of 16777216 in "big table init" (all compiled with Sun C 5.5 compiler).

Of course, who will run applications that use libdvdcss on a such 
machine these
days; but if things can be done much more effectively, efficiently and 
in more
elegant and clean manner, then why not?

The main reason for using only (exactly) 8000 bytes is that the state of 
17 and
25 bit LFSRs (actually 16 and 24 bits determine an initial state of them) is
dividing the lookup tables. For example, instead of using single lookup 
table
for the 25 bit LFSR of 2^24 entries (64MB), three tables (High, Med and Low)
of 256 entries can be used; if the state of the LFSR (here after 40 cycles)
have to be determined given the initial state X, then it is obtained as:
   LFSR25(X, 40) = High[(X >> 16) & 0xff] ^ Med[(X >> 8) & 0xff] ^ Low[X 
& 0xff]
The 17 bit LFSR can be split into two tables each of 256 entries 
analogously.

The complexity of alternative function is also 2*2^24 = 2^25; the three 
nested
loops iterating to 256 plus the guessed value of "borrow" (0 or 1) - the 
same
as for CrackDiscKey(). Furthermore, the candidate is reported at two 
places in
function CrackDiscKey() - the place it reports the possible solution
corresponds to the value of borrow for disckey_hash_invert(). This 
(informally)
shows the equivalence of these two functions.
But disckey_hash_invert() function doesn't run time and memory consuming 
2^24
iterations for "initing" the huge table.

And finally, what all this is about:
   1) Anyone cares to see the source code of disckey_hash_invert(), 
verify it
      and possibly make any use of it?
   2) If yes, how it should be submitted: as an attachment or "inline" code?
   3) Is it "legal" to post such type of code (I assume it is now)?


Regards,
Alan.



-- 
This is the libdvdcss-devel mailing-list, see http://developers.videolan.org/
To unsubscribe, please read http://developers.videolan.org/lists.html
If you are in trouble, please contact <postmaster at videolan.org>