Switching off a thousand devices can cost less than switching off one

By the 42Math team · 12 September 20267 min read

Sixteen million devices, one of them compromised, and the header that shuts it out is one subset key: sixteen bytes. Compromise thirty-two of them at random and it takes thirty-eight. Compromise thirty-two that came off the same production line and it is back to one.

A key is pulled out of one Blu-ray player and published on a forum. Every disc pressed after that has to keep working in the sixteen million players that are fine and refuse to work in that one, and a disc has no way of finding out which player it has been loaded into. It carries a single message, identical on every copy, and that message has to be the permission and the refusal at the same time.

The structure that makes this possible is a binary tree. Devices sit at the leaves of a tree twenty-four levels deep, every node owns a key, and each device leaves the factory holding the keys of the nodes along its own path to the root: twenty-five of them. A node's key is held by exactly the devices beneath it, so naming a node addresses a group without listing anybody in it. Device Revocation draws that tree and computes everything below.

Cover the honest devices

The honest devices cannot be enumerated, so they get covered instead. Take every maximal subtree that contains no revoked leaf, and encrypt the title key once under each of those nodes. A player works down the list, finds the one node it holds a key for, and decrypts. Dalit Naor, Moni Naor and Jeff Lotspiech published this as the complete subtree scheme at CRYPTO 2001.

Revoke a single device and the cover is the twenty-four siblings hanging off the path from its leaf up to the root. Twenty-four keys, 384 bytes, to disown one player out of sixteen million. It grows from there: thirty-two compromised devices scattered through the population take 583 subsets, and sixty-four take 1,102, which is 17,632 bytes of header on every disc pressed.

Neighbours are almost free

Now change where those devices sit and change nothing else. The tool's block pattern revokes consecutive serial numbers rather than scattered ones, which is what a single bad production run looks like. At sixteen million devices:

• eight revoked, scattered: 159 subsets. Eight consecutive: 21.
• thirty-two scattered: 583. Thirty-two consecutive: 19.
• sixty-four scattered: 1,102. Sixty-four consecutive: 27.

Read the middle line twice. Revoking thirty-two neighbouring devices costs nineteen subsets and revoking one device costs twenty-four, so the larger job is the cheaper one. The tree says why: thirty-two consecutive leaves that begin on a multiple of thirty-two are a single node nineteen levels down, and a node nineteen levels down has nineteen siblings above it instead of twenty-four. Carry that further and an aligned block of 1,024 devices costs fourteen subsets.

The header pays for how deep into the tree you have to reach to name the broken devices.

The sixty-four line is the honest one, and worth pausing on. Those sixty-four consecutive devices cost twenty-seven rather than eighteen because the tool's block happens to start at device 5,788,117, which is not a multiple of sixty-four. Move the same sixty-four devices to start at 5,788,160 and the cover drops to eighteen. Alignment is worth something. It is worth a great deal less than adjacency.

A subset that is a subtraction

Complete subtree still carries the size of the system inside its bound. With r devices revoked the header is at most r log₂(N/r), and that logarithm is the depth of the tree. The second scheme in the same 2001 paper removes it. Let a subset mean everything beneath node i except everything beneath node j, a difference of two subtrees rather than one whole subtree, and the honest devices can always be covered by at most 2r − 1 of them. N is not in that expression.

It is not in the measurements either. Sixty-four devices scattered through the population need 77 subsets under subset difference, and the count is 77 at 16,384 devices, at 262,144, at 4,194,304 and at 16,777,216. Complete subtree over those same four populations runs 462, 718, 974 and 1,102. One of the two schemes is reading the depth of the tree and the other has stopped.

One revoked device is the clean case: everything under the root except that one leaf is a single difference, so the header is one key of sixteen bytes at any population you care to name. The hardest pattern the tool offers is alternating leaves, and even there sixty-four revocations take sixty-four subsets against a bound of 127. Complete subtree on that same pattern needs 1,152, which is exactly 64 × log₂(16,777,216 / 64). Neither bound is a loose one.

The bill arrives inside the device

None of this was free. Under complete subtree a device stores one key per level, log₂(N) + 1, so twenty-five keys at sixteen million devices. Under subset difference it has to be ready to play the "except" in somebody else's subtraction, and the count is ½ log₂²(N) + ½ log₂(N) + 1, which is 301. At a million devices the two are 211 and 21.

That trade is the entire design: twelve times the storage inside every device, bought once at manufacture in a part that had to exist anyway, in exchange for a header that has stopped growing with the population. Header bytes are paid on every disc pressed and every licence issued, for as long as the format lives. AACS took the trade and says so in as many words, in a section of the specification titled Subset-Difference Tree Overview.

Where a device sits is decided once

If adjacency in the tree is worth a factor of seven to forty on the header, then the assignment of devices to leaves is a bandwidth decision, and it is taken at manufacture by whoever hands out serial numbers, long before anything has been compromised. Devices likely to fail together should be neighbours in the tree: the same production run, the same firmware image, the same chipset, the same region. The instinct to scatter leaf positions so that a serial number gives nothing away is the expensive instinct.

Set against that, a key extracted by one determined person from one device they bought is scattered by construction, and no numbering scheme can make those into neighbours. A studio gets both kinds of compromise. It can arrange for the batch ones to be cheap and it cannot arrange the individual ones at all, so the figure to budget against is the scattered one: 1,232 bytes for sixty-four devices, rather than 128.

The device that was never broken

All of which leaves untouched the case a studio actually loses sleep over. A licensed player, working exactly as designed, holding keys nobody has extracted, shows the film on a screen with a camera pointed at it. There is no compromised key to revoke and no leaf to cut off, because nothing about the device is broken.

What remains is to make every copy slightly different and read the difference back out of whatever leaks. Forensic Watermarking builds a Tardos code to do that, and it prices the same way round. Protecting a million customers against a coalition of two needs 623 marked positions; against a coalition of ten it needs 15,560, twenty-five times as many, because the length goes as the square of the coalition. Hold the coalition at ten and grow the audience instead, from a thousand customers to a hundred million, and the code moves from 9,773 positions to 19,452. The audience went up by a factor of a hundred thousand and the code did not quite double.

Both halves of this are priced by what the attacker took. The audience enters the revocation bound not at all, and the code length only through a logarithm.

So a design like this holds two questions, and only one of them is cryptographic. The other is whether the person handing out serial numbers was ever told that the order they go out in is the difference between a 1,102-key header and a twenty-seven-key one.

Published 12 September 2026 · corrections welcome via the corrections page.