Revoking a Device Without Telling Everyone Else

Every device holds keys, one of them leaks, and the licence has to keep working for everybody else. Set how many devices exist and how many are compromised; the tool builds both of the covers Naor, Naor and Lotspiech defined in 2001, draws the one you pick, and counts what the header has to carry.

Worked example — Revoking a Device Without Telling Everyone Else

Keys in the header	4
Header size at 16 bytes a key	64 B

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Revoking a Device Without Telling Everyone Else

In broadcast encryption the same encrypted film reaches every device, and the licence decides who can open it. Arrange the devices as the leaves of a binary tree and give every node its own key; a device is handed the keys on its own path from its leaf up to the root, so log₂N + 1 of them. A node then names a set of devices — everyone beneath it — and the licence header carries the film's key encrypted once for each set in a collection that covers the honest devices and leaves the compromised ones out. Revoking a device is choosing a different collection.

What each symbol means

N: how many devices exist, always a power of two here so the tree is full
r: how many of them are compromised and must be locked out
S(i,j): the subset-difference set: every device under node i except those under node j, which is what lets one header entry skip past a single bad leaf

Assumes: That a revoked device cannot be repaired, only excluded, and that it never forgets the keys it was given. That is what "stateless receiver" means in the title of the paper, and it is the reason the answer is a covering problem rather than a re-keying one: nobody can send a device a new key, because the device that leaked its keys would receive that too.
Breaks when: When the compromised devices are spread evenly. Both schemes are at their best on a batch of consecutive serial numbers and at their worst on every other device, where no subtree is clean and the header needs one entry per surviving device — which is what you would pay with no scheme at all.

The header does not know how many devices there are 🖖

Set the compromised count to 10 and then drag the system size. Complete subtree goes 58 keys at 1,024 devices, 98 at 16,384, 158 at 1,048,576, 198 at 16,777,216 — every doubling of the system adds one more key per compromised device, because each one needs a subset for every sibling on its path to the root. Subset difference reads 13 at all four sizes. Not 13 and then 14; the same 13, and the same 13 at every size from 512 devices upward, which is a thirty-two-thousand-fold increase in the system for no change at all. A subset-difference subset is "everybody under node i except the ones under node j", so a single entry can hand the key to 1,048,575 devices and withhold it from the one, and the depth it reaches down through costs nothing. That is why the bound is 2r − 1 with no N in it at all, and it is the reason the Media Key Block on a Blu-ray disc is a subset-difference tree: the studios go on adding devices for twenty years and the header does not notice.

The price is paid by every device, once 🖖

Look at the last row of the table. Complete subtree asks each device for log₂N + 1 keys: 21 at a million devices, the nodes on its own path to the root. Subset difference asks for ½log₂²N + ½log₂N + 1, which is 211. Ten times the storage to make the header a twelfth of the size at ten scattered compromised devices, and an eleventh at sixty-four. That trade is only obvious once you notice which number is paid how often — the keys go into the device once, in the factory, and the header goes out with every licence for every title to every device for ever. 211 keys is 3.4 kB of flash. Each of those million devices then fetches a 13.5 kB header instead of a 1.23 kB one, every time it asks for a licence, which is the same argument run the other way.

Who you revoke matters more than how many 🖖

Press One bad batch in a million, then 64 scattered in a million. The same 64 devices are revoked. The subset-difference header goes from 3 keys to 77 and the complete-subtree header from 17 to 846. Nothing changed except where the bad devices sit in the tree, and leaves are handed out in manufacturing order, which turns that into a lever: a compromised production run, a cloned model, a region — anything that revokes a contiguous block — is almost free, and a thousand individually cracked boxes bought from a thousand shops is not. Press Every other device for the other end of it. Half the devices revoked, alternating, and both schemes need 32 keys for 32 survivors, which is what you would pay with no scheme at all.

Problems solved in full

Where does 2r − 1 come from? The tool prints it in the fourth row and it is the number the whole scheme rests on: whatever the system size, a subset-difference header never needs more than two entries per compromised device. The proof is a counting argument on the algorithm, and it fits in four lines.

Open this problem in the tool
1. Start with the spine: the union of the paths from the root to the r compromised leaves. Every leaf of that spine is a compromised device, so it starts with r leaves, and the algorithm's whole job is to eat them.
  
  $ST (R) has r leaves$
2. One round: find a node v whose two branches each contain exactly one remaining leaf. Emit one subset for each branch that is more than a bare leaf, so at most two subsets, then collapse everything below v so that v itself becomes a leaf.
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. Count what that round did to the leaves. Two went away and one appeared, so the spine is one leaf shorter, whatever the tree looked like.
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. So there are exactly r − 1 rounds before a single leaf is left, each adding at most 2 subsets, and then one closing subset for what remains above that last leaf.
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. Nothing in that argument mentioned the depth of the tree, which is the point. A round costs the same whether v sits three levels down or thirty.
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. The bound is also loose almost everywhere, because it needs every round to emit both of its subsets. Over 200 seeded revocation sets at 1,048,576 devices the average header is 1.2513 keys per compromised device at 64 revoked, 1.2520 at 32 and 1.2580 at 10, against a bound of 2 — so the figure to design a licence format around is about 1.25r, and the figure to guarantee is 2r − 1.
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
Answer

At most 2 subsets per round, r − 1 rounds, plus 1 to close: 2(r − 1) + 1 = 2r − 1, with no N anywhere in it. The complete-subtree bound is r·log₂(N/r) for the same revocations, and the log₂(N/r) is exactly the thing subset difference removes — the price being ½log₂²N + ½log₂N + 1 keys inside every device instead of log₂N + 1.

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
What does a real Media Key Block cost? The tool counts a header in entries, which is the mathematics. A Blu-ray disc carries it in bytes, in a format anyone can read: the AACS specification says exactly how a subset-difference is written down, so the header on a real disc can be sized rather than guessed.

Open this problem in the tool
1. AACS identifies each subset-difference by a one-byte u mask and a four-byte uv number, and carries sixteen bytes of encrypted key data for it — "for each subset-difference included in the identification part, there are 16 bytes of key data in the key data part", in the specification's own words. Twenty-one bytes a subset, and nothing else per subset at all.
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. The cover itself is what the tool computes. About 1.25 entries per revoked device in practice, never more than two.
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. So a Media Key Block is about twenty-six bytes per revoked device. That is the whole size calculation, and it is linear in the number of players being locked out with the size of the system nowhere in it.
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. Put the two schemes side by side at the same revocations. The subset-difference column is what ships; the complete-subtree column is what the same revocations would have cost under the simpler scheme.
  
  $r 100 1, 000 10, 000 S_{SD} 125 1, 250 12, 500 bytes 2, 625 26, 250 262, 500 S_{CS} 2, 436 21, 034 177, 123 bytes 51, 156 441, 714 3, 719, 583$
5. The second column is where the tree height enters. At a system of 2³¹ devices — the largest a 32-bit uv number can address — revoking a thousand players costs about 21,000 complete-subtree entries against 1,250 subset-difference ones, because log₂(2³¹/1000) is about 21 and every revoked device pays it.
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
Answer

A Media Key Block runs at roughly 26 bytes per revoked device: 2.6 kB for a hundred players, 26 kB for a thousand, 262 kB for ten thousand, and never worse than 42 kB, 420 kB and 4.2 MB in the worst case the bound allows. Complete subtree would want 442 kB where subset difference wants 26 kB. Two things follow that the tool does not print. The disc is pressed once and read for twenty years, so an MKB only ever grows — which is why the identification part is five bytes rather than a full node address, and why the format puts the key data in a separate run instead of interleaving it. And a 26 kB header is nothing beside a 25 GB disc: the reason subset difference won was never the bytes, it was that the alternative grows with the size of the system and a disc pressed today has to serve the devices of 2040.

$MKB \approx 26.25 r bytes vs 21 r lo g_{2} \frac{N}{r} bytes$

Learning path

Protecting a stream: revoke a device, then find out which one

References (3)

Both schemes on this page, the two bounds, and the algorithm the worked problem follows: D. Naor, M. Naor and J. Lotspiech, "Revocation and Tracing Schemes for Stateless Receivers." Advances in Cryptology — CRYPTO 2001, LNCS 2139, pp. 41–62.
Why this scheme rather than a nicer one: the Media Key Block on a Blu-ray disc is a subset-difference tree, and the specification says so in as many words. AACS LA, Advanced Access Content System (AACS): Introduction and Common Cryptographic Elements, Revision 0.91, 17 February 2006, §3.2.1 "Subset-Difference Tree Overview".
The problem before either scheme existed, and the source of the term: A. Fiat and M. Naor, "Broadcast Encryption." Advances in Cryptology — CRYPTO '93, LNCS 773, pp. 480–491.