A Marca de Água que Sobrevive a um Conluio

Dê a cada assinante uma cópia com o seu próprio padrão de bits e um filme vazado identificará o infrator. Um grupo que junte as suas cópias consegue ver onde diferem e escolher o que lá colocar. Defina quantos são, qual o comprimento da sequência e quantos assinantes não deve acusar por engano.

Exemplo resolvido — A Marca de Água que Sobrevive a um Conluio

Tamanho necessário para este conluio e público	2.490 bits · 311 B
Comprimento de fato transportado	3.200 bits · 400 B
Conluiados acima do limiar	3 de 4
Pontuação do conluiado mais fraco	230,9
Colunas que não podem alterar	52,3%
Pontuação média de um conluiado	262,4
Dispersão da pontuação de um inocente	42,8
Limiar de acusação	239,9

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 — A Marca de Água que Sobrevive a um Conluio

Um código de impressão digital fornece a cada assinante uma cópia do mesmo filme com uma sequência diferente de m bits. Assim, uma cópia vazada identifica quem a recebeu. Os bits não são escolhidos uniformemente. Cada posição j recebe o seu próprio viés p_j, gerado para que a maioria das posições apresente quase exclusivamente uns ou quase exclusivamente zeros em toda a base de assinantes. Um grupo que junte as suas cópias apenas consegue detetar uma posição caso os seus próprios bits divirjam. A pontuação de acusação soma, ao longo das posições onde a falsificação regista um, quão surpreendente era o bit de cada assinante.

O que significa cada símbolo

m: o comprimento do código em bits, que é o tema central de toda a lição
c: quantos assinantes agrupam as suas cópias
Z: o limiar de acusação: uma pontuação acima deste valor aponta um culpado

Pressupõe: A premissa da marcação: nas posições em que todas as cópias da coligação carregam o mesmo bit, o grupo não consegue perceber que essa posição existe e não a pode alterar. Tudo nesta página repousa sobre este princípio. Num sistema real, trata-se de uma afirmação sobre o método de incorporação. Uma marca invisível durante a comparação de cópias constitui uma marca impossível de remover. Os ataques alvejam sempre esta componente da arquitetura e não a aritmética.
Falha quando: Quando o número de conspiradores ultrapassa a capacidade para a qual o código foi dimensionado. Não existe uma degradação suave. As pontuações dos culpados decaem como 1/c enquanto a fasquia permanece onde a população inocente a estabelece. Consequentemente, um código suficientemente longo para quatro que venha a enfrentar oito não aponta um culpado com menos frequência. Não aponta rigorosamente ninguém.

O dobro dos conluiados, o quádruplo da marca de água 🖖

Arraste o controle deslizante do conluio e observe o primeiro cartão. Dois conluiados precisam de 623 bits, quatro de 2.490, oito de 9.959, dezesseis de 39.833. Cada duplicação multiplica o comprimento por quatro, três vezes seguidas. A razão para c² cai entre 155,60 e 155,75 nos quatro casos. Não é exatamente quatro apenas porque um comprimento é um número inteiro de bits, sendo as proporções 3,9968, 3,9996 e 3,9997. A razão está nos dois cartões ao lado, e nenhum deles é misterioso por si só. A pontuação de um conluiado é a evidência que o código recolhe sobre o mesmo, e eles partilham-na. Ela cresce como o comprimento dividido pelo número de conluiados. A pontuação de um assinante inocente é um passeio aleatório do mesmo comprimento, de modo que a sua dispersão cresce como a raiz quadrada desse comprimento. A evidência sobre o ruído avança, portanto, como m/c dividido por √m, que é √m/c. Manter isso constante enquanto c duplica significa que m tem de quadruplicar. Tudo o resto nesta página é consequência destas duas linhas.

O limite é definido pelas pessoas que não se deve acusar 🖖

Pressione Quatro, código longo, e depois Público de dez milhões. Os conluiados são as mesmas quatro pessoas com as mesmas cópias e a mesma falsificação. O limiar move-se de 239,9 para 254,5 e um a menos deles é identificado. Nada no crime mudou, mas o tamanho da população inocente sim. O limiar não é uma propriedade da evidência. É o nível que uma pontuação inocente excede por acidente apenas uma vez em mil execuções em toda a base de assinantes, pelo que dez vezes mais assinantes significa que cada um deles tem de ser submetido a um teste mais rigoroso. Esta é a correção de comparações múltiplas que arruína a estatística descuidada a fazer algo útil por uma vez. É a única defesa entre um esquema de marca de água e um cliente injustamente acusado.

O código é dimensionado para capturar um, não todos 🖖

Com exatamente o comprimento que o primeiro cartão exige, execute-o quarenta vezes com códigos diferentes. Pelo menos um conluiado é identificado em 38 execuções de 40 quando quatro deles entram em conluio, e os quatro são identificados em nenhuma. Aumente o código na metade do seu tamanho e todos os quatro surgem em 15 execuções de 40. Pressione Dezesseis conluiados para o extremo oposto, onde 10 de 16 estão acima do limite e o mais fraco fica 270 pontos aquém. Existe nisto um estranho consolo para o estúdio. Um conluio maior torna cada membro mais difícil de condenar e torna quase certo que alguém o será, pois há mais pessoas para cometer um erro. Ao comprimento exigido, quatro conluiados produzem um nome em 38 execuções de 40 e dezesseis conluiados em 40 de 40.

Problemas resolvidos na íntegra

De onde vem o 2.490? A ferramenta apresenta este valor para quatro cúmplices entre um milhão de assinantes, e não é um número simulado. Resulta de duas leis medidas e de uma decisão sobre a frequência com que se aceita acusar uma pessoa inocente. A dedução faz-se em quatro linhas. É a última que gera o quadrado.

Abrir este problema na ferramenta
1. As provas que um cúmplice deixa são proporcionais ao comprimento do código e repartem-se pelo grupo, pois cada coluna que controlam resulta da intervenção de todos. Numa medição feita em conluios de 2 a 16 elementos e códigos de 800 a 51.200 bits, o valor ronda os 0,34 m/c.
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. A pontuação de um assinante inocente é a soma de m contribuições independentes de média nula. Trata-se, por isso, de um passeio aleatório. A sua dispersão cresce com a raiz quadrada do comprimento, e não com o comprimento linear. Valor medido: cerca de √(m/2).
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. Comece por decidir com que frequência admite acusar uma pessoa inocente: no máximo ε numa população de n. Logo, é preciso ilibar um assinante ao nível de 1 − ε/n. Para um milhão de assinantes e uma probabilidade em mil, isto equivale a 6,00 desvios-padrão de afastamento.
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. A deteção exige que os indícios superem o limiar. Substitua as duas leis na equação e resolva em ordem a 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. O c encontra-se dentro do quadrado, e é aqui que reside toda a resposta: 2.490 bits para quatro cúmplices e 9.959 para oito. É um valor quatro vezes superior, descontando apenas o arredondamento para bits inteiros.
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. O valor em torno do qual se desenha o sistema não é o valor que a demonstração matemática nos dá. O próprio teorema de Tardos assegura o resultado com 100c²⌈ln(n/ε)⌉ bits, o que neste caso corresponde a 2.100c². É um código treze vezes mais longo do que a estimativa gaussiana, porque a prova matemática tem de resistir a todas as estratégias de conluio possíveis e não apenas às três referidas nesta página.
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
Resposta

m > (z c √(1/2) ÷ 0,34)² = 4,3253 z² c², o que para z = 5,9978 resulta em 155,60 c² antes do arredondamento para bits inteiros: 623 bits para dois cúmplices, 2.490 para quatro, 39.833 para dezasseis. Em bytes, isto corresponde a uma carga útil de marca de água de 78 B, 311 B e 4,98 kB. São dimensões tão pequenas que o comprimento nunca é um verdadeiro obstáculo, o que explica por que razão os especialistas debatem, em vez disso, a premissa da marcação. A única variável imune ao peso do quadrado é o público. O n entra apenas por via de z, que cresce segundo √(log n). Passar de mil assinantes para dez milhões faz o comprimento subir de 1.564 bits para 2.801, um aumento de 79%, ao passo que duplicar o conluio apenas uma vez custa 300%.

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
Um serviço de streaming precisa de alguma destas coisas? O primeiro passo desta série aborda um mundo onde todas as cópias são idênticas e não existe forma de comunicar com um dispositivo. Um serviço de assinaturas é o cenário oposto. A própria documentação do Widevine refere que um pedido de licença segue via HTTPS para um servidor de licenças, e que "o conteúdo da licença não pode ser modificado e é individualizado para o dispositivo que a solicita". O que sobra, então, da matemática?

Abrir este problema na ferramenta
1. Metade dela desaparece por completo. Existindo um canal de retorno, não há nenhum cabeçalho a proteger. Excluir um dispositivo não tem qualquer custo na transmissão, bastando não lhe emitir uma licença. O problema de cobertura do primeiro passo é o preço a pagar por não haver forma de obter uma resposta. Um disco não tem como perguntar quem o está a reproduzir.
2. A outra metade não desaparece. Ganha, pelo contrário, uma importância reforçada. Um servidor de licenças consegue bloquear os dispositivos que sabe estarem comprometidos, mas não tem como impedir um assinante em situação regular de gravar aquilo que desencriptou de forma legítima. Essa fuga de conteúdos leva consigo uma impressão digital, e essa impressão digital é a única pista capaz de revelar a identidade de quem o fez.
3. Assim, a questão do dimensionamento é a que abordamos nesta página, perante uma base de assinantes real. O comprimento do código cresce com o quadrado da coalizão e, em relação ao público, apenas através de um logaritmo.
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. Leia a tabela na horizontal e de seguida na vertical. Dezasseis cúmplices custam sessenta e quatro vezes mais do que dois cúmplices. A passagem de dez mil assinantes para cem milhões (um salto de quatro ordens de grandeza) representa um aumento de apenas 1,66 vezes.
  
  $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. Para dez milhões de assinantes e quatro cúmplices, obtemos 2.801 bits. Trata-se de trezentos e cinquenta bytes de carga útil, num filme que ocupa vários gigabytes.
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
Resposta

O comprimento do código nunca constitui o problema de fundo. Falamos de 350 bytes num contexto em que os conteúdos pesam milhares de milhões de bytes, e em que um público mil vezes superior implica um custo extra de apenas dois terços, e não um custo mil vezes maior. A dimensão do conluio é o único fator de rutura, por ser o único que se encontra dentro do quadrado. Ora, o número de pessoas dispostas a juntar as suas cópias é a única grandeza de todo o cálculo que ninguém consegue medir à partida. A engenharia de um sistema real não gasta os seus recursos nesta aritmética. O verdadeiro esforço passa por garantir que a marca sobrevive a recodificações, a cortes na imagem e a uma câmara apontada ao ecrã. Passa também por conseguir sustentar a premissa da marcação quando o atacante tem nas mãos duas cópias e uma ferramenta de comparação.

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

Percurso de aprendizagem

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

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

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