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 ***@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 ***@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.

[Sam Hocevar]

1) Anyone cares to see the source code of disckey_hash_invert(), verify it
and possibly make any use of it?

Yes, I'd definitely love to see it. I have been wondering of ways to
make the key detection more robust but haven't tried anything.

2) If yes, how it should be submitted: as an attachment or "inline" code?

Patches sent to the list are OK. If you think it might be too big,
please send it to me personally.

3) Is it "legal" to post such type of code (I assume it is now)?

We have never been threatened by anyone about the libdvdcss code, so
I guess so.