Re: AACS and Processing Key

2007-05-04 Thread Steve Schear

At 11:32 AM 5/2/2007, Perry E. Metzger wrote:

Anyone very familiar with AACS have ideas on what optimal attack and
defense strategies are? This seems like a fertile new ground for
technical discussion.

Ed Felton wrote and excellent piece on AACS from the technical and 
economic/tactical standpoint.  This link is to the part that addresses your 
particular question:


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

AACS and Processing Key

2007-05-02 Thread Hal Finney
Since this is the cryptography mailing list, there might be
interest in the cryptography behind this infamous key.  This is from , particularly the first spec,
Common Cryptographic Elements.  The basic cryptography is from Naor, Naor
and Lotspiech, .

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 

Re: AACS and Processing Key

2007-05-02 Thread Perry E. Metzger

[EMAIL PROTECTED] (Hal Finney) writes:
 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.

However, it is still fine for decrypting old disks, and thus
revelation of this sort of information ruins inventory, which is very

All cryptography is about economics. In crypto, we usually consider
what the best strategy for an attacker is in terms of breaking a
cryptosystem, but here I think the right question is what the optimal
strategy is for the attacker in terms of maximizing economic pain for
the defender. I'd be very interested in what the optimal strategy is
for the attacker in a system like this, and what possible changes
could be made to such a system to defeat such strategies.

At first glance, it would seem that, for the attackers, the right
strategy is not to flood the world with newly cracked keys but to
release them quite slowly. Lets say that the lifetime of the
technology in question is somewhere around ten years. Releasing one
key on the order of every two months or so -- only sixty keys in all
over the life of the technology -- would be crippling. It would render
all inventory in warehouses and the production pipeline useless, at
quite minimal cost to the attackers. The defenders then have a choice
-- destroy all your inventory, or give up. (Or, do they have alternate
strategies here?)

Anyone very familiar with AACS have ideas on what optimal attack and
defense strategies are? This seems like a fertile new ground for
technical discussion.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]