Understanding AACS (including Subset-Difference)

[xyz987]

Originally Posted by FMalibu

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]

Originally Posted by FoxDisc

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]

Originally Posted by FoxDisc

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:

1. 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.
2. 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]

Originally Posted by FMalibu

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]

Originally Posted by xyz987

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]

Originally Posted by FoxDisc

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

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]

Originally Posted by xyz987

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]

Originally Posted by xyz987

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.

[FoxDisc]

Originally Posted by FMalibu

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.

I have done that many times Usually I realize my error after I post While writing this post to explain why I was right, I realized that perhaps you are right I was writing very loosely

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.

Just for clarity For those reading along, the notation used by FMalibu for S-D set 1-8 means the set of all devices under node 1 minus all those under node 8. The S-D set 1-8 is devices 9-15

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?

You are right that release of that one key would compromise half of the keys.

In this case they could do one of two things:

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

1. These are not "overlapping" they are still disjoint sets, but yes, that is what I was discussing - traitor tracing as a secondary use of the processing key and revocation procedure.
   
   

   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

Although no device key was released, the processing key for set 1-8 was released. This discussion came from how they might do traitor tracing, since the processing key tells them nothing except that some member of the S-D set released it. Some have wondered why they did not start out with multiple disjoint S-D sets from the beginning.

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.

Yes.

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.

Yes. This is exactly what I was saying. Divide it into two will disallow the current procesing key, but not require revocation. Dividing in two give som limited inforamtion for future traitor tracing. They could also divide it into even more sets for more information in the future.

If they do not care about traitor tracing, and only want to disallow the processing key currently loose, they do not even have to use two keys. Just use the 1-9 key instead of 1-8. As long as device 9 is not assigned yet, and there should be lots of unassigned devices.

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

I agree with all you have posted. I really have not thought too much about releasing device keys, as no one seems to have any to release!

[FoxDisc]

Originally Posted by FMalibu

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.

I wrote pporly and did mean to say that it worked for all titles, but this raises an interesting question, and begins to tread in an area you have looked at more closely than I - the organization of the MKB. The processing key matches an S-D set of devices. Are all current devices a member of that set? We know that one is not - the special lower left device, but that we can ignore as no device has been revoked yet. We also know the root of the S-D set for this processing key is at level 22, not the highest root. Are all devices below this root at level 22 or not? I gues we don't know.

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.

Can you explain this better? What S-D sets are currently defined in the MKB? I know I need to read your text file more closely to understand.

If you would, explain these two:
Found Subset-Difference: from 0x00000000 at level 22 to 0x00000000 at level 0
Found Subset-Difference: from 0x00400000 at level 22 to 0x00400000 at level 0

Level 0 is at the bottom correct? Level 22 is 22 up from the bottom? I need help with the "from" and "to" parts. there seemed to be 512 S-D records in your text file. They all seem to start at 22. Do they all start at different nodes below the true top? I think yes, since the "froms" differ, but not sure. What is the difference part of the S-D set on the 0 level? Is that the "to" part? If so, the first S-D set ends on the lower left of its tree, but it'snot clear to me about the second one.

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

So the "another S-D set" you refer to might be that line:
Found Subset-Difference: from 0x00400000 at level 22 to 0x00400000 at level 0?

Two devices are attacked, but neither has any device keys lost or compromised. All we know is that all devices in the S-D set for the current processing key can get that key, so presumably they will use that key. Am I correct in thinking that the current processing key matches the S-D set corresponding to the first line from your text file:

Found Subset-Difference: from 0x00000000 at level 22 to 0x00000000 at level 0

It wouldn't make sense to un-revoke the lower-left device, since it wouldn't be able to play back current titles.

True. Obvious mistake by me.

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.

I wondered when you would spot that.

[FoxDisc]

Originally Posted by FMalibu

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

This is how I think it works too. FMalibu has described it somewhat differently than the AACS specs, and it took me a while to reach the same answer he has reached - by reading non AACS work. I will throw in one important additional feature here: "There is one master tree and every node in this tree has a master key."

These "master" keys are random numbers. No one except the AACS LA has any of them, and even if one was figured out, it would tell you nothing about any other master key.

[FMalibu]

Originally Posted by arnezami

Wow! Some solid good discussion here .

It seems out collective understanding of the Subset-difference has grown...

Damn you for making me so curious

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

That much is true. I was merely speculating on something that would perhaps be more valuable in light of countermeasures, but obviously something that is more valuable will also be harder to obtain.

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 disc (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.)

I think I see what you're getting at. By revoking a different fake nodes for each disc you get a different tree structure and a different Explicit Subset-Difference Record in each. BTW, did you mean title or actual disc? Including a different MKB for each individual disc seems unfeasable and not economically sound when it comes to pressing discs. Maybe for different batches.

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

It will be quite interesting to see what countermeasures will be taken. For the current generation of titles the one processing key suffices. As many people have already speculated, it will be much of a cat-and-mouse game.

-- FMalibu

[FMalibu]

FoxDisc: For brevity, I wont quote everything you said, as the only comment I have for those parts that are missing is that I agree.

Originally Posted by FoxDisc

These are not "overlapping" they are still disjoint sets, but yes, that is what I was discussing - traitor tracing as a secondary use of the processing key and revocation procedure.

By overlapping I meant that they are not disjoint because they both share node 3. But indeed this is the only node they share. The device nodes are still disjoint. And yes, I was describing the traitor tracing you were discussing.

Some have wondered why they did not start out with multiple disjoint S-D sets from the beginning.

They have! See the description of the MKB later on.

Yes. This is exactly what I was saying. Divide it into two will disallow the current procesing key, but not require revocation. Dividing in two give som limited inforamtion for future traitor tracing. They could also divide it into even more sets for more information in the future.

For some reason I thought instantly dividing it into more than two wouldn't work, but I see you're right now. In the example of the compromised device node 12, instead of making it 3-6 and 3-7 they could use 6-12, 6-13, 7-14 and 7-15. If another processing key is released this would tell them instantly which device was compromised (the 6-13 device key of the device with device node 12 would be used).

If they do not care about traitor tracing, and only want to disallow the processing key currently loose, they do not even have to use two keys. Just use the 1-9 key instead of 1-8. As long as device 9 is not assigned yet, and there should be lots of unassigned devices.

That's the question. Are they assigining them randomly? Also, 1-4 would make more sense, as device 8 is already revoked

About the MKB text file, I probably should have explained it better. Of course I just made the script for my personal use so ik makes sense that I'm the only one that can decipher it

The file just lists all the Explicit Subset-Difference entries, i.e. S-D sets, it finds sequentially, in the format "From S to D":

Found Subset-Difference: from 0x00000000 at level 22 to 0x00000000 at level 0
Found Subset-Difference: from 0x00400000 at level 22 to 0x00400000 at level 0

The specs work with masks, but I found this notation to be a little more intuitive. The level indicates how high up the tree the node is. Level 0 is a device node, the root node is at level 31 (or 30?), making a total of 32 (31?) levels. As you can see, the S node for each S-D set is located at level 22. (I'm not sure about my maths here...)

The hexadecimal numbers represent a 32-bit integer. As the device numbers are given in 31 bits, the first (most significant) bit is always 0. The rest of the bits give the path to the node, a 0 being "left", the 1 being "right". Of course, if the level is higher than 0, the number will contain that many trailing 0's, as it won't travel further down the tree.

Notice that for each S-D entry the S value is increased by 0x400000, which equals 1 << 22, and that there are a total of 512 entries. This means that all nodes at level 22 are represented as S nodes. Also notice that for each S-D entry the D value equals the S value. Since the trailing 0's for this values are revelent however, this simply means the leftmost device node that has the D node as a parent.

I hope you're getting the same mental picture as I am (I like to visualise things in my head, but am to lazy to open ms paint). 512 equal height pyramids which are nearly touching (but not overlapping) at the bases, each pyramid with a red dot in the lower left corner indicating the D node and thus the revoked device. Our compromised device resides somwhere along the base of the first pyramid.

This is how I think it works too. FMalibu has described it somewhat differently than the AACS specs, and it took me a while to reach the same answer he has reached - by reading non AACS work. I will throw in one important additional feature here: "There is one master tree and every node in this tree has a master key."

These "master" keys are random numbers. No one except the AACS LA has any of them, and even if one was figured out, it would tell you nothing about any other master key.

Exactly! They are fully random and independent values.

Somehow section 3.2.1 is misleading (it does say "Informative") and slightly at odds with the rest of the document.

-- FMalibu

[arnezami]

Originally Posted by FMalibu

BTW, did you mean title or actual disc? Including a different MKB for each individual disc seems unfeasable and not economically sound when it comes to pressing discs. Maybe for different batches.

Yeah. I'm sorry. I meant Title/movie.

Originally Posted by FMalibu

It will be quite interesting to see what countermeasures will be taken. For the current generation of titles the one processing key suffices. As many people have already speculated, it will be much of a cat-and-mouse game.

Yeah. But don't forget: they are the mouse. We are hunting for them or better: their methods and keys .

In fact: there are many cats around here..

[arnezami]

Originally Posted by FMalibu

Somehow section 3.2.1 is misleading (it does say "Informative") and slightly at odds with the rest of the document.

Just for the record I believe section 3.2.1 is badly written and simply isn't very informative: it doesn't fill the gap between its very (and too) general explanation and the more precise and technical sections that follow.

In fact it was exactly this gap I wanted to fill . And something tells me it worked...

[FMalibu]

Originally Posted by arnezami

Just for the record I believe section 3.2.1 is badly written and simply isn't very informative: it doesn't fill the gap between its very (and too) general explanation and the more precise and technical sections that follow.

In fact it was exactly this gap I wanted to fill . And something tells me it worked...

I would say it verges on being incorrect, but I can't prove it, that's why I'm sticking to misleading.

I find that in particular your diagrams of the coloured tiles are a very potent metaphor. The whole business with the trucks however collides with the mental picture I had already formed, but I can imagine it being usefull to others.

[arnezami]

Originally Posted by FMalibu

I would say it verges on being incorrect, but I can't prove it, that's why I'm sticking to misleading.

I find that in particular your diagrams of the coloured tiles are a very potent metaphor. The whole business with the trucks however collides with the mental picture I had already formed, but I can imagine it being usefull to others.

The point of the using trucks is to make a more physical analogy instead of a mathematical one. In my experience this works better for getting the gest of an idea. More accurate (and mathematical/logical) analyses will usually follow. This choice was very deliberate.

I don't just want to tell people how things work. I want them to "see" it themselves and then start to think for themselves about it .

[FoxDisc]

Originally Posted by FMalibu

They have! See the description of the MKB later on.

Yes, as I looked closer at your file on the MKB, I suspected that.

This means that all nodes at level 22 are represented as S nodes.

To be sure we are on the same wavelength, an "S node" in your notation is an upper Subset node and a D is a lower Difference node? So an S=u and a D=v in the AACS uv mask notation?

I hope you're getting the same mental picture as I am (I like to visualise things in my head, but am to lazy to open ms paint). 512 equal height pyramids which are nearly touching (but not overlapping) at the bases, each pyramid with a red dot in the lower left corner indicating the D node and thus the revoked device. Our compromised device resides somewhere along the base of the first pyramid.

I had this picture before I opened your file or read your response. :-) I just needed to be sure that was what was in the MKB.

So we do not know for sure about non-software players, but perhaps some lie in the second 512 height pyramid, the one just to the right of the one the software players are in, and they would normally use a processing key different from the one arnezami located? Hmmm. The processing key from arnezami confirms to them that a device from the first tree was used. (As if they didn't know where the software players reside.)

I am wondering about this breakup at level 22 into 512 pyramids. I wonder if devices have device keys for above that level? I have forgotten if any specs tell how many device keys each device has. IIRC 253 are needed for one of the 512 pyramids at level 22, but only 496 or 528 for 31 or 32 levels. I'm getting a picture of this divided up base of 512 pyramids having only a few devices in each pyramid, perhaps separated by manufacturer or with software players in one and hardware in another.