Ein Gerät widerrufen, ohne allen anderen Bescheid zu sagen

Jedes Gerät speichert Schlüssel. Einer davon leakt, und die Lizenz muss für alle anderen weiterhin funktionieren. Stell ein, wie viele Geräte existieren und wie viele kompromittiert sind. Das Tool konstruiert beide Überdeckungen, die Naor, Naor und Lotspiech 2001 definiert haben. Es zeichnet die von dir gewählte und zählt, was der Header transportieren muss.

Rechenbeispiel — Ein Gerät widerrufen, ohne allen anderen Bescheid zu sagen

Schlüssel im Header	4
Header-Größe bei 16 Byte pro Schlüssel	64 B

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Ein Gerät widerrufen, ohne allen anderen Bescheid zu sagen

Bei der Broadcast-Verschlüsselung erreicht derselbe verschlüsselte Film jedes Gerät, und die Lizenz bestimmt, wer ihn entschlüsseln darf. Ordne die Geräte als Blätter eines Binärbaums an und weise jedem Knoten einen eigenen Schlüssel zu. Ein Gerät erhält die Schlüssel auf seinem Pfad vom Blatt hinauf zur Wurzel. Das sind log₂N + 1 Stück. Ein Knoten steht somit für eine Gerätemenge, nämlich alle unter ihm liegenden Geräte. Der Lizenz-Header enthält den Filmschlüssel. Dieser wird für jede Menge in einer ausgewählten Kollektion einmal verschlüsselt. Diese Kollektion deckt alle legitimen Geräte ab und lässt die kompromittierten aus. Ein Gerät zu widerrufen bedeutet lediglich, eine andere Kollektion zu wählen.

Was die einzelnen Symbole bedeuten

N: die Gesamtzahl der Geräte, hier immer eine Zweierpotenz, damit der Baum vollständig besetzt ist
r: die Anzahl der Geräte, die kompromittiert sind und ausgeschlossen werden müssen
S(i,j): die Teilmengendifferenz: jedes Gerät unter Knoten i, ausgenommen jene unter Knoten j. Genau dadurch kann ein einzelner Header-Eintrag ein fehlerhaftes Blatt überspringen

Setzt voraus: Dass ein widerrufenes Gerät nicht repariert, sondern nur ausgeschlossen werden kann. Außerdem vergisst es die einmal erhaltenen Schlüssel niemals. Genau das meint der Begriff „stateless receiver“ im Titel der Publikation. Aus diesem Grund ist die Lösung ein Überdeckungsproblem und kein Schlüsselaustausch. Niemand kann einem Gerät einen neuen Schlüssel senden. Das kompromittierte Gerät würde diesen nämlich ebenfalls empfangen.
Versagt, wenn: Wenn die kompromittierten Geräte gleichmäßig verteilt sind. Beide Verfahren arbeiten am effizientesten bei einem Block aufeinanderfolgender Seriennummern. Am schlechtesten schneiden sie ab, wenn jedes zweite Gerät betroffen ist. In diesem Fall ist kein Teilbaum sauber. Der Header benötigt dann für jedes verbleibende Gerät einen eigenen Eintrag. Das ist exakt der Preis, den du auch ganz ohne ein solches Verfahren zahlen würdest.

Der Header weiß nicht, wie viele Geräte es gibt 🖖

Setz die Zahl der kompromittierten Geräte auf 10 und zieh an der Systemgröße. Der vollständige Teilbaum benötigt 58 Schlüssel bei 1.024 Geräten, 98 bei 16.384, 158 bei 1.048.576 und 198 bei 16.777.216. Jede Verdopplung des Systems fügt einen weiteren Schlüssel pro kompromittiertem Gerät hinzu. Jedes von ihnen braucht nämlich eine Teilmenge für jeden Geschwisterknoten auf seinem Pfad zur Wurzel. Die Teilmengendifferenz zeigt bei allen vier Größen 13 an. Nicht 13 und dann 14. Es bleibt dieselbe 13. Und es ist die gleiche 13 bei jeder Größe ab 512 Geräten aufwärts. Das ist eine Zweiunddreißigtausendfachung des Systems bei exakt null Veränderung. Eine Teilmenge in der Teilmengendifferenz bedeutet „alle unter Knoten i außer denen unter Knoten j“. Ein einziger Eintrag kann also den Schlüssel an 1.048.575 Geräte übergeben und ihn diesem einen vorenthalten. Die Tiefe, in die er dabei nach unten reicht, kostet nichts. Genau deshalb lautet die Schranke 2r − 1 und kommt komplett ohne N aus. Es ist auch der Grund, warum der Media Key Block auf einer Blu-ray-Disc ein Teilmengendifferenz-Baum ist. Die Studios fügen zwanzig Jahre lang Geräte hinzu, und der Header bemerkt es nicht einmal.

Jedes Gerät zahlt den Preis, ein einziges Mal 🖖

Schau dir die letzte Tabellenzeile an. Ein vollständiger Teilbaum verlangt von jedem Gerät log₂N + 1 Schlüssel. Bei einer Million Geräten sind das 21, nämlich die Knoten auf dem eigenen Pfad zur Wurzel. Die Teilmengendifferenz verlangt ½log₂²N + ½log₂N + 1, was 211 ergibt. Das ist der zehnfache Speicherplatz, um den Header bei zehn verstreuten kompromittierten Geräten auf ein Zwölftel der Größe zu schrumpfen. Bei vierundsechzig ist es ein Elftel. Dieser Handel leuchtet erst ein, wenn du bemerkst, welche Zahl wie oft bezahlt wird. Die Schlüssel wandern ein einziges Mal im Werk in das Gerät. Der Header hingegen geht für immer mit jeder Lizenz für jeden Titel an jedes Gerät hinaus. 211 Schlüssel sind 3,4 kB Flash-Speicher. Jedes dieser Millionen Geräte ruft dann jedes Mal einen Header von 13,5 kB statt 1,23 kB ab, wenn es nach einer Lizenz fragt. Das ist dasselbe Argument in die andere Richtung gedacht.

Wen du widerrufst, ist wichtiger als wie viele 🖖

Klick auf Eine Charge pro Million und danach auf 64 verstreut pro Million. Dieselben 64 Geräte werden widerrufen. Der Header der Teilmengendifferenz springt von 3 Schlüsseln auf 77. Der Header des vollständigen Teilbaums schnellt von 17 auf 846 hoch. Nichts hat sich geändert, außer der Position der defekten Geräte im Baum. Blätter werden in der Reihenfolge der Herstellung vergeben, was genau das zu einem Hebel macht. Eine kompromittierte Produktionsreihe, ein geklontes Modell, eine Region. Alles, was einen zusammenhängenden Block sperrt, ist beinahe kostenlos. Tausend einzeln geknackte Boxen aus tausend verschiedenen Läden sind es nicht. Klick für das andere Extrem auf Jedes zweite Gerät. Die Hälfte der Geräte wird abwechselnd gesperrt. Beide Verfahren benötigen nun 32 Schlüssel für 32 Überlebende. Das ist genau das, was du auch ganz ohne Verfahren bezahlen würdest.

Aufgaben vollständig gelöst

Woher kommt die 2r − 1? Das Tool gibt sie in der vierten Zeile aus, und auf ihr ruht das gesamte Verfahren: Unabhängig von der Systemgröße braucht ein Subset-Difference-Header nie mehr als zwei Einträge pro kompromittiertem Gerät. Der Beweis ergibt sich durch einfaches Abzählen im Algorithmus und passt auf vier Zeilen.

Öffne diese Aufgabe im Tool
1. Beginne mit dem Grundgerüst: der Vereinigung aller Pfade von der Wurzel zu den r kompromittierten Blättern. Jedes Blatt dieses Gerüsts ist ein kompromittiertes Gerät. Es beginnt also mit r Blättern, und die einzige Aufgabe des Algorithmus ist es, diese abzuarbeiten.
  
  $ST (R) has r leaves$
2. Eine Runde: Finde einen Knoten v, dessen zwei Äste jeweils genau ein verbleibendes Blatt enthalten. Gib für jeden Ast, der mehr als ein bloßes Blatt ist, ein Subset aus – also höchstens zwei Subsets. Reduziere dann alles unterhalb von v, sodass v selbst zu einem Blatt wird.
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. Zähle nach, was diese Runde mit den Blättern gemacht hat. Zwei sind verschwunden und eines ist dazugekommen. Das Gerüst ist somit ein Blatt kürzer, völlig unabhängig davon, wie der Baum aussah.
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. Es gibt also exakt r − 1 Runden, bis ein einziges Blatt übrig bleibt. Jede davon fügt höchstens 2 Subsets hinzu. Danach folgt ein letztes Subset für den Rest, der über diesem letzten Blatt verbleibt.
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. In dieser ganzen Überlegung kam die Baumtiefe nicht vor, und genau das ist der Punkt. Eine Runde kostet dasselbe, ob v nun drei oder dreißig Ebenen tiefer liegt.
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. Diese Schranke ist zudem fast überall unscharf, weil in jeder Runde beide Subsets ausgegeben werden müssten. Bei über 200 zufällig erzeugten Widerrufslisten in einem System mit 1.048.576 Geräten hat der durchschnittliche Header 1,2513 Schlüssel pro kompromittiertem Gerät bei 64 widerrufenen, 1,2520 bei 32 und 1,2580 bei 10. Die theoretische Grenze liegt bei 2. Der Richtwert für den Entwurf eines Lizenzformats liegt also bei etwa 1,25r, und der garantierte Wert ist 2r − 1.
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
Antwort

Höchstens 2 Subsets pro Runde, r − 1 Runden, plus 1 zum Abschluss: 2(r − 1) + 1 = 2r − 1. Nirgends taucht darin ein N auf. Die Complete-Subtree-Schranke für die gleichen Widerrufe lautet r·log₂(N/r). Genau diesen Term log₂(N/r) eliminiert die Subset-Difference – der Preis dafür sind ½log₂²N + ½log₂N + 1 Schlüssel in jedem Gerät anstelle von log₂N + 1.

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
Was kostet ein echter Media Key Block? Das Tool zählt einen Header in Einträgen, das ist die reine Mathematik. Eine Blu-ray Disc speichert ihn in Bytes, in einem Format, das jeder auslesen kann: Die AACS-Spezifikation legt exakt fest, wie eine Subset-Difference notiert wird. Die Größe des Headers auf einer echten Disc lässt sich also berechnen und nicht nur schätzen.

Öffne diese Aufgabe im Tool
1. AACS identifiziert jede Subset-Difference über eine Ein-Byte-Maske u und eine Vier-Byte-Nummer uv. Dazu kommen sechzehn Bytes an verschlüsselten Schlüsseldaten. In den eigenen Worten der Spezifikation: „Für jede Subset-Difference im Identifikationsteil gibt es 16 Bytes an Schlüsseldaten im Schlüsseldatenteil.“ Einundzwanzig Bytes pro Subset. Sonst absolut nichts.
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. Die Überdeckung selbst berechnet das Tool. In der Praxis sind es etwa 1,25 Einträge pro widerrufenem Gerät, niemals mehr als zwei.
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. Ein Media Key Block benötigt also ungefähr sechsundzwanzig Bytes pro widerrufenem Gerät. Das ist die komplette Größenberechnung. Sie verläuft linear zur Anzahl der ausgesperrten Player, ohne dass die Systemgröße irgendwo eine Rolle spielt.
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. Stelle die beiden Verfahren bei identischen Widerrufen gegenüber. Die Subset-Difference-Spalte ist das, was tatsächlich ausgeliefert wird. Die Complete-Subtree-Spalte zeigt, was dieselben Widerrufe unter dem einfacheren Verfahren gekostet hätten.
  
  $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. In der zweiten Spalte kommt die Baumhöhe ins Spiel. Bei einem System mit 2³¹ Geräten – das Maximum, das eine 32-Bit-uv-Nummer adressieren kann – kostet der Widerruf von tausend Playern etwa 21.000 Complete-Subtree-Einträge gegenüber 1.250 Subset-Difference-Einträgen. Denn log₂(2³¹/1000) ist ungefähr 21, und jedes widerrufene Gerät zahlt diesen Preis.
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
Antwort

Ein Media Key Block erfordert grob 26 Bytes pro widerrufenem Gerät: 2,6 kB für hundert Player, 26 kB für tausend, 262 kB für zehntausend. Selbst im schlechtesten von der Schranke erlaubten Fall sind es nie mehr als 42 kB, 420 kB und 4,2 MB. Complete Subtree bräuchte 442 kB, wo Subset Difference mit 26 kB auskommt. Daraus folgen zwei Dinge, die das Tool nicht ausgibt. Die Disc wird einmal gepresst und zwanzig Jahre lang gelesen. Ein MKB wächst folglich immer nur. Deshalb ist der Identifikationsteil fünf Bytes lang und keine vollständige Knotenadresse. Aus demselben Grund lagert das Format die Schlüsseldaten in einen separaten Block aus, statt sie zu verschachteln. Und ein 26 kB großer Header fällt auf einer 25 GB großen Disc kaum ins Gewicht. Subset Difference gewann nie wegen der Bytes. Es siegte, weil die Alternative mit der Systemgröße wächst und eine heute gepresste Disc auch die Geräte des Jahres 2040 bedienen muss.

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

Lernpfad

Einen Stream schützen: Ein Gerät widerrufen, dann herausfinden, welches

Quellen (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.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.