Understanding AACS (including Subset-Difference)

[arnezami]

For those that have been following the developments lately concerning HD DVD and Blu-Ray decryption it might seem difficult to get a grip on what has actually happened. There has been so much talk about so many different kinds of Keys and IDs that everything might start to look like a big blur of encryption gibberish. So far there has not really been any overview of what has actually been "broken" and what the consequences of some of the recent finds are. Basicly there is a gaping hole in our understanding of how things work which prevents us from making any definitive conclusions about the meaning of events occured. The biggest gap being the Subset-Difference technique used by AACS.

With this post/article I would like to fill this particular gap. It is meant to explain how the Subset-Difference technique works. Before that I will quickly explain how the general picture looks like so you can see how and where the Subset-Difference technique fits in.

[edit] If you're really new to AACS you might want to read this thread (http://forum.doom9.org/showthread.php?t=124505) first.

AACS in general

The following is a picture some of you might already have seen. Its a main overview of the AACS protection system. It shows the disc and the player and "all" the important keys involved in the decryption process.

http://img367.imageshack.us/img367/6008/progress6km3nf8.png

MKB = Media Key Block
Process MKB = Subset-Difference Tree system
Km = Media Key
Kvu = Volume Unique Key
Encrypted Key = Encrypted Title Key
Kt = Title Key

What it shows are all the necessary pieces of information you need in order to decrypt the content. And each piece has a role.

Subset-Difference Tree system: essentially a giant and largely secret collection of never changing Processing and Device Keys derived from one Master Device Key (or a few). Device Keys can in essense be used to derive a desired Processing Key and because only a few Device Keys are given (hidden in the Player) only a part of all Processing Keys are "reachable" by any given player. This is used for not allowing ("implicitly revoking") certain players to be able to find the right Processing Key (which is needed to get the Media Key).
Media Key: you could argue this is the "core" Key. Its derived from the Processing and a C-value (which is taken from the MKB file) and is in a way the end result of the Subset difference method. Its different for every movie. So if you find one Media Key you can only decrypt one movie (if you manage to get the Volume ID).
Volume ID: this is used to prevent bit-by-bit copying: the Volume ID can only be retrieved by asking the drive in a special way (its not stored in a file on the disc). When copying a encrypted disc this piece of information will not be on the copy thus making it impossible to decrypt/play the content: the copy won't work. The volume ID should normally only be retrievable given a Host private key (which is hidden in the player). The Volume ID is combined with the Media Key to produce the Volume Unqiue Key. And that Key can decrypt the Title Keys.
Multiple Title Keys: even if you managed to find one Title Key this will only allow you to decrypt part of the content thus making it harder because you need to retrieve all of them. This difference in Title Keys can only be accomplished by giving multiple encrypted Title Keys.
Those are the basics of AACS. While I could go into more detail concerning all these parts I will now concentrate on the Subset Difference technique since its the hardest to understand and least transparent.

The Subset Difference technique

In order to explain how this technique works its best to show how its works in its basic form. Only then we can see how more complex things like "multiple non-adjacent revocations" work. But I will not start explaining it by talking about all kind of cryptographic techniques used. I will begin with giving a real-world-like illustration/analog that everybody can understand while in the meantime being quite accurate in showing how this technique actually works. When reading the next part keep in mind: the subset-difference technique is all about reachability.

Driving a truck

The following picture shows a (tree-like) network of roads, several Parking spots and a truck with a long trailer:

http://img53.imageshack.us/img53/5931/tst5a1ji6.png

The idea is this: the truck cannot make tight turns (90 degrees is its best) and it can't go into reverse. When you look at the picture you can imagine to which places the truck can actually drive. To make it a little easier I colored the parking spots green and red to show which of them are and are not reachable from the starting position of the truck. It may not look like much but if you understand this then you're already quite a long way there of understanding the subset difference method. So look at it closely and let it sink in. :)

How it goes:

The story is like this: you are given a truck with several boxes in it and some instructions. These say you have to reach a specific Parking spot in order to get some information (carved in stone at this Parking spot). This information is important because it gives you the ablity to open one of the boxes (with a "C" on it) in your trailer. In this C-box there is a key (with an "M" on it) which in turn allows you to open other boxes (this isn't part of the subset difference anymore so the illustration ends here). Suffice to say: if all goes well you end up with opening a box with a nice present in it ;).

Revocation:

The thing is you cannot reach every Parking spot. So if you happen to have a starting position from which the Parking spot isn't reachable you will never get the present. Lets say the person that gave you the truck and boxes has also given these trucks to all kinds of people (who have different starting positions) and he does this regularly because he likes to give away presents. And lets assume he doesn't like you anymore (you were unkind to him because ... well fill in yourself). From now on he can choose a Parking spot not reachable by you. He would make sure the C-box can only be opened with the information from that (for you unreachable) Parking spot. This means you will never be able to get any presents from him anymore. You are "revoked".

You now know how the subset difference technique works :D.

Well in principle ;).

How it works in AACS

The reason why the subset-difference method may seem so hard to understand is because they had to make the above work using existing cryptographic techniques. And that could confuse you. Hopefully though since you read/looked at the above you now know the principle design of how it is supposed to work so you will get less confused by the crypto talk: in essence its all a computational way of making information "reachable" or not. Thats basicly it.

To explain how it works in AACS lets first look at the letters/examples I mentioned and clarify them:

- Parking spots: these are the Processing Keys. These are the goals to reach. Keep in mind Processing Keys don't change: the only thing that changes is the choice of the "man who gives presents" which one of all the Processing Keys has to be reached.
- The instructions: these "instructions" are in the MKB file and tell you which Processing Key (parking spot) you have to get to.
- C-box: this is a C-value in the MKB file. In fact a C-value is simply an encrypted Media Key (a "locked box" if you will). There is more than one C-value but I will get to that later (when it gets complicated ;)). In reality there is only one C-value in use at the moment.
- M-key: you guessed it. Its the Media Key. Its the result of the Processing Key and the C-value.
- You/the truck: you are basicly the Software player that tries to get to the Processing Keys.

Now what is obviously still missing are the Device Keys and an explanation of how you "drive" cryptographically. I will deal with that now :).

Device Keys:

To do that lets first look at an example of driving towards a Parking spot:

http://img95.imageshack.us/img95/7603/tst7a1os7.png

As you can see the truck has to drive north first and then goes south. This is always the case: first north (NE/NW) then south (S/SE/SW).

In reality in AACS there is no driving north: this part is skipped and you simply "jump" to the point where you start driving south (the purple arrow). But you can only jump to points that would in fact be reachable (if you would have done the actual northish driving first). As you can see in the picture I've marked the point where the truck starts going south (the purple arrow). This is the Device Key. Device Keys are the points where you normally would start driving south.

Here is a little more zoomed out picture which depicts the starting-to-drive-south points (= Device Keys) in purple:

http://img412.imageshack.us/img412/1109/tst9a2xy3.png

What you may have noticed is that these Device Keys are all right along the path north. In fact there are as many Device Keys for a tree as there are branches along the path from your position to the top of the tree. In order to drive towards a certain parking spot (Processing Key) you first need to look at the map and see which Device Key has to be your starting point (only one allows you to go to the Processing Key). From there you can "drive" southwards towards the desired Processing Key. Also notice that along the path north the are red Parking spots. These are the Processing Keys you will never be able to get to. But all the rest of them are reachable by you (green).

Driving:

In AACS "driving" always starts with a Device Key. So there is no need to drive north only south. But when going south it should also not be possible to reverse. In order for that to work they have made it impossible to go north at all (which is also why the "jumping" was needed I talked about above).

How? Well they use one-way functions: you take a Device Key and do some operation/function on it (AES-G3 to be exact) and you can get any of three things: a left sub-Device Key, a right sub-Device Key or a middle Processing Key. Whichever one you need at that point. (note: a sub-Device Key is a Device Key you generated this way. While a Device Key is given to you). Driving simply means: doing this operation on (sub) Device Keys. With each operation you move toward other sub-Device Keys (you move SE or SW in the tree) or you move towards the Processing Key (you move S in the tree and you stop). But there is no function/operation to do the reverse thus preventing you to go north.

Thats essentially how its implemented in AACS. And its equavalent to the story with the truck above.

--- Just to clear up the above pictures: the yellow arrows is the path north (in AACS driving this path isn't actually done). The purple arrow is a Device Key (this is a point where you start driving in AACS, thus skipping the northern route to it). The blue arrows indicate Keys that are somehow derived from a Device Key (sub-Device Keys and Processing Keys). The green Parking spots are Processing Keys you can reach. The red Parking spots are Processing Keys you can't reach. ---

[continued in next post]

[arnezami]

Subsets and revocation

You may have been asking yourself why its called a subset-difference method and how the revocation works (also for "multiple non-adjacent revocations" whatever that means ;)). I will explain that here.

First lets see how simple revocation works. Lets look at this picture (i've added trucks):

http://img100.imageshack.us/img100/6576/tst10a1sh3.png

Each truck represents a Software Player: they each have a "truck" and a starting position. Each one of them can only go to a certain amount of Parking spots, but no two trucks can go to the same set of Parking spots.

I've added the choice (by the "present giving man") of the Processing Key to be found (the blue circle). As you can see this revokes truck nr 1 and 2 (indicated by a red truck). This is because they both cannot get to the circled Parking spot. So by choosing the Parking spot correctly the AASC LA can revoke one or more adjacent "trucks" this way.

Good for them. But how do they revoke "trucks" that are not next to each other? Your intuitive response might be to use two (or more) Parking spots inside the tree. There are however problems with that idea. Let me give this example (this is not how its done but is just to demonstrate why they need something more than just one big tree)

http://img75.imageshack.us/img75/3937/tst10a3hl8.png

As you can see there are now two Parking spots that if reached give information to open the C-box. The intend is to revoke trucks 1, 2, 7 and 8. Well thats the idea at least. But it doesn't work. Why? Because trucks 1 and 2 can now reach the Parking spot to the right and trucks 7 and 8 can still reach the Parking spot on the left! So by doing it this way nothing is revoked (which clearly wasn't desired). The problem is caused by the fact that the positions of these trucks are not adjacent. In other words: "non-adjacent revocation" isn't possible with this method.

The solution: additional sub-trees. Basicly making it a giant "parking garage" with several floors (about 22) where each floor is twice as small as the one beneath. The top floor being very tiny. And an elevator for each truck at the starting position so they can choose the floor they want to drive on.

Here is an attempt to illustrate this:

http://img178.imageshack.us/img178/843/tst1bqq0.png

Each color is a floor. The smaller floors are on top of the larger ones (and since this is a top view you cannot see those parts of the larger lower floor). The red dots are the positions of the trucks to be revoked (these truck can move to the desired floor using an elevator).

Here are the parts relevant for these "trucks":

http://img218.imageshack.us/img218/2941/tst1ajo3.png

Ok. How does this solve the problem? Let me explain. For that we first zoom in again on our to-be-revoked trucks and see how this is done:

http://img227.imageshack.us/img227/4425/tst10a5dk8.png

I've used the same colors so you can match this with the zoomed out picture above. As you can see there are again two Parking spots used. However the trucks 1 and 2 cannot reach the circled Parking spot to the right and the trucks 7 and 8 can't reach the circled Parking spot to the left. So now these trucks (1,2,7,8) have been revoked while the other trucks (3,4,5,6) haven't been.

What is important to note is that since the information coming from the two different Parking spots (Process Keys) is different there is also a different C-value corresponding to the subtrees where the Parking spots lie in. This way it is garanteed that both trucks 3,4 and 5,6 end up with exactly the same Media Key (which is calculated by taking the Process Key and use it to decrypt the corresponding C-value).

How is all this a "subset-difference" thing? Well its not so difficult to see now: take (for example) the subtree containing trucks 1-4. These trucks are a subset of the entire collection of trucks. Another sub-set (trucks 1 and 2) are revoked. If you substract these sub-sets you end up with trucks 3 and 4 (so you take 1,2,3,4 and substract 1 and 2 from that set) which are the non-revoked trucks. Therefore its called a "subset-difference".

Some remarks

Well. That was quite a lot of information already :D. I think I've covered the bulk of the subset-difference method.

Because I know there are going to be questions I also created a separate sections for that: a special FAQ for AASC (which I will extend whenever there are more good questions and whenever I have time). I've also created a seperate post for Advanced AACS topics. Which sort of speaks for itself I hope (its still in progress :)).

I hope I did a good job in explaining this stuff. Suggestions are welcome but purely negative critical remarks that don't help our collective understanding are not sought for. Just keep in mind: I've spend an awful lot of time on this and I'm only human :).

Hope you enjoyed it...

Regards,

arnezami


------

This was posted by FoxDisc after a long discussion and probably some pondering. He says things very well :).

If anyone has followed along this thread, they will realize the complexity of this subject. I thought I might add some things that will help simplify why the AACS LA chose this system. It's not just because it's complicated.

Let's say we want to build their DRM system:

Our first crack at it:
A simple design would be to give every player/device a secret device key. Then we encrypt the media key (the media key lets us decrypt the movie) with every secret key for every device and put all those encrypted copies of the same media key on the disc. Each device would look through all the encrypted copies of the media key on a disc until it found the one it could decrypt. To "revoke" a device we just leave off the copy of the media key encrypted with his secret key!

This would work but it takes lots of space on the disc. We need room for every device present and future. We need keys that are secure (16 bytes minimum) With all those keys, there's no room for the movie!

That was their first concern. They didn't want to use up all the space on the disc.

Our second crack at it:
OK, how about this - we put the devices into lots of overlapping groups. Each device goes into many groups. We assign a secret key to each group. If a device is in a group, he gets the secret key for that group. If he's not in that group he doesn't get the key. Now, the devices have to store more than one key.

What do we do with the disc? Well, we start off by encrypting the media key only once using the key for a really big group that everyone is in. Since they all have that key, every device can decrypt it. This is looking good! We only had to use one key on the disc! We've reduced the space used on the disc by making the devices store more keys.

So how do you "revoke" devices? You stop using the key for the big group (everyone, including the bad boys have that key), and you use keys for smaller groups that the revoked devices don't belong to, but the unrevoked devices do.

This is essentially what the AACS did! A "subset difference set" is just a group of devices. A processing key is just a secret key assigned to that group. All this stuff about subset difference sets is all about ways to divide up the devices into groups so we can give a secret processing key to that group. It's fundamentally simple.

So how do we divide up the devices into groups? How do we decide how many keys to give each device? How do we make sure we can always exclude all the devices that need to be excluded while allowing all the devices we want? How do we know who leaked a key so we can exclude him? How do we make sure that knowing one key doesn't let the bad boy figure out any others? How .....

Whoa! Enough questions already ....... it's time to call in the experts - cryptologists and mathematicians. They think about this for a long while and they come up with: The Subset Difference System.


--------------

FAQ for AACS

This is a FAQ for general AACS matters. I know many of you have questions even (or should I say: especially) after reading all the above.

Here are some of the questions. There will probably be many more so I will extend this list.

Question: Why do we need the Volume ID? We already have a Processing Key!

Answer: Discs on PC based systems are protected in two ways: (1) Only non-revoked Device Keys make it possible to get a valid Media Key (see above) (2) The Volume ID is only given away by a drive if the program that is asking it has proof it has a non-revoked Host Certificate. Software players have that (hidden somewhere) so right now we can sniff the traffic between the Software Player and the drive and retrieve the Volume ID that way. But its not a perfect solution: you really want the Host Certificate/Private Key.

Question: Why don't we need Device Keys? Why do we only need a Processing Key to get a Media Key.

Answer: Well thats because they have chosen the same Processing Key on every disc. Right now there are no revokations in the subset-tree so this means all discs have the same Explicit Subset-difference Record (which are basicly the "instructions" I talked about earlier). This means for each disc we have to go to the same Parking spot/Processing Key.

Question: How does the technique of Processing Key + Volume ID differ from extracting Volume Unique Keys directly from the Software Player?

Answer: Currently the easiest way of getting hold of a VUK is by extracting it directly from the memory of WinDVD. However this is likely to be changed: they will probably "harden" this player so its not easy for anybody to write a program that can easely extract a VUK for everybody who wants to. With a known Processing/Device Keys though you wouldn't need a program to extract the VUK out of the memory of a Software player: you only need to sniff the bus for the Volume ID (or even try to guess it). If you have the VID you can calculate the VUK.

Question: Why are there 253 Device Keys for a Player? Why exactly that (strange) number?

Answer: The largest trees used are 22 nodes high. Because there is a Device Key at each branch from the top to the starting position of a Player it will have 22 Device Keys for that tree. He will also have 21 for its sub-tree. And so forth. This means a Player has 22 + 21 + 20 + ... + ... + 3 + 2 + 1 = 253 Device Keys. :)

Probably many more to follow... ;)

[arnezami]

Advanced AACS Topics

Here I would like to write about certain advanced AACS topics. So I reserved this post for that puspose (because I suspect I need a lot of space and I think its a good idea to put it right after the above explanation so we keep it organized).

The topics I'm currently thinking of are these:

Processing Keys can be different for every movie

This is about the value of the Processing now and in the future. There are ways the AACS LA can issue MKBs in such a way that each disc/movie will have to use a different Processing key thus making a Processing Key in the future much less valueable. However this is really an advanced topic which requires a thourough analysis of what can and can't be done. Its very interesting in itself.

There is also some doubt why the AACS LA hasn't used this techinque. Its possible there was too little time for them to do this properly, or they simply don't understand it themselves. Either way they screwed up by not making use of it in the first place and are not even willing to admit it (when looking at the latest "press release").

Squence Keys and tracing

This is all about sequence keys, segments etc. Currently this isn't used on any of the discs found so far but it may be in the (near) future. This is also an advanced topic so I put it here. There is a lot to be understood about this technique and therefor much to explain.

And maybe there are other advanced topics I haven't thought of. I will see when I have time to write about these subjects.

[mrazzido]

Great Work !! arnezami !!!!

[blutach]

Thanks for that arnezami. Very easy to understand. Well done!

Regards

[xyz987]

Great!

:thanks:


Advanced AACS Topics
This is about the value of the Processing now and in the future. There are ways the AACS LA can issue MKBs in such a way that each disc/movie will have to use a different Processing key thus making a Processing Key in the future much less valueable. However this is really an advanced topic which requires a thourough analysis of what can and can't be done. Its very interesting in itself.

There is also some doubt why the AACS LA hasn't used this techinque. Its possible there was too little time for them to do this properly, or they simply don't understand it themselves. Either way they screwed up by not making use of it in the first place and are not even willing to admit it (when looking at the last "press release").


I think using a different Processing Key per movie is not a good idea for them. Now they have to revoke just one Processing Key, but firts they need to close the hole. They have "lost" just one Processing Key per hole. If they use 150 keys (one per movie), they will lose 150 keys per hole. In the future tens of thousand of movies will be released, they would be losing tens of thousand of PKs per newly discovered hole.

A player has only 253 Device Keys. Sure, there are lots of posible PKs and DKs, but it is a limited resource anyway. Already-sold home players must work with any future released movie no matter how many revokations they do. If they don't achieve this goal, the whole revocation system becomes broken.

[guile]

Very impressive!! You have been a very busy boy Arnezami.

To think I feel like I am "Smart" (or something) when searching out my own keys while you are THE guy that figured out the "how" and the "why" makes me feel like a complete idiot in your presence.

Respectfully,

Clueless (g)

[snurregrekk]

thanks for your effort of making this rather hard-to-grasp information easier to understand for us all. very interesting reading! :thanks:

[h.monay]

THANK YOU SO MUCH

I understand it now :D

[Adub]

Well, done mate, well done. I look forward to added information and updates soon.

[h.monay]

here is a pic if ud like to use to show the levels
http://img53.imageshack.us/img53/7382/mkbez3.jpg

[noclip]

You mean Ted Stevens lied to me? It really is a big truck, and not just a series of tubes?

So do you have any ideas about how to get our hands on the AACS LA root key?

[xyz987]

Question: Why are there 253 Device Keys for a Player? Why exactly that (strange) number?

Answer: The largest trees used are 22 nodes high. Because there is a Device Key at each branch from the top to the starting position of a Player it will have 22 Device Keys for that tree. He will also have 21 for the sub-tree its part of. And so forth. This means a Player has 22 + 21 + 20 + ... + ... + 3 + 2 + 1 = 253 Device Keys. :)


Far good :-)

Note however that a player never gets the root Device Key (neither the root master tree key), because a root key can derive the rest of them.

So the largest tree is 23 nodes hight.

[xyz987]

EDIT: I have rewritten this message. Prior version of this message was not an accurate explanation.

Here is a little explanation with numbered nodes. This is a master tree:




1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
/ \ / \ / \ / \
8 9 10 11 12 13 14 15




A master tree is just a tree that complies this rules:

- Any lower key can be derived from higher keys through a one-way function.

- Its keys are used (directly or indirectly) to encrypt or decrypt content

- Its keys can be derived from Device Keys

First of all, what kind of keys are master tree keys?. Posibilities are Title Keys, Volume Keys, Media Keys, Processing Keys, Device Keys or "any other kind of keys" (just to be systematic). Any master tree key is used sometimes to encrypt Media Keys, so it must be a Device Key or a Processing Key. Also it can be used to derive a lower master tree key, and this derived key is used sometimes to encrypt a Media Key. Processing Keys do not comply these conditions, the only kind of key that comply this are Device Keys. So master tree keys are Device Keys.

Player 9 will receive Device Keys 8,5,3. This set of keys is chosen because they can derive any Device Key except the keys from the leaf to the root of master tree. There is no way to derive keys 1,2,4,9 from keys 3,5,8.

If you want to revoke the set of keys player 9 has, i.e. the set of Device Keys that contains key 8 (and only that set), you simply encrypt Media Key with key 9. As stated above the set of keys player 9 has received (8,5,3) can not derive key 9, so player 9 can not decrypt the content.

[HyperHacker]

Let me just make sure I get this last image...

http://img227.imageshack.us/img227/4425/tst10a5dk8.png
In this case, 7 and 8 can't reach that leftmost key, because once they get into the light-blue area they can't turn left back into the other blue area that the key is in? They can only keep going "down" to the lowest floor (the root of the tree)?

[arnezami]

Let me just make sure I get this last image...

http://img227.imageshack.us/img227/4425/tst10a5dk8.png
In this case, 7 and 8 can't reach that leftmost key, because once they get into the light-blue area they can't turn left back into the other blue area that the key is in? They can only keep going "down" to the lowest floor (the root of the tree)?

No. Keep in mind there is an elevator only at their starting point. They first have to choose their floor and then they cannot change floors. So they can't even get to the light blue area: they can only drive on one floor (which is quite small btw). Furthermore they can only move within the confines of the grey roads. So there is no way they can get to the light blue area if they started on the higher floor (the darker one).

As an aside: Also on the light blue floor no P has been chosen. So there is nothing to do there even if they started there.

Regards,

arnezami

[arnezami]

@xyz987: concerning Master Device Keys. I believe every "floor" in the garage has some kind of sub-Master Device Key and each of these keys is probably derived from a Master Device Key.

To be honest though there is not much to say or speculate about it than this. We simply don't know how they derive the Master Keys. And personally I don't think its very interesting since we can never find them out.

The only thing that matters is they have the ability to reach every Device and Processing Key.

[FoxDisc]

@arnezami - Excellent work!

At the present time, all discs use the same Processing Key
(Parking Space). Unless the same Processing Key (which is just a number) appears on different subtrees (levels of the parking garage), this means that the Processing Key in current use is on the largest master tree (the only one that all devices/trucks can access/drive on) No device (truck) can get to a Processing Key that is in its own upward chain. Yet every Processing Key in the master tree is in some (possible) device's upward chain. I'm guessing that there is a special spot in use right now at the base of the master tree that holds the current Processing Key/Parking space instead of a device/truck. All other devices in the tree can get to that spot, except the device/truck that starts there (The truck would already be there, but I thought I understood that a device could not calculate it's own single node Processing Key, as well as all the upward processing keys in its chain to the root.)

I understand the "instructions" in the MKB define the "path" to get to the Processing Key, by using ones to go right and zeros to go left when tracing from the top (perhaps I have it reversed - don't recall). Can you confirm where the current Processing Key is located on the tree/parking level and whether it's down low near the base of the master tree/trucks or up higher in the tree? Is it over on the far lower right or left of the master tree?

[arnezami]

@arnezami - Excellent work!

At the present time, all discs use the same Processing Key
(Parking Space). Unless the same Processing Key (which is just a number) appears on different subtrees (levels of the parking garage), this means that the Processing Key in current use is on the largest master tree (the only one that all devices/trucks can access/drive on) No device (truck) can get to a Processing Key that is in its own upward chain. Yet every Processing Key in the master tree is in some (possible) device's upward chain. I'm guessing that there is a special spot in use right now at the base of the master tree that holds the current Processing Key/Parking space instead of a device/truck. All other devices in the tree can get to that spot, except the device/truck that starts there (The truck would already be there, but I thought I understood that a device could not calculate it's own single node Processing Key, as well as all the upward processing keys in its chain to the root.)

I understand the "instructions" in the MKB define the "path" to get to the Processing Key, by using ones to go right and zeros to go left when tracing from the top (perhaps I have it reversed - don't recall). Can you confirm where the current Processing Key is located on the tree/parking level and whether it's down low near the base of the master tree/trucks or up higher in the tree? Is it over on the far lower right or left of the master tree?
The current Processing Key is in the far lower left of the tree used. This tree is the first tree (out of 513 I believe, I haven't analyzed yet why it isn't 512) which is why the first C-value is used. In other words: the largest tree isn't the 31 nodes high tree (which would be the truely root tree) but several floors higher. AACS simply doesn't use the trees with 31-23 nodes high. Which is why the lowest floor (for AACS) is still didived in approx 500 trees I believe.

If you open your MKBROM.AACS and take/print the docs you can see the all this in the Explicit Subset Difference Record. It takes a little effort but the number 17h (=23d) is already telling. Maybe we should make an MKB file reader or something which graphically shows you which sub-trees are used (and thus have a C-value) and what their "shape" is (the position of the C-values in the trees creating subset-differences). Would be cool and informative in the future (when they start revoking).

There could also be some slight difference in the way it works (at the very lower end) and how I pictured it. But these details will eventually be ironed out ;).

[Jay Bee]

Looks like a good effort!

But personally I didn't get any further than the first image. Maybe an explanation of what all the abbreviations in it mean would help clueless noobs (like me) getting started.

[arnezami]

Looks like a good effort!

But personally I didn't get any further than the first image. Maybe an explanation of what all the abbreviations in it mean would help clueless noobs (like me) getting started.

I've added what the abbreviations stand for in my first post. Hope that helps a (little) bit.

(keep in mind though that this article mainly focuses on the Subset-Difference method)

[Jay Bee]

thx !

[xyz987]

The current Processing Key is in the far lower left of the tree used. This tree is the first tree (out of 513 I believe, I haven't analyzed yet why it isn't 512) which is why the first C-value is used. In other words: the largest tree isn't the 31 nodes high tree (which would be the truely root tree) but several floors higher. AACS simply doesn't use the trees with 31-23 nodes high. Which is why the lowest floor (for AACS) is still didived in approx 500 trees I believe.


Where did you get number 31 from?

[arnezami]

Where did you get number 31 from?

AACS Common:

3.2.3 Storing Device Keys
Each device is given its Device Keys and a 31-bit number d called the device number.

and at a different point:

For conciseness, the path number and the “v” mask are encoded in a single 32-bit number, referred to as the uv number. The mask for v is given by the first lower-order 1-bit in the uv number.

32 - 1 = 31


General remark: for programmers I advice them to read chapter 3 of the Common AACS specs. Its shows how things are implemented and stored and is quite thourough and precise.

[xyz987]

32 - 1 = 31



Okay. Could you publish the uv number and u mask that are stored at first entry of Explicit Subset-Difference Record on MKB?

Edit: I think you already have published u mask entry (23d), right?

[xyz987]

If is noteworthy to say that an attacker that gets the full set of Device Keys (253 keys) from any soft player can do some interesting things because he can derive any key of master tree and sub-trees, except a handful of them.

Nowadays movies are (indirectly) encrypted with the Device Key that is at position 8 in below example of a master tree:



1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
/ \ / \ / \ / \
8 9 10 11 12 13 14 15



Once arnezami's Processing Key is revoked, they will start using key 9 to encrypt. Then this attacker can immediately publish key 9. Then they revoke key 9 and start encrypting with key 4, then attacker immediately publish key 4, and so on.

Any attacker with a full set of Device Keys can simply sit and wait next revocation, publishing always just the necessary Device Key to decrypt, sans revealing the identity of his player, so his set of Device Keys can not be revoked.

The only necesary caution is to check first that the next Device Key attacker is going to publish is not his Leaf Device Key (far improbable). If it is any other, and they are already using it to encrypt, the attacker can safely publish it.

[FoxDisc]

If is noteworthy to say that an attacker that gets the full set of Device Keys (253 keys) from any soft player can do some interesting things because he can derive any key of master tree and sub-trees, except a handful of them.

This has been here for a while, and no one has commented, so I guess I will. As far as I can tell, and I've brought my own understanding up another notch, the above statement is not true.

Nowadays movies are (indirectly) encrypted with the Device Key that is at position 8 in below example of a master tree:



1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
/ \ / \ / \ / \
8 9 10 11 12 13 14 15




Yes, they are "sort of" using key 8. Let's make sure we are using the same terms. I'm assuming that the tree above represents the lowest level in the AACS parking garage used in the analogy of this thread. We can ignore the other levels for right now. The "key" at 8 is a processing key that corresponds to a subset difference set. It may not be clear, but every processing key (and there may be billions - haven't done the math yet) corresponds to one and only one subset difference set. What is a subset difference set? It is a set of bottom edge leaf nodes (the devices/trucks in this thread) that is defined by every device below some upper node minus every device below some lower node.

There are lots and lots and lots of possible such S-D sets. The S-D method allows most of the processing keys to be calculated from some other processing key.

Anyway, every device gets a set of device keys and can calculate all the other processing keys for any S-D set that it is a member of. So what processing key is now in use, and what S-D set does that key correspond to?

As best I can tell, for the numbered tree above and the AACS tree, the S-D set in question is the set starting at the top node (number 1 above) minus the set starting at the lower left (number 8 above). To make that clear: there is no device at the lower left (it's special), and every device is below the top. Thus, when you subtract off the set comprising the lower left from all devicees below the top, you still leave all devices.

That is the S-D set now in use. That S-D set has one and only one unchanging processing key. Every device out there is a member of that S-D set. Every device can calculate that processing key, and use that processing key to get the media key, etc. to decrypt.

Once arnezami's Processing Key is revoked, they will start using key 9 to encrypt.

Perhaps. Key 9 is the processing key for the S-D set comprising all devices below the top minus the device at 9. Device 9 cannot calculate this processing key from its own device keys. It can only calculate (or was given) keys for S-D sets that it is a member of. If Device 9 is PowerDVD, then PowerDVD will break as he will not be able to decrypt the media key when it is encrypted with the processing key for the S-D set comprising all devices below the top minus all devices at 9.

Then this attacker can immediately publish key 9.

No, he won't have it, if he *is* device 9, and if he's not, they won't use that processing key. They won't encrypt the media key and put it on the disc with any processing key that corresponds to a S-D set that has the attacker as a member. That's how it works.

Then they revoke key 9 and start encrypting with key 4, then attacker immediately publish key 4, and so on.
Any attacker with a full set of Device Keys can simply sit and wait next revocation, publishing always just the necessary Device Key to decrypt, sans revealing the identity of his player, so his set of Device Keys can not be revoked.

No. No player has all the keys. A device has all the keys for every S-D set that it is a member of, but there are lots of sets the device is not a member of and that the device does not have processing keys for and cannot calculate.

The only necesary caution is to check first that the next Device Key attacker is going to publish is not his Leaf Device Key (far improbable). If it is any other, and they are already using it to encrypt, the attacker can safely publish it.

I'll leave this on the quote, but it makes no sense to me.

[FoxDisc]

I might as well go on a bit further from my last post. The processing key that arnezami found is a key that corresponds to a S-D set that all devices are members of and all devices can therefore calculate. If arnezami or muslix64 had just popped up and said here's the processing key, no one at AACS would have been sure where that key came from. Any device could have found it in theory. Lots of people are wondering why they did it this way.

Of course, they might well have suspected it came from a licensed PC software player, a la WinDVD or PowerDVD. I think they are probably pretty sure of how it's leaked out by now :)

They could have done some things to help them figure out where it came from and that process is called "traitor tracing." It turns out they have some sophisticated procedures using what are called "sequence keys" to help with traitor tracing, but as far as anyone can tell, they are not using that method.

Purely to help understand S-D sets, here is another way they could have done this - they could have divided all the devices up into two S-D sets. Using the convenient number tree quoted in my last post, one set would be the S-D set including: the set of all devices below node 1 minus the set of all devices below node 3. That S-D set would be devices 8, 9, 10 and 11. That S-D set would have only one processing key and only those devices could have figured it out.

The other S-D set would be: the set of all devices below node 1 minus the set of all devices below node 2. That S-D set would be devices 12, 13, 14 and 15. That S-D set would also have only one processing key, different from the first and only devices 12-15 could have figured it out.

Those two S-D sets do not overlap. Using the AACS system, they would have encrypted the media key twice, once with the processing key for the first set above and once for the second set above. Then when the processing key leaked, they would have known which of the two groups it came from. All devices could have decrypted the media key, but only with the processing key they knew how to get.

[xyz987]

This has been here for a while, and no one has commented, so I guess I will. As far as I can tell, and I've brought my own understanding up another notch, the above statement is not true.


From aacs spec:

"A given set of Device Keys enables derivation of every key in the master tree except the keys between its leaf and the root"

and also:

"For each sub-tree corresponding to a node in the master tree
between a given device’s leaf and the root, that set of Device Keys
enables derivation of every key in that sub-tree except the keys between
its leaf and the root within that sub-tree."


As best I can tell, for the numbered tree above and the AACS tree, the S-D set in question is the set starting at the top node (number 1 above) minus the set starting at the lower left (number 8 above). To make that clear: there is no device at the lower left (it's special), and every device is below the top. Thus, when you subtract off the set comprising the lower left from all devicees below the top, you still leave all devices.


I have not checked your idea of "special key" (prior to any revocation), but anyway what is important is if an attacker with a full set of Device Keys will be able to derive the new Processing Key after revocation. He will be, in the same way any non-revoked player does.

Furthermore, attacker can safely publish the Device Key who derives the new Processing Key. If several Processing Keys are used to encrypt different movies, attacker can publish the Device Key that derives all of them. Any player can derive that Device Key, attacker is not revealing identity of the player he got Device Key set from.


No, he won't have it, if he *is* device 9, and if he's not, they won't use that processing key. They won't encrypt the media key and put it on the disc with any processing key that corresponds to a S-D set that has the attacker as a member. That's how it works.


Of course, if he (it, the device) is device 9 game is over. But AACS LA doesn't know which device the keys of the Device Key set are from, so they can not choose to revoke a group it is a member, because they don't know its identity.

[xyz987]

I might as well go on a bit further from my last post. The processing key that arnezami found is a key that corresponds to a S-D set that all devices are members of and all devices can therefore calculate. If arnezami or muslix64 had just popped up and said here's the processing key, no one at AACS would have been sure where that key came from. Any device could have found it in theory. Lots of people are wondering why they did it this way.


arnezami did it that way just because he didn't get a Device Key set. He got a Processing Key, and this Processing Key can be revoked no matter if AACS LA knows how (or from) arnezami got it.

Revoking a key is just stop releasing new movies encrypted with that key.


They could have done some things to help them figure out where it came from and that process is called "traitor tracing." It turns out they have some sophisticated procedures using what are called "sequence keys" to help with traitor tracing, but as far as anyone can tell, they are not using that method.


So let's wait until they start using Sequence Keys. BTW, AFAIK Sequence Keys say nothing about where the Processing Key is from, but i have not read completely spec chapter about Sequence Keys.


Purely to help understand S-D sets, here is another way they could have done this - they could have divided all the devices up into two S-D sets. Using the convenient number tree quoted in my last post, one set would be the S-D set including: the set of all devices below node 1 minus the set of all devices below node 3. That S-D set would be devices 8, 9, 10 and 11. That S-D set would have only one processing key and only those devices could have figured it out.

The other S-D set would be: the set of all devices below node 1 minus the set of all devices below node 2. That S-D set would be devices 12, 13, 14 and 15. That S-D set would also have only one processing key, different from the first and only devices 12-15 could have figured it out.

Those two S-D sets do not overlap. Using the AACS system, they would have encrypted the media key twice, once with the processing key for the first set above and once for the second set above. Then when the processing key leaked, they would have known which of the two groups it came from. All devices could have decrypted the media key, but only with the processing key they knew how to get.

So attacker publish both Processing Keys, because he can derive both (as any player). Just an example: device 12 has keys 13,7, 2 so it can derive any Leaf Device Key except key 12.

[FoxDisc]

From aacs spec:
"A given set of Device Keys enables derivation of every key in the master tree except the keys between its leaf and the root"


This is correct. It doesn't conflict with what I posted. It's saying that a device can derive all Processing keys for every S-D set that the device is a member of. It's also saying it can't derive keys for S-D sets that it is not a member of. If the AACS LA knows which device is compromised, and revokes that device, all of the device keys for that device become totally useless.

I have not checked your idea of "special key" (prior to any revocation), but anyway what is important is if an attacker with a full set of Device Keys will be able to derive the new Processing Key after revocation. He will be, in the same way any non-revoked player does.

I'm not sure what you are saying here. If he's revoked, he can't calculate anything useful. The only hope he has is if the AACSLA does not know who he is. That's what Traitor Tracing is all about.

Furthermore, attacker can safely publish the Device Key who derives the new Processing Key. If several Processing Keys are used to encrypt different movies, attacker can publish the Device Key that derives all of them. Any player can derive that Device Key, attacker is not revealing identity of the player he got Device Key set from.

The revoked attacker won't have any device keys that derive a valid processing key.

Of course, if he (it, the device) is device 9 game is over. But AACS LA doesn't know which device the keys of the Device Key set are from, so they can not choose to revoke a group it is a member, because they don't know its identity.

OK, so you are assuming they do not know the identity of the attacker? That's what Traitor Tracing is for. They have a method to find out, but they are not yet using it. They could also just assume it's one of the two PC players and revoke both sets, and force updates.

[FoxDisc]

arnezami did it that way just because he didn't got a Device Key set. He got a Processing Key, and this Processing Key can be revoked no matter if AACS LA knows how (or from) arnezami got it.

Agreed

Revoking a key is just stop releasing new movies encrypted with that key.

They don't revoke keys, they revoke devices. When they revoke a device, they automatically revoke (or more accurately, they just stop using) all the device keys that device has, because all of those keys enable calculation of a processing key that corresponds to a Subset Difference Set that the revoked device belongs to. That means that any revocation of any player (not just WinDVD or PowerDVD) will cause arnezami's processing key to stop working, since it's a processing key that all devices can calculate. Every possible revoked player could calculate it, so they can't use it any more.

So let's wait until they start using Sequence Keys. BTW, AFAIK Sequence Keys say nothing about where the Processing Key is from, but i have not read completely spec chapter about Sequence Keys.

I have not read all about sequence keys either. They may decide not to use them yet. I think they know how the keys were obtained. They don't have the scenario they planned for of leaked device keys, so they don't really need to revoke those keys (equivalent to revoking a device). They may just harden the players and use another one of many possible processing keys that all players can calculate.

So attacker publish both Processing Keys, because he can derive both (as any player). Just an example: device 12 has keys 13,7, 2 so it can derive any Leaf Device Key except key 12.

The attacker cannot derive both Processing keys. He can only derive processing keys for S-D sets that include him. He can't derive any processing key for any set that does not include him.

I think you've misunderstood what it means for device 12 to have keys 13, 7 and 2 for the S-D set that starts at node 1. Since the set starts at node 1, all devices 8-15 are in that set. However, key 2 corresponds to that set (below node 1) minus the set that starts at node 2. Thus the key at 2 in the example is a processing key that works for device 12-15. Since 12 is in that set, he has that key or can calc it. The key at 7 is for the S-D set that includes every device elow node 1 minus every device below 7. That includes devices 8-13. Since 12 is in that set, he's got that key too, etc.

What device 12 does *not* have is the key at 6 or 3 or 12. He's not in those S-D sets, and he can't get those keys. As soon as the AACS LA figures out he's #12, they'll use one of those keys and he's out of luck. To emphasize, the key at 3 is good for everyone below 1 minus everyone below 3. Since 12 is below 3 he's not in that S-D set and wasn't given that key.

[xyz987]

If the AACS LA knows which device is compromised, and revokes that device, all of the device keys for that device become totally useless.


I am saying there is no way to know it. All my point is this: there is no way to know it.

If you think there is a method to know which device the DK set is from, explain your method.


OK, so you are assuming they do not know the identity of the attacker? That's what Traitor Tracing is for. They have a method to find out, but they are not yet using it. They could also just assume it's one of the two PC players and revoke both sets, and force updates.


Could you explain a method of Traitor Tracing that works?

And yes, they can revoke all the soft players. However, if they don't close first the hole that allowed attacker to get the old DK set, attacker will get the new set again.

Even worse, once the old DK set is revoked, attacker can publish it, and this would cause AACS LA loses a big chunk of key space for future revocations. Just publishing Device Key 2 causes LA loses half of master tree keyspace.

[xyz987]

What device 12 does *not* have is the key at 6 or 3 or 12. He's not in those S-D sets, and he can't get those keys. As soon as the AACS LA figures out he's #12, they'll use one of those keys and he's out of luck. To emphasize, the key at 3 is good for everyone below 1 minus everyone below 3. Since 12 is below 3 he's not in that S-D set and wasn't given that key.

So we are saying the same thing. AACS needs to know (or at least to figure out) which is the compromised player.

[FMalibu]

First of all, thanks for the explenation and all other hard work. The thread about the processing key peaked my intested and prompted me to figure out how this part of AACS actually works and what actually was uncovered. From what I understand of it, this explanation is correct, but I still wanted to add some points that I have gathered. Note that a lot of information came from http://www.wisdom.weizmann.ac.il/~naor/PAPERS/2nl.pdf.

FoxDisc seems to be spot on with his description of the S-D sets. What I think is happening is that node in the tree has its own random master key, which are never released by the AACS-LA. When the S point equals a node, the master key for this node is used. The full set of S-D points included in the MKB creates a tree that reaches only those device nodes (i.e. the nodes at the bottom) which have not been revoked. Note that these sets never overlap (as the specifications state they area collection of "disjoint subsets").

Each device key also has a S-D set associated with it. This is because a device key is simply a key that is derived from the master key of node S, downwards until it has reached node D, using the AES-G3 function. The device keys are handed out in such a way that a device can derive the processing key for any given S-D set, except for those where the D is a node that is on the path from the root node to the device node.

As an example, lets look at that nice tree again:

1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
/ \ / \ / \ / \
8 9 10 11 12 13 14 15


Now, suppose we are a device with corresponding device node 12. The device keys given to us will be from these S-D sets: 1-2, 1-7, 1-13, 3-7, 3-13 and 6-13.

What a device has to do to find the Media Key is this:

Evaluate in which of the subset-difference trees given in the MKB its device node is located. This can be achieved by parsing all the S-D sets and seeing if the S value is a parent node of the device node, but the D node is not. If it does not find any then the device has been revoked.
Once it has found the subtree it belongs to (and it should be exactly one), the correct device key should be found.
The device key that should be used is the one that has the same S node and has either the same D node or a D node that is a parent of the D node of the subset tree from the MKB.
Note that it should have exactly one device key that fits these criterea.
In the former case, the processing key can be calculated directly with the AES-G3 function. In the latter case, the so-called subsidiary device key needs to be calculated from the device key first by iterating down the tree towards the D node of the given subtree.
Once the processing key is found, it can be combined with the C-value that corresponds to the subset-tree, also given in the MKB, to arrive at the Media Key.


Let's continue the example. Suppose that those devices that correspond to nodes 8,9 and 14 have been revoked. The S-D values given in the MKB should then be 2-4 and 3-14, as this is the set that reaches all device nodes except those that have been excluded. The device with device node 12 selects the 3-14 substree, as it is included in that, and uses its 3-7 key, as this key has also has 3 as its S node and its D node is on the route to node 14. It uses this key to derive the subsidiary device key at node 14 and subsequently the processing key. It will look up the C-value belonging to subset-tree 3-14 and decode the media key.

This has repeated a lot of things that have been said before in this thread, but I hope that by reiterating it, it will be better understood. Also, of course I do not know if what I said is correct at all, I just inferred it from what I've read so far. Please comment on those issues you have found to be different.

If you open your MKBROM.AACS and take/print the docs you can see the all this in the Explicit Subset Difference Record. It takes a little effort but the number 17h (=23d) is already telling. Maybe we should make an MKB file reader or something which graphically shows you which sub-trees are used (and thus have a C-value) and what their "shape" is (the position of the C-values in the trees creating subset-differences). Would be cool and informative in the future (when they start revoking).

I've written a small script that parses this file. I've included the output as attachment. It indicates the position and level (0=device nodes) of the S-D points found.

Indeed, there are 512 S-D sets. As already indicated, the device node for the device for which the processing key was found is located within the very first set. If I'm correct in what I've said above, this means that the compromised device can actually located within 1/512th of the total device space. If devices are spread randomly and equally among all the device node values, it shouldn't be too hard too track down.

However, it seems like a big coincidence that the device is located within the first S-D tree. If they (stupidly) started handing out device nodes at value 0 and work their way upwards (in the tree this would be starting at the left bottom node and going right one step each time), then there is no way to determine which device was compromised. In fact, a total of 2^22 - 1 = 4194303 devices should get a hit on the first S-D value :)

This is about the value of the Processing now and in the future. There are ways the AACS LA can issue MKBs in such a way that each disc/movie will have to use a different Processing key thus making a Processing Key in the future much less valueable. However this is really an advanced topic which requires a thourough analysis of what can and can't be done. Its very interesting in itself.

Please explain this further. How can they give S-D values that build the same tree? Or would they use some other technique?

-- FMalibu

[FoxDisc]

I am saying there is no way to know it. All my point is this: there is no way to know it.

You are right that the processing key tells only one thing - that some device in the S-D set for that processing key used their Device keys to get that processing key.

If you think there is a method to know which device the DK set is from, explain your method.

1) The main way is with sequence keys - not currently in use.
2) Second way is with processing keys as explained above. This is slow, but basically, they know for every processing key released that some device in the corresponding S-D set released it.
3) They read this forum and find which software player and how it was done :-)

And yes, they can revoke all the soft players. However, if they don't close first the hole that allowed attacker to get the old DK set, attacker will get the new set again.

Exactly!

Even worse, once the old DK set is revoked, attacker can publish it, and this would cause AACS LA loses a big chunk of key space for future revocations. Just publishing Device Key 2 causes LA loses half of master tree keyspace.

No- half of keyspace is not lost with key 2. You are only looking at one floor of arnezami's parking garage. Read more about subset difference sets and the AACS system. The system assumes that all device keys for any possible set of R devices are lost and the system still works.

[xyz987]

2) Second way is with processing keys as explained above. This is slow, but basically, they know for every processing key released that some device in the corresponding S-D set released it.


Too slow. Say 1 million players are sold this year, 2 million player next year, 4 million players at 2009. Yes, I am being malicious with the numbers, but they can find that the number of players in that subtrees increases faster than the speed at they reduce posibilities.

On the other hand I must say that I didn't understand you first time you mencioned this method. I was talking about master tree and you started to talk about subtrees. Note however that encrypting with keys at subtrees is supposedly reserved to revocation of noncontiguous leaf keys:

"This scheme enables efficient revocation of any combination of Leaf Keys. To revoke only a single Leaf Key (i.e., to enable calculation of the Media Key by any set of Device Keys except the set containing that Leaf Key), the Media Key Block will include the Media Key encrypted only by the master tree’s Leaf Key that is being revoked. If the Media Key is encrypted using a key located higher in the tree, the effect will be revocation of a contiguous range of Leaf Keys which are commonly rooted at that node. Efficient revocation of noncontiguous Leaf Keys can be accomplished through use of the sub-tree key systems"

If they follow their own spec, they won't leave the master tree until a revocation of noncontiguous leaf keys is needed. Device Key revocation is not a Traitor Tracing method, it is just revocation.


3) They read this forum and find which software player and how it was done :-)


;-DDDDD


No- half of keyspace is not lost with key 2. You are only looking at one floor of arnezami's parking garage. Read more about subset difference sets and the AACS system. The system assumes that all device keys for any possible set of R devices are lost and the system still works.

I wrote "half of master tree keyspace", not "half of keyspace". Master tree is first floor of arnezami's parking garage (the biggest one).

[xyz987]

Let's continue the example. Suppose that those devices that correspond to nodes 8,9 and 14 have been revoked. The D-S values given in the MKB should then be 2-4 and 3-14, as this is the set that reaches all device nodes except those that have been excluded. The device with device node 12 selects the 3-14 substree, as it is included in that, and uses its 3-7 key, as this key has also has 3 as its D node and its S node is on the route to node 14. It uses this key to derive the subsidiary device key at node 14 and subsequently the processing key. It will look up the C-value belonging to subset-tree 3-14 and decode the media key.


Good explanation, but your example is a revocation of noncontiguous keys. Things are different if they revoke contiguous keys. If keys 8,9 are revoked, they encrypt with key 4 of master tree, and any player can derive that key.


Indeed, there are 512 D-S sets. As already indicated, the device node for the device for which the processing key was found is located within the very first set. If I'm correct in what I've said above, this means that the compromised device can actually located within 1/512th of the total device space. If devices are spread randomly and equally among all the device node values, it shouldn't be too hard too track down.

However, it seems like a big coincidence that the device is located within the first D-S tree. If they (stupidly) started handing out device nodes at value 0 and work their way upwards (in the tree this would be starting at the left bottom node and going right one step each time), then there is no way to determine which device was compromised. In fact, a total of 2^22 - 1 = 4194303 devices should get a hit on the first D-S value :)


They are just following their own specification. There is not "big coincidence" neither "they (stupidly) started". This is what you and FoxDisc miss. AACS LA is still at master tree (no subtrees, no subset differences), and they won't leave master tree until they need to revoke noncontiguous keys. That's why the very first C-value is the only one used.

[FMalibu]

Good explanation, but your example is a revocation of noncontiguous keys. Things are different if they revoke contiguous keys. If keys 8,9 are revoked, they encrypt with key 4 of master tree, and any player can derive that key.

Thanks.

I'm not sure what "master keys" you are referring to. When I'm talking about master keys, I mean keys of a specific node, that are to be used when this node is the starting node (S node), and are thus used to derive device keys, subsidiary device keys and eventually processing keys.

So in this case of contiguous device revocation (devices 8 and 9), as subset tree will be given for 2-4, as I said. By definition this includes every device node (at the bottom) that has node 2 as a parent, except for those that have node 4 as a parent, which are device nodes 8 and 9. So I maintain that my example was correct.

What did you mean by "encrypt with key 4 of the master tree"?

They are just following their own specification. There is not "big coincidence" neither "they (stupidly) started". This is what you and FoxDisc miss. AACS LA is still at master tree (no subtrees, no subset differences), and they won't leave master tree until they need to revoke noncontiguous keys. That's why the very first C-value is the only one used.

I understand that you would think that (I assumed this at first as well), but please look at the text file I included. It's a bit cryptic, but I will attempt to describe what the Explicit Subset-Difference tree from current MKBs look like:

Suppose the device nodes at the bottom are called level 0. Since the tree is 31 tiers high, the root node would be at level 30. All S entries for the S-D sets are at level 22 now. Each of these S-D sets has a D node at the leftmost bottom of the tree where the S node is root. According to FoxDisc this is a special value and indicates no device revocation (thanks for that info, must have missed that somewhere). No device should exist with those D values as device nodes, they'll be revoked and won't work. It follows that there must be a total of 512 of these trees (2^(31-22) = 512) to make a complete tree that reaches all device nodes, except the leftmost ones in each subtree.

The device node of the compromised device resides in the very first D-S set, not in any of the other 511 D-S sets, which means that its "location" can be determined within 1/512th of the total device node space. It remains to be seen if this is a coincidence or not.

Also:

Even worse, once the old DK set is revoked, attacker can publish it, and this would cause AACS LA loses a big chunk of key space for future revocations. Just publishing Device Key 2 causes LA loses half of master tree keyspace.

I agree with FoxDisc here. The system is designed in such a way to prevent exactly this. They will just map out all of the S-D sets in such a way that any node en route from the root node to the compromised device node is never inluded in them. Those are all the nodes you lose.

-- FMalibu

[FoxDisc]

Too slow.
Yes, it is a slower method, and it is not the principal method. At this point it does not look like they are using any method except 3
On the other hand I must say that I didn't understand you first time you mencioned this method. I was talking about master tree and you started to talk about subtrees.

I was still talking about the master tree then. If they decide to split up the master tree and encrypt with multiple processing keys according to the divided master tree, they will know which set the traitor is in when he releases his processing key for his set. Future discs could then divide the set he is in into multiple other sets, etc. All of this could be done in the largest tree space. Of course, this is theoretic only. They are not doing it now, and I presume they would use the sequence key method, not this.

I wrote "half of master tree keyspace", not "half of keyspace". Master tree is first floor of arnezami's parking garage (the biggest one).

You are correct, I was rushing and missed this. Yes, half of largest (master) tree is available to all devices, so any one compromised device discloses that half. It's not a real limitation however - there are lots of remaining keys in subtrees and in the other half of the master tree.

[xyz987]

I'm not sure what "master keys" you are referring to. [...]

What did you mean by "encrypt with key 4 of the master tree"?


Just to clarify, I didn't say "master keys". And "encrypt with key 4 of the master tree" means that: "encrypt with key 4 of the master tree". AACS spec talks about a master tree, i drew an example numbered tree, and I said that numbered tree is an example of a master tree (not so big as the real one, of course). Master tree and subtrees are explained at chapter 3 of "AACS: Introduction and Common Cryptographic Elements" (see section 3.2.1). Note that this document is part of AACS spec.

You can download this document (and the rest of the spec) from here:

http://www.aacsla.com/specifications/

I think we have a problem of understanding, sometimes you and FoxDics say you don't understand some of the things I wrote, although I am always using the same language, terms and concepts of the spec. So please, read section 3.2.1. It is just one page.

BTW the document you linked is not part of the spec. I think that if you (FMalibu and Foxdisc) read section 3.2.1 you will understand what I say, and probably you will agree. Even if you don't agree, at least you will understand what I am saying.

Best regards :-)

[xyz987]

I was still talking about the master tree then. If they decide to split up the master tree and encrypt with multiple processing keys according to the divided master tree, they will know which set the traitor is in when he releases his processing key for his set.


This is not what spec says. Attacker can derive any key at master tree, they can not split master tree, any device can derive any key of master tree (except a little number of them). See section 3.2.1 of "AACS: Introduction and Common Cryptographic Elements)":

"A given set of Device Keys enables derivation of every key in the master tree except the keys between its leaf and the root"

and also (see figure at page 12 of "AACS: Introduction and Common Cryptographic Elements)":

"The nodes in white correspond to keys that cannot be derived using that set of Device Keys."

The nodes in white (at the mencioned figure) are precisely "the keys between its leaf and the root". Spec is far clear here.

[FMalibu]

You are correct, I was rushing and missed this. Yes, half of largest (master) tree is available to all devices, so any one compromised device discloses that half. It's not a real limitation however - there are lots of remaining keys in subtrees and in the other half of the master tree.

Interesting. I was just writing a post stating that I disagree with this and working up an example explaining why, when it struck me that you're actually right. Let me give you the example to see if we're thinking the same thing.

Suppose that initially there is only one S-D set given, 1-8, that includes all of the device nodes except for the special leftmost one. Now suppose that the device with device node 12 is compromised. As explained in my example, it has device key 1-2. What you guys are talking about is if only this key is released, right?

In this case they could do one of two things:

As only one device keys was released, the exact device that has been compromised cannot be determined. To fix the hole they would have to revoke all devices that have this device key.
Logically, this includes all devices in the rightmost half of the example tree, i.e. devices 12-15. This has the disadvantage of cripling any devices that happen to be in this range and potentially hurting a lot of users. Bad publicity.
Try to narrow down the comrpomised device node by actually releaseing a MKB with an overlapping collection of D-S sets. For example, suppose that a new MKB was included in subsequent releases that has 2-8, 3-6 and 3-7 as its sets. This still includes all device nodes (except 8), but disallows the use of the 1-2 device key. A new key has to be released to allow decryption, in case of device node 12 this would be 3-7. This halves the number of possible device node that could be the compromised node. This can be iterated until the compromised node is found. As FoxDisc already said, if the tree is big enough it would basically take a long time to find the compromised node. Actually, it depends on the distribution of the device nodes over the total device node space. If the distribution is random, and they keep track of device nodes not yet issued to manufacturers, it should be quite easy to eliminate device nodes that are known to be unused. If the distribution is sequential, it will get a lot harder.


This is all some nice theory, but no device key was released, so let's discuss countermeasures for the Processing Key :)

Let's consider the example tree to be a simplified representation of the first S-D set that is currently given in the MKB (this tree actually has a height of 23). What has happened now is that processing key for this set, in the example tree given by 1-8, is known. To disallow use of this key, they can do something similar to what I mentioned above, but simpler. They can just avoid using 1-8 and replace it with the sets 1-2, 2-8. This would still allow decryption by all devices except 8, but would disallow use of this particular Processing Key.

For the actualy subtree of height 23, the principle is the same, the one S-D value could just be replaced by two, one excluding the left branch and another originating at the left child node and ending again in the leftmost device node.

In summary, I think I can say the following:

With the current Processing Key, all titles already out can be decrypted, given that the Volume-ID can be extracted (I've completely avoided discussion of it, belongs in another thread).
A new MKB can be released in future titles that will prevent use of this Processing Key, but will still allow all devices to find the Media Key.
Tracking down which device was compromised depends on device node distribution. My guess is that all software players will be revoked anyway, but that's an informed guess.
Again depending on device node distribution, finding the device key that a direct child of the S node of the first S-D set (or any S-D set) may be a more future-proof method for decrypting the media key, as countermeasures are harder, although it will probably be unwise to publish it before the first round of countermeasures are released. Of course it is important in this case that only 1 device key is released and that it be as high up the tree as possible (i.e. the direct child node of the S node).


I'm pretty much just thinking out loud here. Please point out the errors in my reasoning ;)

-- FMalibu

[FoxDisc]

Each of these D-S sets has a S node at the leftmost bottom of the tree where the D node is root. According to FoxDisc this is a special value and indicates no device revocation (thanks for that info, must have missed that somewhere). No device should exist with those S values as device nodes, they'll be revoked and won't work.

That info about lower left special key is based on comments from arnezami that the processing key he found lies in the lower left corner of the 22 high largest tree now in use. Since one processing key seems to work for all devices, all devices must be in the S-D set that corresponds to that processing key. That means the S-D set must be rooted up high to include all devices below it.

Since processing keys only match S-D sets, and all S-D sets exclude at least one device below some lower node, there must be some lower "device" location that is not used (at least not yet). It made sense for them to use the smallest possible excluded set of devices, i.e., one device, and they chose the lower left one. I suppose they could revoke another lower device later and then assign the lower left location to a real device, as the device keys have not really leaked for that location.

I don't know if the lower left is actually special in any sense other than that they had to start the S-D system with at least one excluded device.

[FMalibu]

I think we have a problem of understanding, sometimes you and FoxDics say you don't understand some of the things I wrote, although I am always using the same language, terms and concepts of the spec. So please, read section 3.2.1. It is just one page.

Language is a tricky thing. You'll have to excuse my thought patterns being different from yours. I'm still in the process of trying to understand it all, but writing things down and discussing them here helps a lot.

I think I arrived at what you were trying to say before in the previous post. What you're saying suddenly makes a lot more sense :)

Please read my previous post and point out the things you disagree with. I'll try re-reading the thread and see if there are things you have said that aren't clear to me or just seem wrong.

BTW the document you linked is not part of the spec. I think that if you (FMalibu and Foxdisc) read section 3.2.1 you will understand what I say, and probably you will agree. Even if you don't agree, at least you will understand what I am saying.

Best regards :-)

Yes, you are correct. It is not referenced by the AACS specs (which I have read...at least the parts relevant to this discussion.). However, it is my understanding that the specs are based on the theory described in this document. It has helped me to understand the AACS specs, which in itself weren't clear to me. It is not a normative document, but if you read it and keep in mind what is said in the specs, you'll see that it matches up. Unfortunately they use slightly different terminology sometimes.

Oh, and thanks for the discussion ;)

[FMalibu]

That info about lower left special key is based on comments from arnezami that the processing key he found lies in the lower left corner of the 22 high largest tree now in use. Since one processing key seems to work for all devices, all devices must be in the S-D set that corresponds to that processing key. That means the S-D set must be rooted up high to include all devices below it.

(...)

I don't know if the lower left is actually special in any sense other than that they had to start the S-D system with at least one excluded device.

Well it sounded likely. I suppose they had to start somewhere.

However, you say that "one processing key seems to work for all devices". You cannot know this. Maybe what you mean to say is that one processing key works for all titles. It should, because all titles can be played back by the compromised device and the S-D sets given in the MKB are the same for all titles. But it could be that another device has its device node located within another S-D set. We don't know this, because AFAIK only one device was compromised...

Since processing keys only match S-D sets, and all S-D sets exclude at least one device below some lower node, there must be some lower "device" location that is not used (at least not yet). It made sense for them to use the smallest possible excluded set of devices, i.e., one device, and they chose the lower left one. I suppose they could revoke another lower device later and then assign the lower left location to a real device, as the device keys have not really leaked for that location.

It wouldn't make sense to un-revoke the lower-left device, since it wouldn't be able to play back current titles. I guess it's just lost forever, but that doesn't matter as the device node space is HUGE.

Also, ARGH!. I just realised I have been using both S-D and D-S inconsistently in my previous posts. I will edit them and try to correct it.

-- FMalibu

[FMalibu]

xyz987:

I've re-read the thread and I think I've come up with what is the difference between the way you think it works and I think it works. It's an issue that I got wrong at first as well (wrong IMHO), but the PDF I just linked helped me understand it. Indeed the wording in the AACS specification is a bit misleading about it, particularly in the section 3.2.1 you mentioned.

First I'll tell you how I think you think it works, compiled from your previous posts, and you can confirm or correct this. There is one master tree and every node in this tree has a master key. Lower master keys can always be derived from higher master keys. Device keys are master keys. Processing keys can be derived from these device keys, in case of a single revocation within a tree at the device node that has been revoked, in case of a contiguous revokation at the parent of the contiguous set.

But what about non-contiguous revocations? Suppose in your example tree that 8 is still revoked and 14 is as well. If it is encrypted with the key at 8 then 14 can decrypt it, and if it is decrypted with the key at 14, then 8 can decrypt it. I'm not sure how you envisaged this.

How I think it works is the following:
There is one master tree and every node in this tree has a master key. Every node below a particular node has derrived keys, which are different for every root node. If we take the example key, the derived key for point 4 that has point 1 as its root node is different from the derived key for point 4 that has point 2 as its root node and again different from the master key of point 4. Device keys are always derived keys, never master keys. Each device key has two nodes associated with it, a root key and a node for which this device key is the derived key (starting at the root key). This is explained in section 3.2.4. This is why in your example a device has only 3 device keys (8,5 and 3 for node 9) and in my example it has 6 (1-2, 1-7, 1-13, 3-7, 3-13 and 6-13 for node 12). Please keep this in my when you read my examples and see if they make sense.

-- FMalibu

[arnezami]

Wow! Some solid good discussion here :).

It seems our collective understanding of the Subset-difference has grown... :D

I haven't got much time now but would like to say a few things.


Different Processing Keys:

Processing Keys are interesting not so much because they (usually) won't identify a Player (since they can guess anyway) but they are interesting because they can be used to decrypt every disc and are easy to get.

In other words: it will be relavily easy to extract a Processing Key from a future Software Player. Its harder to get the (given) Device Key used. But its much harder to extract all 253 Device Keys from a player: thats because most of them are not used and can therefore not be found in memory (and even if found there is no way to check their validity).

So what matters for us (in the near future) is whether we would need a Processing Key to decrypt all discs or need one or more (given) Device Keys.

How do you know you only need a Processing Key: if all Explicit Subset-Difference Records (=ESDRs) on each (new) disc are the same. If its not you need Device Keys (or more Processing Keys depending on how many different ESDRs there are).

How can they create different (but "equivalent") ESDRs? One way (but there are several things they can do) would be to put all Software players close to each other (say in a part of 256 adjacent leaves) and use the tree right next to it (also 256) as a "fake player revocation" collection. In that tree there are a little over 500 Processing Keys (keep in mind: not just the 256 leaves!) that are all reachable by the Software Players. Btw: for that to work they have to use the sub-tree covering all 512 (2x256) leaves. That way they can choose to use a different Processing Key for each movie (there are no real players in that fake-filled tree so they can "revoke" whatever they want). And they can do this every x months.

This would the easiest way for them to use a different Processing Key on each disc but could cost a lot of end nodes. There are more efficient (but trickier) ways but thats just a matter of "cost". (It is noteworthy though this particular technique can be "broken" by finding just one (given) Device Key.)

Now whether they will use this technique (or a variant) is going to be very interesting.

Btw: I assume/suspect they will revoke each Software Player's Device Keys every so many months as a default safety procedure. Whether they will do they same for Host Private Keys I don't know (likely though).

Now you got (even) more to talk about ;).

Regards,

arnezami

[FoxDisc]

BTW the document you linked is not part of the spec. I think that if you (FMalibu and Foxdisc) read section 3.2.1 you will understand what I say, and probably you will agree. Even if you don't agree, at least you will understand what I am saying.

If it helps, I have read all of section 3 and all other parts of the common crypto specification, with special attention to section 3.2.1. Part of the problem is that I have also read the original Naor, Naor, and Lotspiech paper:
http://www.wisdom.weizmann.ac.il/~naor/PAPERS/2nl.pdf.
and many other papers on the AACS system. These other papers make some aspects more clear about why it's called subset-difference, why it was chosen, and how the processing key matches up to the S-D set.

[FoxDisc]

This is not what spec says. Attacker can derive any key at master tree

This is what spec says and it is correct.

, they can not split master tree, any device can derive any key of master tree (except a little number of them). See section 3.2.1 of "AACS: Introduction and Common Cryptographic Elements)":
"A given set of Device Keys enables derivation of every key in the master tree except the keys between its leaf and the root"
and also (see figure at page 12 of "AACS: Introduction and Common Cryptographic Elements)":
"The nodes in white correspond to keys that cannot be derived using that set of Device Keys."
The nodes in white (at the mencioned figure) are precisely "the keys between its leaf and the root". Spec is far clear here.

This is also all correct, except the part where you say "they cannot split the master tree." Why can't they split it? The attacker device does not have the "keys between its leaf and the root" as you quoted. The key just below the root that an attacker does not have is the processing key that half of the devices have and half do not have. Think about S-D sets. Half the devices are in the S-D set for key 2 and half are in the S-D set for key 3. The attacker does not have one of those keys. Half of the possible devices do not have it. Half do have it. No device has both. If the media key is encrypted twice, once with key at 2 and once with key at 3, all devices could decrypt, but half would have to use a different processing key, and this would tag them as being in one group or the other. This may be what arnezami refers to in later post as "fake player revocation" (perhaps not, I have read his post only briefly and not absorbed it yet)
Revocation works by just not using any processing key that the revoked device has. However, if you do use it anyway, it is a fake revocation that may help you trace the player. I do not know if they will do this.

Now, I confess something: I am not certain if it even possible to do this. I am looking at how the crypto works more than specifically how the AACS has implemented it. Crypto says they can split the devices in half and use that for traitor tracing, but I'm not sure if this is feasible with the exact AACS implementation. I have more reading to do on this.