Case Study
Overview and Cryptanalysis of the DvD Contents Scrambling System and DeCSS

The DeCSS (Decrypt CSS, or the ‘De’ is like the ‘De’ in Decipher as against cipher) is surrounded by controversy. There are sides for and against DeCSS. The against side is represented mainly by the "Motion Picture Association of America" (MPAA) and the for side is represented mainly by the LiViD community. It was to the LiViD website that the original "anonymous" email posting of the DeCSS algorithm was sent.

The MPAA cites its main objection to the creation and distribution of the DeCSS algorithm as breach of copyright because DeCSS allows the content of DvD’s to be copied to a computer’s hard disk. A secondary, but equally important, concern to the movie industry is the bypassing of the region codes as a byproduct of decrypting the DvD contents. The MPAA says "Regional DvD coding was devised to protect the theatrical distribution market for motion pictures in international markets." [4]

The "hacking community" at large believes the existence of the DeCSS algorithm does not contravene copyright laws by its mere existence. They also believe the region coding on the DvDs allows the movie industry to charge inflated prices outside of the United States. They believe the movie industry does not want the consumer to enjoy the benefits of the global economies as the movie industries itself. They say that books and CDs may be bought on holiday or over the Internet between the US and Europe or Australia, so, why not DvDs?

Some Hacking sources say the original reason the hacking and open source communities came up with the crack for the CSS algorithm was to enable the creation of an open source DvD reader. Thus enabling users of open source operating systems such as Linux to be able to view DvDs on their own PCs.

There are many arguments for and against DeCSS but it does inarguably now exist, and cannot be wiped out of existence. The CSS was a complex algorithm, and the fact it was broken by volunteers over a period of around twelve months indicates the strength and commitment of the hacking community.

This paper, however, discusses the CSS algorithm itself. I’ll attempt to explain the strength and weakness of the algorithm and then produce an "Attack Tree" as outlined in Schneier’s paper [14].

The video information stored on a DvD is stored in a file system called "The Micro UDF file system". The main item of importance is that the files are stored in directories and subdirectories, not dissimilar to that of the DOS file system. And it is easy to implement, which precludes the need for a complex operating system in the DvD players.

All the files must be stored sequentially in a specific order on the disk for a DvD player to accept the disk. All video content on a DvD is found in a directory called "VIDEO_TS". There are three types of files contained in this directory. They are ‘.VOB’ files which contain the video and audio data in MPEG-2 or MPEG-1 formats. ‘.IFO’ files contain the information on how and when to play the data in the .VOB files. And finally ‘.BUP’ files contain a backup of the data in the .IFO files, as this information is critical for the DvD to remain playable. The files are always stored in the following order .IFO, .VOB1….,VOBn, .BUP.

On every DVD-Video a Video Manager (VMG) has to be present. The VMG consists of an IFO file (VIDEO_TS.IFO) which contains information that is global to the disc, for example in which region it may be played. Also it may contain information on how to display an optional menu for which the data is stored in VIDEO_TS.VOB. This is the menu the player shows first when a DVD-Video is inserted. Most menus allow jumping to specific scenes of a movie, subtitle selections and access to additional or deleted scenes etc.

At least one video title set has to be present on each DVD-Video. A video title contains the actual data to be presented, i.e. a movie. The different video titles are stored in files named VTS_xx_y.VOB, where "xx" is the title number from 01 to 99 and "y" a number from 0 to 9. MicroUDF limits the file size to 1 GB; movies have to be stored on more than one file. The VTS_xx_y.IFO file provides all the information about the video and audio format of the corresponding VOB.

The information in this section is largely based on a paper by Frank A. Stevenson "Cryptanalysis of Contents Scrambling System". For clarification of information represented in the paper I have referred to the original source code posted to the LiViD Developers list.

The CSS System comprises two entities: the DvD Player, and the DvD Disk. The ultimate aim of the system is for the DvD Player to Authenticate itself to the DvD. Find out which Disk Key (D_A) the Disk has its title keys (D_B) encrypted with. Then decrypt the title keys. And for each title key decrypt the associate ‘.VOB’ file.

The DvD Player contains a number of Player Keys, from one to 409 (K_pN, N = 1…409). Each player key is 5 bytes long. Which give a key length of 40 bits.

The DvD Disk has the following.

dk_N, which is the Disk Key encrypted with player key N (K_pN). The DvD only has one of these.

Hash of length 40 bits, which is the Disk Key (K_d) encrypted with the correct K_d, using the CSS Algorithm in encryption mode A (D_A)

tk, which is the Title Key encrypted with K_d, using CSS Algorithm in encryption mode B (D_B).

Examining "Flow chart #1: Basic Content Scrambling System Algorithm" it can be seen the process is as follows.

The DvD Player uses equation (1) and the first of its player keys K_pN in an attempt to decrypt the Disk Key K_d.

The player then checks its decrypted value of K_d to ensure it is the correct one, by attempting to decrypt the hash contained on the disk using equation 2.

Equation (2) K_d = D_A(hash, K_d) => Decrypt hash with K_d using CSS Decryption mode A.

If the Kd is the valid one, the hash will decrypt to K_d itself. If the decrypted hash is not K_d, the DvD player tries the next Player Key available. It continues checking until it finds a matching K_d, hash pair. If none is found then the DvD player cannot read the disk!

When a matching K_d, hash pair is found the DvD Player can then decrypt the title keys contained on the DvD Disk using K_d and the CSS Algorithm in mode B (See Equation 3 below).

Equation (3) K_t = D_B(tk, K_d) => Decrypt tk with K_d using the CSS Decryption mode B.

The contents of the DvD may now be decrypted using the Title Key K_t found using equation 3.

Each sector of the data files is optionally encrypted with a key derived from K_t by an exclusive OR of specified bytes from the unencrypted first 128 bytes of the 2048 byte data sectors.

The CSS Stream Cipher is made up of two Linear Feedback Shift Registers (LFSRs). The LFSRs are clocked 8 times per byte output. There are four ways to combine the output of the two LFSRs (modes of operation) which is accomplished by two inverter switches. The modes of operation are further

The modes of operation are as follows.

1. Authentication of the DvD Player to the disk.
2. Decryption of the Disk Key (Decryption mode A).
3. Decryption of the Title Key (Decryption mode B).
4. Decryption of the Data Blocks.

The CSS Stream Cipher is shown in diagrammatic form in Figure 2.

Click for full size

In comparison to the Alleged A5 Stream Cipher [6] it is relatively simple. The A5 Stream Cipher has three LFSRs and stop start mechanisms to further confuse its output.

LFSR1 is 17 bits with two taps at 15, and 1. It is initialised with the first two bytes of the key material. The most significant bit is set to 1, to prevent null cycling.

LFSR2 is 25 bits wide, with four taps, at 23, 20, 19 and 11. ([18] by code examination). LFSR2 is initialised with bytes 3, 4 and 5 of the key shifting all but the least significant bits up one position (Thus bit four would be zero due to the shifting). And then bit four is set to 1 to prevent NULL cycling.

The two outputs are combined with carry to produce the CSS Stream Cipher output. The carry is added to the next output byte See equation (4).

If the output of LFSR1 is O₁(j) where j = 1 to N.

And if the output of LFSR2 is O₂(j) where j = 1 to N.

Then the combined output is …

Equation (4) O(j) = O₁(j) + O₂(j) + carry, where carry is the carry bit from O(j-1).

When the CSS Stream Cipher is being used in either "Decryption of the Disk Key" or "Decryption of the Title Key" modes, the input data is mangled in a further step using a mangling function (Figure 3: CSS Mangling Function) before being exclusive ORed with the output of the Stream Cipher. This mangling function is not used when decrypting the data blocks on the DvD. [5]

The Mangling function is represented by the diagram in Figure 3.

The inputs enter the mangling function from the top of the diagram at ‘A’ (bytes 1 to 5) and are output at the bottom of the diagram at ‘C’ (bytes 1 to 5).

Level ‘B’ (bytes 1 to 5) is an intermediate stage, which is necessary for a better understanding of the algorithm.

The mangling function handles 40 bits or 5 bytes of data at a time.

Kj = O(j) where j = {1, 2, 3, 4 and 5} the five initial output bytes from the CSS Stream Cipher.

The equations for the Mangling function are as follows [16].

B(j) = XOR( F( A(j) ), A(j-1), k_j) for j = { 2, 3, 4, 5 }

B(1) = XOR( F( A(1) ), B(5), k₁)

C(j) = XOR( F( B(j) ), B(j-1), k_j) for j = { 2, 3, 4, 5 }

C(1) = XOR ( F(B(1)), k₁)

Where F is a permutation of a byte, and is defined in a byte permutation table. (Not shown here, see [5]).

I’ll explain each in turn.

(1). Initialise communications with the DvD Player (Player). The Player sends back some information confirming it is able to communicate.

(2). If the initial communication with the Player is OK, the Host sends nine bytes of challenge data to the Player.

(3). The DvD Player responds to the challenge data sent to it, by sending the host a key, Key1. Key1 is generated using the CSS Algorithm in one of 32 modes. The host (computer software) examines Key1 and ensures it can also generate Key1 from the challenge data sent. If the generated and received keys match, then the Player has been authenticated successfully to the Host.

(4). The Player sends the Host its challenge data. The Host then encrypts this challenge data using the CSS Algorithm.

(5). The Host sends the Player the generated key, Key2.

(6). The Player responds with either "Authentication Established", or "Authentication Failure". If Authentication is established communication can continue between the DvD Player and the Computer Software.

In this section I’ll outline the attacks that have been used on the CSS Stream Cipher thus far, and attempt to build an Attack Tree, which could be used to cryptanalyse and evaluate other such proprietary systems, and hence be added to a cryptanalyst’s tool.

There are five attacks on the CSS Stream Cipher and associated components of the system thus far. The attacks can be categorised as follows with the level of difficulty for each attack indicated (2^x).

• Brute Force Attack on Hash of the Disk Key (2⁴⁰).
• Attacking the CSS Stream Cipher
• Six Output bytes known (2¹⁶).
• Five Output bytes known (2¹⁶).
• Known Cipher Text and Plain Text attacks on the Mangling Function (2⁸).
• Better Attack on the reversible Disk Key Hash (2²⁵).

Brute Force Attack on the Hash of the Disk Key (2⁴⁰).

Once the CSS Stream Cipher had been uncovered and it was realised that 40 bit keys were in use (due to export restrictions in the US), a "Brute Force" Attack on the Disk Key Kd was possible. With a 40-bit key there are 2⁴⁰ possible combinations. Code was written which could try 17e6 potential hashes/second [2] on a Celeron 366 (a slow machine by today’s standards). This gave a search time of approximately 17 hours. It was found that the hash function (i.e. the CSS Cipher) is not a bijection, thus a number of ‘valid’ keys could be found. At the time it was recommended to the reader (of the source code) to try multiple DvDs to ensure they had the correct key. [2]

Thus with the known Disk Key, and the CSS Cipher output known, it was possible to read the content of DvDs.

Seventeen hours is still a fairly long time, so the challenge was put out to improve on the 2⁴⁰ combinations and thus completely ‘break’ the CSS Algorithm.

The aim of this attack is to find the initial states of LFSR1 and LFSR2.

Examining fig 1 it can be seen If the output bytes O(j) where j = {1, 2, 3, 4, 5, and 6} are known. An attack of 2¹⁶ is possible. Because the MSB of LFSR1 (width 17 bits) is set to one on initialisation, we only have to guess the remaining 16 bits.

This is done the in following way.

1. Guess the initial state of LFSR1, up to 2¹⁶ (65536) times.
2. Clock out 4 bytes, O₂(1), O₂(2) , O₂(3) , O₂(4) can be uniquely determined.
3. From the bytes above the state at j = 4 is known.
4. LFSR1 can be verified by clocking out 2 or more bytes of the cipher and comparing the result.
5. Upon finding the initial Start State of LFSR1 and LFSR2 we have the original key material, as the keys provide the initialisation state for the Stream Cipher.

The aim of this attack is to find the initial states of LFSR1 and LFSR2.

Examining fig 1, once again, if output bytes O(j) where j = {1, 2, 3, 4, and 5} are known. An attack of around 2¹⁶ is once again possible. It is done in the following way.

1. Guess the initial state of LFSR1, up to 2¹⁶ (65536) times.
2. Clock out 3 bytes. O₂(1), O₂(2) and O₂(3) can be found as in Attack 1. All the bits of LFSR2 are revealed except for the MSB of LFSR2 (Remember it is 25 bits, 3 bytes are 24 bits).
3. Try both alternatives for the MSB.
4. Clock LFSR2 backwards 24 steps (i.e. one bit at a time).
5. LFSR2 should now be at state 1 (j=1). The value of bit 3 (assuming we start from bit 0) should be set to one, as it is set at initialisation.
6. Clock out two more bytes to verify the guess for LFSR1.
7. Upon finding the initial Start State of LFSR1 and LFSR2 we have the original key material, as the keys provide the initialisation state for the Stream Cipher.

The aim of this attack is to get k₁ to k₅ and thus recover five output bytes of the CSS Stream Cipher, which can be used in the CSS Stream Cipher Attacks.

Examining the Mangling Function Diagram Figure 3.

For a known Cipher Text and Known Plain Text attack on the Mangling Function the steps are as follows.

1. Guess k₅ (See Diagram), up to 2⁸ (255) times.
2. Make the following calculations in the order shown,
   
   B(5) = XOR( F( A(5) ), A(4), k₅)
   
   B(4) = XOR( F( B(5) ), C(5), k₅)
   
   k₄ = XOR( F( A(4) ), A(3), B(4))
   
   B(3) = XOR( F( B(4) ), C(4), k₄)
   
   k₃ = XOR( F( A(3) ), A(2), B(3))
   
   B(2) = XOR( F( B(3) ), C(3), k₃)
   
   k₂ = XOR( F( A(2) ), A(1), B(2))
   
   B(1) = XOR( F( B(2) ), C(2), k₂)
   
   k₁ = XOR( F( A(1) ), B(5), B(1))
   
3. Verify the guess on k₅ by checking and calculating C(1) = XOR( F( B(1), k₁)

If k₅ verifies, then we have recovered five output bytes of the CSS Stream Cipher.

The aim of this attack is to recover the Disk Key in better than brute force time.

Examining Figure 3, the attack follows the steps below and has a complexity of 2²⁵ (33,554,432).

I’ll first point out that the data is mangled via the CSS Mangling function after it has been XORed with the output of the CSS Stream Cipher, thus C(1) to C(5) are the five demangled output bytes (80 bits) of the hashed key! k₁ to k₅ are the five initial bytes output from the CSS Stream Cipher. A(1) to A(5) are the hash bytes of the Disk Key.

Hash = XOR(CSS Stream Cipher 5 bytes output, Mangling Function Output)

The aim of this attack is to get k₁ to k₅, which will be the decrypted hash of the Disk Key, i.e., the Disk Key will be revealed!

This attack was reputed to take 18 seconds on a Pentium III 450Mhz. [16]

The basic idea of an attack tree is to present all possible actions to take when presented with a given problem. This can be presented either in graphical form, or in indented textual form, like I’ve done below. See [14] for a complete description of Attack Trees.

The Attack trees are used by beginning at the top of the tree and working your way down. If the condition on the level of the attack tree is true or applies then enter the indented text below the current level. Otherwise go to the next line of text with the same indentation.

I’ve created two Attack Trees. The first is someone who has a DvD and would like to view the DvD. Therefore the goal of the first attack tree is "Play a DvD". There are a number of possible options, which range from buying a legal DvD player, to writing your own version of DeCSS.

The second attack tree has a goal of "Decipher secret from a CSS ‘like’ cipher". In this second attack tree I’ve attempted to capture how I think the original breakers of the encryption scheme may have methodically broken down the CSS algorithm and associated components.

• Get a Legal DvD Player.
• Build own copy of DeCSS from scratch (OR)
• Get Copies of official documentation from CCA of stream cipher (Cost $5000).
• Build legal version of a DeCSS Algorithm.

• Get Copies from someone who has bought them from the CCA.

• Use information in documentation to build own illegal version of DeCSS.
• Get Copies of DeCSS from the Internet.
• Compile and build illegal DeCSS.
• Break CSS Cipher and build DeCSS from scratch (AND)
• Figure out initial structure of cipher (AND)
• Reverse Engineer Cipher.
• Reverse Engineer mangling function.
• Figure out player keys from known attacks on algorithm
• Build own illegal copy of DeCSS

• Get the cipher structure from LiViD server.
• Use information to write own illegal copy of the DeCSS Algorithm

• Structure of cipher is known.
• Structure is that of the CSS Stream Cipher.
• Use known attacks on cipher.
• Cipher is different to that of the CSS Stream Cipher.

• Brute Force Attack on cipher.
• Break down the cipher into component parts.
• Devise attacks against individual components.
• Combine attacks to improve on brute force.
• Attempt known Cipher Text and Plain Text attacks.
• Refine attacks to reduce the number of known output and input bytes needed.

• Structure of cipher is unknown.
• Establish Structure of cipher.
• Go back to the top of attack tree.
• Unable to Establish Structure of cipher.
• No Solution at this point in time.

The CSS Algorithm has been completely broken. It was intended to provide a cipher with strength of a 40-bit key. The algorithm fell far short of the 40-bit protection offered by the key width. The strength of the cipher has been proven to be only of complexity 2¹⁶.

A number of lessons can be learned from the events surrounding the CSS algorithm.

The CCA along with the MPAA attempted to move into the field of cryptography which is a very complex field. Upon entering the field of cryptography they broke all of Bauer’s proposed five "Maxims of Cryptology". [3]

The open source hacker community broke the CSS cipher in less than 12 months.

Rumor has it from emails on the LiViD website that the CCA had the algorithm analysed by a cryptanalyst at Intel, who informed them the encryption algorithm was weak, but they did not heed the warning.

The adversary discovered the algorithm. Because the algorithm was weak, it was duly broken.

The CCA and MPAA were fooled by the little understood digital wizardry of digital encryption schemes, into thinking a weak encryption scheme kept secret would guard their DvD secrets.

Licensing a software version of the DvD player allowed an easily reversible (to a competent programmer) version of the algorithm into the public space.

• Title search pointer table
  Describes which title can be found in which video title set, how this is linked to other titles and the start address of the corresponding VTS.
• Video Manager Menu Program Chain Information Unit Table
  This provides pointers to the VMG Menu in different languages
• Parental Management Information Table
• Video Title Set Attribute Table
  A copy of the attribute information for each VTS on the disc.
• Text Data Manager
  Here the volume name, title name, Album name and/or Producer name for the disc or for every title can be found.
• Video Manager Menu Cell Address Table
  Stores the start and end addresses of all cells in the VMG VOB.
• Video Manager Menu Video Object Unit Address Map
  Provides the start addresses of all VOB units.

Bibliography

End of Document.