La marca de agua que sobrevive a una colusión

Entrega a cada suscriptor una copia con su propio patrón de bits y una película filtrada delatará al responsable. Un grupo que junta sus copias puede ver dónde difieren y decidir qué poner en esos puntos. Ajusta cuántos son, qué longitud tiene la cadena y a cuántos suscriptores no debes acusar por error.

Ejemplo resuelto — La marca de agua que sobrevive a una colusión

Longitud necesaria	2490 bits · 311 B
Longitud real incluida	3200 bits · 400 B
Coludidos sobre el umbral	3 de 4
Puntuación del coludido más débil	230,9
Columnas que no pueden tocar	52,3%
Puntuación de coludido medio	262,4
Dispersión de un inocente	42,8
Umbral de acusación	239,9

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — La marca de agua que sobrevive a una colusión

Un código de huella digital asigna a cada suscriptor una copia de la misma película con una cadena distinta de m bits, para que cualquier copia filtrada delate a quién se le entregó. Los bits no se eligen de manera uniforme. Cada posición j recibe su propio sesgo p_j, extraído de forma que la mayoría de las posiciones sean casi todas unos o casi todas ceros en toda la base de suscriptores. Un grupo que combina sus copias solo puede detectar una posición allí donde sus propios bits difieren. La puntuación de acusación suma, a lo largo de las posiciones donde la falsificación muestra un uno, cuán sorprendente resultaba el bit de cada suscriptor.

Qué significa cada símbolo

m: la longitud del código en bits, que es de lo que trata toda la lección
c: cuántos suscriptores combinan sus copias
Z: el umbral de acusación: una puntuación por encima de este señala a alguien

Supone: El supuesto de marcado: allí donde cada copia de la coalición lleva el mismo bit, no pueden percibir que esa posición existe ni pueden cambiarla. Todo lo que verás en esta página se apoya en esto. En un sistema real es una afirmación sobre la incrustación (que una marca que no puedes ver al comparar copias es una marca que no puedes borrar) y es esta parte del diseño la que recibe los ataques, no la aritmética.
Falla cuando: Cuando el número de cómplices supera la capacidad para la que se diseñó el código. No hay una degradación progresiva. Las puntuaciones de los culpables caen como 1/c mientras que el listón se mantiene donde lo pone la población inocente. Por tanto, un código lo bastante largo para cuatro pero que se enfrenta a ocho no delata a alguien con un poco menos de frecuencia, sino que no delata a nadie.

El doble de coludidos, el cuádruple de marca de agua 🖖

Arrastra el control de colusión y observa la primera tarjeta. Dos coludidos necesitan 623 bits, cuatro necesitan 2.490, ocho necesitan 9.959 y dieciséis necesitan 39.833. Cada duplicación multiplica la longitud por cuatro, tres veces seguidas, y la proporción respecto a c² se sitúa entre 155,60 y 155,75 en los cuatro casos. No es exactamente cuatro solo porque una longitud es un número entero de bits: las proporciones son 3,9968, 3,9996 y 3,9997. La razón se encuentra en las dos tarjetas de al lado y ninguna de ellas encierra un misterio por sí sola. La puntuación de un coludido es la prueba que el código recopila sobre ellos, y se la reparten. Crece de forma proporcional a la longitud dividida por el número de coludidos. La puntuación de un suscriptor inocente es un paseo aleatorio de la misma longitud, por lo que su dispersión crece como la raíz cuadrada de la longitud. Por tanto, la relación entre prueba y ruido avanza como m/c dividido por √m, lo que da √m/c. Mantener esto constante mientras c se duplica significa que m debe cuadruplicarse. Todo lo demás en esta página es consecuencia de esas dos líneas.

El límite lo marca la gente a la que no debes acusar 🖖

Pulsa Cuatro, longitud válida y luego Diez millones en total. Los coludidos son las mismas cuatro personas con las mismas copias y la misma falsificación. El umbral pasa de 239,9 a 254,5 y se delata a uno menos de ellos. No ha cambiado nada sobre el delito; lo que cambió fue el tamaño de la población inocente. El umbral no es en absoluto una propiedad de las pruebas. Es el nivel que una puntuación inocente supera por accidente solo una vez de cada mil en toda la base de suscriptores. Que haya diez veces más suscriptores significa someter a cada uno a una prueba más estricta. Esa es la corrección por comparaciones múltiples que arruina las estadísticas descuidadas, haciendo algo útil por una vez: es lo único que se interpone entre un sistema de marcas de agua y un cliente acusado falsamente.

El código se diseña para atrapar a uno, no a todos 🖖

Con la longitud exacta que exige la primera tarjeta, ejecútalo cuarenta veces con códigos diferentes. Al menos un coludido sale a la luz en 38 de las 40 ejecuciones cuando cuatro de ellos se asocian, y los cuatro completos en ninguna. Si haces el código una vez y media más largo, los cuatro salen en 15 de 40 ejecuciones. Pulsa Dieciséis coludidos para ver el extremo opuesto, donde 10 de 16 superan el umbral y el más débil se queda a 270 puntos. El estudio encuentra aquí un extraño consuelo. Una colusión mayor hace que cada miembro sea más difícil de condenar, pero asegura casi por completo que alguien caiga, porque al ser más, resulta más probable que alguno falle. Con la longitud necesaria, cuatro coludidos dan un nombre en 38 de 40 ejecuciones y dieciséis coludidos en 40 de 40.

Problemas resueltos al detalle

¿De dónde sale 2.490? La herramienta lo calcula para cuatro cómplices entre un millón de suscriptores. No es un número simulado: nace de dos leyes empíricas y de tu decisión sobre la frecuencia con la que toleras acusar a un inocente. La deducción ocupa apenas cuatro líneas. La última produce el cuadrado.

Abre este problema en la herramienta
1. La evidencia que deja un cómplice es proporcional a la longitud del código y se reparte entre todos ellos. Cada columna que controlan es el resultado de un esfuerzo conjunto. Las mediciones en coaliciones de 2 a 16 usuarios y códigos de 800 a 51.200 bits arrojan un valor de unos 0,34 m/c.
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. La puntuación de un suscriptor inocente suma m aportaciones independientes de media cero; un camino aleatorio. Su dispersión crece con la raíz cuadrada de la longitud, no en proporción directa. El valor medido ronda √(m/2).
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. Elige con qué frecuencia acusarás a un inocente: como máximo ε en una población de n. Para exculpar a un suscriptor necesitas 1 − ε/n. Con un millón de usuarios y una probabilidad entre mil, esto te sitúa a 6,00 desviaciones típicas.
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. Para que haya detección, la evidencia debe superar ese umbral. Combina ambas leyes y despeja m.
  
  $0.34 \frac{m}{c} > z \frac{m}{2} ⟹ m > \frac{z c}{0 . 34 2} ⟹ m > 4.3253 z^{2} c^{2}$
5. La variable c queda dentro del cuadrado, y ahí reside toda la respuesta. Necesitas 2.490 bits para cuatro cómplices y 9.959 para ocho. Hablamos del cuádruple, salvo por el redondeo a números enteros.
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. La cifra que debes usar al diseñar un sistema no es la que te daría una demostración matemática. El teorema original de Tardos lo garantiza con 100c²⌈ln(n/ε)⌉ bits, que aquí serían 2.100c². Es una estimación trece veces mayor que la gaussiana. Una prueba formal tiene que resistir cualquier estrategia de colusión imaginable, no solo las tres de esta página.
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
Respuesta

m > (z c √(1/2) ÷ 0,34)² = 4,3253 z² c², que para z = 5,9978 equivale a 155,60 c² antes de redondear al alza a bits enteros. Son 623 bits para dos cómplices, 2.490 para cuatro y 39.833 para dieciséis. En bytes hablamos de 78 B, 311 B y 4,98 kB de carga útil. Es tan poco espacio que la longitud casi nunca será el problema que te frene. Por eso los expertos prefieren discutir la premisa de la marca. Lo único que no puedes compensar frente a ese cuadrado es la audiencia. La n interviene solo a través de la z, que aumenta como √(log n). Pasar de mil suscriptores a diez millones alarga el código de 1.564 a 2.801 bits. Es una subida del 79%, mientras que duplicar la coalición una sola vez eleva el coste un 300%.

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
¿Para qué necesita esto una plataforma de streaming? El primer paso de esta serie describe un entorno donde todas las copias son idénticas y resulta imposible comunicarse con el dispositivo. Un servicio de suscripción es el extremo opuesto. La propia documentación de Widevine indica que la solicitud de licencia viaja por HTTPS hasta el servidor y que «el contenido de la licencia ya no se puede modificar y está individualizado para el dispositivo que lo solicita». Entonces, ¿qué nos queda de las matemáticas?

Abre este problema en la herramienta
1. La mitad desaparece por completo. Si dispones de un canal de retorno, no hay cabecera que cubrir. Excluir a un dispositivo del flujo de datos no te cuesta nada, porque basta con no emitirle la licencia. Todo el problema de recubrimiento del primer paso es el precio a pagar por la falta de comunicación. Un disco no puede preguntar quién lo está reproduciendo.
2. La otra mitad no desaparece; se vuelve aún más importante. El servidor de licencias bloquea aquellos dispositivos comprometidos que ya conoce, pero no puede evitar que un suscriptor legítimo grabe lo que acaba de descifrar. Esa filtración lleva una huella digital. Y esa huella es el único elemento que delata su identidad.
3. Así que el problema de dimensionamiento es el que tienes en esta página, con una base de suscriptores real. La longitud del código crece con el cuadrado de la coalición y, en cuanto a la audiencia, solo mediante un logaritmo.
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. Lee la tabla en horizontal y luego en vertical. Dieciséis cómplices cuestan sesenta y cuatro veces más que dos. Pasar de diez mil suscriptores a cien millones (cuatro órdenes de magnitud) multiplica la necesidad por 1,66.
  
  $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. Con diez millones de suscriptores y cuatro cómplices obtenemos 2.801 bits: trescientos cincuenta bytes de carga útil para una película de varios gigabytes.
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
Respuesta

La longitud del código nunca supone un problema. Hablamos de 350 bytes a una escala donde el contenido se mide en miles de millones de bytes. Multiplicar la audiencia por mil solo aumenta la longitud en dos tercios, en lugar de mil veces. El tamaño de la coalición es el único factor que muerde fuerte, porque es el único que queda dentro del cuadrado. Y la cantidad de personas que acabarán juntando sus copias es el único dato de todo el cálculo que nadie puede medir de antemano. Un sistema real no invierte su ingeniería en esta aritmética. La dedica a lograr que la marca resista recodificaciones, recortes y una cámara apuntando a la pantalla, y a sostener la premisa de la marca cuando el atacante dispone de dos copias y una herramienta para buscar diferencias.

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

Ruta de aprendizaje

Proteger una transmisión: revocar un dispositivo y descubrir cuál fue

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

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.