Welcome to Doom9's Forum, THE in-place to be for everyone interested in DVD conversion.

Before you start posting please read the forum rules. By posting to this forum you agree to abide by the rules.

 

Go Back   Doom9's Forum > General > Decrypting

Reply
 
Thread Tools Search this Thread Display Modes
Old 18th March 2007, 12:15   #221  |  Link
awhitehead
Registered User
 
Join Date: Jan 2007
Location: Tel-Aviv, Israel
Posts: 185
Since everyone is linking to paper co-authored by Jeffrey Lotspiech, I just want to point out that he has a website, http://www.lotspiech.com/ and that archive.org has an archive of http://www.lotspiech.com/AACS/ from before he started asking to register to view it: http://web.archive.org/web/200606040...iech.com/AACS/

Since he talks about NNL trees, original paper on NNL by Naor, Naor and Lotspiech is at http://www.wisdom.weizmann.ac.il/~naor/PAPERS/2nl.pdf

HTH
awhitehead is offline   Reply With Quote
Old 18th March 2007, 12:54   #222  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by arnezami View Post
PS. I'm still trying to understand certain things in the paper about some hazy things he said. Eg he is talking about 4 or 6 columns (sometimes 18) and seems to completely ignore the fact that there are 256 columns. There is also the picture of 1 movie per column which is weird because 256 movies using 256 columns won't work because if one key is revoked innocent devices will be revoked to. So interpretation of the text is still a bit of an issue for me atm. Some parts seem to be written hastely (especially the multi-time "fixing" parts) indicated by the many typos, short sentences and lack of precision.
I am glad you say this - I am also puzzled by some of the same things in the papers. He talks about 16 variations at 15 points producing 256 versions of the movie. The AACS specs refer to eight versions at 32 points.
FoxDisc is offline   Reply With Quote
Old 18th March 2007, 14:08   #223  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by arnezami View Post
In the old system (with no clustering) this wouldn't work very well since you would need something like 7000-10000 volunteers (assuming only 4096 rows). Although any model could be used so it might have been a little easier to get more volunteers but still. However because they used clustering (did they really btw or was Lotspiech too late with his "fix"?) they reduced the keys per column (for one model) from 4096 to 64. Thats quite significant!
This key assignment is far surprising for me. Of course any key assignment that is not entirely random is a Bad Idea, but this one seems to be a Very Bad Idea if i understood it. This seems to be equivalent to assign a SK matrix to each model, a matrix whose number of rows is far lower that the number of rows of master matrix.

The weak point of any SK matrix is the number of rows (it is noteworthy to say that NNL paper says "the CPRM method is not r-flexible: the probability that a non-revoked device is uncovered grows with r, hence in order to keep it small enough the number of revocations must be bounded by A"). But it seems Lotspiech is proposing here to reduce a lot the number of rows for each manufacturer/model.

Have i understood it?. It is hard to believe they did a so big mistake.
xyz987 is offline   Reply With Quote
Old 18th March 2007, 14:47   #224  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Ok. I did some simulations. It appears my estimates are somewhat off. But still practical.

For finding 58 of the 64 keys (per cluster) we need approx 146 volunteers.

For finding 60 of the 64 keys (per cluster) we need approx 169 volunteers.

For finding 63 of the 64 keys (per cluster) we need approx 239 volunteers.

For finding 64 of the 64 keys (per cluster) we need approx 308 volunteers.

(this is based on random distribution of the keys)

Thats quite a bit more than I guessed earlier but still very doable.

The question is: do we even need so many of the keys per cluster to be safe? In other words: assume they revoke all released keys (say 60 of all 64 keys for each column). How big a chance is there that some/many innocent devices get revoked in the process? My bet is (although we could do the math on this properly) that there will be quite a lot of innocents revoked if they would do that. Especially since different movies would require keys from different columns. And there are bound to be innocents that do not have the keys in those columns (for at least some movies) if they revoke all these keys.

Personally I think its better to be safe than sorry: 64 out of 64 will always be safe (with maybe a few columns with 63 or 62)

There is also the possibility they aren't even using all 64 keys (within clusters) but are only using a subset of those (maybe some sequential non-random distribution). This could have both advantages (less keys per cluster is easier) aswell as disadvantages (how do you know you have all keys that are in use?) But when you have enough voluntiers there won't be any risk of missing keys.

arnezami

PS. For 256 keys per cluster (16K rows) it would take around 1000-1500 voluntiers to get around 250-256 keys for each column. Thats starting to get somewhat impractical. But maybe not. Since we can take all the time in the world for more people to join the effort.

Last edited by arnezami; 18th March 2007 at 15:52.
arnezami is offline   Reply With Quote
Old 23rd March 2007, 07:12   #225  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
I did some searching and figuring out concerning the timing of the specifications of AACS. I now believe the paper from Lotspiech and Hongxia (the "Renweable traitor tracing: ..." paper we are getting all this info from) was not written in late 2006 but in 2004 (or maybe 2005). I think it was lately edited to add new references (I now believe it originally had something like 12 or 13 references all of which are from 2004 and before).

Why is this important? Because I also believe the problems Lotspiech and Hongxia found might have been fixed in a different/better way than they proposed in their paper.

Things that are better/different when looking at the (most recent) AACS specs:
  • Amount of points in the movie for variations was 15: aacs specs now says 32 (and thats per title/EVOB). The number of variations was 16 per variation point: in aacs specs it seems like to be 8 now.
  • Only speaks of one SKB per disc: aacs specs say 6 SKBs (and SKGs).

The above might have solved some of the problems they described. There are now max 1024 Variation Data and combined with the (six) Segment/Sequence key blocks the problem with Multi-time might might have been solved wihtout having to make sure each column gets different variations which caused the q / c to go too low thus requiring the slot/clustering method.

I'm not sure though...

Some more dates:
  • July 14 2004: AACS common specs technical overview draft (this is quite interesting because it shows whats changed since then, also look at their design regarding Bus encryption ) No talk about Sequence Keys.
  • 2004/2005??: Renweable traitor tracing etc written (but not released) by Lotspiech and Hongxia.
  • April 2005: the AACS (common) specs released. No talk about Sequence Keys though (and can't find the 0.90 specs released then, does anybody still have them?) Does anybody know if and when the Prerecorded specs came out?
  • March 13 2006: version 0.911 of the BD and HD DVD pre-recorded books released (these were hardly different from the 0.912 specs released Agust 15 2006, see "red line" documents for this)
  • March 31 2006: Toshiba released their first HD DVD player in Japan (wikipedia)
  • November 2006: After being edited IBM releases the paper from Lotspiech and Hongxia along with what appears to be an even older one about Efficient traitor tracing.

The reason why I think the paper was written earlier? Because it wouldn't make sense that they release the AACS specs and start selling players and then write a paper on how to fix a major problem. It just looks like this was written before 2006 also because a few things appears to have changed (like the 15 / 32 discrepancy) after that. Also the last reference in the document is not referred to (and is a very recent late 2006 piece) and is therefore probably added just before release (but the paper isn't based on it).

In other words: I don't think we can be sure whether or not the clustering "fix" has been implemented or not.

Regards,

arnezami

Last edited by arnezami; 15th June 2007 at 07:08.
arnezami is offline   Reply With Quote
Old 23rd March 2007, 22:20   #226  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by arnezami View Post
In other words: I don't think we can be sure whether or not the clustering "fix" has been implemented or not.
Of course. It is not on spec, so may be they have done it this way or not. That's why we must rely just on spec.

So the old questions arise again. But i am simply tired and bored these old questions are never finished just because the focus is always changing again and again.

If someone really wants to debate what happens if each attacker publish just one key per player, i will do it to the very end of the question.

Changing the focus and keeping old questions unresolved is just a waste of time.

And yes, i am angry.

Edit: of course i am not angry with you, arnezami.

Last edited by xyz987; 24th March 2007 at 08:17.
xyz987 is offline   Reply With Quote
Old 25th March 2007, 12:55   #227  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
If someone really wants to debate what happens if each attacker publish just one key per player, i will do it to the very end of the question.
We know what will happen if an unlimited number of compromised devices each publish one unique SK per player. There are more players than SKs and each player has multiple SKs. Ultimately all keys get published and AACS is broken. The question has always been how many players less than "an unlimited number" have to get together and the answer to that question depends on key assignment. If you think you have some answers to questions that have not been considered or some insight that has not been revealed, why don't you post your analysis? This is an explanation thread, not some kind of debate contest.
FoxDisc is offline   Reply With Quote
Old 2nd April 2007, 03:24   #228  |  Link
gaurav1780
Registered User
 
Join Date: Mar 2007
Posts: 3
a physical example...

hi,

how about having a small practical example showing how NON-CONTIGUOUS devices are revoked. Say in an 8-device environment (d0-d7), d1 and d6 need to be revoked. which are the keys used to encrypt media key. If the answer is device key of d1 and d6, it is not accurate since d1 and d6 can collude and share information. maybe we can deploy a shared nomenclature....
root ..............................................A
level 1 ............................B..........................C
level 2 .....................E...........F.............G............H
level 3 (devices) ....d0..d1....d2..d3......d4..d5.....d6..d7


what would be really clarifying is answer to the question "which keys do the subset difference trees rooted at A-H store?"
gaurav1780 is offline   Reply With Quote
Old 2nd April 2007, 05:43   #229  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by gaurav1780 View Post
hi,

how about having a small practical example showing how NON-CONTIGUOUS devices are revoked. Say in an 8-device environment (d0-d7), d1 and d6 need to be revoked. which are the keys used to encrypt media key. If the answer is device key of d1 and d6, it is not accurate since d1 and d6 can collude and share information. maybe we can deploy a shared nomenclature....
root ..............................................A
level 1 ............................B..........................C
level 2 .....................E...........F.............G............H
level 3 (devices) ....d0..d1....d2..d3......d4..d5.....d6..d7


what would be really clarifying is answer to the question "which keys do the subset difference trees rooted at A-H store?"
No. They cannot collude. They both have the same disc (so they exactly the same information) and none of their Device Keys allows them to go to any Processing Keys (that would reveal the Media Key). So having the collection of the Device Keys of both participants won't help at all since none of those lead to anything useful.

You need a non-revoked third participant.
arnezami is offline   Reply With Quote
Old 3rd April 2007, 01:26   #230  |  Link
gaurav1780
Registered User
 
Join Date: Mar 2007
Posts: 3
Quote:
Originally Posted by arnezami View Post
No. They cannot collude. They both have the same disc (so they exactly the same information) and none of their Device Keys allows them to go to any Processing Keys (that would reveal the Media Key). So having the collection of the Device Keys of both participants won't help at all since none of those lead to anything useful.

You need a non-revoked third participant.
continuing along the same notation -
root ..............................................A
level 1 ............................B..........................C
level 2 .....................E...........F.............G............H
level 3 (devices) ....d0..d1....d2..d3......d4..d5.....d6..d7

d1 and d6 are revoked and collude

d1 has device keys k_d0, k_F, k_C
d6 has device keys k_d7, k_G, k_B

isn't it right that k_C and k_B can effectively derive all device keys (k_d0...........k_d7).

am i missing something here? (i am pretty sure i am, but can't figure out what)

do the key subsystems originating at the nodes of the master key tree contain key K to decrypt media key, such that K can't be reached by a combination of revoked keys?
gaurav1780 is offline   Reply With Quote
Old 3rd April 2007, 05:41   #231  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by gaurav1780 View Post
continuing along the same notation -
root ..............................................A
level 1 ............................B..........................C
level 2 .....................E...........F.............G............H
level 3 (devices) ....d0..d1....d2..d3......d4..d5.....d6..d7

d1 and d6 are revoked and collude

d1 has device keys k_d0, k_F, k_C
d6 has device keys k_d7, k_G, k_B

isn't it right that k_C and k_B can effectively derive all device keys (k_d0...........k_d7).

am i missing something here? (i am pretty sure i am, but can't figure out what)

do the key subsystems originating at the nodes of the master key tree contain key K to decrypt media key, such that K can't be reached by a combination of revoked keys?
Yes you're missing something here .

When both devices are revoked this whole tree won't be used again. The tree (or floor if you will) above it is used.

Here is your example (using my truck/garage picture style) to explain this:



As you can see the trucks (d1 and d6) cannot reach the tree the other one is driving on because there simply isn't any road to it. And they cannot get to the circled Parking spot in their own tree. Note that the floor below (the very light blue one) is simply not used anymore (on new discs).

Hope that helps.

arnezami

Last edited by arnezami; 3rd April 2007 at 06:23.
arnezami is offline   Reply With Quote
Old 3rd April 2007, 16:05   #232  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by gaurav1780 View Post
continuing along the same notation -
root ..............................................A
level 1 ............................B..........................C
level 2 .....................E...........F.............G............H
level 3 (devices) ....d0..d1....d2..d3......d4..d5.....d6..d7

d1 and d6 are revoked and collude

d1 has device keys k_d0, k_F, k_C
d6 has device keys k_d7, k_G, k_B
Your notation is part of what is confusing you. You are looking at a subtree that starts at the node A. When you write:
Quote:
d1 has device keys k_d0, k_F, k_C
d6 has device keys k_d7, k_G, k_B
You should write:
d1 has device keys A-d0, A-F, A-C
d6 has device keys A-d7, A-G, A-B
These are device keys that signify a Subset Difference set rooted at A and subtracting out the devices below another node. Thus, the device key for A-F matches the S-D set of d0, d1, d4-d7. (d2 and d3 are below F so they are not part of the A-F S-D set. The other devices are below A, but not below F so they are members). The device key for A-F allows calculation of the processing key for that S-D set and the S-D sets of A-d2 and A-d3.

Quote:
isn't it right that k_C and k_B can effectively derive all device keys (k_d0...........k_d7).
Yes, but only for the S-D sets rooted at node A. The AACS LA won't use those S-D sets for the MKB and they won't use the device keys for those sets. There is another set of device keys for S-D sets rooted at B (and every other node). d1 does not have the key on the subtree rooted at B for the S-D set B-d1, but d0, d2 and d3 all do have that device key or one that will calculate it (d2 and d3 have B-E and can calculate B-d1 from B-E).
d6 is not below B and has no B-rooted device keys so he can't help d1.

Quote:
am i missing something here? (i am pretty sure i am, but can't figure out what)
Did that help?

Edit:
For reference and to clarify - the full set of device keys for the two revoked devices are:

d1 has device keys A-d0, A-F, A-C, B-F, B-d0, E-d0 (3 keys on A-level, 2 keys on B level, 1 key on E)

d6 has device keys A-d7, A-G, A-B, C-G, C-d7, H-d7 (3 keys on A-level, 2 keys on C level, 1 key on H)

The simplest MKB encryption of the media key that excludes d1 and d6 is to encrypt the media key twice, once with the B-d1 key and once with the C-d6 key. These are the largest S-D sets (first node is as high as possible, second node as low as possible) that exclude both d1 and d6.

Last edited by FoxDisc; 4th April 2007 at 20:53.
FoxDisc is offline   Reply With Quote
Old 10th April 2007, 23:59   #233  |  Link
gaurav1780
Registered User
 
Join Date: Mar 2007
Posts: 3
Hey Arnezami and FoxDisc, both the replies were EXTREMELY helpful. Thanks a lot for the help. I am writing a program to provide a comprehensive example of which subsets are used when different pairs (of size 2, 3, ...n) collude. I will shortly have an example for others with a 16 device structure. thanks again, mates.
gaurav1780 is offline   Reply With Quote
Old 13th April 2007, 21:39   #234  |  Link
ffguy
Registered User
 
Join Date: Feb 2007
Posts: 2
While I claim no significant knowledge of the AACS system, I may still be able to help with the cause.

Given a large number of nodes, is it even feasible to consider brute forcing parts of the protection with a distrubuted approach? I'm sure many people on the forums and projects such as distributed.net could help, especially considering the importance of the task.

Also, I can potentially get runtime on a large 1024-node cluster, if that would help. I'm a simple techie who takes care of minor problems, but for the most part I can run whatever I want while nobody is using it. I enjoy brute forcing sudoku solutions during my lunch break :)
ffguy is offline   Reply With Quote
Old 14th April 2007, 20:06   #235  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by ffguy View Post
While I claim no significant knowledge of the AACS system, I may still be able to help with the cause.

Given a large number of nodes, is it even feasible to consider brute forcing parts of the protection with a distrubuted approach? I'm sure many people on the forums and projects such as distributed.net could help, especially considering the importance of the task.

Also, I can potentially get runtime on a large 1024-node cluster, if that would help. I'm a simple techie who takes care of minor problems, but for the most part I can run whatever I want while nobody is using it. I enjoy brute forcing sudoku solutions during my lunch break
Brute forcing AACS keys is not an option. In short: you won't be able to crack AES (which is the encryption cypher used for most keys) or ECDSA for that matter. In this area they have done well.

There may be a role for the community concerning Sequence Keys in the future. But this is based on speculation combined with logic so far. We'll have to wait until they really start using Sequence Keys and see if its practical.

But if we need people to help you can be assured we will tell everyone we can reach .

arnezami

Last edited by arnezami; 14th April 2007 at 20:10.
arnezami is offline   Reply With Quote
Old 8th May 2007, 03:32   #236  |  Link
awhitehead
Registered User
 
Join Date: Jan 2007
Location: Tel-Aviv, Israel
Posts: 185
Ok, this is a question for folks who understand AACS and AES a bit better then I do, primarily FoxDisc and xyz987 (anyone else, pipe in, of course).

We know that in process of decryption, volume ID is hashed together with the media key to obtain VUK. Media key, in turn is generated by using the processing key to decrypt the c-value on the disc.

How strong is the system if the volume ID is known to be all zeros, and we do not know the processing key? Does a mastering house forgetting to set a volume ID on a title gives us anything in terms of finding a valid processing key? My gut feeling tells me that "not much if anything", but I'd like a confirmation.

Thank you.
awhitehead is offline   Reply With Quote
Old 8th May 2007, 12:48   #237  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by awhitehead View Post
How strong is the system if the volume ID is known to be all zeros, and we do not know the processing key? Does a mastering house forgetting to set a volume ID on a title gives us anything in terms of finding a valid processing key? My gut feeling tells me that "not much if anything", but I'd like a confirmation.
You are right, we get nothing. In fact VoID is not a key, but a dirty trick to avoid bit-per-bit home copying. Althought it is not a key, burning software doesn't know this value because it is stored at a reserved data area (2 reserved areas in fact), so it is not possible to do a verbatim copy of the disk.

Of course, there are "unofficial ways" to get VoID, so this dirty trick will become "broken" as soon as anybody develops the appropiate burning soft. However it is far more useful to decrypt the movie, and store it decrypted. That's the reason nobody is developing such kind of burning soft.
xyz987 is offline   Reply With Quote
Old 8th May 2007, 12:57   #238  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by awhitehead View Post
How strong is the system if the volume ID is known to be all zeros, and we do not know the processing key? Does a mastering house forgetting to set a volume ID on a title gives us anything in terms of finding a valid processing key? My gut feeling tells me that "not much if anything", but I'd like a confirmation.
I agree with xyz and your gut - knowing the VID is zero is no better than knowing it's value when it's not zero, and it's easy to get the value, whatever it is.
FoxDisc is offline   Reply With Quote
Old 8th May 2007, 13:27   #239  |  Link
awhitehead
Registered User
 
Join Date: Jan 2007
Location: Tel-Aviv, Israel
Posts: 185
Quote:
Originally Posted by xyz987 View Post
You are right, we get nothing. In fact VoID is not a key, but a dirty trick to avoid bit-per-bit home copying. Althought it is not a key, burning software doesn't know this value because it is stored at a reserved data area (2 reserved areas in fact), so it is not possible to do a verbatim copy of the disk.
So basically, once HD-DVD recorders start showing up, mastering house not setting VID (leaving it all zeros) would mean that home bit by bit copy of that particular disc in an encrypted state is possible (assuming that the protectred areas on the HD-DVD-R or equivalent media would have the BCA and friends all zeros, of course). And given how easy it is for consumer to create a fully decrypted backup, plus lack of long term problems with decrypted backups (inplying that consumers that would make backups of their media would chose to make decrypted backups), it's not as major an oversight at it might seem.

Hrm.

Thank you for clarifying.

BTW, this question came up when I was looking at "Relentless Enemies" - it has an all zeros VID but is AACS protected.
awhitehead is offline   Reply With Quote
Old 8th May 2007, 18:39   #240  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by awhitehead View Post
So basically, once HD-DVD recorders start showing up, mastering house not setting VID (leaving it all zeros) would mean that home bit by bit copy of that particular disc in an encrypted state is possible (assuming that the protectred areas on the HD-DVD-R or equivalent media would have the BCA and friends all zeros, of course).
I'm reasonably sure that a pre-recorded disc that has VID set to zero would be handled differently from a recordable disc copy. The pre-recorded disc should be recognized as an AACS disc by the drive and the drive should enter into an AACS authenticated session with the host. The VID, even if it's zero, will be used with the media key to calculate a volume unique key.

For the case of a recordable disc copy, however, I suspect that whole process won't happen. I don't think it will get a zero for the VID, I think it will get an error when it tries to read the portion of the VID in the Burst Cutting Area of a recordable disc.

It would be an interesting thing to test, however.
FoxDisc is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

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

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

Forum Jump


All times are GMT +1. The time now is 21:18.


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