Página do jqr

A look at the algorithm at the heart of AACS copy protection’s revocation scheme

A lot of technical and mainstream media attention has recently turned towards the ‘cracking’ of the AACS copy protection on next generation media distribution formats Blu-ray and HD-DVD.

In actual fact nothing has been cracked – all that has been recovered is the media key from the memory of WinDVD, which was then fed into a piece of software that implements the AACS standard and decrypts the disc. Nothing is surprising about this – the content obviously exists in a decrypted form at some point in the chain for it to be viewed, and the key that encrypts the disc itself (the media key) has to exist in plain-text for the decryption to occur as well. So content can always be recovered given enough reverse engineering.

What is more interesting is AACS’s counter-measures against this inevitable reality. In simplest terms, AACS contains the ability to prohibit individual players (that are known to be compromised and leaking copyrighted content) from playing any future pressed discs. In fact for a very interesting overview of the capabilities and game theory behind AACS I highly recommend this series of blog articles by Ed Felten and Alex Halderman.

The technology is sophisticated enough to be able to eliminate any subset of players the copyright owners desire, and borrows from algorithms initially developed to protect pay-TV content. This contrasts with the CSS copy protection on DVD, which only can revoke a particular model of player. There exists some confusion I have seen on how this mechanism works. It does not involve new discs causing HD-DVD drives to modify some firmware and revoke themselves (although another part of the AACS specification employs this kind of idea). It is a purely cryptographic solution that no ‘firmware hacks’ can defeat. The rest of this post will concentrate on explaining the functioning behind the revocation algorithm at the heart of AACS - the subset-difference algorithm.

The problem in a nut shell

(I’ll try and be as lean as possible on the mathematics but sometimes it’s unavoidable)

Given a set of N players in the system, only allow |N| – |R| users to be able to decrypt the content, where R is the set of players that have been banned.

If you thought about this problem one of the first ideas you might think of is this – simply give each unique player a different key (player key). Then, encrypt each disc with a media key. Then, at the start of the disc, encrypt the media key |N| – |R| times with each of the allowed player keys. So each player has to find the encryption of the media key that has been encrypted with its player key, decrypt the media key, and then use the media key to decrypt the disk. A revoked player won’t be able to find the media key encrypted with its player key, and thus can’t decrypt the rest of the disc.

The problem with this naïve approach is that the disk needs to contain a key for every permitted player. Suppose there are a billion (non-revoked) such HD-DVD players eventually. This means we need to include the media key encrypted a billion times. Suppose we want to make the media key some length that is cryptographically secure – such as a 128-bit (16 bytes) AES key. This means we include 1 billion * 16 bytes = ~16G of key data before we even start on the disk content. Not even HD-DVD or Blu-ray can afford that sort of space. Interestingly, this scheme is the scheme adopted by CSS, but rather than having a unique key per player, there were several hundred player keys and revoking one with revoke any DVD player models using that key; thus revoking was not really a feasible option.

The subset-cover framework

The basic idea of the subset-cover schemes is to now organize the entire set of players N into (overlapping) subsets T, and assign a unique key to each subset. Then, for each player, give it the keys of each subset it belongs to. Then, when preparing a disc, find a minimal list of subsets S in T that cover the permitted subscribers, and encrypt the media key for each subset Sj in S. This obviously introduces a new trade-off – each player needs to store more than 1 key.

In the example above the 9 allowed (green) players are grouped into 3 subsets, and only 3 encrypted media keys need to be encoded on the disc, because each member of each of the subsets Sj in the cover S will be able to decrypt one of these encrypted keys, and thus the disc. Members of the revoked set R (in red) will not have the keys corresponding to these subsets, and cannot decrypt the disc. Even if all of the players in R form a coalition and share their private information (their player keys), discs cannot be compromised. Thus the scheme is said to be resilient to coalitions of any size, or r-flexible.

How the subsets are specified and how the keys are distributed/computed is specific to the particular scheme within the subset-cover family. Obviously, we need some efficient way of describing subsets that is much better than the performance of the naïve algorithm in terms of both the amount of data in the header of the disc and in the amount of player keys the player needs to store.

The subset-difference approach – subsets

The subset difference scheme is an efficient solution designed by Dalit Naor, Moni Naor and Jeff Lotspiech [2] which uses binary trees and one-way hash functions to essentially ‘compress’ the number of encrypted media keys stored on the HD-DVD down to the order of about 1.38R keys (even less with certain assumptions). Furthermore, each player needs to store on the order of 0.5 * log2(|N|)^2 keys with the subset-difference. With a billion HD-DVD players, this is still only about 450 keys.

The subset-difference approach, like many others, arranges all of the players in the leaf nodes of a binary tree large enough to contain the complete set of players. Each node in the tree, both internal and leaf are numbered.

A subset in the cover (i.e. a set of allowed players) is described by a sub-tree of this master tree, with a sub-tree of this sub-tree subtracted from it. For example, the group of players {1,2,3,4} is described efficiently as the sub-tree from node 2 without the subtree from 5. Thus, a subset can be described with a pair of two integers.

It can be shown that under the worst case scenario, the maximum number of these subsets that will be needed to cover the entire set of legitimate subscribers N \ R is 2|R| - 1. In this example, the number of 4 subsets is far less than that. Here is the complete cover for the example set:

So the header of the disc in this example will contain the media key encrypted 4 times for each of the 4 subsets. Only the members in each subset have the decryption key for that subset. The problem now is how to distribute the keys to each player, for every subset the player is a member of, as it is clear that a single player is a member of many possible subsets. For example, player 1 is a member of the possible subsets S_1,5, S_1,10, S_1,11, S_1,20 and many, many, more. In fact a player is a member of about N possible subsets when subsets are defined in this way. If we assign a player a key for each subset it is a member of then we need to assign it N keys, which is impractical for realistic N (such as a billion players).

The subset-difference approach – assigning keys

For each node – internal and external in the tree the manager of the scheme (i.e. AACS licensing authority) assigns a random key. In other words, each sub-tree in the tree is effectively assigned its own independent key. We call these the label keys (to avoid confusion with other types of key), and label them as L_n for each node.

Now, the final key for a particular subset is generated by taking the sub-tree containing the subset of interest – i.e. to generate the key for {13,14,15} we take the tree rooted at 7 and it’s associated label key:

A variant of the AES algorithm (shown as H(x)) that functions like a 1-way hash is then used to compute the keys for the difference part of the subset. The hash function takes a 128-bit input (the master key) and produces a 372-bit output (i.e. 3 times the length). The left most (denoted LEFT(X)) 128-bits are the interim key for the left node, the right-most 128-bits (denoted RIGHT(X)) are the interim key for the right-node, and the middle 128-bits (denoted MID(X)) is the processing key for this node. By recursively applying this we can compute the key for any subset contained in this sub-tree. In this example, we start with the label at node 7, hash it, take the right-most 128-bits to get the key for node 15, hash this again, and take the right-most 128-bits to get the key for node 31, hash this key and the take the middle 128-bits. This is the key for the subset S_7,31, which the authority can use to encrypt the media key.

Given this key a player can’t calculate the keys for other subsets in this tree because the hash-function is one way. Thus, keys for all subsets within a single sub-tree can be derived from a single key. Furthermore, we can’t use this key to determine the keys for another sub-tree because the label keys were randomly assigned.

The only issue left now is how to distribute keys to a player so that it can only calculate the keys for subsets it is a member of. The elegant solution involves simply giving it the keys that ‘hang off’ (as Naor, Naor and Lotspiech describe it) the path from the root of the sub-tree to the player of interest, for each of the log2(N) sub-trees the player belongs to. For example, for player 1, for the largest sub-tree (i.e. the whole tree), we give it the interim keys of nodes 3, 5, 9 and 17.

For the next sub-tree, rooted at 2, we give it the interim-keys derived from node 2’s label key for nodes 5, 9, and 17. This way the player can only compute the encryption/decryption keys for subsets it belongs to.

And we continue on for each of the log2(N) sub-trees the player is a member of (i.e. for player 1 the next sub-trees would be rooted at nodes 4, then 8 and finally 16 - the player itself).

Now player 1 can calculate the keys for any subset that stems from a tree that contains player 1 but does not exclude player 1. If player 1 were in the revoked set, it would need to be able to compute one of the interim keys (marked in yellow) which, it can’t, because it only has the (blue) interim keys and the one-way hash function does not allow the yellow keys to be derived.

Conclusion

The subset-difference method allows AACS to be able to revoke any desired set of subscribers that are known to be leaking either copyrighted content or their decryption keys but whilst still using a practical overhead in both the AACS-protected discs (i.e. minimizing the number of encryptions of the media key) and keeping the non-volatile secure storage requirements of players feasible (i.e. minimizing the number of interim keys each player has to store permanently). Even all of the blocked players colluding and sharing their private keys cannot defeat this system.

For more information on these algorithms, as well as some interesting optimizations, here is some suggested reading:

1. Fiat and Naor, “Broadcast Encryption”, 1993
2. Naor, Naor and Lotspiech, “Revocation and Tracing Schemes for Stateless Receivers”, 2002
3. Horwitz, “A survey of Broadcast Encryption”, 2003