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.

 

Go Back   Doom9's Forum > General > Decrypting

Reply
 
Thread Tools Search this Thread Display Modes
Old 18th February 2007, 17:36   #21  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by Jay Bee View Post
Looks like a good effort!

But personally I didn't get any further than the first image. Maybe an explanation of what all the abbreviations in it mean would help clueless noobs (like me) getting started.
I've added what the abbreviations stand for in my first post. Hope that helps a (little) bit.

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

Last edited by arnezami; 18th February 2007 at 17:39.
arnezami is offline   Reply With Quote
Old 18th February 2007, 17:49   #22  |  Link
Jay Bee
Registered User
 
Join Date: May 2006
Posts: 451
thx !
Jay Bee is offline   Reply With Quote
Old 18th February 2007, 22:51   #23  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by arnezami View Post
The current Processing Key is in the far lower left of the tree used. This tree is the first tree (out of 513 I believe, I haven't analyzed yet why it isn't 512) which is why the first C-value is used. In other words: the largest tree isn't the 31 nodes high tree (which would be the truely root tree) but several floors higher. AACS simply doesn't use the trees with 31-23 nodes high. Which is why the lowest floor (for AACS) is still didived in approx 500 trees I believe.
Where did you get number 31 from?
xyz987 is offline   Reply With Quote
Old 19th February 2007, 07:02   #24  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by xyz987 View Post
Where did you get number 31 from?
AACS Common:

Quote:
3.2.3 Storing Device Keys
Each device is given its Device Keys and a 31-bit number d called the device number.
and at a different point:

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


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

Last edited by arnezami; 19th February 2007 at 07:09.
arnezami is offline   Reply With Quote
Old 19th February 2007, 10:48   #25  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by arnezami View Post

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

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

Last edited by xyz987; 19th February 2007 at 11:02.
xyz987 is offline   Reply With Quote
Old 19th February 2007, 11:22   #26  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
If is noteworthy to say that an attacker that gets the full set of Device Keys (253 keys) from any soft player can do some interesting things because he can derive any key of master tree and sub-trees, except a handful of them.

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

Code:
                       1
                      /  \
                     /    \
                    /      \
                   /        \
                  /          \
                 /            \
                /              \
               /                \
              /                  \
             2                    3
            / \                  / \
           /   \                /   \
          /     \              /     \
         /       \            /       \
        4        5          6         7
       / \       / \       / \        / \
      /   \     /   \     /   \      /   \
     8     9   10    11   12   13   14   15
Once arnezami's Processing Key is revoked, they will start using key 9 to encrypt. Then this attacker can immediately publish key 9. Then they revoke key 9 and start encrypting with key 4, then attacker immediately publish key 4, and so on.

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

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

Last edited by xyz987; 19th February 2007 at 16:03.
xyz987 is offline   Reply With Quote
Old 20th February 2007, 21:37   #27  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
If is noteworthy to say that an attacker that gets the full set of Device Keys (253 keys) from any soft player can do some interesting things because he can derive any key of master tree and sub-trees, except a handful of them.
This has been here for a while, and no one has commented, so I guess I will. As far as I can tell, and I've brought my own understanding up another notch, the above statement is not true.

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

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

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

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

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

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

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

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

Quote:
Then they revoke key 9 and start encrypting with key 4, then attacker immediately publish key 4, and so on.
Any attacker with a full set of Device Keys can simply sit and wait next revocation, publishing always just the necessary Device Key to decrypt, sans revealing the identity of his player, so his set of Device Keys can not be revoked.
No. No player has all the keys. A device has all the keys for every S-D set that it is a member of, but there are lots of sets the device is not a member of and that the device does not have processing keys for and cannot calculate.

Quote:
The only necesary caution is to check first that the next Device Key attacker is going to publish is not his Leaf Device Key (far improbable). If it is any other, and they are already using it to encrypt, the attacker can safely publish it.
I'll leave this on the quote, but it makes no sense to me.
FoxDisc is offline   Reply With Quote
Old 20th February 2007, 22:05   #28  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Traitor Tracing

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

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

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

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

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

Those two S-D sets do not overlap. Using the AACS system, they would have encrypted the media key twice, once with the processing key for the first set above and once for the second set above. Then when the processing key leaked, they would have known which of the two groups it came from. All devices could have decrypted the media key, but only with the processing key they knew how to get.
FoxDisc is offline   Reply With Quote
Old 21st February 2007, 00:42   #29  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by FoxDisc View Post
This has been here for a while, and no one has commented, so I guess I will. As far as I can tell, and I've brought my own understanding up another notch, the above statement is not true.
From aacs spec:

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

and also:

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

Quote:
As best I can tell, for the numbered tree above and the AACS tree, the S-D set in question is the set starting at the top node (number 1 above) minus the set starting at the lower left (number 8 above). To make that clear: there is no device at the lower left (it's special), and every device is below the top. Thus, when you subtract off the set comprising the lower left from all devicees below the top, you still leave all devices.
I have not checked your idea of "special key" (prior to any revocation), but anyway what is important is if an attacker with a full set of Device Keys will be able to derive the new Processing Key after revocation. He will be, in the same way any non-revoked player does.

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

Quote:
No, he won't have it, if he *is* device 9, and if he's not, they won't use that processing key. They won't encrypt the media key and put it on the disc with any processing key that corresponds to a S-D set that has the attacker as a member. That's how it works.
Of course, if he (it, the device) is device 9 game is over. But AACS LA doesn't know which device the keys of the Device Key set are from, so they can not choose to revoke a group it is a member, because they don't know its identity.
xyz987 is offline   Reply With Quote
Old 21st February 2007, 01:19   #30  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by FoxDisc View Post
I might as well go on a bit further from my last post. The processing key that arnezami found is a key that corresponds to a S-D set that all devices are members of and all devices can therefore calculate. If arnezami or muslix64 had just popped up and said here's the processing key, no one at AACS would have been sure where that key came from. Any device could have found it in theory. Lots of people are wondering why they did it this way.
arnezami did it that way just because he didn't get a Device Key set. He got a Processing Key, and this Processing Key can be revoked no matter if AACS LA knows how (or from) arnezami got it.

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

Quote:
They could have done some things to help them figure out where it came from and that process is called "traitor tracing." It turns out they have some sophisticated procedures using what are called "sequence keys" to help with traitor tracing, but as far as anyone can tell, they are not using that method.
So let's wait until they start using Sequence Keys. BTW, AFAIK Sequence Keys say nothing about where the Processing Key is from, but i have not read completely spec chapter about Sequence Keys.

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

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

Those two S-D sets do not overlap. Using the AACS system, they would have encrypted the media key twice, once with the processing key for the first set above and once for the second set above. Then when the processing key leaked, they would have known which of the two groups it came from. All devices could have decrypted the media key, but only with the processing key they knew how to get.
So attacker publish both Processing Keys, because he can derive both (as any player). Just an example: device 12 has keys 13,7, 2 so it can derive any Leaf Device Key except key 12.

Last edited by xyz987; 21st February 2007 at 02:20.
xyz987 is offline   Reply With Quote
Old 21st February 2007, 01:58   #31  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
From aacs spec:
"A given set of Device Keys enables derivation of every key in the master tree except the keys between its leaf and the root"
This is correct. It doesn't conflict with what I posted. It's saying that a device can derive all Processing keys for every S-D set that the device is a member of. It's also saying it can't derive keys for S-D sets that it is not a member of. If the AACS LA knows which device is compromised, and revokes that device, all of the device keys for that device become totally useless.

Quote:
I have not checked your idea of "special key" (prior to any revocation), but anyway what is important is if an attacker with a full set of Device Keys will be able to derive the new Processing Key after revocation. He will be, in the same way any non-revoked player does.
I'm not sure what you are saying here. If he's revoked, he can't calculate anything useful. The only hope he has is if the AACSLA does not know who he is. That's what Traitor Tracing is all about.

Quote:
Furthermore, attacker can safely publish the Device Key who derives the new Processing Key. If several Processing Keys are used to encrypt different movies, attacker can publish the Device Key that derives all of them. Any player can derive that Device Key, attacker is not revealing identity of the player he got Device Key set from.
The revoked attacker won't have any device keys that derive a valid processing key.

Quote:
Of course, if he (it, the device) is device 9 game is over. But AACS LA doesn't know which device the keys of the Device Key set are from, so they can not choose to revoke a group it is a member, because they don't know its identity.
OK, so you are assuming they do not know the identity of the attacker? That's what Traitor Tracing is for. They have a method to find out, but they are not yet using it. They could also just assume it's one of the two PC players and revoke both sets, and force updates.
FoxDisc is offline   Reply With Quote
Old 21st February 2007, 02:30   #32  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
arnezami did it that way just because he didn't got a Device Key set. He got a Processing Key, and this Processing Key can be revoked no matter if AACS LA knows how (or from) arnezami got it.
Agreed

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

Quote:
So let's wait until they start using Sequence Keys. BTW, AFAIK Sequence Keys say nothing about where the Processing Key is from, but i have not read completely spec chapter about Sequence Keys.
I have not read all about sequence keys either. They may decide not to use them yet. I think they know how the keys were obtained. They don't have the scenario they planned for of leaked device keys, so they don't really need to revoke those keys (equivalent to revoking a device). They may just harden the players and use another one of many possible processing keys that all players can calculate.

Quote:
So attacker publish both Processing Keys, because he can derive both (as any player). Just an example: device 12 has keys 13,7, 2 so it can derive any Leaf Device Key except key 12.
The attacker cannot derive both Processing keys. He can only derive processing keys for S-D sets that include him. He can't derive any processing key for any set that does not include him.

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

What device 12 does *not* have is the key at 6 or 3 or 12. He's not in those S-D sets, and he can't get those keys. As soon as the AACS LA figures out he's #12, they'll use one of those keys and he's out of luck. To emphasize, the key at 3 is good for everyone below 1 minus everyone below 3. Since 12 is below 3 he's not in that S-D set and wasn't given that key.
FoxDisc is offline   Reply With Quote
Old 21st February 2007, 02:41   #33  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by FoxDisc View Post
If the AACS LA knows which device is compromised, and revokes that device, all of the device keys for that device become totally useless.
I am saying there is no way to know it. All my point is this: there is no way to know it.

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

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

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

Even worse, once the old DK set is revoked, attacker can publish it, and this would cause AACS LA loses a big chunk of key space for future revocations. Just publishing Device Key 2 causes LA loses half of master tree keyspace.
xyz987 is offline   Reply With Quote
Old 21st February 2007, 03:02   #34  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
What device 12 does *not* have is the key at 6 or 3 or 12. He's not in those S-D sets, and he can't get those keys. As soon as the AACS LA figures out he's #12, they'll use one of those keys and he's out of luck. To emphasize, the key at 3 is good for everyone below 1 minus everyone below 3. Since 12 is below 3 he's not in that S-D set and wasn't given that key.
So we are saying the same thing. AACS needs to know (or at least to figure out) which is the compromised player.
xyz987 is offline   Reply With Quote
Old 21st February 2007, 03:48   #35  |  Link
FMalibu
Registered User
 
Join Date: May 2003
Posts: 22
First of all, thanks for the explenation and all other hard work. The thread about the processing key peaked my intested and prompted me to figure out how this part of AACS actually works and what actually was uncovered. From what I understand of it, this explanation is correct, but I still wanted to add some points that I have gathered. Note that a lot of information came from http://www.wisdom.weizmann.ac.il/~naor/PAPERS/2nl.pdf.

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

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

As an example, lets look at that nice tree again:
Code:
                       1
                      /  \
                     /    \
                    /      \
                   /        \
                  /          \
                 /            \
                /              \
               /                \
              /                  \
             2                    3
            / \                  / \
           /   \                /   \
          /     \              /     \
         /       \            /       \
        4        5          6         7
       / \       / \       / \        / \
      /   \     /   \     /   \      /   \
     8     9   10    11   12   13   14   15
Now, suppose we are a device with corresponding device node 12. The device keys given to us will be from these S-D sets: 1-2, 1-7, 1-13, 3-7, 3-13 and 6-13.

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

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

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

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

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

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

Quote:
This is about the value of the Processing now and in the future. There are ways the AACS LA can issue MKBs in such a way that each disc/movie will have to use a different Processing key thus making a Processing Key in the future much less valueable. However this is really an advanced topic which requires a thourough analysis of what can and can't be done. Its very interesting in itself.
Please explain this further. How can they give S-D values that build the same tree? Or would they use some other technique?

-- FMalibu
Attached Files
File Type: txt mkb.txt (39.8 KB, 888 views)

Last edited by FMalibu; 21st February 2007 at 15:57. Reason: S-D/D-S mixup
FMalibu is offline   Reply With Quote
Old 21st February 2007, 04:59   #36  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
I am saying there is no way to know it. All my point is this: there is no way to know it.
You are right that the processing key tells only one thing - that some device in the S-D set for that processing key used their Device keys to get that processing key.

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

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

Quote:
Even worse, once the old DK set is revoked, attacker can publish it, and this would cause AACS LA loses a big chunk of key space for future revocations. Just publishing Device Key 2 causes LA loses half of master tree keyspace.
No- half of keyspace is not lost with key 2. You are only looking at one floor of arnezami's parking garage. Read more about subset difference sets and the AACS system. The system assumes that all device keys for any possible set of R devices are lost and the system still works.
FoxDisc is offline   Reply With Quote
Old 21st February 2007, 05:43   #37  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by FoxDisc View Post
2) Second way is with processing keys as explained above. This is slow, but basically, they know for every processing key released that some device in the corresponding S-D set released it.
Too slow. Say 1 million players are sold this year, 2 million player next year, 4 million players at 2009. Yes, I am being malicious with the numbers, but they can find that the number of players in that subtrees increases faster than the speed at they reduce posibilities.

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

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

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

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

Quote:
No- half of keyspace is not lost with key 2. You are only looking at one floor of arnezami's parking garage. Read more about subset difference sets and the AACS system. The system assumes that all device keys for any possible set of R devices are lost and the system still works.
I wrote "half of master tree keyspace", not "half of keyspace". Master tree is first floor of arnezami's parking garage (the biggest one).

Last edited by xyz987; 21st February 2007 at 06:12.
xyz987 is offline   Reply With Quote
Old 21st February 2007, 06:09   #38  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by FMalibu View Post
Let's continue the example. Suppose that those devices that correspond to nodes 8,9 and 14 have been revoked. The D-S values given in the MKB should then be 2-4 and 3-14, as this is the set that reaches all device nodes except those that have been excluded. The device with device node 12 selects the 3-14 substree, as it is included in that, and uses its 3-7 key, as this key has also has 3 as its D node and its S node is on the route to node 14. It uses this key to derive the subsidiary device key at node 14 and subsequently the processing key. It will look up the C-value belonging to subset-tree 3-14 and decode the media key.
Good explanation, but your example is a revocation of noncontiguous keys. Things are different if they revoke contiguous keys. If keys 8,9 are revoked, they encrypt with key 4 of master tree, and any player can derive that key.

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

However, it seems like a big coincidence that the device is located within the first D-S tree. If they (stupidly) started handing out device nodes at value 0 and work their way upwards (in the tree this would be starting at the left bottom node and going right one step each time), then there is no way to determine which device was compromised. In fact, a total of 2^22 - 1 = 4194303 devices should get a hit on the first D-S value
They are just following their own specification. There is not "big coincidence" neither "they (stupidly) started". This is what you and FoxDisc miss. AACS LA is still at master tree (no subtrees, no subset differences), and they won't leave master tree until they need to revoke noncontiguous keys. That's why the very first C-value is the only one used.
xyz987 is offline   Reply With Quote
Old 21st February 2007, 13:25   #39  |  Link
FMalibu
Registered User
 
Join Date: May 2003
Posts: 22
Quote:
Originally Posted by xyz987 View Post
Good explanation, but your example is a revocation of noncontiguous keys. Things are different if they revoke contiguous keys. If keys 8,9 are revoked, they encrypt with key 4 of master tree, and any player can derive that key.
Thanks.

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

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

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

Quote:
They are just following their own specification. There is not "big coincidence" neither "they (stupidly) started". This is what you and FoxDisc miss. AACS LA is still at master tree (no subtrees, no subset differences), and they won't leave master tree until they need to revoke noncontiguous keys. That's why the very first C-value is the only one used.
I understand that you would think that (I assumed this at first as well), but please look at the text file I included. It's a bit cryptic, but I will attempt to describe what the Explicit Subset-Difference tree from current MKBs look like:

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

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

Also:

Quote:
Even worse, once the old DK set is revoked, attacker can publish it, and this would cause AACS LA loses a big chunk of key space for future revocations. Just publishing Device Key 2 causes LA loses half of master tree keyspace.
I agree with FoxDisc here. The system is designed in such a way to prevent exactly this. They will just map out all of the S-D sets in such a way that any node en route from the root node to the compromised device node is never inluded in them. Those are all the nodes you lose.

-- FMalibu

Last edited by FMalibu; 21st February 2007 at 15:58. Reason: S-D/D-S mixup
FMalibu is offline   Reply With Quote
Old 21st February 2007, 13:58   #40  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
Too slow.
Yes, it is a slower method, and it is not the principal method. At this point it does not look like they are using any method except 3
Quote:
On the other hand I must say that I didn't understand you first time you mencioned this method. I was talking about master tree and you started to talk about subtrees.
I was still talking about the master tree then. If they decide to split up the master tree and encrypt with multiple processing keys according to the divided master tree, they will know which set the traitor is in when he releases his processing key for his set. Future discs could then divide the set he is in into multiple other sets, etc. All of this could be done in the largest tree space. Of course, this is theoretic only. They are not doing it now, and I presume they would use the sequence key method, not this.

Quote:
I wrote "half of master tree keyspace", not "half of keyspace". Master tree is first floor of arnezami's parking garage (the biggest one).
You are correct, I was rushing and missed this. Yes, half of largest (master) tree is available to all devices, so any one compromised device discloses that half. It's not a real limitation however - there are lots of remaining keys in subtrees and in the other half of the master tree.
FoxDisc is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 16:00.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, vBulletin Solutions Inc.