Doom9's Forum - View Single Post - Understanding AACS (including Subset-Difference)

arnezami · 17th February 2007, 14:05

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

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:

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

.

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:

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:

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]

17th February 2007, 14:05	#1 \| Link
arnezami Registered User Join Date: Sep 2006 Posts: 390	Understanding AACS (including Subset-Difference) 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 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. 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: 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 . 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: 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: 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] Last edited by arnezami; 20th April 2007 at 08:00.