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 17th February 2007, 14:05   #1  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Understanding AACS (including Subset-Difference)

For those that have been following the developments lately concerning HD DVD and Blu-Ray decryption it might seem difficult to get a grip on what has actually happened. There has been so much talk about so many different kinds of Keys and IDs that everything might start to look like a big blur of encryption gibberish. So far there has not really been any overview of what has actually been "broken" and what the consequences of some of the recent finds are. Basicly there is a gaping hole in our understanding of how things work which prevents us from making any definitive conclusions about the meaning of events occured. The biggest gap being the Subset-Difference technique used by AACS.

With this post/article I would like to fill this particular gap. It is meant to explain how the Subset-Difference technique works. Before that I will quickly explain how the general picture looks like so you can see how and where the Subset-Difference technique fits in.

[edit] If you're really new to AACS you might want to read this thread first.

AACS in general

The following is a picture some of you might already have seen. Its a main overview of the AACS protection system. It shows the disc and the player and "all" the important keys involved in the decryption process.



MKB = Media Key Block
Process MKB = Subset-Difference Tree system
Km = Media Key
Kvu = Volume Unique Key
Encrypted Key = Encrypted Title Key
Kt = Title Key

What it shows are all the necessary pieces of information you need in order to decrypt the content. And each piece has a role.
  • Subset-Difference Tree system: essentially a giant and largely secret collection of never changing Processing and Device Keys derived from one Master Device Key (or a few). Device Keys can in essense be used to derive a desired Processing Key and because only a few Device Keys are given (hidden in the Player) only a part of all Processing Keys are "reachable" by any given player. This is used for not allowing ("implicitly revoking") certain players to be able to find the right Processing Key (which is needed to get the Media Key).
  • Media Key: you could argue this is the "core" Key. Its derived from the Processing and a C-value (which is taken from the MKB file) and is in a way the end result of the Subset difference method. Its different for every movie. So if you find one Media Key you can only decrypt one movie (if you manage to get the Volume ID).
  • Volume ID: this is used to prevent bit-by-bit copying: the Volume ID can only be retrieved by asking the drive in a special way (its not stored in a file on the disc). When copying a encrypted disc this piece of information will not be on the copy thus making it impossible to decrypt/play the content: the copy won't work. The volume ID should normally only be retrievable given a Host private key (which is hidden in the player). The Volume ID is combined with the Media Key to produce the Volume Unqiue Key. And that Key can decrypt the Title Keys.
  • Multiple Title Keys: even if you managed to find one Title Key this will only allow you to decrypt part of the content thus making it harder because you need to retrieve all of them. This difference in Title Keys can only be accomplished by giving multiple encrypted Title Keys.
Those are the basics of AACS. While I could go into more detail concerning all these parts I will now concentrate on the Subset Difference technique since its the hardest to understand and least transparent.

The Subset Difference technique

In order to explain how this technique works its best to show how its works in its basic form. Only then we can see how more complex things like "multiple non-adjacent revocations" work. But I will not start explaining it by talking about all kind of cryptographic techniques used. I will begin with giving a real-world-like illustration/analog that everybody can understand while in the meantime being quite accurate in showing how this technique actually works. When reading the next part keep in mind: the subset-difference technique is all about reachability.

Driving a truck

The following picture shows a (tree-like) network of roads, several Parking spots and a truck with a long trailer:



The idea is this: the truck cannot make tight turns (90 degrees is its best) and it can't go into reverse. When you look at the picture you can imagine to which places the truck can actually drive. To make it a little easier I colored the parking spots green and red to show which of them are and are not reachable from the starting position of the truck. It may not look like much but if you understand this then you're already quite a long way there of understanding the subset difference method. So look at it closely and let it sink in.

How it goes:

The story is like this: you are given a truck with several boxes in it and some instructions. These say you have to reach a specific Parking spot in order to get some information (carved in stone at this Parking spot). This information is important because it gives you the ablity to open one of the boxes (with a "C" on it) in your trailer. In this C-box there is a key (with an "M" on it) which in turn allows you to open other boxes (this isn't part of the subset difference anymore so the illustration ends here). Suffice to say: if all goes well you end up with opening a box with a nice present in it .

Revocation:

The thing is you cannot reach every Parking spot. So if you happen to have a starting position from which the Parking spot isn't reachable you will never get the present. Lets say the person that gave you the truck and boxes has also given these trucks to all kinds of people (who have different starting positions) and he does this regularly because he likes to give away presents. And lets assume he doesn't like you anymore (you were unkind to him because ... well fill in yourself). From now on he can choose a Parking spot not reachable by you. He would make sure the C-box can only be opened with the information from that (for you unreachable) Parking spot. This means you will never be able to get any presents from him anymore. You are "revoked".

You now know how the subset difference technique works .

Well in principle .

How it works in AACS

The reason why the subset-difference method may seem so hard to understand is because they had to make the above work using existing cryptographic techniques. And that could confuse you. Hopefully though since you read/looked at the above you now know the principle design of how it is supposed to work so you will get less confused by the crypto talk: in essence its all a computational way of making information "reachable" or not. Thats basicly it.

To explain how it works in AACS lets first look at the letters/examples I mentioned and clarify them:

- Parking spots: these are the Processing Keys. These are the goals to reach. Keep in mind Processing Keys don't change: the only thing that changes is the choice of the "man who gives presents" which one of all the Processing Keys has to be reached.
- The instructions: these "instructions" are in the MKB file and tell you which Processing Key (parking spot) you have to get to.
- C-box: this is a C-value in the MKB file. In fact a C-value is simply an encrypted Media Key (a "locked box" if you will). There is more than one C-value but I will get to that later (when it gets complicated ). In reality there is only one C-value in use at the moment.
- M-key: you guessed it. Its the Media Key. Its the result of the Processing Key and the C-value.
- You/the truck: you are basicly the Software player that tries to get to the Processing Keys.

Now what is obviously still missing are the Device Keys and an explanation of how you "drive" cryptographically. I will deal with that now .

Device Keys:

To do that lets first look at an example of driving towards a Parking spot:



As you can see the truck has to drive north first and then goes south. This is always the case: first north (NE/NW) then south (S/SE/SW).

In reality in AACS there is no driving north: this part is skipped and you simply "jump" to the point where you start driving south (the purple arrow). But you can only jump to points that would in fact be reachable (if you would have done the actual northish driving first). As you can see in the picture I've marked the point where the truck starts going south (the purple arrow). This is the Device Key. Device Keys are the points where you normally would start driving south.

Here is a little more zoomed out picture which depicts the starting-to-drive-south points (= Device Keys) in purple:



What you may have noticed is that these Device Keys are all right along the path north. In fact there are as many Device Keys for a tree as there are branches along the path from your position to the top of the tree. In order to drive towards a certain parking spot (Processing Key) you first need to look at the map and see which Device Key has to be your starting point (only one allows you to go to the Processing Key). From there you can "drive" southwards towards the desired Processing Key. Also notice that along the path north the are red Parking spots. These are the Processing Keys you will never be able to get to. But all the rest of them are reachable by you (green).

Driving:

In AACS "driving" always starts with a Device Key. So there is no need to drive north only south. But when going south it should also not be possible to reverse. In order for that to work they have made it impossible to go north at all (which is also why the "jumping" was needed I talked about above).

How? Well they use one-way functions: you take a Device Key and do some operation/function on it (AES-G3 to be exact) and you can get any of three things: a left sub-Device Key, a right sub-Device Key or a middle Processing Key. Whichever one you need at that point. (note: a sub-Device Key is a Device Key you generated this way. While a Device Key is given to you). Driving simply means: doing this operation on (sub) Device Keys. With each operation you move toward other sub-Device Keys (you move SE or SW in the tree) or you move towards the Processing Key (you move S in the tree and you stop). But there is no function/operation to do the reverse thus preventing you to go north.

Thats essentially how its implemented in AACS. And its equavalent to the story with the truck above.

--- Just to clear up the above pictures: the yellow arrows is the path north (in AACS driving this path isn't actually done). The purple arrow is a Device Key (this is a point where you start driving in AACS, thus skipping the northern route to it). The blue arrows indicate Keys that are somehow derived from a Device Key (sub-Device Keys and Processing Keys). The green Parking spots are Processing Keys you can reach. The red Parking spots are Processing Keys you can't reach. ---

[continued in next post]

Last edited by arnezami; 20th April 2007 at 08:00.
arnezami is offline   Reply With Quote
Old 17th February 2007, 14:06   #2  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Subsets and revocation

You may have been asking yourself why its called a subset-difference method and how the revocation works (also for "multiple non-adjacent revocations" whatever that means ). I will explain that here.

First lets see how simple revocation works. Lets look at this picture (i've added trucks):



Each truck represents a Software Player: they each have a "truck" and a starting position. Each one of them can only go to a certain amount of Parking spots, but no two trucks can go to the same set of Parking spots.

I've added the choice (by the "present giving man") of the Processing Key to be found (the blue circle). As you can see this revokes truck nr 1 and 2 (indicated by a red truck). This is because they both cannot get to the circled Parking spot. So by choosing the Parking spot correctly the AASC LA can revoke one or more adjacent "trucks" this way.

Good for them. But how do they revoke "trucks" that are not next to each other? Your intuitive response might be to use two (or more) Parking spots inside the tree. There are however problems with that idea. Let me give this example (this is not how its done but is just to demonstrate why they need something more than just one big tree)



As you can see there are now two Parking spots that if reached give information to open the C-box. The intend is to revoke trucks 1, 2, 7 and 8. Well thats the idea at least. But it doesn't work. Why? Because trucks 1 and 2 can now reach the Parking spot to the right and trucks 7 and 8 can still reach the Parking spot on the left! So by doing it this way nothing is revoked (which clearly wasn't desired). The problem is caused by the fact that the positions of these trucks are not adjacent. In other words: "non-adjacent revocation" isn't possible with this method.

The solution: additional sub-trees. Basicly making it a giant "parking garage" with several floors (about 22) where each floor is twice as small as the one beneath. The top floor being very tiny. And an elevator for each truck at the starting position so they can choose the floor they want to drive on.

Here is an attempt to illustrate this:



Each color is a floor. The smaller floors are on top of the larger ones (and since this is a top view you cannot see those parts of the larger lower floor). The red dots are the positions of the trucks to be revoked (these truck can move to the desired floor using an elevator).

Here are the parts relevant for these "trucks":



Ok. How does this solve the problem? Let me explain. For that we first zoom in again on our to-be-revoked trucks and see how this is done:



I've used the same colors so you can match this with the zoomed out picture above. As you can see there are again two Parking spots used. However the trucks 1 and 2 cannot reach the circled Parking spot to the right and the trucks 7 and 8 can't reach the circled Parking spot to the left. So now these trucks (1,2,7,8) have been revoked while the other trucks (3,4,5,6) haven't been.

What is important to note is that since the information coming from the two different Parking spots (Process Keys) is different there is also a different C-value corresponding to the subtrees where the Parking spots lie in. This way it is garanteed that both trucks 3,4 and 5,6 end up with exactly the same Media Key (which is calculated by taking the Process Key and use it to decrypt the corresponding C-value).

How is all this a "subset-difference" thing? Well its not so difficult to see now: take (for example) the subtree containing trucks 1-4. These trucks are a subset of the entire collection of trucks. Another sub-set (trucks 1 and 2) are revoked. If you substract these sub-sets you end up with trucks 3 and 4 (so you take 1,2,3,4 and substract 1 and 2 from that set) which are the non-revoked trucks. Therefore its called a "subset-difference".

Some remarks

Well. That was quite a lot of information already . I think I've covered the bulk of the subset-difference method.

Because I know there are going to be questions I also created a separate sections for that: a special FAQ for AASC (which I will extend whenever there are more good questions and whenever I have time). I've also created a seperate post for Advanced AACS topics. Which sort of speaks for itself I hope (its still in progress ).

I hope I did a good job in explaining this stuff. Suggestions are welcome but purely negative critical remarks that don't help our collective understanding are not sought for. Just keep in mind: I've spend an awful lot of time on this and I'm only human .

Hope you enjoyed it...

Regards,

arnezami


------

This was posted by FoxDisc after a long discussion and probably some pondering. He says things very well .

Quote:
Originally Posted by FoxDisc View Post
If anyone has followed along this thread, they will realize the complexity of this subject. I thought I might add some things that will help simplify why the AACS LA chose this system. It's not just because it's complicated.

Let's say we want to build their DRM system:

Our first crack at it:
A simple design would be to give every player/device a secret device key. Then we encrypt the media key (the media key lets us decrypt the movie) with every secret key for every device and put all those encrypted copies of the same media key on the disc. Each device would look through all the encrypted copies of the media key on a disc until it found the one it could decrypt. To "revoke" a device we just leave off the copy of the media key encrypted with his secret key!

This would work but it takes lots of space on the disc. We need room for every device present and future. We need keys that are secure (16 bytes minimum) With all those keys, there's no room for the movie!

That was their first concern. They didn't want to use up all the space on the disc.

Our second crack at it:
OK, how about this - we put the devices into lots of overlapping groups. Each device goes into many groups. We assign a secret key to each group. If a device is in a group, he gets the secret key for that group. If he's not in that group he doesn't get the key. Now, the devices have to store more than one key.

What do we do with the disc? Well, we start off by encrypting the media key only once using the key for a really big group that everyone is in. Since they all have that key, every device can decrypt it. This is looking good! We only had to use one key on the disc! We've reduced the space used on the disc by making the devices store more keys.

So how do you "revoke" devices? You stop using the key for the big group (everyone, including the bad boys have that key), and you use keys for smaller groups that the revoked devices don't belong to, but the unrevoked devices do.

This is essentially what the AACS did! A "subset difference set" is just a group of devices. A processing key is just a secret key assigned to that group. All this stuff about subset difference sets is all about ways to divide up the devices into groups so we can give a secret processing key to that group. It's fundamentally simple.

So how do we divide up the devices into groups? How do we decide how many keys to give each device? How do we make sure we can always exclude all the devices that need to be excluded while allowing all the devices we want? How do we know who leaked a key so we can exclude him? How do we make sure that knowing one key doesn't let the bad boy figure out any others? How .....

Whoa! Enough questions already ....... it's time to call in the experts - cryptologists and mathematicians. They think about this for a long while and they come up with: The Subset Difference System.

--------------

FAQ for AACS

This is a FAQ for general AACS matters. I know many of you have questions even (or should I say: especially) after reading all the above.

Here are some of the questions. There will probably be many more so I will extend this list.

Question: Why do we need the Volume ID? We already have a Processing Key!

Answer: Discs on PC based systems are protected in two ways: (1) Only non-revoked Device Keys make it possible to get a valid Media Key (see above) (2) The Volume ID is only given away by a drive if the program that is asking it has proof it has a non-revoked Host Certificate. Software players have that (hidden somewhere) so right now we can sniff the traffic between the Software Player and the drive and retrieve the Volume ID that way. But its not a perfect solution: you really want the Host Certificate/Private Key.

Question: Why don't we need Device Keys? Why do we only need a Processing Key to get a Media Key.

Answer: Well thats because they have chosen the same Processing Key on every disc. Right now there are no revokations in the subset-tree so this means all discs have the same Explicit Subset-difference Record (which are basicly the "instructions" I talked about earlier). This means for each disc we have to go to the same Parking spot/Processing Key.

Question: How does the technique of Processing Key + Volume ID differ from extracting Volume Unique Keys directly from the Software Player?

Answer: Currently the easiest way of getting hold of a VUK is by extracting it directly from the memory of WinDVD. However this is likely to be changed: they will probably "harden" this player so its not easy for anybody to write a program that can easely extract a VUK for everybody who wants to. With a known Processing/Device Keys though you wouldn't need a program to extract the VUK out of the memory of a Software player: you only need to sniff the bus for the Volume ID (or even try to guess it). If you have the VID you can calculate the VUK.

Question: Why are there 253 Device Keys for a Player? Why exactly that (strange) number?

Answer: The largest trees used are 22 nodes high. Because there is a Device Key at each branch from the top to the starting position of a Player it will have 22 Device Keys for that tree. He will also have 21 for its sub-tree. And so forth. This means a Player has 22 + 21 + 20 + ... + ... + 3 + 2 + 1 = 253 Device Keys.

Probably many more to follow...

Last edited by arnezami; 24th February 2007 at 14:57.
arnezami is offline   Reply With Quote
Old 17th February 2007, 14:06   #3  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Advanced AACS Topics

Here I would like to write about certain advanced AACS topics. So I reserved this post for that puspose (because I suspect I need a lot of space and I think its a good idea to put it right after the above explanation so we keep it organized).

The topics I'm currently thinking of are these:

Processing Keys can be different for every movie

This is about the value of the Processing now and in the future. There are ways the AACS LA can issue MKBs in such a way that each disc/movie will have to use a different Processing key thus making a Processing Key in the future much less valueable. However this is really an advanced topic which requires a thourough analysis of what can and can't be done. Its very interesting in itself.

There is also some doubt why the AACS LA hasn't used this techinque. Its possible there was too little time for them to do this properly, or they simply don't understand it themselves. Either way they screwed up by not making use of it in the first place and are not even willing to admit it (when looking at the latest "press release").

Squence Keys and tracing

This is all about sequence keys, segments etc. Currently this isn't used on any of the discs found so far but it may be in the (near) future. This is also an advanced topic so I put it here. There is a lot to be understood about this technique and therefor much to explain.

And maybe there are other advanced topics I haven't thought of. I will see when I have time to write about these subjects.

Last edited by arnezami; 18th February 2007 at 21:35.
arnezami is offline   Reply With Quote
Old 17th February 2007, 14:20   #4  |  Link
mrazzido
Registered User
 
mrazzido's Avatar
 
Join Date: Jan 2007
Posts: 114
Great Work !! arnezami !!!!
mrazzido is offline   Reply With Quote
Old 17th February 2007, 14:40   #5  |  Link
blutach
Country Member
 
blutach's Avatar
 
Join Date: Sep 2004
Location: is everything!
Posts: 6,499
Thanks for that arnezami. Very easy to understand. Well done!

Regards
__________________
Les

Only use genuine Verbatim or Taiyo Yuden media.
blutach is offline   Reply With Quote
Old 17th February 2007, 15:34   #6  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Great!




Quote:
Originally Posted by arnezami View Post
Advanced AACS Topics
This is about the value of the Processing now and in the future. There are ways the AACS LA can issue MKBs in such a way that each disc/movie will have to use a different Processing key thus making a Processing Key in the future much less valueable. However this is really an advanced topic which requires a thourough analysis of what can and can't be done. Its very interesting in itself.

There is also some doubt why the AACS LA hasn't used this techinque. Its possible there was too little time for them to do this properly, or they simply don't understand it themselves. Either way they screwed up by not making use of it in the first place and are not even willing to admit it (when looking at the last "press release").
I think using a different Processing Key per movie is not a good idea for them. Now they have to revoke just one Processing Key, but firts they need to close the hole. They have "lost" just one Processing Key per hole. If they use 150 keys (one per movie), they will lose 150 keys per hole. In the future tens of thousand of movies will be released, they would be losing tens of thousand of PKs per newly discovered hole.

A player has only 253 Device Keys. Sure, there are lots of posible PKs and DKs, but it is a limited resource anyway. Already-sold home players must work with any future released movie no matter how many revokations they do. If they don't achieve this goal, the whole revocation system becomes broken.
xyz987 is offline   Reply With Quote
Old 17th February 2007, 15:56   #7  |  Link
guile
Registered User
 
Join Date: Oct 2002
Posts: 65
Very impressive!! You have been a very busy boy Arnezami.

To think I feel like I am "Smart" (or something) when searching out my own keys while you are THE guy that figured out the "how" and the "why" makes me feel like a complete idiot in your presence.

Respectfully,

Clueless (g)

Last edited by guile; 17th February 2007 at 15:59.
guile is offline   Reply With Quote
Old 17th February 2007, 15:58   #8  |  Link
snurregrekk
Registered User
 
Join Date: Dec 2006
Location: Norway
Posts: 8
thanks for your effort of making this rather hard-to-grasp information easier to understand for us all. very interesting reading!
snurregrekk is offline   Reply With Quote
Old 17th February 2007, 20:10   #9  |  Link
h.monay
Registered User
 
Join Date: Jan 2007
Posts: 2
THANK YOU SO MUCH

I understand it now
h.monay is offline   Reply With Quote
Old 17th February 2007, 20:50   #10  |  Link
Adub
Fighting spam with a fish
 
Adub's Avatar
 
Join Date: Sep 2005
Posts: 2,685
Well, done mate, well done. I look forward to added information and updates soon.
__________________
FAQs:Bond's AVC/H.264 FAQ
Site:Adubvideo
Adub is offline   Reply With Quote
Old 17th February 2007, 21:27   #11  |  Link
h.monay
Registered User
 
Join Date: Jan 2007
Posts: 2
here is a pic if ud like to use to show the levels

Last edited by h.monay; 17th February 2007 at 21:29.
h.monay is offline   Reply With Quote
Old 17th February 2007, 22:53   #12  |  Link
noclip
Registered User
 
Join Date: Dec 2006
Posts: 154
You mean Ted Stevens lied to me? It really is a big truck, and not just a series of tubes?

So do you have any ideas about how to get our hands on the AACS LA root key?

Last edited by noclip; 17th February 2007 at 22:59.
noclip is offline   Reply With Quote
Old 18th February 2007, 02:41   #13  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by arnezami View Post

Question: Why are there 253 Device Keys for a Player? Why exactly that (strange) number?

Answer: The largest trees used are 22 nodes high. Because there is a Device Key at each branch from the top to the starting position of a Player it will have 22 Device Keys for that tree. He will also have 21 for the sub-tree its part of. And so forth. This means a Player has 22 + 21 + 20 + ... + ... + 3 + 2 + 1 = 253 Device Keys.
Far good :-)

Note however that a player never gets the root Device Key (neither the root master tree key), because a root key can derive the rest of them.

So the largest tree is 23 nodes hight.
xyz987 is offline   Reply With Quote
Old 18th February 2007, 05:08   #14  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
EDIT: I have rewritten this message. Prior version of this message was not an accurate explanation.

Here is a little explanation with numbered nodes. This is a master tree:

Code:

                       1
                      /  \
                     /    \
                    /      \
                   /        \
                  /          \
                 /            \
                /              \
               /                \
              /                  \
             2                    3
            / \                  / \
           /   \                /   \
          /     \              /     \
         /       \            /       \
        4        5          6         7
       / \       / \       / \        / \
      /   \     /   \     /   \      /   \
     8     9   10    11   12   13   14   15
A master tree is just a tree that complies this rules:

- Any lower key can be derived from higher keys through a one-way function.

- Its keys are used (directly or indirectly) to encrypt or decrypt content

- Its keys can be derived from Device Keys

First of all, what kind of keys are master tree keys?. Posibilities are Title Keys, Volume Keys, Media Keys, Processing Keys, Device Keys or "any other kind of keys" (just to be systematic). Any master tree key is used sometimes to encrypt Media Keys, so it must be a Device Key or a Processing Key. Also it can be used to derive a lower master tree key, and this derived key is used sometimes to encrypt a Media Key. Processing Keys do not comply these conditions, the only kind of key that comply this are Device Keys. So master tree keys are Device Keys.

Player 9 will receive Device Keys 8,5,3. This set of keys is chosen because they can derive any Device Key except the keys from the leaf to the root of master tree. There is no way to derive keys 1,2,4,9 from keys 3,5,8.

If you want to revoke the set of keys player 9 has, i.e. the set of Device Keys that contains key 8 (and only that set), you simply encrypt Media Key with key 9. As stated above the set of keys player 9 has received (8,5,3) can not derive key 9, so player 9 can not decrypt the content.

Last edited by xyz987; 19th February 2007 at 20:34.
xyz987 is offline   Reply With Quote
Old 18th February 2007, 06:36   #15  |  Link
HyperHacker
Resident DRM Hater
 
HyperHacker's Avatar
 
Join Date: Oct 2006
Location: International waters
Posts: 242
Let me just make sure I get this last image...


In this case, 7 and 8 can't reach that leftmost key, because once they get into the light-blue area they can't turn left back into the other blue area that the key is in? They can only keep going "down" to the lowest floor (the root of the tree)?
__________________
Because Moogles pwn.
HyperHacker is offline   Reply With Quote
Old 18th February 2007, 07:50   #16  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by HyperHacker View Post
Let me just make sure I get this last image...


In this case, 7 and 8 can't reach that leftmost key, because once they get into the light-blue area they can't turn left back into the other blue area that the key is in? They can only keep going "down" to the lowest floor (the root of the tree)?
No. Keep in mind there is an elevator only at their starting point. They first have to choose their floor and then they cannot change floors. So they can't even get to the light blue area: they can only drive on one floor (which is quite small btw). Furthermore they can only move within the confines of the grey roads. So there is no way they can get to the light blue area if they started on the higher floor (the darker one).

As an aside: Also on the light blue floor no P has been chosen. So there is nothing to do there even if they started there.

Regards,

arnezami

Last edited by arnezami; 18th February 2007 at 08:02.
arnezami is offline   Reply With Quote
Old 18th February 2007, 08:39   #17  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
@xyz987: concerning Master Device Keys. I believe every "floor" in the garage has some kind of sub-Master Device Key and each of these keys is probably derived from a Master Device Key.

To be honest though there is not much to say or speculate about it than this. We simply don't know how they derive the Master Keys. And personally I don't think its very interesting since we can never find them out.

The only thing that matters is they have the ability to reach every Device and Processing Key.
arnezami is offline   Reply With Quote
Old 18th February 2007, 14:45   #18  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
@arnezami - Excellent work!

At the present time, all discs use the same Processing Key
(Parking Space). Unless the same Processing Key (which is just a number) appears on different subtrees (levels of the parking garage), this means that the Processing Key in current use is on the largest master tree (the only one that all devices/trucks can access/drive on) No device (truck) can get to a Processing Key that is in its own upward chain. Yet every Processing Key in the master tree is in some (possible) device's upward chain. I'm guessing that there is a special spot in use right now at the base of the master tree that holds the current Processing Key/Parking space instead of a device/truck. All other devices in the tree can get to that spot, except the device/truck that starts there (The truck would already be there, but I thought I understood that a device could not calculate it's own single node Processing Key, as well as all the upward processing keys in its chain to the root.)

I understand the "instructions" in the MKB define the "path" to get to the Processing Key, by using ones to go right and zeros to go left when tracing from the top (perhaps I have it reversed - don't recall). Can you confirm where the current Processing Key is located on the tree/parking level and whether it's down low near the base of the master tree/trucks or up higher in the tree? Is it over on the far lower right or left of the master tree?
FoxDisc is offline   Reply With Quote
Old 18th February 2007, 16:47   #19  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Quote:
Originally Posted by FoxDisc View Post
@arnezami - Excellent work!

At the present time, all discs use the same Processing Key
(Parking Space). Unless the same Processing Key (which is just a number) appears on different subtrees (levels of the parking garage), this means that the Processing Key in current use is on the largest master tree (the only one that all devices/trucks can access/drive on) No device (truck) can get to a Processing Key that is in its own upward chain. Yet every Processing Key in the master tree is in some (possible) device's upward chain. I'm guessing that there is a special spot in use right now at the base of the master tree that holds the current Processing Key/Parking space instead of a device/truck. All other devices in the tree can get to that spot, except the device/truck that starts there (The truck would already be there, but I thought I understood that a device could not calculate it's own single node Processing Key, as well as all the upward processing keys in its chain to the root.)

I understand the "instructions" in the MKB define the "path" to get to the Processing Key, by using ones to go right and zeros to go left when tracing from the top (perhaps I have it reversed - don't recall). Can you confirm where the current Processing Key is located on the tree/parking level and whether it's down low near the base of the master tree/trucks or up higher in the tree? Is it over on the far lower right or left of the master tree?
The current Processing Key is in the far lower left of the tree used. This tree is the first tree (out of 513 I believe, I haven't analyzed yet why it isn't 512) which is why the first C-value is used. In other words: the largest tree isn't the 31 nodes high tree (which would be the truely root tree) but several floors higher. AACS simply doesn't use the trees with 31-23 nodes high. Which is why the lowest floor (for AACS) is still didived in approx 500 trees I believe.

If you open your MKBROM.AACS and take/print the docs you can see the all this in the Explicit Subset Difference Record. It takes a little effort but the number 17h (=23d) is already telling. Maybe we should make an MKB file reader or something which graphically shows you which sub-trees are used (and thus have a C-value) and what their "shape" is (the position of the C-values in the trees creating subset-differences). Would be cool and informative in the future (when they start revoking).

There could also be some slight difference in the way it works (at the very lower end) and how I pictured it. But these details will eventually be ironed out .

Last edited by arnezami; 18th February 2007 at 16:54.
arnezami is offline   Reply With Quote
Old 18th February 2007, 17:18   #20  |  Link
Jay Bee
Registered User
 
Join Date: May 2006
Posts: 451
Looks like a good effort!

But personally I didn't get any further than the first image. Maybe an explanation of what all the abbreviations in it mean would help clueless noobs (like me) getting started.
Jay Bee is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

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

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

Forum Jump


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


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