Welcome to Doom9's Forum, THE in-place to be for everyone interested in DVD conversion. Before you start posting please read the forum rules. By posting to this forum you agree to abide by the rules. |
17th February 2007, 14:05 | #1 | Link |
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.
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. |
17th February 2007, 14:06 | #2 | Link | |
Registered User
Join Date: Sep 2006
Posts: 390
|
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): 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) 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: 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": 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: 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 . 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 . Quote:
-------------- 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... Last edited by arnezami; 24th February 2007 at 14:57. |
|
17th February 2007, 14:06 | #3 | Link |
Registered User
Join Date: Sep 2006
Posts: 390
|
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. Last edited by arnezami; 18th February 2007 at 21:35. |
17th February 2007, 15:34 | #6 | Link | |
Registered User
Join Date: Dec 2006
Posts: 142
|
Great!
Quote:
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. |
|
17th February 2007, 15:56 | #7 | Link |
Registered User
Join Date: Oct 2002
Posts: 65
|
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) Last edited by guile; 17th February 2007 at 15:59. |
17th February 2007, 22:53 | #12 | Link |
Registered User
Join Date: Dec 2006
Posts: 154
|
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? Last edited by noclip; 17th February 2007 at 22:59. |
18th February 2007, 02:41 | #13 | Link | |
Registered User
Join Date: Dec 2006
Posts: 142
|
Quote:
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. |
|
18th February 2007, 05:08 | #14 | Link |
Registered User
Join Date: Dec 2006
Posts: 142
|
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: Code:
1 / \ / \ / \ / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ / \ / \ / \ / \ 4 5 6 7 / \ / \ / \ / \ / \ / \ / \ / \ 8 9 10 11 12 13 14 15 - 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. Last edited by xyz987; 19th February 2007 at 20:34. |
18th February 2007, 06:36 | #15 | Link |
Resident DRM Hater
Join Date: Oct 2006
Location: International waters
Posts: 242
|
Let me just make sure I get this last image...
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)?
__________________
Because Moogles pwn. |
18th February 2007, 07:50 | #16 | Link | |
Registered User
Join Date: Sep 2006
Posts: 390
|
Quote:
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 Last edited by arnezami; 18th February 2007 at 08:02. |
|
18th February 2007, 08:39 | #17 | Link |
Registered User
Join Date: Sep 2006
Posts: 390
|
@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. |
18th February 2007, 14:45 | #18 | Link |
Registered User
Join Date: Jan 2007
Posts: 274
|
@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? |
18th February 2007, 16:47 | #19 | Link | |
Registered User
Join Date: Sep 2006
Posts: 390
|
Quote:
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 . Last edited by arnezami; 18th February 2007 at 16:54. |
|
Thread Tools | Search this Thread |
Display Modes | |
|
|