Understanding AACS (including Subset-Difference)

[xyz987]

Originally Posted by arnezami

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]

Originally Posted by FoxDisc

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]

Originally Posted by FoxDisc

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]

Originally Posted by xyz987

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:



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]

Originally Posted by ErazorTT

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]

Originally Posted by arnezami

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 (but its different because herbivore focuses on privacy while we want to compare notes without actually releasing the notes). Which is hard btw .

[FoxDisc]

Originally Posted by 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 .

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]

Originally Posted by FoxDisc

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.

[xyz987]

Originally Posted by FoxDisc

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]

Originally Posted by xyz987

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]

Originally Posted by FoxDisc

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]

Originally Posted by FoxDisc

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]

Originally Posted by xyz987

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]

Originally Posted by ErazorTT

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:


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]

Originally Posted by 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.

Cool stuff . Thanks.

[FoxDisc]

Originally Posted by arnezami

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.