AACS and Processing Key

[Hal Finney]

Since this is the cryptography mailing list, there might be
interest in the cryptography behind this infamous key.  This is from
http://www.aacsla.com/specifications/ , particularly the first spec,
Common Cryptographic Elements.  The basic cryptography is from Naor, Naor
and Lotspiech, http://www.wisdom.weizmann.ac.il/~naor/PAPERS/2nl.html .

The AACS system implements broadcast encryption.  This is a scheme which
has also been used for satellite TV.  The idea is that you want to encrypt
data such that any of a large number of devices can decrypt it, with also
the possibility of efficiently revoking the keys in a relatively small
subset of devices.  The revocation is in case attackers manage to extract
keys from devices and use them to decrypt data without authorization.

Broadcast encryption schemes such as that used by AACS equip each device
with a set of keys, and encrypt a content key to various subsets of
these keys such that each authorized device can decrypt the content key
but the revoked devices cannot.  Various methods have been proposed for
achieving this, with tradeoffs between the number of keys held by each
device and the amount of data which must be broadcast to hold all of
the necessary encryptions.

AACS uses a binary tree based method, where each device corresponds to
the leaf node of a tree.  It uses a tree with depth of 31, so there are
2^31 leaf nodes and 2^32 - 1 nodes in all.  At this point it is believed
that software players of a particular type are all considered a single
device, while hardware players are each a unique device.  This will allow
individual hardware players to be revoked, while requiring all software
players of a given brand or type to be revoked at once.  This tradeoff
is assumed to be acceptable because it is easy to get a new version of
a software player.

The method of assigning and handling the keys is called subset-difference.
It allows a single encryption to be decrypted by any of the devices in
a given subtree of the main tree, minus any sub-subtree of that subtree.
In this way, any set of revoked nodes can be handled by the union of an
appropriate chosen set of subset-difference encryptions.  For example,
suppose two nodes A and B are to be revoked.  Let A be to the left of B,
and call their lowest common ancestor node C.  Encrypt to the whole tree
minus the subtree rooted at C; also to C's left child's subtree minus A;
also to C's right child's subtree minus B.  This will cover all nodes
except A and B.

To implement subset-difference, the root node of each subtree is assigned
a unique key called a device key.  Then going down the subtree from that
node, each node gets its own device key as a distinct one-way hash of its
parent's device key.  The result is that if you know a node's device key,
you can deduce the device keys of all descendants of that node.

This assignment of keys is carried out independently for each subtree,
so a node at level n has n+1 device keys associated with it, one for
each of the n+1 subtrees that it is a part of.

Leaf nodes correspond to devices, but devices do not get the device keys
for "their" leaf node.  Instead, they are given the device keys of the
sibling node of their leaf, as well as the device keys of all of the
siblings of their ancestor nodes.  Because knowing a device key allows
deducing the device keys of all its descendents, this assignment allows
each physical device to deduce all device keys in the tree except for
their "ancestor" nodes: those on the one branch of the tree leading to
the leaf node.

To implement subset-difference encryption, suppose we want to encrypt
to all nodes in the subtree rooted at node A except those nodes in the
sub-subtree rooted at node B.  Then we encrypt to the device key of node
B that was assigned as part of the device key system rooted at node A.
All nodes in the node-A subtree except those below node B can deduce
this device key, because B is not one of their ancestors.  Nodes below
B cannot deduce the device key because B is an ancestor, and nodes not
below A cannot deduce it because this set of device keys was unique to
the node-A subtree.

In order to get the system started, one node is considered pre-revoked and
not assigned to any physical device.  Initially, the data is encrypted
to the device key assigned to that node as part of the system for the
whole tree.  Every device will be able to deduce that device key and
decrypt the data.

That one key is the "processing key" about which so much fuss is
being made.  All HD-DVD disks that were initially produced have their
content keys encrypted to that single key.  Knowing this processing key,
along with other information available from the disk, allows determining
all necessary decryption keys and provides access to the plaintext of
the content.  With this value having been published, all of the first
generation of HD-DVD disks can be played.

The interesting thing is that publishing a processing key like this does
not provide much information about which device was cracked in order
to extract the key.  This might leave AACSLA in a quandary about what to
revoke in order to fix the problem.  However in this particular case the
attackers made little attempt to conceal their efforts and it was clear
which software player(s) were being used.  This may not be the case in
the future.

AACSLA has announced that they will be changing the processing keys used
in disks which will begin to be released shortly.  Software players have
been updated with new device keys, indicating that the old ones will be
revoked.  In the context of the subset-difference algorithm, there will
now probably be a few encryptions necessary to cover the whole tree while
revoking the old software player nodes as well as the pre-revoked node.
This will make the processing key which has been published useless for
decrypting new disks.

Because processing keys do not unambiguously point to their source,
AACSLA may choose to set up subset-difference encryptions in which
each software player is part of a different subtree and therefore uses
a different processing key.  This might require a few more encryptions
than the minimal number that subset-difference allows, but it would
reduce the chance that AACSLA would find themselves unable to determine
the source of a published processing key.  This will only work as long
as attackers restrict themselves to the relatively few software players.
If some group were to succeed in extracting keys from a hardware player
and publish a processing key that might apply to the majority of hardware
players in use, AACSLA would seemingly have no way to determine how to
address the problem.

Now I must confess that this already long message has oversimplified the
AACS system in certain respects.  First, the subset-difference system is
only carried on for the lowest 22 levels of the 31 level tree.  There are
effectively 512 independent trees where the algorithm is applied, each
with a single pre-revoked leaf node.  However at this time it appears
that only one is in use.

Second, the processing key is not actually the same as the node's device
key, but rather is a hash of the device key.  Further, the exact details
of how you go from the processing key to the various disk content keys
involve several levels of indirection and encryption.

Third, even given the processing key, some of the information needed
to derive all of the disk's content is not easily available.  One piece
needed is a per-title Volume ID which is not readable from the disk in a
straightforward way.  Volume IDs have been discovered by eavesdropping
on the USB bus connected to a disk player, or by hacking disk player
firmware.  At this point it is hard for typical end users to read
Volume IDs, so knowing the processing key is not generally sufficient
to read disks.  Databases of Volume IDs have been published online,
but disk media keys could just as easily have been published.

Speculating now, the AACS system is flexible but it is possible that
publication of processing keys may not have been fully anticipated by the
designers.  The difficulty of tracing processing keys to their source in
an environment in which new disks may require many weeks or even months of
lead time may interfere with the planned revocation system.  The current
processing key will soon be rendered invalid for new releases, so AACSLA's
aggressive legal tactics seem disproportionate compared to the relative
unimportance of this particular key.  Perhaps these legal actions are
primarily intended to limit distribution of future processing keys that
are found on the next set of disk releases.  That would further point
to technical difficulties in revocation strategy when a new processing
key is published.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com