Understanding AACS (including Subset-Difference)

[ralferoo]

2) A Title has up to 32 spots where one of 8 different cells must be decrypted. It appears that each of the 8 cells can potentially be decrypted, so that all that is required is to give one decryption key for one of the 8 cells at each of the 32 locations. These keys are the equivalent of the title key that is used for the rest of the movie. I'm still not sure how much information a single decryption key for a cell gives out about the source of that key. The 32 keys needed could come from many different players.
Before I start, I should note that in this post I'll be using the term "oracle server" as mentioned in previous posts as a term for an internet service that is given a request containing enough information to identify a disc and returns a response containing the keys required to decrypt the the title. If sequence keys are used, you'd get back a general media key and 32 cell keys to decrypt a particular title. Hopefully, this is also the meaning others were using for that term.

Now, if each of these 32 keys (cells) can each take on 1 of 8 possible values, we have 3 bits of information, meaning overall there is 96 bits of information given out about the device's SK set. 96 bits is large enough that every individual device can be uniquely, and this seems the likely way of identifying a set of keys to be revoked. I would strongly imagine that the device class is encoded into this so they can work out which nodes in the regular tree need to be revoked if it became apparent that an entire class of device had become easy to compromise and an easy source of keys.

If an oracle service had access to two sets of keys, in the best case scenario (from its perspective) it could come up with a different key for each cell and choose randomly which one to publish, effectively making 32 bits of that 96 bits random. From a sample of one, the tracing technique would identify the wrong device completely (assuming the cell keys weren't all from the same player). However, as the oracle server offered keys to decrypt different titles, it would become apparent which 32 bits were being chosen randomly, and so which 64 bits were correct.

Now, this is probably where the 256 columns comes in, because if one set of keys was "temporarily revoked" when questioning the oracle server, it would have to choose a different set of keys for each of the columns. If these were chosen carefully by the LA then the identifying bits would be distributed differently and so a different set of 64 bits could be determined. Now, if the column was chosen particularly so that those 64 bits included the 32 unknown bits, then the oracle server would be giving up the identity of both of its sources of device keys.

Now, the oracle server stands a better chance of avoiding detection if it doesn't randomly choose a key from each cell, but instead having that choice as a function of the input. Thus, for the same request it will always impersonate the same device rather than carelessly giving away information about which bits are entropic.

On the other hand, if the oracle server is prepared to attempt to decrypt any request that comes in, it will be forced to give up that information as it will have to decrypt MSKs from arbitrary columns. The only way the oracle server can be relatively safe is if it gives keys out from known good requests, e.g. when it has itself previously seen that physical media. Even then, given enough titles using keys from different columns it will give up its own identity.

Obviously, the more SKs the oracle server has the more entropy it can provide in the output, but all this does is increase the number of columns needed to identify its sources.

So, the other obvious approach is finding a way of discovering a large source of these key sets. This is most likely to come from a class of device being compromised (e.g. a particular model of hardware player or version of software player where the keys can be easily discovered). So, in all likelihood the LA will assign a large common set of keys to a manufacturer and a smaller set of keys that particularly identify the individual device. e.g. cells 1-16 might be decoded using exactly the same key for all devices of the same model and 17-32 providing a serial number for an individual device. This would improve security the available bits of entropy from an oracle server would be greatly diminished unless it had key sets from several different types.

[FoxDisc]

Before I start, I should note that in this post I'll be using the term "oracle server" as mentioned in previous posts as a term for an internet service that is given a request containing enough information to identify a disc and returns a response containing the keys required to decrypt the the title. If sequence keys are used, you'd get back a general media key and 32 cell keys to decrypt a particular title. Hopefully, this is also the meaning others were using for that term.

Yes, this is an "anonymous" oracle because it gives out the final key for each encrypted section, without disclosing the smaller set of Sequence Keys it used to get the answers . A non-anonymous oracle would give out the 6 Sequence Key/row# sets and let the recipient calculate the keys for each of the 32 sections.

The terminology makes more sense in the Device Key scenario. In that scenario, the media key/title key is encrypted multiple times by multiple processing keys. Every device ultimately arrives at the same Title Key, but could have used any one of many different processing keys. The anonymous oracle would only give out the final title key (or the final decrypted movie) which could have come from any device - disclosing nothing. In contrast, a program capable of playing a disc must calculate the title key and that discloses the exact device keys/processing keys used for the calculation, so it is not anonymous.

The terminology as applied to the Sequence Key scenario is a bit confusing since the purpose of the SKs is to identify the device even with an "anonymous oracle" attack, although it is more difficult than when the non-anonymous SKs are given out.

Now, if each of these 32 keys (cells) can each take on 1 of 8 possible values, we have 3 bits of information, meaning overall there is 96 bits of information given out about the device's SK set. 96 bits is large enough that every individual device can be uniquely, and this seems the likely way of identifying a set of keys to be revoked. I would strongly imagine that the device class is encoded into this so they can work out which nodes in the regular tree need to be revoked if it became apparent that an entire class of device had become easy to compromise and an easy source of keys.

I suspect you are right.

If an oracle service had access to two sets of keys, .....

Interesting analysis. Clearly the more final decryption keys for the 32 times 8 cells that the oracle has, the harder it is to identify it. If it had all of them, it would be truly anonymous, but I doubt that anything short of all keys from all devices would give that level of information.

[FoxDisc]

2) A Title has up to 32 spots where one of 8 different cells must be decrypted. It appears that each of the 8 cells can potentially be decrypted, so that all that is required is to give one decryption key for one of the 8 cells at each of the 32 locations. These keys are the equivalent of the title key that is used for the rest of the movie. I'm still not sure how much information a single decryption key for a cell gives out about the source of that key. The 32 keys needed could come from many different players.

A related issue to the above: The result of decrypting one of the 8 cells is a time portion of the movie/title. That section has to be marked. Each of the other cells from the 8 has to have a different mark. We're talking about true watermarking here. The video data needs to be fundamentally the same or everyone will see a different movie.

Instead of issuing decryption keys, the oracle could theoretically issue the decrypted section of the movie. The oracle could serve up all of the decrypted sections with the watermarking removed so it couldn't be traced back to the keys used to decrypt it. This anonymizes the oracle. I've seen some interesting analyses of watermarking removal techniques. Unfortunately, now we're talking about needing a pirate server (for 32 short sections of the movie) to protect the fair use right to make backups. It would be ironic if the whole AACS system pushed legitimate users towards piracy merely to exercise their fair use rights.

I suppose the encrypted sections could be uploaded, decrypted, then processed to remove the watermarking before being returned. I haven't checked to see how big these sections are.

[xyz987]

We agree on this. There are only 2^16 different rows for each column. There are up to 2^32 different possible players, so up to 2^16 may have this exact SK in this row.


I want to be sure we really agree on this. If an attacker publishes just one SK (just the SK) from his player, do you agree LA doesn't know the identity of attacker player?

May be an step-by-step approach is more fruitful.

[FoxDisc]

I want to be sure we really agree on this. If an attacker publishes just one SK (just the SK) from his player, do you agree LA doesn't know the identity of attacker player?

May be an step-by-step approach is more fruitful.

There are up to 2^16 rows in a single column. Let's assume that all rows were used in the master matrix (this give the AACS LA the maximum information). If the attacker publishes a single SK they know he had that SK. They know where that SK is in the master matrix. Someone has a record of all the players ever issued with that SK. We don't know how many players have been issued SKs. However, if all 2^32 possible players were randomly issued SKs, 2^16 players would have that same key.

Yes, I think we agree about this.

[arnezami]

There are up to 2^16 rows in a single column. Let's assume that all rows were used in the master matrix (this give the AACS LA the maximum information). If the attacker publishes a single SK they know he had that SK. They know where that SK is in the master matrix. Someone has a record of all the players ever issued with that SK. We don't know how many players have been issued SKs. However, if all 2^32 possible players were randomly issued SKs, 2^16 players would have that same key.

Yes, I think we agree about this.

So if there are 256 people who each release 1 sequence key (each out of a different column) we will have a complete set of 256 Sequence keys. And the 256 people will not be identified if (1) there are more than enough players sold (2) sequence keys are distributed randomly.

The problem is of course: they can revoke unique sets of 256 keys. Since we would have exactly that it may be possible (1) none of the 256 sequence keys actually works in the first place or (2) they will make sure none of the 256 keys work (by not using any of these 256 keys on future discs).

Alternative: make sure you find say 256 people each releasing 2 keys. Assuming we now have two sequence keys in each column I have the feeling they (the AACS LA) would then have a real problem. Why? Because there are upto 2^256 possible combinations of unique sets of 256 keys. And (given pure random distribution) how do they know which sets to revoke?

All depends on the amount of players sold (that is: those with unique sets of keys**) and the randomness/smartness of the distribution. Eg. we might not be able to find two different Sequence keys in each column (but that has both advantages and disadvantages: revoking-wise).

Maybe we should do some concrete examples:

- Only 1000 players released. Random distribution.
- Only 1000 players released. "Smarter" distribution.
- 100000 players released. Random distribution.
- 100000 players released. "Smarter" distribution.
- 10000000 players released. Random distribution.
- 10000000 players released. "Smarter" distribution.

In any way I believe (from a comsumers point of view) the general rule of thumb is this: if you have found a Key and several other people have it too you can probably release it without risk.

Regards,

arnezami

** Needless to say that if they would use the same set of sequence keys in many standalones they are screwed since they would have to revoke them all. In fact: even if many Keys of the sets of a single type of player are shared between those players we could release these (maybe 200?) and they wouldn't be able to revoke them. So non-randomness may not be "Smarter" at all: we would have reduced the problem from finding 256 keys to say 50 (in for example a software player or from standalones by less savvy people).

[xyz987]

Yes, I think we agree about this.

Okay. Next step:

A guy called Peter has downloaded the published SK. Peter wants to get a valid Volume Variant Unique Key (he wants just one of the VVUKs), he can check if a VVUK is valid looking at Segment Key File. He knows which is the column number for each SKB (there are 6 SKBs on disk) because it is stored on it, but there are 2 things he doesn´t know:

1- Row number

2- Which SBK he must use (there are 6)

So Peter try all the possibilities. First he tries row number 0 with SKB 1 and he checks if he has got a valid VVUK, if not then he tries row 1 with SKB 1 and so on. If SKB 1 doesn't output a valid VVUK, he repeat the process with SKB 2 and so on.

Do you agree that Peter will find a valid VVUK?

[xyz987]

Alternative: make sure you find say 256 people each releasing 2 keys. Assuming we now have two sequence keys in each column I have the feeling they (the AACS LA) would then have a real problem. Why? Because there are upto 2^256 possible combinations of unique sets of 256 keys. And (given pure random distribution) how do they know which sets to revoke?


They can not revoke any player if the 512 SKs are from 512 different players, but all the published 512 SKs will become "compromised", i.e. they will not be useful to decrypt newly released movies.

[arnezami]

They can not revoke any player if the 512 SKs are from 512 different players, but all the published 512 SKs will become "compromised", i.e. they will not be useful to decrypt newly released movies.

Sure. But we would then have the Sequence Keys for a large amount of discs. Without giving up any identities.

Problem is: you would have to give away more and more information (or let more people be involved) for the next batch of discs. Unless they are distributing Sequence Keys in a non-random (and not so smart) way.

Naturally extracting all 256 Keys from a Software Player is far more effective. Revocation is probably default (for Software players) so it doesn't really matter.

[FoxDisc]

So if there are 256 people who each release 1 sequence key (each out of a different column) we will have a complete set of 256 Sequence keys. And the 256 people will not be identified if (1) there are more than enough players sold (2) sequence keys are distributed randomly.

I will just quickly comment on this. There are 2^4096 different possible sets of sequence keys. There are only 2^32 possible players, so there are many sets that are never assigned. This goes back to my question #1 - is a set of SKs - some from A and some from B a valid set? I haven't decided yet, but I suspect, based on the process and math that the answer is no. I think they can build SKB files with the 6 SKBs so that random collections of SKs will not be valid - they won't work to decrypt anything. Worse - the SKs will become compromised. They can be revoked individually, requiring the players who have them to go to the second column containing an uncompromised SK when processing that SKB.

Of course, I am still not certain - it's an area I'm planning to look at. Comments are welcome.

Another general comment - I'm pretty sure everyone understands that this is highly theoretical. The AACSLA knows that software players are being attacked. There's not a lot of "tracing" that needs to be done when they know the attack is from software players. Nonetheless, I think they will implement SKBs because it does increase the number of keys to be handled, stored, uploaded and processed. It makes backing up harder.

[arnezami]

This goes back to my question #1 - is a set of SKs - some from A and some from B a valid set? I haven't decided yet, but I suspect, based on the process and math that the answer is no. I think they can build SKB files with the 6 SKBs so that random collections of SKs will not be valid - they won't work to decrypt anything.
I suspect a (randomly) collected set of 256 Sequence Keys will be able to decrypt at least some movie or movie fragments. Especially if Sequence Keys are released (by customers) that are actually used for decrypting already released movies/discs. If we could choose 256+ Keys that work on several discs they will probably be able to decrypt most (if not all) discs released so far. This is because I think the SKs used in the SKBs might always be the same for one SKB version.

I agree this is quite theoretical stuff right now. We don't need any of this right now but its interesing stuff. And I also believe extracting 256 keys is much harder than extracting just a (few) Processing/Device Keys and a Pirvate Key. So it would be wise for them to implement it even if they don't use it for tracing.

[FoxDisc]

Okay. Next step:

You have my respect - this is a very good way to find out where we disagree. Together we look for the truth of how it works.

A guy called Peter has downloaded the published SK. Peter wants to get a valid Volume Variant Unique Key (he wants just one of the VVUKs), he can check if a VVUK is valid looking at Segment Key File. He knows which is the column number for each SKB (there are 6 SKBs on disk) because it is stored on it, but there are 2 things he doesn´t know:

1- Row number

2- Which SBK he must use (there are 6)

So Peter try all the possibilities. First he tries row number 0 with SKB 1 and he checks if he has got a valid VVUK, if not then he tries row 1 with SKB 1 and so on. If SKB 1 doesn't output a valid VVUK, he repeat the process with SKB 2 and so on.

Do you agree that Peter will find a valid VVUK?

This SK is going to be found in only one row and column of the master AACS matrix of SKs. Whoever disclosed it knew that information, and the AACS LA knows it, so there is no reason to keep secret either number 1 (row) or 2 (column = which of 6 SKBs it matches.)

There is no reason for the recipient to have to search for row or column number. If it is not in the correct column for any of the 6 SKBs for the movie he is trying to decrypt, it is of no use.

Now, let me break the question down further. First, let's assume the SK is an unrevoked SK in the correct column for the first of the six SKBs. Then the answer is clearly yes. The recipient will be able to calculate a valid Volume Variant Unique Key (Kvvu) and valid Variant Data Dv. The lower 10 bits of the Variant Data are the Segment Key Unit Number (SKUN). This process would be the same as any other valid device would follow.

Now the process gets more tricky. You want to know if a valid Volume Variant Unique Key (Kvvu) and valid Variant Data (Dv) will be calculated for this key if it is not in the column of the first SKB. I think the answer is again technically yes. I think at this level the SKs are still independent (not totally sure, but I think so) IOW, any device having this SK in this column will calculate the same Kvvu and Dv.

It would produce valid Volume Variant Unique Key (Kvvu) and valid Variant Data (Dv). However, that's not the end of the story. You don't use the Kvvu's and Dv's independently. You use them to build a table with the other 5 SKs you have. My reading of the process is that you will build the wrong table and/or use/decrypt the wrong entries in that table with the wrong keys if your set of 6 SKs is not a valid set.

This goes directly back to my question #1 of whether a set of SKs made up of the SKs from different players forms a valid set.

The above is intended to lead you to the next question - about how the Kvvu's and Dv/SKUN's are used with the Segment Key File (SKF) in the “AACS” directory. The SKF contains six Segment Key Group (SKG) fields. Each SKG field contains 1024 Segment Key Unit (SKU) fields. An SKU field contains 32 encrypted pairs of a Segment Key Number (SEG_NO) and a Segment Key of 16 bytes. From the 1024 SKU fields in the correct one of the six SKG fields, one SKU field is chosen according to the SKUN number above. The chosen SKU field,can be decrypted by the matching Volume Variant Unique Key Kvvu.

So to answer your question - yes, I think six individually valid Kvvu's and 6 matching valid Variant Data Dv's would be calculated by Peter (if 6 unrevoked SKs are disclosed for the specified 6 columns). I say "independently valid" because I think that one by one, each Kvvu matches what a valid device would have calculated at that position. The set of 6, however, depends on what 6 SKs were used. If they all came from a single valid device, we are on the right track for a successful decryption. If not .... we are about to reach the crux of the matter.

[FoxDisc]

I suspect a (randomly) collected set of 256 Sequence Keys will be able to decrypt at least some movie or movie fragments.

Arnezami and xyz drive me to understand more deeply. After the last post, I looked more closely at my first question - will SKs from different devices succeed in decryption. Although I cannot be certain, I now lean towards the belief that they will allow decryption, provided that only one column and one key is required for each SKB.

I have not found any definitive connection between the six SKBs. I now believe that the SK system works as follows: Each time SKs are released capable of decrypting a title (or a decrypted title is released), it will identify six compromised SKs. They may come from one device or they may come from multiple devices.

Since innocent devices share SKs, they could not revoke the device that has those 6 keys. They might define an innocent device. However, they can also obtain information from other titles, which would reveal another 6. This will narrow it down as to whether one device or multiple devices are compromised, but perhaps it is not enough information still.

So what they do is revoke all of the known compromised Sequence Keys with a new SKB file. They don't revoke any player yet. This requires the attacker to disclose a pair of SKs for each of the six SKBs. This narrows down the suspect list substantially. With multiple titles, they should quickly be able to identify whether the keys come from one compromised device or multiple devices. Just knowing one pair of SKs in two columns tells the LA that the device is in one of 2^32 different groups (first column is one of 2^16 groups and second is one of 2^16 different subgroups within the first group). There are only 2^32 different players. This should tell them what they want to know.

I believe I was incorrect in thinking that the keys used for the six SKBs are linked. It is more likely that the linking is done on an SKB by SKB basis as described above by requiring more than one SK to be used to get the correct Kvvu and Dv. To emphasize: if the first SK in the defined column is compromised, you must still use that compromised SK to get a first Dv. You then must use an SK from another column and the DV previously calculated to get the final Kvvu and Dv. You can't get the final without the first, and you don't get the right answer for the final if the first wasn't calculated from the same SK set used for the final. This is the linkage the AACS LA needs.

In fact, I suppose they could do this on the first SKB set released. They could assume that every single SK released is compromised and force every device to use two keys from its set of SKs for every SKB. It is those keys that are clearly linked.

This will be much easier to understand when (if?) the first SKB files are released.

[xyz987]

Sure. But we would then have the Sequence Keys for a large amount of discs. Without giving up any identities.


Yeah, that's true.


Problem is: you would have to give away more and more information (or let more people be involved) for the next batch of discs.


The only way to avoid this is to break completely the SKB system. It is theoretically possible to do so because the maximum number of players is a 32 bit number, and the number of positions at the matrix is a 24 bit number. However I simply don't know how many SKs from different players must be published to achieve this goal. If a group of attackers get 16 millions SKs no doubt they have broken it, but 16 million is not a practical number. The problem is to find a far lower number (may be there is no that lower number!).


Naturally extracting all 256 Keys from a Software Player is far more effective. Revocation is probably default (for Software players) so it doesn't really matter.

Yeah, nowadays soft players are almost completely broken but they can be hardened. In my opinion, we should go further. We should go to "things" that can not be hardened (i.e. standalones). This is the only way to escape from revocations.

[xyz987]

I now lean towards the belief that they will allow decryption


Okay. Next step:

Now Peter has decrypted the movie using 6 SKs from different players. But these SKs will become "compromised" soon, so the new movie that Peter will buy later can not be decrypted using them.

Afortunately, other 6 attackers publish other 6 SKs from different players. Let's say 3 of these SKs are at the "first" column of the corresponding SKB and the other 3 are at the "second" column. To get 6 valid VVUKs for the new movie Peter needs the 6 SKs work right.

For the first 3 SKs Peter finds they are at the "first" column of the first 3 SKBs and he repeats the process we have explained on former messages. No news here.

For the other 3 SKs (they are not at "first" column) Peter does as follow:

He tries the first of the compromised SKs (the old SKs) to process the first column of the fourth SKB. This allows him to go to second column (rightly or wrongly), then he uses the fourth of the uncompromised SKs (the new SKs) at second column and he checks if the resulting VVUK is valid. If not, he repeats the process with another old SK or another SKB or another new SK.

Do you agree that Peter will get 6 valid VVUKs for the new movie?

[FoxDisc]

Okay. Next step: Now Peter has decrypted the movie using 6 SKs from different players.

You have assumed that each of the SKB's required only one SK. I am fine with this assumption, but I suspect the LA will start off requiring at least two SKs from the same device for at least one of the six SKB decryptions. This will identify that device for revocation.

But these SKs will become "compromised" soon, so the new movie that Peter will buy later can not be decrypted using them.

Agreed. Also, when you say SKs are compromised and Peter can't decrypt, you are saying that the LA has changed the disc. They can revoke devices (and their SK set) when they did this. Did they find out the device/devices the SKs came from previously? If they did, they have revoked devices and all their device and sequence keys. If they are smart, they can identify all 6 devices that provided the original SKs for the 6 SKBs. All their DKs and SKs become useless.

Afortunately, other 6 attackers publish other 6 SKs from different players. Let's say 3 of these SKs are at the "first" column of the corresponding SKB and the other 3 are at the "second" column. To get 6 valid VVUKs for the new movie Peter needs the 6 SKs work right.

For the first 3 SKs Peter finds they are at the "first" column of the first 3 SKBs and he repeats the process we have explained on former messages. No news here.

Agreed so far.

For the other 3 SKs (they are not at "first" column) Peter does as follow:

He tries the first of the compromised SKs (the old SKs) to process the first column of the fourth SKB. This allows him to go to second column (rightly or wrongly), then he uses the fourth of the uncompromised SKs (the new SKs) at second column and he checks if the resulting VVUK is valid. If not, he repeats the process with another old SK or another SKB or another new SK.

Do you agree that Peter will get 6 valid VVUKs for the new movie?

This deserves a long answer, but all I have time for is the short answer: No.

In general, when a first and second column are required for an SKB, the SKs must be from the same set. The first column produces a specific Dv and that Dv gets modified correctly by the second column SK processing only when the first answer was right and the second column was processed by a member of the same set as the first SK. When the set is revoked, they never get the right answer.

[xyz987]

If they are smart, they can identify all 6 devices that provided the original SKs for the 6 SKBs.

I don't understand this. First you agree that attacker player (one SK per player) can not be identified, now you say it can be identified. Could you clarify this?.

Just to clarify: a SK is "compromised" when SKB column sends the player to another column. A SK set is revoked when final output is zero. I have not said that first 6 players have been revoked, I have just said that the published SKs become "compromised" (i.e. these keys send to another column).


This deserves a long answer, but all I have time for is the short answer: No.

In general, when a first and second column are required for an SKB, the SKs must be from the same set. The first column produces a specific Dv and that Dv gets modified correctly by the second column SK processing only when the first answer was right and the second column was processed by a member of the same set as the first SK. When the set is revoked, they never get the right answer.


To answer this i prefer to wait until you clarify the above.

Hint: the Variant Data from the first column is always the same value for every player that must use the second column. Any player that lands on second column decrypts DEADBEEFh before processing second column. Further details as soon as you have clarified the above.

[FoxDisc]

I don't understand this. First you agree that attacker player (one SK per player) can not be identified, now you say it can be identified. Could you clarify this?.

If only one column (and only one SK) is required for an SKB, then attacker can be narrowed to one in 2^16. That is not enough to identify him. If two are required, he can be narrowed to one in 2^32. There are only 2^32 players. We started off assuming the LA would only use one column, since that was the simplest to analyze. If they use two, he can be identified.

Just to clarify: a SK is "compromised" when SKB column sends the player to another column. A SK set is revoked when final output is zero. I have not said that first 6 players have been revoked, I have just said that the published SKs become "compromised" (i.e. these keys send to another column).

I agree with this terminology and understand that the 6 devices were not revoked. Individual devices and sets of SKs are revoked. When a set is revoked, all of its SKs are presumably compromised.

To answer this i prefer to wait until you clarify the above.

Was I clear? One column per SKB is not enough to identify source (original simpler assumption by both of us). Two or more is enough (later assumption by me - you are still talking about one in some spots, so I try to answer based on that assumption).

Hint: the Variant Data from the first column is always the same value for every player that must use the second column.

Yes. After the first column the LA has found the one group out of 65,000 possible groups that the bad boy is in. All we need to know is which member of this group is the bad boy,and which are innocent. The second column divides the first group up again into 65,000 more subgroups.

Any player that lands on second column decrypts DEADBEEFh before processing second column.

Yes. We agree everyone in this smaller group can get the DEADBEEF. But now the bad boy uses his second SK and row number for the second column. Now the LA says AHA! Bad Boy Found! He is the only one in the first group (with SK1) who had this SK2.

The first SK1 was 64 bits long. The second was 64 bits long. The two form a 128 bit number that only the Bad Boy has. Good Boys share the first half of the 128 bit number, but not the second half.

Further details as soon as you have clarified the above.

OK

[ErazorTT]

i've been reading that whole thread with much of interest lately.

now, i feel i have to interfere. i'm not quite sure why you two (Fox, xyz) talk at cross-purposes, at least this is what i think you are just doing.

i'll try to sum up what each of you has written, perhaps that helps you to get back in line.

each of you must agree with every point. if one of you doesn't agree with one point further dicussion is senseless.
so than this would be where you have to come to an agreement, before goning on.

1. only one SK is enough to decrypt one SBK. there may be 6 SK from 6 different players to decrypt an whole film.

2. there are 2^32 players and one SK reveals that the player is one out of 2^16.
so with one published SK he cannot be revoken.

-- 6 SKs from 6 different players are distributed

3. peter takes these published SKs. he will be able to decode the film SHREK1 if the 6 SKs are all from the 1st row.
It actually doesn't matter if he knows the row and/or the column of these SKs or not.
he could try them out if he didn't new the row and/or column.

4. after the SKs are published they are labeld compromised and will be revoked on futere disks
(the SKs are revoked not the players, because LA doesn't know which player to revoke).

--6 new SKs are distributed from 6 different players. these player are not the first 6 player, these are other 6 different players.

5. if these SKs were again entirely from the first row Peter would be able to decrypt the new film SHREK2.

--but, to complecate the situation, the 6 SKs are now not entirely from the first row.

6. will peter be able to decrypt the film SHREK2?

[FoxDisc]

Hint: the Variant Data from the first column is always the same value for every player that must use the second column. Any player that lands on second column decrypts DEADBEEFh before processing second column.

A brief additional comment: The result for the first column is always the same for every player that must use the second column. However, the LA can send some players from the first column to the third column and others to the second column. After the first column is processed, players who need to go farther get a "link" to another column. The link could go to the second column or the third, etc. Different devices with different SK1s can get different links to different columns requiring different SK2s. This gives the Licensing Authority additional options to identify the attacker or revoke key sets.

[FoxDisc]

i've been reading that whole thread with much of interest lately. now, i feel i have to interfere. i'm not quite sure why you two (Fox, xyz) talk at cross-purposes, at least this is what i think you are just doing.

Perhaps you don't see how basic assumptions change as we study it more deeply. This causes early posts to be outdated and later posts to be inconsistent with early assumptions. It takes time to agree on each point.

i'll try to sum up what each of you has written

each of you must agree with every point. if one of you doesn't agree with one point further dicussion is senseless.
so than this would be where you have to come to an agreement, before goning on.

1. only one SK is enough to decrypt one SBK. there may be 6 SK from 6 different players to decrypt an whole film.

This calls for a prediction of what the LA will do. It can't be answered. I think xyz and I agree that one SK is needed per column used in each SKB. If the SKB defines only one column, only one SK is needed. If it defines two, then two are needed. We will know the answer as soon as they release an SKB. I suspect at least one will need two columns. Neither of us can answer what they will do, only what the effect of the two possibilites will be.

2. there are 2^32 players and one SK reveals that the player is one out of 2^16.

Agreed

so with one published SK he cannot be revoken.

I technically disagree, but agree in practice. Technically, all devices with an SK can be revoked. Practically, that might require revoking innocents (we don't know how many players have that key or what the LA knows about the members of the group.) Most likely, the published SK would just be considered to be "compromised" and the LA would look for more info if that was all the info they had. We don't know if a single published SK would be of any value (I suspect not), so the situation may not arise.

-- 6 SKs from 6 different players are distributed

We don't know if this is of any value - do you want to talk about it or not? It is sometimes useful to talk about it to agree what would happen if .... even when we don't think it will happen or we don't think it will be useful.

3. peter takes these published SKs. he will be able to decode the film SHREK1 if the 6 SKs are all from the 1st row.
It actually doesn't matter if he knows the row and/or the column of these SKs or not.
he could try them out if he didn't new the row and/or column.

You are doing pretty good, but I don't think you meant "all from the 1st row." Rows and columns are in the master matrix. Each SKB defines a column from the master matrix. Every device has one SK in that column, but they are usually on different rows. I don't see how you would get the SKs from the first row. If they were from the first row, you would know the row. I think you should be asking for agreement on whether a specific SK for a specific column defined in an SKB uniquely identifies the row. The answer to that is yes. (It probably uniquely identifies the column too.) The LA knows the row, the device disclosing it knows the row, so it's not a secret. If you don't understand why that is the question you should ask - ask.

4. after the SKs are published they are labeld compromised and will be revoked on futere disks
(the SKs are revoked not the players, because LA doesn't know which player to revoke).

You are deep into an assumption I think is probably not valid (one SK per SKB), and you are asking for a prediction about what the LA will do. I agree that published SKs will be considered compromised. We don't know how many devices actually share SKs. If PDVD has SK1 and WDVD has SK2, but not SK1, and SK1 and SK2 have not been assigned to any other device, then the release of SK1 means it came from PDVD.

--6 new SKs are distributed from 6 different players. these player are not the first 6 player, these are other 6 different players.

5. if these SKs were again entirely from the first row Peter would be able to decrypt the new film SHREK2.

--but, to complecate the situation, the 6 SKs are now not entirely from the first row.

Again with the "first row." You will have to clarify. If you want to be very clear, make sure you distinguish between the column of the LA's SK master matrix and the column of the SKB that specifies the column in the master matrix. Sometimes in this thread the column specified by the SKB is called the "first column" It is officially the "Unconditional Column." All other columns in the SKB are "Conditional" columns (sometimes called the "second column" here) and they also point to a column in the master matrix. A device checks the unconditional column in the SKB, reads the specified column for the master matrix, and get his single SK and row number for that column. Every device gets one and only one SK from each column of the master matrix. The device will need the SK, the row and the column to work through the first column of the SKB. If the SKB sends him to another column, he'll need that info again for the next specified column of the master matrix, etc.

6. will peter be able to decrypt the film SHREK2?

Not if he's a bad boy and the LA has his number. :)

[FoxDisc]

This thread is deep into details of the SKB traitor tracing system. I'm going to step away from the details a bit to remind us of what is under discussion in this thread.

1) The beginning of this thread covers the Subset Difference System, Device Keys, Subsidiary Device Keys, MKBs, Processing Keys, etc. It describes how the main keys are distributed, controlled and revoked for the majority of the movie. It is based on a binary tree of 32 levels, with 2^32 players at the bottom. The AACS LA has one secret random number at every node of that tree (or a way to calculate a pseudorandom number). This system alone was relied on to encrypt all discs and it has been shown to be insufficient.

2) Sequence Keys are under discussion now. They are used to get the keys needed to decrypt 32 short segments of the movie. They are used to find the device at the bottom of the tree above that is the "traitor." Once found, he can be revoked from both parts of the system (Sequence Keys and Device Keys) SKs come from a master matrix possessed by the LA that has 256 columns and 2^16 rows. Each cell in the matrix has a 64 bit SK. It is to the SK system like the Master Tree referred to above is to the DK system. Sequence Keys are not yet in use. There are actually two parts of this SK system under simultaneous discussion - Anonymous attack and Non-anonymous:

2A) Non-anonymous is getting the most discussion here. This may be confusing, as a lot of the discussion is about trying to remain anonymous in the non-anonymous attack. Non-anonymous means that someone releases Sequence Keys allowing one to decrypt the segment keys needed to decrypt the 32 missing segments of the movie. Sequence Keys are like Device Keys, they are shared, but they tell something about where they came from.

2B) Anonymous. This refers to releasing the segment keys after decryption by the Sequence Keys (or the actual decrypted segments of the movie). There are 192 segment keys per movie (6 SKBs times 32 segments). Only 32 are needed, but having a specific 32 tells the LA something about where they came from. Again this may be confusing, because the purpose of the SK system is to identify an attacker making an anonymous attack. There has been very little discussion of this type of attack here, but after the non-anonymous scenario is fully understood, focus may shift again to the anonymous scenario.

[ErazorTT]

We don't know if this is of any value - do you want to talk about it or not? It is sometimes useful to talk about it to agree what would happen if .... even when we don't think it will happen or we don't think it will be useful.

Ok let's say they want two SK for an SKB. Wouldn't it be possible to feed the SKB with two SK's from different players?

You are doing pretty good, but I don't think you meant "all from the 1st row." Rows and columns are in the master matrix. Each SKB defines a column from the master matrix. Every device has one SK in that column, but they are usually on different rows. I don't see how you would get the SKs from the first row. If they were from the first row, you would know the row. I think you should be asking for agreement on whether a specific SK for a specific column defined in an SKB uniquely identifies the row. The answer to that is yes. (It probably uniquely identifies the column too.) The LA knows the row, the device disclosing it knows the row, so it's not a secret. If you don't understand why that is the question you should ask - ask.

I meant columns in the SKB.

You are deep into an assumption I think is probably not valid (one SK per SKB), and you are asking for a prediction about what the LA will do. I agree that published SKs will be considered compromised. We don't know how many devices actually share SKs. If PDVD has SK1 and WDVD has SK2, but not SK1, and SK1 and SK2 have not been assigned to any other device, then the release of SK1 means it came from PDVD.

there are 2^8*2^16=16mio different SK. there can be 2^32 players. it could be actually possible to give the first 16mio player an idividual SK, that's true. this would mean that a single SK is enough to revoke a player. as long they don't sell many players they can have very few player to share SK's. but for later there are clearly too few SK's.

Again with the "first row." You will have to clarify. If you want to be very clear, make sure you distinguish between the column of the LA's SK master matrix and the column of the SKB that specifies the column in the master matrix. Sometimes in this thread the column specified by the SKB is called the "first column" It is officially the "Unconditional Column." All other columns in the SKB are "Conditional" columns (sometimes called the "second column" here) and they also point to a column in the master matrix. A device checks the unconditional column in the SKB, reads the specified column for the master matrix, and get his single SK and row number for that column. Every device gets one and only one SK from each column of the master matrix. The device will need the SK, the row and the column to work through the first column of the SKB. If the SKB sends him to another column, he'll need that info again for the next specified column of the master matrix, etc.

Just for beeing sure i understood the SK-system the right way:
There is this master matrix of SK's. it has 256 columns and 64K rows. each player gets one SK from each column.
The SKB asks for (Ok let's say) two SK's. it can define from which colums (one of those 256) these SK'S have to come from, so it defines the unconditional column. if it gets a revoked SK it will ask for an other SK (with the deadbeef thing), now we're in the conditional column(s). If it the SKs are all revoken than the player is revoken. Is this right? am i useing terminology right?

[xyz987]

i'll try to sum up what each of you has written, perhaps that helps you to get back in line.

each of you must agree with every point. if one of you doesn't agree with one point further dicussion is senseless.
so than this would be where you have to come to an agreement, before goning on.

1. only one SK is enough to decrypt one SBK. there may be 6 SK from 6 different players to decrypt an whole film.

2. there are 2^32 players and one SK reveals that the player is one out of 2^16.
so with one published SK he cannot be revoken.

-- 6 SKs from 6 different players are distributed

3. peter takes these published SKs. he will be able to decode the film SHREK1 if the 6 SKs are all from the 1st row.
It actually doesn't matter if he knows the row and/or the column of these SKs or not.
he could try them out if he didn't new the row and/or column.

4. after the SKs are published they are labeld compromised and will be revoked on futere disks
(the SKs are revoked not the players, because LA doesn't know which player to revoke).

--6 new SKs are distributed from 6 different players. these player are not the first 6 player, these are other 6 different players.

5. if these SKs were again entirely from the first row Peter would be able to decrypt the new film SHREK2.

--but, to complecate the situation, the 6 SKs are now not entirely from the first row.


Agreed. You have summarized it far well.

Just a clarification: Peter doesn't need to try all columns, because the column number that must be used is at SKB.


6. will peter be able to decrypt the film SHREK2?


My answer is yes. 3 SKBs are using the second column. On this SKBs the first column outputs a link to the second column when one of the previously compromised SKs is used. Peter has these SKs (and decrypted Shrek 1 with them), so Peter can go to the second column, and the newly published SKs will give him the decrypted movie.

[FoxDisc]

Ok let's say they want two SK for an SKB. Wouldn't it be possible to feed the SKB with two SK's from different players?

Short answer: No. The first SK1 sends you to one of the Conditional Columns. The second SK2 only works in that column. Only one out 2^32 players has both SK1 and SK2. There are only 2^32 players.

there are 2^8*2^16=16mio different SK. there can be 2^32 players. it could be actually possible to give the first 16mio player an idividual SK, that's true.

Each player gets one and only only one from each column of the master matrix.

this would mean that a single SK is enough to revoke a player. as long they don't sell many players they can have very few player to share SK's. but for later there are clearly too few SK's.

Yes. They can start with unique SKs and then use them as they get more players. Who knows how they did it.

Just for beeing sure i understood the SK-system the right way:
There is this master matrix of SK's. it has 256 columns and 64K rows. each player gets one SK from each column.
The SKB asks for (Ok let's say) two SK's. it can define from which colums (one of those 256) these SK'S have to come from, so it defines the unconditional column. if it gets an revoked SK it will ask for an other SK, conditional column. Is this right? am i useing terminology right?

Yes. You are using terminology right. The unconditional column of the SKB specifies one column of the master matrix. The device will have an SK and a row number for that column of the master matrix. If that SK is "compromised", the calculation produces a link to another column in the SKB (a conditional column) The link can be to any one of the conditional columns. The new column in the SKB specifies another column in the master matrix. Again, the device looks up the SK and matching row number for the specified column of the master matrix.

[ErazorTT]

Short answer: No. The first SK1 sends you to one of the Conditional Columns. The second SK2 only works in that column. Only one out 2^32 players has both SK1 and SK2. There are only 2^32 players.

My answer is yes. 3 SKBs are using the second column. On this SKBs the first column outputs a link to the second column when one of the previously compromised SKs is used. Peter has these SKs (and decrypted Shrek 1 with them), so Peter can go to the second column, and the newly published SKs will give him the decrypted movie.

i know you haven't answered to the same question but it is almost the same.
at least if oue is right the other must be wrong and the other way round.

so here is the point where you two have to find an agreement. don't feel that i have read enough of the specs that i can say anything of who could be right.

[xyz987]

If only one column (and only one SK) is required for an SKB, then attacker can be narrowed to one in 2^16. That is not enough to identify him. If two are required, he can be narrowed to one in 2^32. There are only 2^32 players. We started off assuming the LA would only use one column, since that was the simplest to analyze. If they use two, he can be identified.


Well, we are just now talking about using 2 columns, right?


Yes. After the first column the LA has found the one group out of 65,000 possible groups that the bad boy is in. All we need to know is which member of this group is the bad boy,and which are innocent. The second column divides the first group up again into 65,000 more subgroups.

[...]

Yes. We agree everyone in this smaller group can get the DEADBEEF. But now the bad boy uses his second SK and row number for the second column. Now the LA says AHA! Bad Boy Found! He is the only one in the first group (with SK1) who had this SK2.


Who is "bad boy"?. The guy that published SK1 or the guy that published SK2?. It is perfectly possible the guy that publishes SK2 has not SK1 in his player.

Take a view at figure 4-1 of prerecorded spec (page 22). At column 2, players with different SKs (rows 3 and 5) go to column 3.

SK1 and SK2 are not related at all because they are from different players. For SK1 there are just 2 possibilities:

1- SK1 is not "compromised" at that SKB. So SK1 is enought to decrypt the movie.

2- SK1 is "compromised" at that SKB. So SK1 (and may be other SKs) outputs a link to the second column.

SK2 is from other player, so there are 2 possibilities:

A - SK2 is at first column (a lot of players have an uncompromised SK for first column) so SK2 decrypts the movie.

B - SK2 is at second column. So Peter uses SK1 to go to second column, and uses SK2 to decrypt the movie.

Edit:

If just one row of first column has the link to second column the probabilities for second attacker are:

Almost 100% his player just uses first column (this is the probability of A).

Near 0% (1/65536) his player goes to second column (this is the probability of B).

Also, if just one row of first column has NOT the link to second column the probabilities for second attacker are:

Near 0% (1/65536) his player just uses first column (this is the probability of A).

Almost 100% his player goes to second column (this is the probability of B). In this case almost 100% of the players go to second column. LA can not get information from here.

When i wrote about decrypting Shrek2 i have been using a probability of 50% (half the rows have a link). Of course LA can choose any other probability, but this is a win-win game for second attacker. No matter which probability LA chooses, the player of second attacker can not be identified.

If you disagree, just say me how many rows at first column have a link.

@FoxDisc: I have edited this post several times.

[xyz987]

A brief additional comment: The result for the first column is always the same for every player that must use the second column. However, the LA can send some players from the first column to the third column and others to the second column. After the first column is processed, players who need to go farther get a "link" to another column. The link could go to the second column or the third, etc. Different devices with different SK1s can get different links to different columns requiring different SK2s. This gives the Licensing Authority additional options to identify the attacker or revoke key sets.

Another terminology problem. I am using "SK1" to refer the SK that has been published by first attacker, but you are using it with a different meaning (any SK that is at first column).

[FoxDisc]

so here is the point where you two have to find an agreement.

Yes. This is what we have been discussing. I'm not sure why you think we are not discussing it.

[arnezami]

there are 2^8*2^16=16mio different SK. there can be 2^32 players. it could be actually possible to give the first 16mio player an idividual SK, that's true. this would mean that a single SK is enough to revoke a player. as long they don't sell many players they can have very few player to share SK's. but for later there are clearly too few SK's.
Haven't got much time to discuss (busy programming ;)). But just a few things:

1) Giving the first 16 million devices a unique SK (and using only those in the SKBs) is not going to work (for them): the size of the SKBs would become too large. This limitation has not really been discussed yet. In fact they may choose to try to keep SKBs as small as possible. In any way its likely many/all players will have at least some keys in common with any other player. It is therefore unlikely that releasing only one (or just a few) Sequence Key(s) per device will reveal its identity (asuming many devices have been sold).

2) Since a Link Key can be verified (by the deadbeef check) it has to be the same for every device that uses that column in the SKB. In other words: a Sequence Key (first column) from device A that will result in a Link Key (for say column 5) can be used in combination with a Sequence Key (for column 5) from device B that also uses this column 5 in the SKB. This directly affects the possibility of using Sequence Keys from different devices. Given this example though: it might be true that the identity of device B is revealed this way. So the owner of B should only reveal this Sequence Key if it knows that this exact Key is also used by different devices. Whether this is always the case highly depends on what I mentioned in my first point above.

3) When looking at the following picture it shows the paths followed by different devices while processing a SKB. I have a gut feeling these paths will be exactly the same for every disc/movie that have the same SKB "version":

http://img138.imageshack.us/img138/3659/seqop7.png

This would be very similar to their use of the same MKB version: they use the same Explicit Subset-Difference Record (and thus Processing Key) for every disc/movie but their C-values are different. This I think will also be the case with SKBs: the values of the keys will be different but the arrows/paths taken by devices might very well be the same on every disc (using this same SKB "version"). This is just a feeling though. It would mean that only if things are revoked (new "version") will the structure/paths of this picture change (working with the above example: arrows will change or be added and more K's will become 0's). If this is true though (and combine this idea with my second point here) that could lead to some interesting things... :)

What is also interesting is the question: will all, some or none of these K's in this picture be the same? In other words: will a resulting Dv be different for every device? How many different Dv's can (at most) come out of one SKB (assuming you have all Sequence Keys from all devices) considering that all these devices should still be able to decrypt all movies (all segments)? What is the limitation of different Dv's here? 1024?

Just something to discuss.

Regards,

arnezami

[xyz987]

Since a Link Key can be verified (by the deadbeef check) it has to be the same for every device that uses that column in the SKB. In other words: a Sequence Key (first column) from device A that will result in a Link Key (for say column 5) can be used in combination with a Sequence Key (for column 5) from device B that also uses this column 5 in the SKB. This directly affects the possibility of using Sequence Keys from different devices. Given this example though: it might be true that the identity of device B is revealed this way. So the owner of B should only reveal this Sequence Key if it knows that this exact Key is also used by different devices. Whether this is always the case highly depends on what I mentioned in my first point above.


No, identity of B is not revealed. All the players have a SK at column 5. To understand this, read the below example:

Let's say LA is using a matrix that has 2 columns and 2 rows, so there are 4 SKs. SK1 is at first row of first column, SK2 is at second row of first column, and so on.

Key distribution is as follows:

25% of the players (group 1) have SK1 and SK3
25% of the players (group 2) have SK1 and SK4
25% of the players (group 3) have SK2 and SK3
25% of the players (group 4) have SK2 and SK4

Traitors tracing works as follows:

Let's say LA release a new SKB. SK1 ouputs a link to the second column. SK2 decrypts the movie. Also SK3 and SK4 decrypt the movie, but at second column.

When a player decrypts the movie:

50% of the players will use SK2 to decrypt it
25% of the players will use SK3 to decrypt it and all these players have SK1
25% of the players will use SK4 to decrypt it and all these players have SK1

Using more columns LA can determine the identity of any player, because each additional column reduces the probabilities if the SKs used to decrypt are from the same player.

However if attackers publish just one SK from different players (one SK per player), LA can not reduce the probabilities from column to column.

If attacker A publishes SK1 the movie is decrypted and his identity is not revealed because 50% of all players has this key. Nothing new here but this is just a reference case (just one column have been used to decrypt). I put this case here just for illustrative purposes (LA can force all the players to go to other columns).

If attacker A publishes SK2 (yes, SK2), and attacker B publishes SK4 the movie is decrypted too. Of course LA knows that the player of attacker A is a member of groups 3 or 4 (50% of all players, no news here). Now the funny thing: LA just knows that the player of attacker B is a member of groups 2 or 4 (50% of all players). LA is not getting new information from attacker B, it is not getting aditional information from the fact that 2 columns are used to decrypt if SKs are from different players.

If 2 columns are used to decrypt then a link to the second column is needed, but this link is the same for everybody, it always decrypt DEADBEEF. Peter just needs SK2 (to get the link) and SK4 (to decrypt).

[ErazorTT]

Short answer: No. The first SK1 sends you to one of the Conditional Columns. The second SK2 only works in that column. Only one out 2^32 players has both SK1 and SK2. There are only 2^32 players.

Ok i don't get that.
let's say the unconditional SK (SK1) was rejected.
then SKB wants to have one conditional SK (SK2) form a specific column.
why can't this SK (SK2) be from another player than SK1. SK2 beeing from the right colum obviously.

i mean SKB just wants one SK from the right conditional column.
how could SKB know these SK are from different columns?

[FoxDisc]

@FoxDisc: I have edited this post several times.

I am not ignoring you. I started a long reply post, was busy, did some more work on it, got busy again. Now I see you've changed some things. I haven't even had time to read the edits yet, so that will take some time, and I think arnezami has some good points too. At least we are all on the same path - working through what hapens when the SKB is processed column by column.

Think about this question, previously mentioned in this thread, as you think about arnezami's comments.

Suppose the LA began to assign their "sets of SKs" by giving the first device the first SK in every row, and the second device the first SK in every row except the last column (#256) where they assigned the SK from row 2. The third gets the same, except the SK in the third row for the last column. The first 2^16 devices get the same SK (from first row) in the first 155 columns and a different one in the last column only. Then the 2^16 plus one device gets the first SK in every row except the 255th column. He gets the SK from row one in column 256, the 2^16 plus 2 device increments the SK in the last column jsut like the second device did. He gets the second row SK in column 256.

If you proceed this way, every device will get a "unique set of SKs" and yet we are done assigning Devices SKs when we fill the last two cloumns. Everyone got the same SK in the first 254 rows!

The point is that there are only 2^32 devices, yet there are 2^4096 different "unique set of SKs" from the master matrix.

The method described above made the sets of SKs as similar as possible. I don't think they assigned device multiple identical SKs, even though they could. I think they assigned them set of SKs that are as different as possible, not as similar as possible or something in between those limits. I think they made the sets as differnt as possible so that they could identify the device as easily as possible knowing as few as possible of their SKs.

The question is: What happens if a device having a set of SKs that was not actually assigned by the LA tries to process an SKB by following the table (I see that arnezami has posted it for our convenience)? This is key to understanding your idea of mixing SKs from two different devices to hide where the SKs came from. A mixed set of SKs is likely to be one of the 2^4096 possible sets that was never actually assigned to any device.

A related question is: How did the LA assign SKs to devices? More specifically, If device A has an SK and device B has the same SK, do they share any other SKs?

Sorry - even my short post is long, and all I did was point out some key questions.

(BTW, do you agree that every 64 bit SK in every one of the 2^24 cells is probably a unique number so that knowing the SK's 64 bit value uniquely identifies its row and column.)

[xyz987]

The question is: What happens if a device having a set of SKs that was not actually assigned by the LA tries to process an SKB by following the table (I see that arnezami has posted it for our convenience)? This is key to understanding your idea of mixing SKs from two different devices to hide where the SKs came from. A mixed set of SKs is likely to be one of the 2^4096 possible sets that was never actually assigned to any device.


No matter how they do it, the worst case is that Peter just needs a link to go to second column and a SK at second column to decrypt. This link is always the same value for second column of that SKB. If 3 columns are required, Peter will need a link to go to second column and a link to go from second column to third (this is the worst case again because may be some players decrypt at first or second columns and may be the first or second published SKs are from one of these players). Of course if 3 columns are required a third attacker will publish a third SK (just one SK per player).

Any SK from an unrevoked player will output either a link to next column or the final Variant Data. There are no more posibilities.


A related question is: How did the LA assign SKs to devices? More specifically, If device A has an SK and device B has the same SK, do they share any other SKs?


Randomly. It would be a Bad Idea to assign SKs other way.


(BTW, do you agree that every 64 bit SK in every one of the 2^24 cells is probably a unique number so that knowing the SK's 64 bit value uniquely identifies its row and column.)

Yes, I agree. In fact, SKB system wouldn't work if different SKs are asigned to same cell.

[FoxDisc]

No, identity of B is not revealed. All the players have a SK at column 5.

I've been looking for a good place to pick up this thread again, to explain why mixing SKs from different players is not going to work and how the tracing works. I chose here. I think arnezami's post is the most interesting, but I'll try to stick to this discussion first and emphasize why he's right on the point you are disagreeing with here. For reference, we need his image:

http://img138.imageshack.us/img138/3659/seqop7.png

You say: "All the players have a SK at column 5." That's true. Let's be clear on why you are saying that. A first player A has looked at column 1 in the SKB. He has a compromised SK for that column, so instead of getting a key K, he decrypts a link to column 5. OK, now we know that if this device is revoked, when he goes to column 5, he'll decrypt a zero in that column.

If he's not revoked, he'll decrypt the key K from column 5. He could disclose his second uncompromised SK for column 5, but that requires disclosing two SKs from the same set of SKs. The more keys he discloses the more the LA knows about him. Every device has a unique set of SKs and as the specs say: "The fundamental principle is that no two devices have many [sequence] keys in common."

The attacker wants to keep secret his SKs. Of course, the LA knows that is exactly what he wants to do. As they put it:

"Attackers would prefer to use already-compromised Sequence Keys if they could, so that no new forensic information could be deduced by the licensing agency. Therefore, it is important that compromised keys are no longer usable by the attackers. The problem is that many thousands of devices might share a single compromised key."

Anyway, back to your comment which is: "All the players have a SK at column 5." I believe you are saying this because you are not going to use player A's sequence key for column 5 (which will work to decrypt a valid key K) but instead, you are going to use someone else's SK from column 5. The problem is that when you look at column 5, you get a list of keys encrypted with SKs. You need one of the SKs that the LA actually used to encrypt the answer K in that column so you can decrypt it. However, they didn't use everyone's SK from column 5. They only used SK's from people who had the same SK in column 1 that player A had. If you have an SK in column 5 that can decrypt a key K in column 5, then you also had the same key that player A had in column 1.

Perhaps you are lucky, and player B disclosed a key for column 5 that works. Then player B and player A both had the same key in column 1. It's true that player A remains anonymous, but so what? He didn't give out enough information to decrypt anything. Player B gave out enough info to decrypt, but he's no longer anonymous and will be revoked.

Now, you can say this: There are only 2^16 keys in column 5. Everyone of 2^32 players gets a key in column 5, so 2^16 players (or more) share a key in this column. I'll just get one from someone who did not have player A's key in column 1. But is there any such player? The answer is no. More specifically, if their key in column 5 was used to encrypt the answer K, then they had the same key in column 1. Everyone has a key in column 5, but not everyone needs to go to column 5, and not every SK from column 5 will decrypt an answer K. Although we don't know exactly what they did with SK key assignment, we know what they wanted to do. Unless they made a serious stupidity mistake, they only encrypted with SKs from column 5 if that SK in column 5 was assigned to a player that had the SK in column 1 that sent them to column 5 via the link in column 1.

To understand this, read the below example:

Let's say LA is using a matrix that has 2 columns and 2 rows, so there are 4 SKs. SK1 is at first row of first column, SK2 is at second row of first column, and so on.

Key distribution is as follows:

25% of the players (group 1) have SK1 and SK3
25% of the players (group 2) have SK1 and SK4
25% of the players (group 3) have SK2 and SK3
25% of the players (group 4) have SK2 and SK4
Traitors tracing works as follows:
Let's say LA release a new SKB. SK1 ouputs a link to the second column. SK2 decrypts the movie. Also SK3 and SK4 decrypt the movie, but at second column.


Your error is here. They will not assign SK4 to group 4 if SK1 is needed to get to the second column and SK2 is not. You have assigned every possible combination of SKs to a player. You have too many shared keys in common. As you can see from the spec portion quoted above, the LA knows not to do that. In the real world, there are 2^4096 unique sets of SKs and only 2^32 players who get a set. Those who have the second key will also have the first one. That set is needed to decrypt, and it identifies the player.

Sorry about the delay in responding.

[FoxDisc]

let's say the unconditional SK (SK1) was rejected.
then SKB wants to have one conditional SK (SK2) form a specific column.
why can't this SK (SK2) be from another player than SK1.

SK2 can be from another player (call him "X"), but for it to be of any value, the LA must have encrypted the answer key K in the conditional column with the SK2 from player X. The only reason a player would be decrypting something in the conditional column is if it was sent there by the unconditional column. Why would the LA put the answer K there for an unauthorized player to decrypt?

[FoxDisc]

Haven't got much time to discuss (busy programming ;)). But just a few things:

1) Giving the first 16 million devices a unique SK (and using only those in the SKBs) is not going to work (for them): the size of the SKBs would become too large. This limitation has not really been discussed yet. In fact they may choose to try to keep SKBs as small as possible. In any way its likely many/all players will have at least some keys in common with any other player. It is therefore unlikely that releasing only one (or just a few) Sequence Key(s) per device will reveal its identity (asuming many devices have been sold).

I haven't got enough time to discuss all of these now, so I'll tackle the interesting bits as time permits. The specs make it clear that it is advantageous for the LA to minimize the overlap of assigned SKs. The fewer in common, the easier it is to identify a player. We don't have any information yet about how they have actually assigned SKs, but it wouldn't surprise me if the 16 million unique keys in the entire master matrix are assigned very early. That minimizes overlap of commonly assigned keys which is exactly what they want to do.

In contrast, attackers want to disclose only commonly assigned SKs to prevent identification. I think we'll have to wait to see the first SKBs to understand how they intend to implement the tracing system. I agree that there are limits imposed by the size of the SKB.

As we know, they did a poor job with the initial implementation of the MKB system. Only one Processing Key was used. I doubt we'd have guessed that just by reading the specs.

[arnezami]

On a sidenote: I think I have devised a (cryptographically sound) way for several people who have found sequence keys to see if they have any sequence keys in common without releasing the sequence keys themselves :). Its pretty complicated and mainly uses some XOR techniques (and some private/public key pairs for each participant). But it could in principle be done on a forum or a specially designed website.

Anyway. Its not very practical yet and not very efficient. So I'm still trying to make it better. But since this is not needed yet I can take my time. But I think its a good idea to think about this stuff sooner than later. The more people we can get involved the better when it comes to finding and releasing common SKs (if/when we can't use Software Players for retrieving SKs anymore that is). If we can create a system that does it safely for people more will consider and do it.

Regards,

arnezami

PS. It has some similarities with the techniques used for herbivore (http://www.cs.cornell.edu/People/egs/herbivore/how_it_works.html) (but its different because herbivore focuses on privacy while we want to compare notes without actually releasing the notes). Which is hard btw ;).

[FoxDisc]

On a sidenote: I think I have devised a (cryptographically sound) way for several people who have found sequence keys to see if they have any sequence keys in common without releasing the sequence keys themselves :).

I don't think I'd call it a "sidenote." As I was writing one of those posts about how the attacker wants to use only shared keys and the LA wants to reduce the number of shared keys I was thinking how hard it would be to find out how many keys were "shared" without disclosing/compromising them. As usual, it looks like you are thinking way ahead.

[arnezami]

I don't think I'd call it a "sidenote." As I was writing one of those posts about how the attacker wants to use only shared keys and the LA wants to reduce the number of shared keys I was thinking how hard it would be to find out how many keys were "shared" without disclosing/compromising them. As usual, it looks like you are thinking way ahead.

:D :D :D :D

[xyz987]

Anyway, back to your comment which is: "All the players have a SK at column 5." I believe you are saying this because you are not going to use player A's sequence key for column 5 (which will work to decrypt a valid key K) but instead, you are going to use someone else's SK from column 5. The problem is that when you look at column 5, you get a list of keys encrypted with SKs. You need one of the SKs that the LA actually used to encrypt the answer K in that column so you can decrypt it. However, they didn't use everyone's SK from column 5. They only used SK's from people who had the same SK in column 1 that player A had. If you have an SK in column 5 that can decrypt a key K in column 5, then you also had the same key that player A had in column 1.


You simply don't understand how SKB works. However there is an easy solution:

Let's say attacker A has published a SK that is at 12,543th row of 123th column (let's say 123th column was "first" column at Shrek1 SKB).

Now you are LA, and you are designing the SKB of Shrek2. Please say me how is your SKB, and i will say you how it sinks when second attacker publishes his SK. Of course, you must specify all the data of a real SKB. For short you can start saying just some basic data, but if i ask you, you must say me any data that anybody can read on a SKB.

Of course, you know nothing about attacker B. He has not published any SK yet.

Of course, your SKB must allow any player to decrypt. You can choose any SK distribution on players, but there are more that 32 millions of them. There is just one SK per matrix cell (we agreed on it before) i.e. all the players that have a SK at row r of column c will have the same SK.

Let's start the game...

[FoxDisc]

You simply don't understand how SKB works.

It would help if you would explain more.

attacker A has published a SK that is at 12,543th row of 123th column (let's say 123th column was "first" column at Shrek1 SKB).

Odd choice.

Now you are LA, and you are designing the SKB of Shrek2. Please say me how is your SKB, and i will say you how it sinks when second attacker publishes his SK. Of course, you must specify all the data of a real SKB. For short you can start saying just some basic data, but if i ask you, you must say me any data that anybody can read on a SKB.
Of course, you know nothing about attacker B. He has not published any SK yet.
Of course, your SKB must allow any player to decrypt. You can choose any SK distribution on players, but there are more that 32 millions of them. There is just one SK per matrix cell (we agreed on it before) i.e. all the players that have a SK at row r of column c will have the same SK.

Let's start the game...

SK 12,543th row of 123th column is compromised. This one SK was not sufficient to decrypt Shrek1. Attacker A can decrypt with his other secret SKs, but no one else can. Recommend no change for 6 SKBs on Shrek2. Wait for more info on attacker A.

[xyz987]

SK 12,543th row of 123th column is compromised. This one SK was not sufficient to decrypt Shrek1. Attacker A can decrypt with his other secret SKs, but no one else can. Recommend no change for 6 SKBs on Shrek2. Wait for more info on attacker A.

You are changing the case. Shrek1 was decrypted because there was just one column at Shrek1 SKB. Well, no problem. Let's play with Shrek1 SKB.

How many columns are at Shrek1 SKB?. How many rows at each column?.

You say that SK of attacker A is not enought to decrypt. This implies that all the players get at first column a link to another column. Do you agree?.

Everybody knows the published SK, so everybody can know which column this SK outputs a link to. Which is this column at Shrek1 SKB? (second, third...). Which is its column number? (a link to this column can decrypt the column number that is stored on SKB). Note i am asking two different things.

[ErazorTT]

SK2 can be from another player (call him "X"), but for it to be of any value, the LA must have encrypted the answer key K in the conditional column with the SK2 from player X. The only reason a player would be decrypting something in the conditional column is if it was sent there by the unconditional column. Why would the LA put the answer K there for an unauthorized player to decrypt?

1. they don't know which player is unauthorized! if they had known the player would have been revoken by MKB!

2. so you say the link key can be used only with one specific SK form the column? could you please say why you think that, and where it is written in specs?
by the way, i don't see how LA could do this, technically.

3. for safty reasons i think i'd better explain how i interprete the picture of page 22 of prerecorded (the picture we have in this threat):
"The first column will have an encryption of the output key (denoted ‘K’ in the figure) in every uncompromised Sequence Key’s cell"
AND
"The subsequent additional conditional columns are produced the same way as the first column: They will have an encryption of the output key in every uncompromised Sequence Key’s cell."
what i understand by that: In each column (of the SKB) there is an "answer" for every SK of one column (from the master matrix). the answer can be either the output key (K) or the link key (link).

So how does it work:
"Devices that do not have compromised keys in that [unconditional] column immediately decrypt the output key."
This answeres one question from xyz's last post!

"Devices with a compromised key will get a further link key to another column instead of the output key."
AND
"If the header decrypts correctly, the device knows it has a link key and processes the column. If it does not decrypt correctly, the device knows it has either the output key or a link key for a different column."
they don't say anything about SK's in right columns which are however wrong!

so i think every (not compromised) SK from the right column can decrypt the output key.
if you don't agree please explain by refering to specs.

[FoxDisc]

You are changing the case. Shrek1 was decrypted because there was just one column at Shrek1 SKB.
You didn't say that and I thought I had made it clear that I think every device will have to use at least two SKs.

Well, no problem. Let's play with Shrek1 SKB.
How many columns are at Shrek1 SKB?. How many rows at each column?.

Ten columns in each of six SKBs and up to 2^16 rows.

You say that SK of attacker A is not enought to decrypt. This implies that all the players get at first column a link to another column. Do you agree?.

You are attacker A. You know only what attacker A knows. Attacker A knows that his compromised SK leads through five columns of first SKB. He does not know what other players ("all players") will get at first column of first SKB (perhaps link to same column, perhaps link to another column, perhaps key K). Attacker A also knows about other 5 SKBs. What information will you release?

Everybody knows the published SK, so everybody can know which column this SK outputs a link to.
Agreed
Which is this column at Shrek1 SKB? (second, third...).
second
Which is its column number?
124 (adjacent to right of your choice of 123)

[FoxDisc]

1. they don't know which player is unauthorized! if they had known the player would have been revoken by MKB!

I didn't say they knew the player. I said they assigned keys to minimize common shared keys.

2. so you say the link key can be used only with one specific SK form the column?

No, I did not say that. I said that when the LA gave devices an SK for the first column that decrypted the link to the second column, they made sure that they gave keys for the second column too that were not given to any (very few) other devices.

they don't say anything about SK's in right columns which are however wrong!
so i think every (not compromised) SK from the right column can decrypt the output key.
if you don't agree please explain by refering to specs.

Look at the table. Some devices will decrypt zero in the second column. When the system started, the LA assigned some devices an SK for the first column that leads via a link to a second column. What did they assign in the second column to those devices? They were not obligated to use every possible one of the 65,536 SKs in the second column. They did not. Perhaps they assigned only a handful of those 65,536 possible rows/SKs. Many possible rows/SKs were never assigned to any of these devices. What would you decrypt in the second column with an SK from the second column that was never assigned to a device that has the correct SK in the first column?

Remember, there are 2^4096 unique sets of SKs and only 2^32-512 devices. The LA knows which of the 2^4096 sets are valid and which are not valid. Broadly speaking, the question above is all about what happens when you try to decrypt with an invalid set of SKs. If they had used only 2 columns instead of 256, they could have issued 2^32 unique sets of SKs. Why do you think they used 256 columns? It's because the 2 column scenario uses too many shared keys. Every combination is valid for someone, so even though it's unique, you can't be sure if the keys were from the same attacker or from two attackers who shared their keys to look like an innocent user. You and xyz keep looking at the shared key situation and are not focusing on the fact that most combinations are not valid, were never issued, are known by the LA to be invalid and won't decrypt the title.

[FoxDisc]

@Erazor and xyz

Perhaps we can agree on some basics. Look at the graphic:
http://img138.imageshack.us/img138/3659/seqop7.png

Can we agree on what is required to decrypt column 4 and get a valid answer key K in that column? Tell me what minimum information you think is needed for just that one column.

[FoxDisc]

It is amazing what you find on the web. We have been wandering in the dark on sequence keys as we don't know how they are assigned and we've never seen an actual SKB.

Try this link:
http://domino.watson.ibm.com/library/CyberDig.nsf/papers/7158161AA398C8CE8525722200570F64/$File/rj10394.pdf

It describes limitations of the SKB tracing system, anonymous colluding attacks and non-anonymous attacks (the literature calls them "clone decoder attacks"). It's apparently written by those who designed the AACS SK system. Part of it is word for word identical to the AACS spec description of the SK system. Fascinating reading.

[arnezami]

It is amazing what you find on the web. We have been wandering in the dark on sequence keys as we don't know how they are assigned and we've never seen an actual SKB.

Try this link:
http://domino.watson.ibm.com/library/CyberDig.nsf/papers/7158161AA398C8CE8525722200570F64/$File/rj10394.pdf

It describes limitations of the SKB tracing system, anonymous colluding attacks and non-anonymous attacks (the literature calls them "clone decoder attacks). It's apparently written by those who designed the AACS SK system. Part of it is word for word identical to the AACS spec description of the SK system. Fascinating reading.

Cool stuff :). Thanks.

[FoxDisc]

Cool stuff :). Thanks.

I had planned to discuss some of your really interesting comments/questions from one of your earlier posts - like how many different Dvs there are and how many different answer keys K are in a single column of an SKB and how different players and different disks would move through the SKBs. There are some hints to the answers to those questions in that paper.

As I read it, the system is probabilistic, not deterministic (they run some probability of revoking an innocent player when they revoke traitors.) They can set that probability as low as they want (they used one in a million in the paper).

Another interesting thing was that attackers that are randomly distributed among devices were easier to defend against than attackers who all had the same manufacturer or model of player. You would think that one model would be weaker and that most attacks would be by that one compromised model, yet they designed it so that likely scenario puts the most strain on the system. At some point, given enough attacks by a single mnfr/model, they say the AACS system would fail.