[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: EFF misstatements in DeCSS brief

David Wagner writes:
> Looking at the cipher, it appears that it may be possible to discover
> much of its structure with many millions bytes of known text.  Here's
> the mathematical analysis.  Get many streams of known text, and derive
> the corresponding keystream output for each stream.  The internal state
> of the cipher is only 40 bits wide, so by the birthday paradox, there
> is a good chance of a `collision', i.e., an overlap in some pair of
> keystream sequences.  This overlap is easily detected if you only think
> to look for it, and it tells you a lot about the cipher.

A very interesting possibility.  Can you provide a URL which describes
the CSS cipher (or a meta-pointer which can lead to a description, to
avoid legal complications)?  It is certainly questionable for a stream
cipher to have only a 40 bit internal state.  Would this suggest there are
cycles of only 2^20 bytes, enough to be easily detectable in a single DVD?

>     This insight might spark the hypothesis that the keystream might be
>     generated as the sum of two LFSRs.  If you think to check this
>     possibility, an obvious approach is to try sliding two keystream
>     sequences against each other and subtracting; and, if you get the
>     offset right (prob. 1/2^25, so by the birthday paradox, thousands
>     of streams should suffice)

Thousands of streams would mean purchasing thousands of DVDs, right?
That makes for a rather expensive attack, and would strain the resources
of the typical cryptographer who is determined to do it the "hard way"
without peeking at the answer which lies before him in the DVD software.