How many times can they update the MKB tree?

[ridesideways]

Given the way revocation works using the subset-difference method, there must be a finite number of times that the AACS can revoke device keys by updating the MKB, because they will eventually run out of revocable subsets.

I guess it depends on how the AACS is utilizing the nodes in the various trees the comprise the MKB, and on how many vendors are out their needing device keys. But assuming the AACS is smart and assigns nodes in the trees in a manner that maximizes the number of revocations that are possible, how many versions of the MKB can they release before they run out of subsets that allow them to accurately revoke a desired subset of device keys?

I am just asking out of curiosity, it is really just a theoretical question.

[FoxDisc]

Given the way revocation works using the subset-difference method, there must be a finite number of times that the AACS can revoke device keys by updating the MKB, because they will eventually run out of revocable subsets.

I guess it depends on how the AACS is utilizing the nodes in the various trees the comprise the MKB, and on how many vendors are out their needing device keys. But assuming the AACS is smart and assigns nodes in the trees in a manner that maximizes the number of revocations that are possible, how many versions of the MKB can they release before they run out of subsets that allow them to accurately revoke a desired subset of device keys?

I am just asking out of curiosity, it is really just a theoretical question.

There is no limit to the "number of times that the AACS can revoke device keys by updating the MKB" Each MKB stands alone and defines all of the currently revoked devices in one or more subsets. Each time they issue a disc, they can change the revoked subsets, so they will not "eventually run out of revocable subsets"

Revocation of multiple adjacent device numbers is easy. What is hard is to revoke numbers 1, 3, 5 and 7 but not 2, 4, 6 and 8 It actually takes less space to revoke six devices 1-5 and 7 in the next MKB than to revoke only four alternate devices: 1, 3, 5 and 7.

Theoretically, I believe revoking all the alternate device numbers (even or odd) would take the most space.

What you are really asking is how much space is available on each disc to define multiple revoked subsets. I don't know the actual limit. It's probably in the AACS specs, or could be figured out, but it's unlikely to be a limit they will run into any time soon. They still have some branches open, so they could revoke an entire branch and open a new one if it came to that.

[ridesideways]

ok, i see what you're saying. i think i was misunderstanding how the MKB was structured. i was thinking that the MKB tree nodes were forever fixed when they made the first MKB, and the nodes in the tree could not be rearranged or moved, and that to revoke a device key they had to "turn off" certain paths in the fixed tree. if that were the case, you would eventually reach a point where you couldn't "turn off" any more paths and get exactly the combination of revocations you want, because the tree is "fixed".

but it sounds like you're saying that they completely re-make the MKB tree from scratch every time a new one comes out, so there is really no limit to how many times they can do that.

as you said, as the revocation list gets more complicated, the tree might take up more space, but that isn't ever going to realistically be a limiting factor.

thanks for the reply!

[FoxDisc]

ok, i see what you're saying. i think i was misunderstanding how the MKB was structured. i was thinking that the MKB tree nodes were forever fixed when they made the first MKB, and the nodes in the tree could not be rearranged or moved, and that to revoke a device key they had to "turn off" certain paths in the fixed tree.
The tree is fixed and never changes, but they don't turn off entire paths.

if that were the case, you would eventually reach a point where you couldn't "turn off" any more paths and get exactly the combination of revocations you want, because the tree is "fixed".

The tree is fixed - one node at the top and billions of nodes, corresponding to the billions of devices a the bottom. To revoke a device on the bottom, the MKB turns "on" an upper node above the device to be revoked and turns off another node, also above the device to be revoked, but below the '"on" node. Everyone who is below the upper "on" node, but not below the lower "off" node is on. Everyone who is below both nodes is revoked. It sounds complicated, but it is in fact extremely efficient.

it sounds like you're saying that they completely re-make the MKB tree from scratch every time a new one comes out, so there is really no limit to how many times they can do that.

Nope, they just change the on and off nodes.

as you said, as the revocation list gets more complicated, the tree might take up more space, but that isn't ever going to realistically be a limiting factor.

The tree takes up the same space and never changes. The group of allowed players is called a subset difference set. The "subset" is everyone below the upper on node (AACS calls it the u-node) and the "difference" set is everyone below the lower "off" node (which the AACS calls the v-node)

thanks for the reply!

It's complicated, but interesting. The Understanding AACS (http://forum.doom9.org/showthread.php?t=122363)thread has the details if you are want more info.

[loo3aem3ON]

It sounds a bit like the AACS specification chose the symbols "u" and "v" for the nodes. By conventions the symbols "u", "v" and "w" are used for nodes in a graph just like "i", "j" and "k" are used for indices. I thought this might be worth adding to avoid confusion.

[FoxDisc]

It sounds a bit like the AACS specification chose the symbols "u" and "v" for the nodes. By conventions the symbols "u", "v" and "w" are used for nodes in a graph just like "i", "j" and "k" are used for indices. I thought this might be worth adding to avoid confusion.

Yes, AACS used u and v notation for the nodes. The original Naor-Naor-Lotspiech paper that laid the theoretical foundations for AACS used set theory notation (and referred to it as a subset-cover algorithm rather than subset-difference used by AACS), while arnezami's thread linked above used a third.