Das Wasserzeichen, das eine Kollusion übersteht

Gib jedem Abonnenten eine Kopie mit einem eigenen Bitmuster, und ein geleakter Film verrät den Täter. Eine Gruppe, die ihre Kopien zusammenlegt, sieht die Unterschiede und wählt, was sie dort einsetzt. Stell ein, wie viele es sind, wie lang die Folge ist und wie viele Abonnenten du auf keinen Fall fälschlich beschuldigen darfst.

Rechenbeispiel — Das Wasserzeichen, das eine Kollusion übersteht

Nötige Länge für diese Gruppe und Größe	2.490 Bit · 311 B
Tatsächlich eingebettete Länge	3.200 Bit · 400 B
Kolludierer über dem Schwellenwert	3 von 4
Score des schwächsten Kolludierers	230,9
Spalten, die sie nicht ändern können	52,3%
Score eines typischen Kolludierers	262,4
Streuung eines unschuldigen Scores	42,8
Schwellenwert für Beschuldigung	239,9

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 — Das Wasserzeichen, das eine Kollusion übersteht

Ein Fingerprinting-Code versorgt jeden Abonnenten mit einer Kopie desselben Films, die eine individuelle Folge von m Bits trägt. So verrät eine durchgesickerte Kopie sofort ihren Empfänger. Die Bits werden dabei nicht gleichförmig verteilt. Jede Position j bekommt eine eigene Wahrscheinlichkeit p_j, die so ausgelost wird, dass die meisten Positionen über die gesamte Nutzerschaft hinweg fast ausschließlich Einsen oder fast ausschließlich Nullen zeigen. Legt eine Gruppe ihre Kopien zusammen, bemerkt sie eine Position nur dort, wo sich ihre eigenen Bits unterscheiden. Der Beschuldigungswert summiert schließlich für jede Stelle, an der die Fälschung eine Eins aufweist, wie überraschend das Bit des jeweiligen Abonnenten war.

Was die einzelnen Symbole bedeuten

m: die Länge des Codes in Bits, worum sich diese gesamte Lektion dreht
c: wie viele Abonnenten ihre Kopien zusammenlegen
Z: die Beschuldigungsschwelle: Ein Wert darüber benennt jemanden

Setzt voraus: Die Markierungsannahme: Zeigt jede Kopie innerhalb der Gruppe das gleiche Bit, kann die Gruppe diese Position weder bemerken noch verändern. Alles auf dieser Seite beruht darauf. In einem echten System ist dies eine Annahme über die Einbettung. Eine Markierung, die du durch den bloßen Vergleich von Kopien nicht siehst, kannst du auch nicht entfernen. In der Praxis wird exakt dieser gestalterische Ansatz angegriffen und nicht die reine Mathematik.
Versagt, wenn: Wenn die Zahl der Kolludierer größer ist, als beim Design des Codes vorgesehen. Das System versagt dann nicht allmählich. Die Werte der Schuldigen sinken proportional zu 1/c, während die Messlatte dort bleibt, wo die unschuldigen Nutzer sie verankern. Ein Code, der für vier ausreicht und auf acht Angreifer trifft, benennt deshalb nicht einfach etwas seltener jemanden. Er benennt niemanden.

Doppelt so viele Kolludierer, viermal so viel Wasserzeichen 🖖

Zieh den Schieberegler für die Kollusion und betrachte die erste Karte. Zwei Kolludierer benötigen 623 Bit, vier brauchen 2.490, acht 9.959 und sechzehn 39.833. Jede Verdopplung vervierfacht die Länge, und das dreimal hintereinander. Das Verhältnis zu c² landet bei allen vier Werten zwischen 155,60 und 155,75. Dass es nicht exakt vier ist, liegt nur daran, dass eine Länge eine ganze Zahl von Bits sein muss: Die Verhältnisse betragen 3,9968, 3,9996 und 3,9997. Der Grund dafür findet sich auf den beiden Karten daneben, die für sich betrachtet gar nicht rätselhaft sind. Der Score eines Kolludierers ist das Beweismaterial, das der Code über ihn sammelt. Da sie es sich teilen, wächst es wie die Länge geteilt durch die Anzahl der Kolludierer. Der Score eines unschuldigen Abonnenten ist eine Irrfahrt derselben Länge. Seine Streuung wächst also wie die Quadratwurzel der Länge. Beweismaterial geteilt durch Rauschen verhält sich demnach wie m/c geteilt durch √m, also √m/c. Hält man diesen Wert konstant und verdoppelt c, muss sich m vervierfachen. Alles Weitere auf dieser Seite folgt direkt aus diesen beiden Beobachtungen.

Die Hürde wird von den Menschen bestimmt, die du nicht beschuldigen darfst 🖖

Klick auf Vier Täter, langer Code und dann auf Zehn Millionen Abonnenten. Die Kolludierer sind dieselben vier Personen mit denselben Kopien und derselben Fälschung. Der Schwellenwert verschiebt sich von 239,9 auf 254,5, und einer weniger von ihnen wird enttarnt. Das Verbrechen ist exakt dasselbe geblieben. Nur die Zahl der unschuldigen Abonnenten hat sich verändert. Der Schwellenwert ist nämlich gar keine Eigenschaft der Beweislage. Er ist das Niveau, das ein unschuldiger Score über die gesamte Abonnentenbasis hinweg nur einmal in tausend Durchläufen zufällig überschreitet. Zehnmal so viele Abonnenten bedeuten also, dass für jeden Einzelnen strengere Maßstäbe angelegt werden müssen. Das ist die Korrektur für multiples Testen, die sonst unvorsichtige Statistiken ruiniert, hier aber ausnahmsweise etwas Nützliches tut. Sie ist das Einzige, was zwischen einem Wasserzeichen-System und einem fälschlich beschuldigten Kunden steht.

Der Code ist bemessen, um einen zu fassen, nicht alle 🖖

Lass es bei genau der Länge, die die erste Karte fordert, vierzigmal mit verschiedenen Codes laufen: In 38 von 40 Durchgängen wird mindestens ein Kolludierer enttarnt, wenn vier von ihnen zusammenarbeiten. Alle vier werden in keinem einzigen enttarnt. Verlängere den Code um die Hälfte, und in 15 von 40 Durchläufen fliegen alle vier auf. Klick auf Sechzehn Kolludierer für das andere Extrem. Dort liegen 10 von 16 über der Hürde und dem schwächsten fehlen 270 Punkte. Darin liegt ein seltsamer Trost für das Studio. Eine größere Gruppe macht es zwar schwerer, jedes einzelne Mitglied zu überführen, sorgt aber gleichzeitig fast unweigerlich dafür, dass irgendjemand erwischt wird, da mehr Beteiligte Fehler machen können. Bei der geforderten Länge liefern vier Kolludierer in 38 von 40 Durchläufen einen Namen, sechzehn Kolludierer in 40 von 40.

Aufgaben vollständig gelöst

Woher stammt die Zahl 2.490? Das Werkzeug gibt sie für vier Kollusoren unter einer Million Abonnenten aus. Dabei handelt es sich nicht um einen simulierten Wert. Sie ergibt sich aus zwei empirischen Gesetzmäßigkeiten und einer Entscheidung darüber, wie oft du bereit bist, einen Unschuldigen zu beschuldigen. Die Herleitung umfasst vier Zeilen, wobei die letzte das Quadrat hervorbringt.

Öffne diese Aufgabe im Tool
1. Die Spuren, die ein Kollusor hinterlässt, wachsen proportional zur Code-Länge und verteilen sich auf die gesamte Gruppe. Jede von ihnen kontrollierte Spalte haben schließlich alle gemeinsam manipuliert. Gemessen über Koalitionen von 2 bis 16 und Codes von 800 bis 51.200 Bits ergibt sich ein Wert von etwa 0,34 m/c.
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. Der Score eines unschuldigen Abonnenten ist die Summe von m unabhängigen Beiträgen mit Erwartungswert null. Er entspricht somit einer Irrfahrt. Seine Streuung wächst mit der Wurzel der Länge, nicht mit der Länge selbst. Gemessen: etwa √(m/2).
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. Lege fest, wie oft du einen Unschuldigen beschuldigen willst: höchstens ε in einer Population von n. Ein einzelner Abonnent muss daher mit einer Wahrscheinlichkeit von 1 − ε/n freigesprochen werden, was bei einer Million Abonnenten und einer Chance von eins zu tausend einem Abstand von 6,00 Standardabweichungen entspricht.
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. Für eine erfolgreiche Erkennung müssen die Spuren diese Hürde nehmen. Setze die beiden Gesetze ein und löse nach m auf.
  
  $0.34 \frac{m}{c} > z \frac{m}{2} ⟹ m > \frac{z c}{0 . 34 2} ⟹ m > 4.3253 z^{2} c^{2}$
5. Das c steht im Quadrat, und darin liegt die gesamte Antwort: 2.490 Bits für vier Kollusoren und 9.959 für acht. Bis auf das Aufrunden auf ganze Bits ist das genau das Vierfache.
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. Die für das Systemdesign relevante Zahl ist nicht diejenige, die dir ein mathematischer Beweis liefert. Tardos' eigener Satz garantiert dies mit 100c²⌈ln(n/ε)⌉ Bits, was hier 2.100c² entspricht. Das ist dreizehnmal mehr als die Gauß-Schätzung, da ein Beweis gegen jede denkbare Kollusionsstrategie standhalten muss und nicht nur gegen die drei auf dieser Seite.
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
Antwort

m > (z c √(1/2) ÷ 0,34)² = 4,3253 z² c², was bei z = 5,9978 einen Wert von 155,60 c² ergibt, bevor auf ganze Bits aufgerundet wird: 623 Bits für zwei Kollusoren, 2.490 für vier, 39.833 für sechzehn. In Bytes sind das 78 B, 311 B und 4,98 kB an Wasserzeichen-Payload. Diese Längen sind so gering, dass sie dich in der Praxis fast nie ausbremsen. Genau aus diesem Grund drehen sich die Fachdiskussionen stattdessen auch eher um die Markierungsannahme. Das Einzige, wogegen du das Quadrat nicht eintauschen kannst, ist das Publikum. n geht nur über z ein, was wie √(log n) wächst. Ein Sprung von tausend Abonnenten auf zehn Millionen erhöht die Länge also lediglich von 1.564 auf 2.801 Bits. Das ist ein Anstieg von 79 %, während eine einzige Verdopplung der Koalitionsgröße sofort 300 % kostet.

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
Braucht ein Streamingdienst so etwas überhaupt? Schritt eins dieser Reihe behandelt eine Welt, in der jede Kopie identisch ist und es keine Möglichkeit gibt, mit einem Endgerät zu kommunizieren. Ein Abonnementdienst ist das genaue Gegenteil. In der Dokumentation von Widevine heißt es selbst, dass eine Lizenzanfrage über HTTPS an einen Lizenzserver geht und „die Inhalte der Lizenz nicht mehr veränderbar sind und für das anfragende Gerät individualisiert werden“. Was bleibt da von der Mathematik noch übrig?

Öffne diese Aufgabe im Tool
1. Die Hälfte davon entfällt komplett. Mit einem Rückkanal gibt es keinen Header, den man abdecken müsste. Ein Gerät auszuschließen kostet im Stream nichts, da du ihm schlichtweg keine Lizenz ausstellst. Das gesamte Abdeckungsproblem aus Schritt eins ist der Preis für den fehlenden Rückkanal. Eine Disc kann schließlich nicht fragen, wer sie gerade abspielt.
2. Die andere Hälfte bleibt bestehen und wird sogar noch wichtiger. Ein Lizenzserver blockiert ein Gerät, wenn er weiß, dass es kompromittiert ist. Er kann aber einen unauffälligen Abonnenten nicht daran hindern, das legitim Entschlüsselte aufzuzeichnen. Dieses Leak trägt einen Fingerabdruck, und dieser Fingerabdruck ist das Einzige, was die Person namentlich identifiziert.
3. Die Frage der Dimensionierung für einen echten Abonnentenstamm klärst du also auf dieser Seite. Die Codelänge wächst mit dem Quadrat der Koalition, mit dem Publikum hingegen nur über einen Logarithmus.
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. Lies die Tabelle erst zeilenweise und dann spaltenweise. Sechzehn Kollusoren kosten das Vierundsechzigfache von zwei Kollusoren. Zehntausend Abonnenten auf hundert Millionen zu skalieren, was vier Größenordnungen entspricht, kostet das 1,66-Fache.
  
  $n 1 0^{4} 1 0^{5} 1 0^{6} 1 0^{7} 1 0^{8} c = 2 468545623701779 c = 4 1, 871 2, 180 2, 490 2, 801 3, 113 c = 8 7, 484 8, 719 9, 959 11, 202 12, 449 c = 16 29, 933 34, 873 39, 833 44, 808 49, 795 \frac{m ( 1 0 ^{8} )}{m ( 1 0 ^{4} )} = \frac{3 , 113}{1 , 871} = 1.66 against \frac{m ( c = 16 )}{m ( c = 2 )} = 64$
5. Bei zehn Millionen Abonnenten und vier Kollusoren sind das 2.801 Bits: dreihundertfünfzig Bytes an Payload für einen Film von etlichen Gigabytes.
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
Antwort

Die Code-Länge ist nie das eigentliche Problem. 350 Bytes fallen bei Inhalten im Milliarden-Byte-Bereich kaum ins Gewicht, und auch ein tausendmal größeres Publikum kostet nur zwei Drittel zusätzlich und nicht das Tausendfache. Die Koalition ist der einzige Faktor, der wirklich schmerzt, da er als einziger quadriert wird. Wie viele Leute ihre Kopien tatsächlich zusammenlegen werden, ist dabei ausgerechnet die einzige Größe der gesamten Rechnung, die niemand im Voraus messen kann. Die eigentliche Entwicklungsarbeit bei einem realen System fließt nicht in diese Arithmetik, sondern vielmehr in die Robustheit der Markierung, damit sie Neukodierungen, Bildzuschnitte und selbst eine auf den Bildschirm gerichtete Kamera übersteht. Die Markierungsannahme muss auch dann noch aufrechterhalten bleiben, wenn der Angreifer zwei Kopien und ein Tool zur Differenzbildung besitzt.

$m \propto c^{2} lo g \frac{n}{ε} : \times 64 in c, \times 1.66 in n$

Lernpfad

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

Quellen (4)

Worked problem 2 turns on a streaming service working the other way round from step 1 of the series, and this is the vendor's own description of the licence flow: Google, "Widevine DRM Overview", developers.google.com/widevine/drm/overview.
The code this page builds, the accusation score it computes, and the c² the whole lesson is about: G. Tardos, "Optimal probabilistic fingerprint codes." Journal of the ACM 55(2), 2008, pp. 1–24. First published in STOC 2003, pp. 116–125.
Where the marking assumption comes from, and the proof that some length is unavoidable: D. Boneh and J. Shaw, "Collusion-secure fingerprinting for digital data." IEEE Transactions on Information Theory 44(5), 1998, pp. 1897–1905.
Why a studio cares: this is the other half of the same specification as step 1 of the series, and forensic marks are what it falls back on when revocation is too slow. AACS LA, Advanced Access Content System (AACS): Introduction and Common Cryptographic Elements, Revision 0.91, 17 February 2006.

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