Understanding AACS (including Subset-Difference)

[FoxDisc]

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 - cryptographers and mathematicians. They think about this for a long while and they come up with: The Subset Difference System.

[arnezami]

@FoxDisc very well put. I will put a link to this post (or quote it) so others/newcomers will be able to find it.

Originally Posted by FoxDisc

It's fundamentally simple.

Very true.

[FoxDisc]

I thank arnezami for his kind comments.

In my last post, I ended with some questions. The most important one was: How do you divide the devices up into groups? I'm going to try to answer that question here. More specifically, I'm going to try to explain why they chose this strange "subset difference set" to be the group of devices. We'll use the same procedure we used before - let's try to do this ourselves and see what works.

If you've read anything here, you know that we're going to use some kind of tree like this:

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

The experts call this a "binary tree" since it starts at a "root" node (number 1) splits in two to reach two more nodes (2 and 3) and each of those nodes splits in two, etc. 'til you get to the bottom level where the nodes are sometimes called "leaves."

The leaves (8-15) are our devices. Remember that every group is going to be assigned a secret key and every device gets all the secret keys for all the groups he belongs to and none for groups he does not belong to.

OK, here's our first shot at dividing up the 8 devices/leaves on the bottom row into groups. We'll start off simple: A device is a member of a group if he's below a node. He's not a member if he's not below a node. (We'll later call the node above him an "S-node".)

Example time! Group 4 includes devices 8 and 9. Group 2 includes devices 8-11. Device 8 is a member of groups 1, 2 and 4. He's also a member of group 8 (himself). He's not a member of any other groups.

What secret key do we assign to each group? We'll use a random number generator and assign one to every number in the tree. That number is the secret key. (Keep this master tree with random numbers assigned to every node in mind - we'll use it later. The AACS really did this, and they really have such a tree of random numbers. It is the holy grail of their system, and no one except the LA has any of those numbers.)

This looks pretty good so far. Device 8 only has to store four secret numbers for groups 1, 2, 4 and 8. Device 13 also only has to store four secret numbers for groups 1, 3, 6 and 13. Every device stores only 4 numbers. Not too bad! Our disc only has one copy of the media key encrypted with the processing key/secret number for group 1. Everyone can decrypt it since they are all members of that group and all have the processing key for group 1.

Hey this is great! ..... So far...... But along comes a bad boy and he's stolen our secret keys in device 8. We have to punish him! No more decrypting for 8! He is "REVOKED!"

So this is simple. We just stop using processing key 1 to encrypt our media key. Hmmmmm. I guess we can't use 2, 4 or 8 either! Bad boy number 8 has those too. We just have to use groups that he is not a member of. But, we have to make sure we let everyone else decrypt. They are not bad boys.

So here's what we do: We encrypt the media key with the secret numbers for 9, 5 and 3! Now everyone can decrypt it except bad boy 8! We showed him! Except, notice that we started with only one encryption on the disc, but now we've got 3, and we only revoked one bad boy. We had to use all the keys on the branches that lead away from him (His path to the root is 8-4-2-1 and the branches off that path are at 9, 5 and 3. We'll call this the path from a device to root the "device path" and the nodes off that path the "branch nodes"). Even worse, what if this tree was 32 levels high like the real master tree? We would have had to add 32 new entries just to revoke one bad boy!

That's why the AACS used a different system than the simple system described above. They were still worried about running out of space on the disc!

Our simple system in our first crack at this did not make enough groups! We need more groups with more secret processing keys. When we made the group include everyone below a node, they only had one group for every level of the tree. If we can make more groups, a device will have to store more keys, but it will be easier to exclude them, because there will be more groups that he doesn't belong to.

Let's take our second crack at making groups of devices:
Here's what we need: We need more big groups that do not include bad boys. It's really simple. (Can you believe this guy! "Simple" Hah!) We'll take our old group (everyone below an S-node) and we'll kick out of that group everyone below some other node that's below the first node.

That is exactly what the AACSLA did! (I think I read that in the last post!) They called this group of devices a "Subset Difference Set." The upper node is the S-node, the lower node is the D-node. Everyone below the upper S-node is in the subset difference set UNLESS they are also below the lower D-node. We'd have to call on those mathematicians to prove it, but with S-D sets, on average, we only need to add between 1 and 2 encrypted copies of the media key to the disc to revoke our bad boy.

Hang on - we're making progress. All we've got to do now is give all of our devices all the processing keys for all the S-D sets that they belong to! There's only one small problem. There are an awful lot of S-D sets! We tried to make a lot of them, and we succeeded. There are so many different S-D sets that no device has enough memory to store all his keys! Great system! We traded not enough room on the disc for not enough room in the player device!

Here's how they solved that. Remember that master tree with all the assigned random numbers from our first crack at this? (I told you to remember that - why didn't you?) They figured out a way to calculate all the processing keys for all the S-D sets that start at any S-node from that one secret random number in the holy grail tree! Using a "one way function" they start with the secret number for the S-node and they calculate another secret number (a processing key) for each D-node below it. The processing key for an S-D set that starts at S and ends at D is the number assigned to D that was calculated from the original secret random number assigned to S. Because they used a one way function, if they give device 8 the processing key for S-D set 1-7. he can't figure out the secret random number for node 1 and he can't figure out the processing key for set 1-8. (The set 1-7 starts at node S=1 and excludes everyone below node D=7. Device 8 is a member of that set since he is not excluded. Set 1-8 starts at 1, and excludes node 8. Device 8 is not a member of that set.) The AACSLA never gives out the S-node secret random numbers.

Now suppose they gave a device all the secret S-node numbers in the holy grail tree that lie on his device path. That would be exactly equivalent to our first system. A device could calculate all the S-D sets below every node on his device path to the root! That's no good. He's not a member of some of those sets. We have to prevent him from calculating the processing key for an S-D set when D is on his device path.

Here's how they solved that: Remember those "branch nodes" off the device path? (Now what did I tell you about this remembering thing? Try to keep up here - we're moments from the end!) If they keep the S-node secret random number secret, but give every device all the processing keys on the branch D-nodes that are calculated from the S-node secret number, then the device can calculate all the other processing keys it's entitled to, but not the ones it isn't! The branch node processing keys are called "Device Keys." That's it. The end. (Well almost.)

Sequel:
The AACSLA master tree of S-node secret random numbers is 32 levels high. (We refer to the bottom level as level 0 and the root as level 31). For some reason, the AACS LA started off with 512 S-D sets at level 22, not one big one rooted at level 31. Each device is a member of only one of those 512 sets, so it only gets device keys for the 0-22 branch nodes.

[FMalibu]

Hi, keeping up with this thread is a dayjob in itself, so I won't reply to everything

@arnezami:
This KCD intrigues me. I hadn't read up on it and just skipped over it before, assuming it was something to do with BD+ or something. Do you know if it's even used in standalones? Is that mandatory? Indeed, the first S-D tree leads to a plain media key, so if KCD is even used then it would have to be in any of the other 511 trees.

@xyz987:
A lot of confusion in this thread is caused by difference in terminology. It doesn't help that section 3.2.1 seems to be...well weird. I'm can see what you mean now though, and if I apply slightly different terminology it seems to be correct

@FoxDisc:
Good explanation, nicely analogous to NNL paper. Again about terminology, I think you should have used "subsidiary device keys" in place of "processing keys" sometimes. Also, more examples == better!

-- FMalibu

[xyz987]

Originally Posted by FMalibu

@xyz987:
A lot of confusion in this thread is caused by difference in terminology. It doesn't help that section 3.2.1 seems to be...well weird. I'm can see what you mean now though, and if I apply slightly different terminology it seems to be correct

Yeah, terminology is being a real problem. AFAIK i am using AACS terminology. Afortunately, it seems that the worst terminology problems have been sidestepped.

Section 3.2.1 looks so weird for the reason arnezami pointed: there is a gap between the (far general) section 3.2.1 and the (far precise) rest of the spec. My opinion about that section is that it is describing things in a right way (it was written by spec authors), and problems to understand it are just caused by the infamous gap.

[xyz987]

Originally Posted by FoxDisc

Yes, subtrees are part of the 31 level tree (edited from references to 30 level - see below). The paper says to choose a different random key for every node in the tree. I agree, it is a large number. I came up with 64 Gb of data in random numbers. (32 levels counting from 0 level at bottom to level 31 at top times 16 bytes for each 128 bit key).

From NNL paper:

"In both the Complete Subtree and Subset Difference methods, a unique label is associated with each node in the tree. Storing these labels explicitly at the Center can become a serious constraint. However, these labels can be generated at the center by applying a pseudo-random function on the name of the node without affecting the security of the scheme. This reduces the storage required by at the Center to the single key of the pseudo-random function."

NNL says that using pseudo-random keys (labels) is safe. Just to clarify: "random" and "pseudo-random" are not the same thing.

Anyway, AACS is *not* using random keys in master tree (22 level tree) neither subtrees (21 level and lower). Device Keys are not random. Players 9 and 15 will compute the same arnezami's PK. Player 9 will compute it directly from its DK 8. Player 15 will compute Subsidiary Device Key 4 from its DK 2, and later it will compute 8 from 4. Subsidiary DK 8 (computed by player 15) is the same key that Device Key 8 from player 9 DK set.

Root keys at the mentioned trees (22 level and lower) may be random, but the rest of the keys at that trees are not.

Of course, the rest of the keys at 31 level tree may be random, spec says nothing about it.

[arnezami]

Originally Posted by FMalibu

@arnezami:
This KCD intrigues me. I hadn't read up on it and just skipped over it before, assuming it was something to do with BD+ or something. Do you know if it's even used in standalones? Is that mandatory? Indeed, the first S-D tree leads to a plain media key, so if KCD is even used then it would have to be in any of the other 511 trees.

Right now there is no real way to be sure if the KCD is used for standalones yet. If they don't use it yet they can do it for later discs.

The point of the KCD is to prevent using (many different hacked) standalone players to get Device or Processing Keys. These keys (from standalones) are useless now. Keep in mind: many software players all have the same Device Keys, but standalones have different for each (well they should **). The reason these keys are useless is because a KCD based system reveals the Media Key Precursor which together with the KCD in turn produces (in a one-way fashion) the Media Key. In fact (if they implemented the KCD) our Media Key is the result of a one-way operation on the Media Key Precursor and the KCD on that disc (in other words: they couldn't simply choose any Media Key they wanted. They produced the Media Keys by choosing a Media Key precursor and/or KCD first).

So we might find a Device or Processing Key from a standalone but we can only decrypt a C-value which produces a Media Key Precursor. But without a KCD (not readable by PC drive) these Keys are useless for non-KCD systems.

What could theoretically be done? Hack the firmware of a standalone (of a well sold one). Try to figure out how the KCD is put on the disc. Then "teach" the most common PC based drives (by firmware patch) to read the KCD. And of course include some command to retrieve the KCD. And voila . We could use the device/processing keys of every standalone in the world (and there will be many...). They cannot "harden" already sold standalone players so this would be pretty much game over (=known method of retrieving Device/Processing Keys from a standalone and just a PC drive patch needed for people to decrypt discs). Although the sequence keys come in to play here. But at worst this would "only" cost one standalone every so many months... (which is already hacked so it can be reprogrammed anyway, so no real loss)

The question is: can PC drives (physically that is) read the KCD at all?

I can't answer that question but my gut says yes: why make its method of storage "confidential" in the first place?

Ooh. I'm really devious here

Regards,

arnezami

** if they didn't give standalones unique Device Key sets then they are sooooo screwed...

[xyz987]

Originally Posted by arnezami

They cannot "harden" already sold standalone players so this would be pretty much game over (=known method of retrieving Device/Processing Keys from a standalone and just a PC drive patch needed for people to decrypt discs).

Great!

This kind of thing can break AACS completely if someone figures out how to sidestep Sequence Key set revocation.

Although the sequence keys come in to play here. But at worst this would "only" cost one standalone every so many months... (which is already hacked so it can be reprogrammed anyway, so no real loss)

Note that SKs and SKBs are highly decoupled of DKs and MKBs. Standalone player owner can publish the end sub DK (or the PK), and SKs can be from a soft player. Traitor tracing (SKs and SKBs) will detect the soft player, not the standalone. Furthermore, traitor tracing is useful only if attacker publish Media Key Variants (from a soft player, for example). Attacker can not be traced if he doesn't publish Media Key Variants. The problem is that a Sequence Key set can be revoked, so it can not be published. Soft player user is let alone to solve the problem of getting the SKs.

I can't answer that question but my gut says yes: why make its method of storage "confidential" otherwise?

If they are relying on "security through obscurity" they are dead. This is always a Bad Idea.

[FoxDisc]

Originally Posted by FMalibu

@FoxDisc:
Good explanation, nicely analogous to NNL paper. Again about terminology, I think you should have used "subsidiary device keys" in place of "processing keys" sometimes. Also, more examples == better!
-- FMalibu

Yes, I suppose I should have gone into the fact that a starting number (device key) processed through the one way function leads to a number that is three times as big, with the middle section being a processing key and the right and left sections being the subsidiary device keys for the right and left branches. I'd already spent so much time on it, however, I just left it as was.

[HyperHacker]

Thanks, that explanation was a huge help.

Is revocation not a weakness then? Right now the media key is encrypted only once on the disc, with the device key for node 1, but if they wanted to revoke a device they'd have to include a few different copies of the media key encrypted with different device keys; is this right? So then we have a few blocks that we know will all decrypt to the same plaintext. I'm no cryptographist but this seems like a potential weakness...

[xyz987]

Originally Posted by arnezami

Although the sequence keys come in to play here.

A hacked firmware for standalone player can also give Sequence Keys to attacker. Attacker can buy a standalone player, flash it with a hacked firmware, get the keys, flash it again with original firmware and return player to shop (in some countries there is a time of several days to lawfully return a product to shop).

AACS LA would be tracing someone else player.

However real problem remains: if a Sequence Key set is published, that set can be revoked. It is valid for all previously released movies, but not for future ones.

[xyz987]

There is a way to sidestep Sequence Key set revocation. A Sequence Key set can be revoked, but spec clearly says it is impossible to revoke a single SK, because many players share it. So an attacker that gets several SK sets from different players can wait until AACS LA "activates" SKB (i.e. Media Key Variant is used to encrypt part of the movie), and then attacker can publish one SK from one of his SK sets. Then AACS LA will release new movies with an "updated" SKB (where this published key is considered "compromised"), then attacker will publish another SK from another SK set, and so on. Sequence Key sets are never revoked this way.

[arnezami]

Regarding the KCD idea (stealth firmware):

[devious]What would be really cool is to let the "updated" firmware of a PC drive give the KCD and the Volume ID as the first response the drive gives back during the AACS-auth process (Dn|Dcert). It would only do this when we give him the Media Key Precursor first as Hn (so it can calculate the Media Key and check if its correct and only then return the KCD+VID as Dn|Dcert). Since our independent software decrypter/player would have a Processing/Device key from a standalone it can calculate the Media Key Precursor and make the drive give the KCD and Volume ID. However there is no way they can let a official Software Player check if the drive firmware is hacked (by checking whether it gives the KCD or VID) because it cannot make the drive give back the the KCD and Volume ID! It would need the Processing/Device Key of a standalone for that! And thats exactly what they do not want to give to software players [/devious]



We would be beating them at their own game.

Of course this all depends on whether PC drives can actually read the KCD in the first place.

This could be the 3rd-generation way of decrypting discs (using standalones for device key retrieval and using them in PC based systems) The first-gen being direct VUK retrieval (WinDVD memory picking). The second-gen would be the Software Player key snoops/debugs: getting Device/Processing Key + Host Private Key (+Cert). Thats what we are still working on now. Maybe in a year or so will we be needing this new (3rd gen) technique (eg. when no software players are allowed anymore or are very hard to break or are only allowed to run on vista etc) and we'll probably need that time to properly develop this new technique.

Right now I believe we should concentrate on getting a Host Private Key (+Cert) from a software player. That would be really nice.

[FoxDisc]

My two long explanatory posts were an effort to follow in arnezami's footsteps and simplify, simplify.

The first post was an attempt to explain the simple concept of overlapping groups of device with an associated secret number assigned to each group. I was focusing on the "why" overlapping groups were chosen. By giving the secret number to everyone in a group, and not giving it to anyone else, the AACSLA could shift initial key storage away from the disc and into the player devices.

The second post was an attempt to explain why they chose the specific type of overlapping groups (S-D sets). S-D sets do seem like an odd choice, but they were chosen out of the necessity to have lots and lots of such groups. I was focusing on "why" they needed so many groups - again to minimize the space used on the discs, but this time it was for minimizing space used up for each revocation.

On the issue of terminology:
I started off trying not to use any words from the spec for the secret number assigned to a group. I should have tried harder. The terms "secret number," "secret key" "random number," pseudorandom number," "device key," "processing key" and "subsidiary device key" are all words that refer to the original simple concept of a secret number assigned to a group of devices. They are all either the secret number assigned to a group or they are some other number that can be used to calculate the secret number. The true name for that secret number when it's assigned to an S-D set is "processing key," but I started with ordinary sets, not S-D sets, so I didn't want to call the secret number a processing key and I didn't want to go into details of how processing keys were derived from device keys.

[FoxDisc]

Originally Posted by arnezami

The question is: can PC drives (physically that is) read the KCD at all?

The HD DVD and DVD Pre-recorded Book says that the KCD is stored in the Copyright Data Section of the lead in area.
It's right after the lsb_64 of the volume id. If the volume id can be read, doesn't that mean the PC drive should be able to read the KCD?

[arnezami]

Originally Posted by FoxDisc

The HD DVD and DVD Pre-recorded Book says that the KCD is stored in the Copyright Data Section of the lead in area.
It's right after the lsb_64 of the volume id. If the volume id can be read, doesn't that mean the PC drive should be able to read the KCD?

Very possible.

[FoxDisc]

Originally Posted by xyz987

Great! This kind of thing can break AACS completely if someone figures out how to sidestep Sequence Key set revocation.

When I first read arnezami's quote, I didn't understand it. They can always revoke a device. I thought perhaps he meant that they wouldn't dare revoke a widely sold player device. Of course, it's possible that every standalone device out there uses a different set of keys. Then they could revoke player serial #1 from mnfr A without revoking serial #2 of the same model and same mnfr A.

Then I thought perhaps he meant that if there was a method to get device keys out of standalones (plus KCDs), and if that method was quick, then attackers could stay ahead of disc releases and the whole system would collapse. Of course, something like that is already in place with software players, so the whole KCD thing would be a non-issue.

Your comment about sequence keys made it even more confusing to me.

Note that SKs and SKBs are highly decoupled of DKs and MKBs. Standalone player owner can publish the end sub DK (or the PK), and SKs can be from a soft player. Traitor tracing (SKs and SKBs) will detect the soft player, not the standalone. Furthermore, traitor tracing is useful only if attacker publish Media Key Variants (from a soft player, for example). Attacker can not be traced if he doesn't publish Media Key Variants. The problem is that a Sequence Key set can be revoked, so it can not be published. Soft player user is let alone to solve the problem of getting the SKs.

Since SKs are not being used now, there has been little discussion of them. My understanding was that they lead to a different decrypted movie. For example, device #1 decrypts the movie and you see a car with license plate #1 go by. Device #2 decrypts movie and you see a car with license plate #2 go by. The AACSLA can tell from the movie released which device decrypted it. I would not expect that the DKs from one player would work with the SKs from another, but perhaps you have reviewed this? Do you want to discuss your analysis of SKs?

[xyz987]

Originally Posted by FoxDisc

Then I thought perhaps he meant that if there was a method to get device keys out of standalones (plus KCDs), and if that method was quick, then attackers could stay ahead of disc releases and the whole system would collapse. Of course, something like that is already in place with software players, so the whole KCD thing would be a non-issue.

Just think about what i have previously written about an attacker that gets a DK set but he only publishes the (sub) DK that is directly used to compute PK. It is impossible to trace attacker with just one revocation, and several revocations need time. Furthermore, an attacker can simply stop publishing new keys as soon as AACS LA is getting closer, so in fact attacker is never located neither his player is revoked. Using MKB to do traitor tracing is far slow and unefficient (also note MKB was never intended to do so).

The advantage of getting DKs from an standalone player is that already sold home theater players can not be hardened. If they have a hole, they will have that hole forever. Soft players can be upgraded, and users can be forced to upgrade (just revoking previous versions). Standalones can not be upgraded.

Since SKs are not being used now, there has been little discussion of them. My understanding was that they lead to a different decrypted movie. For example, device #1 decrypts the movie and you see a car with license plate #1 go by. Device #2 decrypts movie and you see a car with license plate #2 go by. The AACSLA can tell from the movie released which device decrypted it. I would not expect that the DKs from one player would work with the SKs from another, but perhaps you have reviewed this? Do you want to discuss your analysis of SKs?

Yes, the DKs from one player will work with the SKs from another player. MKB and SKB are almost entirely decoupled, the only linkage is Media Key, and Media Key is the same for each movie, no matter which PK the player have used to decrypt Media Key.

The output of "MKB system" is Media Key and only Media Key, the input of "SKB system" is Media Key and only Media Key. Both systems are decoupled.

SKs and SKB can trace the player SK set is from, not the player DK set is from.

[dirio49]

I don't know much about in cryptology or whatever.
But I saw a video on youtube, a person opened up a standalone Hddvd player and the drive was just a standard computer drive

here is the link.

http://tinyurl.com/27hvrk

[arnezami]

Originally Posted by dirio49

I don't know much about in cryptology or whatever.
But I saw a video on youtube, a person opened up a standalone Hddvd player and the drive was just a standard computer drive

here is the link.

http://tinyurl.com/27hvrk

Cool

This opens possiblities...

As an aside: if they just happen to so stupid not to give each standalone their own unqiue set of Device Keys and it is possible for PC drives to read KCDs then one set of DKs will open up AACS completely (requiring only a firmware patch). The only thing they could do then is to revoke all these standalones of that particular company.

Now surely they haven't been that careless...