AACSTree - A program to visualize the AACS tree / MKB

[aKzenT]

Hello,

this is my first post in this forum, but I have been following the discussions arround AACS here for quite some time now.

Reading threads like this:
http://forum.doom9.org/showthread.php?t=122363

helped me a lot to understand AACS and especially the subset difference method that is used by AACS.

After understanding the Subset Difference technique, I thought it would be cool to visualize the AACS tree with the subset differences, so that you can actually see which devices are revoked and which are not.

And apparently I'm not the only one :)

The same area covered by the new mkb:

umask:uv number

05:0000001C
[...]


The rest is all the same. So only the first tree has been divided.

It would be pretty cool to illustrate this graphically :).


So I wrote a small tool called AACS Tree, which does exactly that.

The program including the source code is attached. You need the .NET Framework 2.0 if you don't have it installed already.

At the moment you can only load the MKBv1 and MKBv3 which are hardcoded in the program. My next goal is to be able to load an mkbrom.aacs directly to support future MKBs.
Unfortunately I don't have an mkbrom.aacs file to play with, so if anyone could send me one I would be very happy.

Also attached you will find 2 pictures of the MKBv3 that were saved from AACSTree.

If you look at the mkb2_large.png while reading this post from FoxDisc:
http://forum.doom9.org/showthread.php?p=1004720#post1004720

you can see that it is exactly what he is describing.

Please try this out and tell me what you think about this. Also if you find bugs or if you would like a feature to be added please let me know.

In the next post I will give you some tips and tricks to use the program.

Image of the MKBv3:
http://img338.imageshack.us/img338/7133/mkb2smallrk8.th.png (http://img338.imageshack.us/my.php?image=mkb2smallrk8.png)

Image of the MKBv3 with all nodes below the first difference node expanded.
http://img503.imageshack.us/img503/6964/mkb2largest4.th.png (http://img503.imageshack.us/my.php?image=mkb2largest4.png)

:thanks:

edit (2007-06-01): Until the download is approved, you can download the new version here: http://www.sendspace.com/file/d5nwai

[aKzenT]

Some tipps and tricks:

To get started go in the menu and select Load MKB > v1 / v2 > First Subtree.

First Subtree means that only the SD sets of the first of the 512 master trees are shown. Complete means that all subset differences (the actual mkb) are included, but this will result in a very big tree.

Click a node to expand or collapse a node.

If you strg-click a node you can expand the tree 9 levels deep starting from the node (be careful with this, because it can make your tree very big)

Use + and - to zoom in and out.

In the top left corner you can see a small box with some information about the node you are currently hovering.

The Path is given in the form 0xXXXXXXXX/MM where X is the binary path from the root of the tree to the node as a hexadecimal number and MM is the number of significant bits in the path value.

The uv number is the same that you find in the mkb.

The "Member Of:" part shows you which Subset-difference-sets in the mkb this node could use to decode a movie.


Nodes labelled S are the Subset nodes in the MKB, nodes labelled D are the Difference nodes. Everything below a difference node is revoked and therefore displayed red. Green nodes are part of at least one subset-difference.

Enjoy!

[arnezami]

This sounds really cool :D.

Can a mod please approve the links? Thanks.

Or aKzenT: maybe upload the files to http://www.sendspace.com/

Eager to see this...

arnezami

[FoxDisc]

After understanding the Subset Difference technique, I thought it would be cool to visualize the AACS tree with the subset differences, so that you can actually see which devices are revoked and which are not.

I'd like to look at your images, but that has to wait until they are approved unless you want to post them elsewhere.

Did you write the program to work in 2-D (single tree) or 3-D (parking garage floors starting at each node)? Did you use the full 32 level tree or the 23 level tree?

Ultimately, I think it would be great to have a 3-D tree that shows all the past and present S-D sets and labels all the devices/software players with their assigned device numbers. I'm not sure how valuable it would be, but it might start to throw some light on the whole device assignment and LA revocation process.

[FoxDisc]

Can a mod please approve the links?

It just occurred to me - aren't we without a moderator right now? These may never get approved.

[aKzenT]

Hey,

it uses 2d since I don't know how you could present that in 3d in an understandable way. The floor / parking garage metaphor is good, but I don't think it works that well if you apply it to the full 32 or 23 level tree (since you cannot show the complete tree).

It uses the 32 level tree, but for the mkb you can choose to ignore all but the first subtree.

The links are all approved, but I removed the images, since they were a little too large. They are now hosted on imageshack.

What else (beside the subset differences) would you like to see visualized with this? I have written the source code so that I can easily add and remove visualizations. For example I thought of adding a visualization that shows the device keys a device has if you hover over the device node.

btw, could one of you send me an mkbrom.aacs file so I can finish my real mkb loader?

[arnezami]

It looks very good. :) You can clearly see now which nodes are revoked. Well done! **


Using my own handcalculations everything is exactly the same exept for one part in your picture:

http://img503.imageshack.us/img503/6964/mkb2largest4.th.png (http://img503.imageshack.us/my.php?image=mkb2largest4.png)

My calculations made me come to the conclusion that nodes 30-33h (if you start counting with 00) are not revoked. Will have to look into that. --- [edit] removed something: was incorrect ---

[edit]Seems my hand-calc was wrong here. Meaning 30-33h are revoked. Too tired now to be accurate. But looks like your picture/program is perfect. :D

arnezami

** I haven't tried the program itself yet (don't like to install .net on this system) but judging by the pictures: well done.

[FoxDisc]

it uses 2d since I don't know how you could present that in 3d in an understandable way.

I've been trying to wrap my mind around the full tree, with all processing keys, device keys, devices and MKBs with all the S-D sets, and I keep coming up with the 3-D layered tree picture.

I presume you've read the AACS specs and they use a layered 3-D picture to ilustrate S-D sets.

I had in mind a 3-D configuration that could be collapsed to 2-D to show revoked and allowed devices for specific MKBs, as you do now. In the 3-D mode you would be able to scroll vertically in sections to see any specific layer/parking garage floor. That would let you see multiple MKBs at the same time. You could eliminate all floors that have no S-D sets on them, which would make visibility better and you could collapse multiple floors (like the full 2-D collapse that you are showing now,) but limited to defined ranges of floors. To distinguish MKBs, you'd use color coding. The nodes at the bottom would be labeled with the manufacturer and software version of the player.

Perhaps something like the eDrawings 3-D viewer from SolidWorks that lets you check out 3-D models could be used.

I know - way too much effort for a simple visualization tool. :)

[aKzenT]

@arnezami:
edit: removed (see arnezamis edit)

@FoxDisc:
The AACS specs use a layered picture, but they show only one layer for each "sublevel" instead of 2,4,8,...

But I agree that this could work and that it is too much effort ;-) And I actually find it now easier to understand in the 2d space. You just have to understand that a device key is not a single node in the tree but a combination of two nodes.

[arnezami]

--- Not relevant anymore. ---
Sorry. You must have missed my edit. Your program is working perfectly :D.

:thanks:

arnezami

[FoxDisc]

But I agree that this could work and that it is too much effort ;-)

I drew up a little map when I was working it out, and like you - I did it in 2-D.

[aKzenT]

@arnezami: yes I missed your edit, but I'm happy that my program works fine ;-)

I am thinking of adding some labels to special nodes. e.g. labeling the first node as the first processing key or labelling known revoked players. Do we know the device nodes of some players? E.g do we know which of the revoked nodes is PowerDVD?

Also could someone please upload a plain mkb file somewhere, so that I can try to load them directly in my program. I don't own a HDDVD player myself.

:thanks:

[arnezami]

@arnezami: yes I missed your edit, but I'm happy that my program works fine ;-)

I am thinking of adding some labels to special nodes. e.g. labeling the first node as the first processing key or labelling known revoked players. Do we know the device nodes of some players? E.g do we know which of the revoked nodes is PowerDVD?

Also could someone please upload a plain mkb file somewhere, so that I can try to load them directly in my program. I don't own a HDDVD player myself.

:thanks:

Look in your pm box ;).

I was thinking something about colors like I do in my examples (when dealing with multiple layers). Still 2D but it is more clear that there is more than one level. Not sure if that would be easy in any way though...

Either way this is already very cool :D.

arnezami

[arnezami]

As an aside: looking at these pictures I have to admit the Subset Difference Technique is quite an accomplishment. I'll give them that (well the cryptographers that invented it).

Its a very clever system by itself.

Of course AACS as a whole is plagued by implementation (security) issues...

[awhitehead]

Very neat!

Thank you for writing this tool - it makes things alot clearer.

Now come the questions.... *runs*

This is a bit of a general question: With MKB v3 (Am I correct in understanding that original MKB was reporting itself as version 1, and now with Matrix HD-DVDs, etc the version that MKB is reported is 3? Amazon delayed my Matrix box set, so I can't check for myself *grumble*) a few devices got rewoked. We know which nodes they are on the tree, but do we know what player corresponded to which node?

It is speculated that WinDVD 8 JP and at least PowerDVD 6.5 keys were revoked (Was PowerDVD 7.1 revoked?). To which nodes to those devices correspond?

Lastly, set top players are using a different subtree then software players, right? Where on the big picture are they? Another branch off node 9 from the top of the big picture?

(Coincidentially, anyone has a legitimate license for PowerDVD 6.5? Maybe it was shipped with your Toshiba Cosmio Laptop? Did PowerDVD 6.5 get an official update as well?)

[aKzenT]

Look in your pm box ;).


:thanks:

I was thinking something in the lines of colors like I do in my examples (when dealing with multiple layers). Still 2D but it is more clear that there is more than one level. Not sure if that would be easy in any way though...


I will look at this. The current view is probably best to show the revocations. If you want to explain how a device can or cannot get to an processing key an layer or coloring approach may be better.


Either way this is already very cool :D.


:thanks:

[FoxDisc]

I am thinking of adding some labels to special nodes. e.g. labeling the first node as the first processing key or labelling known revoked players. Do we know the device nodes of some players? E.g do we know which of the revoked nodes is PowerDVD?

As I suspect you know, the first node is a pseudo device. It was "revoked" with MKB v1. I call it a pseudo device because no device issued that device number could decrypt any of the first set of discs. Interestingly, it was unrevoked with the last MKB v2.

That node also corresponds to multiple Processing Keys and their matching Device Keys - there's one at that node per floor. One of those PKs (on the largest floor) is the famous 09 f9 key.

I don't think anyone has publicly identified any device numbers.

[aKzenT]

Very neat!

Thank you for writing this tool - it makes things alot clearer.

:thanks:


Now come the questions.... *runs*

This is a bit of a general question: With MKB v3 (Am I correct in understanding that original MKB was reporting itself as version 1, and now with Matrix HD-DVDs, etc the version that MKB is reported is 3? Amazon delayed my Matrix box set, so I can't check for myself *grumble*) a few devices got rewoked.

If this is in fact v3, then I mislabelled this mkb as version 2. I will correct that in the next version.


We know which nodes they are on the tree, but do we know what player corresponded to which node?

It is speculated that WinDVD 8 JP and at least PowerDVD 6.5 keys were revoked (Was PowerDVD 7.1 revoked?). To which nodes to those devices correspond?

This is what I also want to know. I don't know if anyone here has information about this?


Lastly, set top players are using a different subtree then software players, right? Where on the big picture are they? Another branch off node 9 from the top of the big picture?


We assume that, but we don't know that for sure.
If this is in fact true, then it would be on the same level as the first S node, possibly the other child of node 9.
You can try to load the complete tree in the program too see all possible subtrees.

[aKzenT]

As I suspect you know, the first node is a pseudo device. It was "revoked" with MKB v1. I call it a pseudo device because no device issued that device number could decrypt any of the first set of discs. Interestingly, it was unrevoked with the last MKB v2.

I was also wondering about this. But I suppose it makes sense, because keeping it revoked would only waste space in the mkb.


That node also corresponds to multiple Processing Keys and their matching Device Keys - there's one at that node per floor. One of those PKs (on the largest floor) is the famous 09 f9 key.

Yes, you are right. Labeling the first node as a special processing key would probably do more harm than good in explaining how AACS works.

I don't think anyone has publicly identified any device numbers.


I was afraid of that...

[Pata]

You can use this program to make this maps.

http://www.research.att.com/sw/tools/graphviz/

[aKzenT]

Ok, I uploaded a new version with these new features:

Loading of Media Key Block files (mkbrom.aacs) is now possible. This means that you will be able to visualize future mkbs without updating the program first.

Function to highlight compromised Subset Differences (subset differences for which we have a processing key). The SD set matching the new processing key for MKBv3 is already included! So you where the compromised device is located in the tree.

A small AES-G3 calculator is included, which is always useful ;-)

Please try this out and tell me what you think!

edit: until the attachment is approved, you can download it here:
http://www.sendspace.com/file/d5nwai

[SvT]

I'm sure gonna try this version ! This program of yours really helps me to understand some things regarding the subset difference and revocation more clearly !

Thanks so far !

[FoxDisc]

Ok, I uploaded a new version with these new features:

I haven't tried the new version yet, but thanks for the old version! It's so much easier than trying to directly read the uv number and umask.

[Rufus210]

Any chance someone can use one of the diagrams produced by this to show where in the V3 tree the new key (http://forum.doom9.org/showthread.php?t=126404) is?

[aKzenT]

@Rufus210:
Yes, you can see the new key:
If you load the MKBv3 in the program, you can see that two nodes are marked blue. The S-node is the subtree where the new processing key is located. The D-node is the node in this subtree from which the new key was derrived.
All the other S,D-pairs you can see match other processing keys in the new MKBs which are not found yet.

Also, a device can only get to a specific processing key if it is located below the S-node for this processing key and not below the D-node of the key.
In this case only one device is below the S-node, but not below the D-node, which is the green node next to the blue nodes.
This is the device/player where the processing key is from. So AACS LA knows exactly what player was cracked.