Revocar un dispositivo sin avisar a los demás

Cada dispositivo guarda claves. Una de ellas se filtra y la licencia debe seguir funcionando para todos los demás. Establece cuántos dispositivos existen y cuántos están comprometidos. La herramienta construye los dos recubrimientos que Naor, Naor y Lotspiech definieron en 2001, dibuja el que elijas y cuenta lo que debe incluir la cabecera.

Ejemplo resuelto — Revocar un dispositivo sin avisar a los demás

Claves en la cabecera	4
Cabecera a 16 bytes por clave	64 B

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 — Revocar un dispositivo sin avisar a los demás

En el cifrado de difusión, la misma película cifrada llega a todos los dispositivos, y la licencia decide quién puede abrirla. Organiza los dispositivos como las hojas de un árbol binario y asigna a cada nodo su propia clave; un dispositivo recibe las claves de su propio camino desde su hoja hasta la raíz, es decir, log₂N + 1 claves. Un nodo define así un conjunto de dispositivos, formado por todos los que descienden de él, y la cabecera de la licencia transporta la clave de la película cifrada una vez por cada conjunto dentro de una colección que cubre a los dispositivos legítimos y excluye a los comprometidos. Revocar un dispositivo consiste en elegir una colección distinta.

Qué significa cada símbolo

N: cuántos dispositivos existen, aquí siempre una potencia de dos para que el árbol esté completo
r: cuántos de ellos están comprometidos y deben quedar bloqueados
S(i,j): el conjunto de diferencia de subconjuntos: cada dispositivo bajo el nodo i excepto los que están bajo el nodo j, lo que permite que una sola entrada de la cabecera evite una única hoja defectuosa

Supone: Que un dispositivo revocado no puede repararse, solo excluirse, y que jamás olvida las claves que se le asignaron. Esto es lo que significa "receptor sin estado" en el título del artículo, y es la razón por la que la respuesta es un problema de cobertura en lugar de uno de renovación de claves: nadie puede enviarle a un dispositivo una clave nueva, porque el dispositivo que filtró sus claves también la recibiría.
Falla cuando: Cuando los dispositivos comprometidos se distribuyen de forma uniforme. Ambos esquemas alcanzan su máxima eficacia con un lote de números de serie consecutivos, y muestran su peor comportamiento en dispositivos alternos, donde ningún subárbol queda limpio y la cabecera necesita una entrada por cada dispositivo superviviente, el mismo coste que pagarías por no aplicar ningún esquema.

La cabecera no sabe cuántos dispositivos hay 🖖

Ajusta el número de comprometidos a 10 y luego arrastra el tamaño del sistema. Subárbol completo marca 58 claves para 1.024 dispositivos, 98 para 16.384, 158 para 1.048.576, 198 para 16.777.216. Cada vez que el sistema se duplica, se añade una clave más por dispositivo comprometido. Cada uno necesita un subconjunto para cada hermano en su camino hacia la raíz. Diferencia de subconjuntos indica 13 en los cuatro tamaños. No 13 y luego 14. El mismo 13, y ese mismo 13 en cualquier tamaño a partir de los 512 dispositivos. Es un aumento del sistema de treinta y dos mil veces sin ningún cambio. Un subconjunto en este esquema es «todos bajo el nodo i excepto los que están bajo el nodo j». Una sola entrada puede entregar la clave a 1.048.575 dispositivos y ocultársela a ese único descartado. La profundidad que alcanza hacia abajo no cuesta nada. Por eso la cota es 2r − 1 sin ninguna N. Es la razón por la que el Media Key Block de un disco Blu-ray es un árbol de diferencia de subconjuntos: los estudios siguen añadiendo dispositivos durante veinte años y la cabecera ni se entera.

El precio lo paga cada dispositivo, una vez 🖖

Mira la última fila de la tabla. Subárbol completo pide a cada dispositivo log₂N + 1 claves: 21 para un millón de dispositivos, los nodos en su propio camino a la raíz. Diferencia de subconjuntos pide ½log₂²N + ½log₂N + 1, que resulta en 211. Diez veces más almacenamiento para reducir la cabecera a una duodécima parte con 10 dispositivos comprometidos dispersos, y a una undécima parte con 64. Este intercambio solo resulta obvio cuando te fijas en qué cifra se paga con qué frecuencia. Las claves entran en el dispositivo una vez en la fábrica. La cabecera sale con cada licencia para cada título a cada dispositivo para siempre. 211 claves son 3,4 kB de memoria flash. Cada uno de ese millón de dispositivos descarga después una cabecera de 13,5 kB en lugar de una de 1,23 kB cada vez que solicita una licencia. Es el mismo argumento aplicado a la inversa.

A quién revocas importa más que a cuántos 🖖

Pulsa Un lote en un millón y luego 64 dispersos en un millón. Se revocan los mismos 64 dispositivos. La cabecera de diferencia de subconjuntos pasa de 3 claves a 77 y la de subárbol completo de 17 a 846. Nada ha cambiado salvo el lugar que ocupan los dispositivos defectuosos en el árbol. Las hojas se asignan en orden de fabricación, lo que convierte esto en una palanca. Una tirada de producción comprometida, un modelo clonado, una región... cualquier cosa que revoque un bloque contiguo sale casi gratis. Mil aparatos pirateados de forma individual y comprados en mil tiendas distintas, no. Pulsa Dispositivos alternos para ver el otro extremo. La mitad de los dispositivos revocados, alternos, y ambos esquemas necesitan 32 claves para 32 supervivientes. Es exactamente lo que pagarías sin usar ningún esquema.

Problemas resueltos al detalle

¿De dónde sale 2r − 1? La herramienta lo muestra en la cuarta fila y es la cifra que sostiene todo el esquema. Sin importar el tamaño del sistema, una cabecera de diferencia de subconjuntos nunca necesita más de dos entradas por dispositivo comprometido. La demostración es un argumento de conteo sobre el algoritmo y cabe en cuatro líneas.

Abre este problema en la herramienta
1. Empieza por la espina: la unión de los caminos desde la raíz hasta las r hojas comprometidas. Cada hoja de esa espina es un dispositivo comprometido, así que arranca con r hojas. Todo el trabajo del algoritmo consiste en consumirlas.
  
  $ST (R) has r leaves$
2. Una ronda: encuentra un nodo v cuyas dos ramas contengan exactamente una hoja restante cada una. Emite un subconjunto por cada rama que sea algo más que una simple hoja (lo que da un máximo de dos subconjuntos). Luego colapsa todo lo que hay por debajo de v para que este se convierta en una hoja.
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. Cuenta qué le hizo esa ronda a las hojas. Dos desaparecieron y surgió una nueva. La espina tiene ahora una hoja menos, sin importar el aspecto que tuviera el árbol.
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. Por tanto, se producen exactamente r − 1 rondas antes de que quede una sola hoja. Cada una añade como máximo 2 subconjuntos, más un subconjunto final de cierre para lo que queda por encima de esa última hoja.
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. Nada en ese argumento menciona la profundidad del árbol, y esa es la clave. Una ronda cuesta lo mismo tanto si v se encuentra tres niveles por debajo como si está a treinta.
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. La cota también es holgada en casi todos los casos, porque necesita que cada ronda emita ambos subconjuntos. En 200 conjuntos de revocación generados sobre 1.048.576 dispositivos, la cabecera promedio es de 1,2513 claves por dispositivo comprometido con 64 revocados, 1,2520 con 32 y 1,2580 con 10, frente a una cota de 2. Por eso, la cifra de diseño para un formato de licencia ronda el 1,25r, mientras que la cifra a garantizar es 2r − 1.
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
Respuesta

Como máximo 2 subconjuntos por ronda, r − 1 rondas, más 1 de cierre: 2(r − 1) + 1 = 2r − 1, sin ninguna N por ninguna parte. La cota del subárbol completo es r·log₂(N/r) para las mismas revocaciones, y el log₂(N/r) es exactamente lo que elimina la diferencia de subconjuntos. El precio a pagar es guardar ½log₂²N + ½log₂N + 1 claves dentro de cada dispositivo en lugar de log₂N + 1.

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
¿Cuánto cuesta un Media Key Block real? La herramienta cuenta la cabecera en entradas, que es la parte matemática. Un disco Blu-ray la transporta en bytes, en un formato que cualquiera puede interpretar. La especificación AACS detalla con exactitud cómo se escribe una diferencia de subconjuntos, por lo que el tamaño de la cabecera en un disco real se puede calcular en lugar de adivinar.

Abre este problema en la herramienta
1. AACS identifica cada diferencia de subconjuntos mediante una máscara u de un byte y un número uv de cuatro bytes, y transporta dieciséis bytes de datos de clave cifrados para ella. "Para cada diferencia de subconjuntos incluida en la parte de identificación, hay 16 bytes de datos de clave en la parte de datos de clave", según las propias palabras de la especificación. Veintiún bytes por subconjunto, y absolutamente nada más.
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. El recubrimiento en sí es lo que calcula la herramienta. Alrededor de 1,25 entradas por dispositivo revocado en la práctica, y nunca más de dos.
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. Así que un Media Key Block ronda los veintiséis bytes por dispositivo revocado. Ese es todo el cálculo de tamaño, y resulta lineal respecto a la cantidad de reproductores bloqueados, sin que intervenga el tamaño del sistema.
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. Compara los dos esquemas uno junto al otro para las mismas revocaciones. La columna de diferencia de subconjuntos es la que llega al mercado. La columna del subárbol completo indica lo que habrían costado esas mismas revocaciones con el esquema más simple.
  
  $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. En la segunda columna es donde entra en juego la altura del árbol. En un sistema de 2³¹ dispositivos, el máximo que puede direccionar un número uv de 32 bits, revocar mil reproductores cuesta unas 21.000 entradas de subárbol completo frente a 1.250 de diferencia de subconjuntos. Esto sucede porque el log₂(2³¹/1000) es aproximadamente 21 y cada dispositivo revocado paga ese costo.
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
Respuesta

Un Media Key Block requiere unos 26 bytes por dispositivo revocado: 2,6 kB para cien reproductores, 26 kB para mil, 262 kB para diez mil, y nunca supera los 42 kB, 420 kB y 4,2 MB en el peor de los casos que permite la cota. El subárbol completo exigiría 442 kB donde la diferencia de subconjuntos solo necesita 26 kB. De esto se deducen dos cosas que la herramienta no muestra. El disco se prensa una vez y se lee durante veinte años, por lo que un MKB solo puede crecer. Por este motivo, la parte de identificación ocupa cinco bytes en lugar de una dirección de nodo completa, y el formato agrupa los datos de las claves en una sección independiente en vez de intercalarlos. Además, una cabecera de 26 kB resulta insignificante frente a un disco de 25 GB. La razón por la que se impuso la diferencia de subconjuntos nunca fueron los bytes. Lo hizo porque la alternativa crece con el tamaño del sistema, y un disco prensado hoy tiene que dar servicio a los dispositivos de 2040.

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

Ruta de aprendizaje

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

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

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