Revogar um dispositivo sem avisar os restantes

Cada dispositivo guarda chaves. Uma delas é exposta, mas a licença tem de continuar a funcionar para todos os outros. Defina o número de dispositivos existentes e quantos foram comprometidos. A ferramenta constrói as duas coberturas definidas por Naor, Naor e Lotspiech em 2001. Depois de desenhar a que escolheu, o sistema contabiliza a carga que o cabeçalho terá de transportar.

Exemplo resolvido — Revogar um dispositivo sem avisar os restantes

Chaves no cabeçalho	4
Tamanho a 16 bytes por chave	64 B

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Revogar um dispositivo sem avisar os restantes

Na criptografia de difusão, o mesmo filme encriptado chega a todos os dispositivos e a licença determina quem o consegue decifrar. Disponha os dispositivos como as folhas de uma árvore binária e atribua a cada nó uma chave própria; um aparelho recebe as chaves presentes no trajeto da sua folha até à raiz, somando log₂N + 1 chaves. Um nó designa então um conjunto de equipamentos, ou seja, todos os seus descendentes. O cabeçalho da licença transporta a chave do filme encriptada uma vez para cada conjunto de uma coleção, a qual engloba os recetores íntegros e exclui os corrompidos. Revogar um dispositivo significa apenas escolher uma coleção diferente.

O que significa cada símbolo

N: o número total de dispositivos, assumindo sempre uma potência de dois para garantir uma árvore completa
r: quantos destes se encontram comprometidos e exigem bloqueio absoluto
S(i,j): o conjunto da diferença de subconjuntos: todos os dispositivos subordinados ao nó i à exceção dos que dependem do nó j, a estrutura que permite a uma entrada do cabeçalho saltar uma única folha corrompida

Pressupõe: Que um equipamento revogado não admite reparação, sofrendo apenas exclusão, e que jamais esquece o material criptográfico que lhe foi fornecido. É esse o significado de "recetor sem estado" no título do artigo. Este detalhe explica o motivo pelo qual a solução reside num problema de cobertura matemática em vez de uma renovação de chaves: torna-se impossível enviar uma nova chave à rede, uma vez que a máquina responsável pela fuga de informação também a iria receber.
Falha quando: Quando os dispositivos comprometidos apresentam uma distribuição uniforme. O rendimento ideal de ambos os esquemas manifesta-se perante um lote de números de série consecutivos. O pior cenário ocorre quando o comprometimento afeta aparelhos alternados. Nessa situação, nenhuma subárvore permanece intata e o cabeçalho passa a exigir uma entrada por cada equipamento sobrevivente. É o preço exato que pagaríamos na ausência de qualquer esquema de proteção.

O cabeçalho ignora a quantidade total de dispositivos 🖖

Defina o número de dispositivos comprometidos como 10 e depois arraste o tamanho do sistema. A subárvore completa pede 58 chaves para 1.024 dispositivos, 98 para 16.384, 158 para 1.048.576 e 198 para 16.777.216. Cada vez que o sistema duplica, acrescenta-se uma chave extra por dispositivo comprometido, porque cada um necessita de um subconjunto para cada nó irmão no seu caminho até à raiz. A diferença de subconjuntos regista 13 chaves nestes quatro tamanhos. Não passa de 13 para 14. São sempre as mesmas 13 chaves para qualquer tamanho a partir de 512 dispositivos. Isto representa um aumento de trinta e duas mil vezes na escala do sistema, a custo zero. Um subconjunto na diferença de subconjuntos significa «todos abaixo do nó i, exceto os do nó j». Por conseguinte, uma única entrada pode entregar a chave a 1.048.575 dispositivos e retê-la daquele que importa. A profundidade a que a operação desce não tem custos. É por isso que o limite superior é 2r − 1 e ignora totalmente a variável N. É também o motivo pelo qual o Media Key Block dos discos Blu-ray utiliza uma árvore de diferença de subconjuntos. Os estúdios continuam a adicionar aparelhos durante vinte anos e o cabeçalho nem sequer dá por isso.

O preço é pago por todos os dispositivos, uma única vez 🖖

Observe a última linha da tabela. A subárvore completa exige log₂N + 1 chaves a cada dispositivo. São 21 chaves para um milhão de aparelhos, correspondentes aos nós no seu próprio caminho até à raiz. A diferença de subconjuntos exige ½log₂²N + ½log₂N + 1, ou seja, 211. Isto significa dez vezes mais espaço de armazenamento. Em troca, permite reduzir o cabeçalho a um doze avos do seu tamanho quando existem dez dispositivos comprometidos dispersos, e a um onze avos para sessenta e quatro. A balança só se torna evidente quando se percebe a frequência com que cada preço é cobrado. As chaves entram no dispositivo uma única vez durante o fabrico. O cabeçalho é distribuído em cada licença, para cada título e para cada aparelho, para sempre. Um bloco de 211 chaves ocupa 3,4 kB de memória flash. Em contrapartida, cada um desse milhão de dispositivos transfere um cabeçalho de 13,5 kB em vez de 1,23 kB de cada vez que pede uma licença, o que corresponde ao mesmo argumento invertido.

Quem é revogado importa mais do que a quantidade 🖖

Selecione Um lote num milhão e depois 64 dispersos num milhão. Revogam-se os mesmos 64 dispositivos. O cabeçalho da diferença de subconjuntos salta de 3 para 77 chaves. O da subárvore completa dispara de 17 para 846. A única diferença reside no local que os dispositivos problemáticos ocupam na árvore. Como as folhas são atribuídas por ordem de fabrico, a posição revela-se um trunfo. Um lote de produção comprometido, um modelo clonado ou uma região inteira formam blocos contíguos e são revogados de forma quase gratuita. Por outro lado, mil consolas craqueadas de forma independente, compradas em mil lojas diferentes, custam caro. Selecione Dispositivos alternados para ver o cenário oposto. Metade dos aparelhos é revogada de forma intervalada e ambos os esquemas pedem 32 chaves para proteger os 32 sobreviventes. É exatamente o mesmo preço que o sistema pagaria se não tivesse qualquer esquema de revogação.

Problemas resolvidos na íntegra

De onde vem o 2r − 1? A ferramenta imprime esse valor na quarta linha. É o número que sustenta todo o esquema: independentemente do tamanho do sistema, um cabeçalho de diferença de subconjuntos nunca precisa de mais do que duas entradas por dispositivo comprometido. A demonstração é um argumento de contagem sobre o algoritmo e cabe em quatro linhas.

Abrir este problema na ferramenta
1. Comece pela espinha dorsal: a união dos caminhos da raiz até às r folhas comprometidas. Cada folha dessa espinha é um dispositivo comprometido. Logo, começa com r folhas, e a única função do algoritmo é consumi-las.
  
  $ST (R) has r leaves$
2. Um ciclo: encontre um nó v em que os seus dois ramos contenham, cada um, exatamente uma folha restante. Emita um subconjunto para cada ramo que seja mais do que uma mera folha, ou seja, no máximo dois subconjuntos. A seguir, comprima tudo o que está abaixo de v para que o próprio v se torne uma folha.
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. Conte o que esse ciclo fez às folhas. Duas desapareceram e uma surgiu. A espinha dorsal ficou com menos uma folha, independentemente do aspeto da árvore.
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. Existem exatamente r − 1 ciclos até que reste uma única folha. Cada um adiciona no máximo 2 subconjuntos. Segue-se um subconjunto de fecho para o que resta acima dessa última folha.
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. Nada neste argumento mencionou a profundidade da árvore. Esse é exatamente o ponto. Um ciclo tem o mesmo custo quer v esteja três níveis abaixo ou trinta.
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. O limite também é folgado em quase todo o lado, porque exige que todos os ciclos emitam ambos os seus subconjuntos. Em 200 conjuntos de revogação semeados em 1.048.576 dispositivos, a média do cabeçalho é de 1,2513 chaves por dispositivo comprometido para 64 revogados, 1,2520 para 32 e 1,2580 para 10, face a um limite de 2. O valor sobre o qual se deve construir um formato de licença é, portanto, de aproximadamente 1,25r, e o valor a garantir é 2r − 1.
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
Resposta

No máximo 2 subconjuntos por ciclo, r − 1 ciclos, mais 1 para fechar: 2(r − 1) + 1 = 2r − 1, sem qualquer N à vista. O limite de subárvore completa é r·log₂(N/r) para as mesmas revogações. E esse log₂(N/r) é exatamente aquilo que a diferença de subconjuntos remove. O preço a pagar é ter ½log₂²N + ½log₂N + 1 chaves dentro de cada dispositivo em vez de log₂N + 1.

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
Quanto custa um Media Key Block real? A ferramenta conta um cabeçalho em entradas, o que corresponde à parte matemática. Um disco Blu-ray carrega-o em bytes, num formato que qualquer pessoa consegue ler: a especificação AACS define ao pormenor como uma diferença de subconjuntos é escrita. Como resultado, o cabeçalho num disco real pode ser medido com precisão em vez de adivinhado.

Abrir este problema na ferramenta
1. O AACS identifica cada diferença de subconjuntos através de uma máscara u de um byte e um número uv de quatro bytes. Traz ainda dezasseis bytes de dados de chave encriptada para a mesma. As palavras da especificação são claras: "para cada diferença de subconjuntos incluída na parte de identificação, existem 16 bytes de dados de chave na parte de dados de chave". Vinte e um bytes por subconjunto, e absolutamente mais nada.
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. A cobertura em si é aquilo que a ferramenta calcula. Cerca de 1,25 entradas por dispositivo revogado na prática. E nunca mais de duas.
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. Logo, um Media Key Block tem cerca de vinte e seis bytes por dispositivo revogado. É este o cálculo de tamanho na sua totalidade. É linear em relação ao número de leitores bloqueados, sem que o tamanho do sistema intervenha em parte alguma.
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. Coloque os dois esquemas lado a lado para as mesmas revogações. A coluna da diferença de subconjuntos é a que chega ao mercado. A coluna da subárvore completa reflete o que essas mesmas revogações teriam custado no esquema mais simples.
  
  $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. A segunda coluna revela o impacto da altura da árvore. Num sistema de 2³¹ dispositivos, que é o maior que um número uv de 32 bits consegue endereçar, revogar mil leitores custa cerca de 21.000 entradas de subárvore completa contra 1.250 de diferença de subconjuntos. Tudo isto acontece porque o log₂(2³¹/1000) é aproximadamente 21, e cada dispositivo revogado paga esse custo.
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
Resposta

Um Media Key Block ocupa cerca de 26 bytes por dispositivo revogado: 2,6 kB para cem leitores, 26 kB para mil e 262 kB para dez mil. E nunca ultrapassa os 42 kB, 420 kB e 4,2 MB no pior cenário permitido pelo limite. A subárvore completa exigiria 442 kB onde a diferença de subconjuntos requer apenas 26 kB. Daqui decorrem duas realidades que a ferramenta não imprime. O disco é prensado uma única vez e lido durante vinte anos, pelo que um MKB só tende a crescer. É por este motivo que a parte de identificação tem cinco bytes em vez de um endereço de nó completo, e a razão pela qual o formato coloca os dados da chave numa sequência separada em vez de os intercalar. Além disso, um cabeçalho de 26 kB não é nada ao lado de um disco de 25 GB. O motivo pelo qual a diferença de subconjuntos venceu nunca foram os bytes. Foi o facto de a alternativa crescer com o tamanho do sistema, quando um disco prensado hoje tem de servir perfeitamente os dispositivos de 2040.

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

Percurso de aprendizagem

Proteger uma transmissão: revogar um dispositivo e depois descobrir qual

Referências (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.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.