Bloco de uso único: inquebrável uma vez, vulnerável em duas

Basta combinar cada byte da mensagem com um byte aleatório da chave por OU exclusivo: o texto cifrado nada revela a um adversário. Contudo, se a mesma chave proteger duas mensagens, ela anula-se por completo. Conjeture uma palavra, faça-a deslizar e leia a outra mensagem por baixo.

Exemplo resolvido — Bloco de uso único: inquebrável uma vez, vulnerável em duas

Caracteres	14
Chaves possíveis com este comprimento	5,2 × 10³³
Mensagens possíveis com este comprimento	1,1 × 10²⁰

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 — Bloco de uso único: inquebrável uma vez, vulnerável em duas

Um bloco de uso único combina cada carácter de uma mensagem com um carácter de chave escolhido ao acaso, utilizado exclusivamente nesse carácter e nunca mais repetido. Nesta lição, a operação é o OU exclusivo (XOR) bit a bit, calculado byte a byte: C = P ⊕ K, sendo a decifração a mesma operação, P = C ⊕ K. Se a chave for perfeitamente aleatória e tiver o comprimento da mensagem, a cifra atinge o sigilo perfeito: o conhecimento do texto cifrado não altera a probabilidade atribuída a nenhuma mensagem concebível. Quando a mesma chave é partilhada por duas mensagens, ela anula-se: C₁ ⊕ C₂ = P₁ ⊕ P₂. O arraste de palavra provável (crib-dragging) consiste em deslizar um termo suposto w ao longo desta soma: onde quer que uma mensagem contenha w, a operação w ⊕ C₁ ⊕ C₂ revelará a outra mensagem.

O que significa cada símbolo

P: a mensagem, com um byte por carácter
K: a chave: bytes aleatórios, em número igual ao de caracteres da mensagem
C: o texto cifrado, P ⊕ K
⊕: OU exclusivo: cada bit do resultado é 1 quando os dois bits correspondentes diferem
w: a palavra provável, uma palavra que se supõe existir numa das mensagens

Pressupõe: As mensagens são constituídas por letras minúsculas e espaços, codificados como bytes ASCII. Os bytes da chave provêm de um gerador iniciado com uma semente de 32 bits, pelo que esta página alcança apenas 2³² ≈ 4,3 × 10⁹ chaves; a partir de sete caracteres, o total de chaves passa a ser inferior ao de mensagens possíveis e, segundo o critério de Shannon, a máscara desta demonstração deixa de ter sigilo perfeito. Um bloco autêntico exige bytes verdadeiramente irreproduzíveis. Considera-se que um excerto «se assemelha a texto» se cada byte for uma letra ou espaço e se todas as suas sequências de três caracteres figurarem nos dois primeiros terços de «O Escaravelho de Ouro» de Poe (1843); as medições foram calculadas com o terço final da obra. Utiliza-se o XOR em vez da soma modular de letras (módulo 26) porque o XOR não tem sinal: o resultado obtido é o mesmo, qualquer que seja a mensagem onde se situe a palavra provável.

Testar todas as chaves revela todas as mensagens 🖖

Avance passo a passo em Ataque ao amanhecer e repare nas duas últimas linhas. Guardam a chave capaz de transformar rigorosamente o mesmo texto cifrado em “retreat at ten”. Se escrever na segunda caixa quaisquer outras 14 letras com espaços simples, surgirá também uma chave para elas. Isto acontece porque o XOR reverte a sua própria operação: o texto cifrado combinado com a sua mensagem fornece a chave. Assim, um espião que teste todas as 256¹⁴ chaves possíveis não encontra a mensagem original. Obtém, isso sim, cada uma das 27¹⁴ ≈ 1,1 × 10²⁰ sequências possíveis com esse comprimento, cada qual gerada por uma chave distinta. Como todas as chaves eram igualmente prováveis, a interceção não torna nenhuma hipótese mais plausível do que era antes. Shannon chamou a isto sigilo perfeito em 1949 e demonstrou o seu preço: são necessárias pelo menos tantas chaves quantas as mensagens possíveis. Uma chave de Vigenère, ao repetir-se, oferece muito menos combinações; é por isso que a análise de frequências a consegue quebrar.

Os espaços revelam-se antes de qualquer tentativa 🖖

Selecione Onde estão os espaços. A chave anulou-se por completo: C₁ ⊕ C₂ equivale a P₁ ⊕ P₂, byte a byte, sem qualquer resquício da chave. Observe agora os bytes a azul, 19 dos 50. Uma letra minúscula situa-se entre 0x61 e 0x7a, enquanto o espaço vale 0x20. Como apenas a combinação de uma letra com um espaço ativa o bit 0x40, qualquer byte igual ou superior a 64 assinala uma posição onde exatamente uma das duas mensagens tem um espaço. Sem arriscar uma única palavra, a fronteira entre os termos fica à vista, embora ainda não se saiba a qual das mensagens pertence cada intervalo. Em 2 000 pares de excertos com 60 caracteres retirados de O Escaravelho de Ouro, cerca de 30 % das posições denunciam esse espaço. O tráfego soviético que Meredith Gardner começou a decifrar em 1946 no projeto Venona somava dígitos de chave a grupos de código em vez de fazer o XOR de bytes, mas subtrair um criptograma de outro anula uma chave partilhada da mesma forma. Tratou-se de uma partilha acidental: sob a pressão do avanço alemão rumo a Moscovo, a fábrica responsável pelos blocos do KGB imprimiu cerca de 35 000 páginas de chaves duplicadas.

Os dois espaços em torno da palavra provável fazem quase todo o trabalho 🖖

Clique em Sem os espaços. O termo “the” na posição 26 gera “org”, formado apenas por letras e cujos trigramas existem no texto de referência; ainda assim, nenhuma das mensagens contém “the” nessa posição. Se voltarmos a incluir os espaços, “ the ”, apenas as correspondências verdadeiras passam no teste deste par. Ao analisar 2 000 pares de excertos com 60 caracteres retirados do terço final de O Escaravelho de Ouro (trecho que a referência nunca utilizou), “ the ” foi validado em 3 661 posições e correspondia a texto real em 3 281 delas: cerca de 9 em cada 10. Já a palavra isolada “the” foi aceite em 9 615 posições, mas só era autêntica em 4 169, menos de metade. O segredo reside nos bytes azuis. Um espaço na palavra provável só se transforma numa letra sobre um byte igual ou superior a 64, e só resulta em espaço sobre um 0; sobre qualquer outro valor, gera um byte alheio ao alfabeto. Por isso mesmo, cada espaço na nossa hipótese tem de coincidir com um espaço autêntico de uma das mensagens. Numa posição errada, é muito raro acertar nos dois.

Problema resolvido na íntegra

Cinco letras a partir de duas mensagens com o mesmo bloco 4 passos
Duas mensagens de 50 caracteres foram transmitidas com o mesmo bloco de uso único. Entre as posições 32 e 36, C₁ ⊕ C₂ apresenta em hexadecimal os valores 54 06 09 0c 4e. Suponha que uma das mensagens contém “ the ” nesse intervalo, correspondente aos bytes 20 74 68 65 20. O que diz a outra mensagem nessas cinco posições? Se essa hipótese pertencer à mensagem 2, cujo texto cifrado nesse trecho é 9d 8e 23 40 9e, quais são os cinco bytes da chave? Em seguida, clique em Problema resolvido e avance um passo na página.

Abrir este problema na ferramenta
1. Escreva o primeiro par em binário: 0x54 é 01010100 e o espaço 0x20 é 00100000. O XOR ativa o bit onde ambos diferem, resultando em 01110100, ou seja, 0x74, que corresponde à letra t. Antes de qualquer dedução, o bit 0x40 em 0x54 já revelava que uma das mensagens tem um espaço na posição 32.
  
  $0x54 \oplus 0x20 = 01010100 \oplus 00100000 = 01110100 = 0x74 = t$
2. Os quatro restantes: 0x06 ⊕ 0x74 = 0x72, r; 0x09 ⊕ 0x68 = 0x61, a; 0x0c ⊕ 0x65 = 0x69, i; 0x4e ⊕ 0x20 = 0x6e, n. A outra mensagem revela a palavra “train”, e as suas três sequências de três letras, “tra”, “rai” e “ain”, constam na íntegra no texto de referência.
  
  $54 06 09 0c 4e \oplus 20 74 68 65 20 = 74 72 61 69 6e = train$
3. Se “ the ” estiver na mensagem 2, a chave é obtida por C₂ ⊕ P₂: 0x9d ⊕ 0x20 = 0xbd, 0x8e ⊕ 0x74 = 0xfa, 0x23 ⊕ 0x68 = 0x4b, 0x40 ⊕ 0x65 = 0x25, 0x9e ⊕ 0x20 = 0xbe. Se a hipótese coubesse à mensagem 1, a mensagem 2 leria “train” e os bytes da chave seriam C₁ ⊕ “ the ”. O valor de C₁ ⊕ C₂ é idêntico em qualquer dos casos, pelo que a aritmética não consegue distinguir entre as duas opções.
  
  $K = C_{2} \oplus P_{2} = 9d 8e 23 40 9e \oplus 20 74 68 65 20 = bd fa 4b 25 be$
4. Na página, fixa-se “ the ” na mensagem 2 na posição 32, enquanto o campo da palavra provável passa a ter “ train ” na posição 31, apostando que “train” é uma palavra completa na mensagem 1. Surge então “y the r” na mensagem 2: apenas letras e espaços, com todos os seus trigramas já catalogados. Ao fixá-lo na mensagem 1, ambas as linhas crescem para sete caracteres.
  
  $(C_{1} \oplus C_{2})_{31..37} \oplus 20 74 72 61 69 6e 20 = 59 54 06 09 0c 4e 52 \oplus 20 74 72 61 69 6e 20 = 79 20 74 68 65 20 72$
Resposta

“train”, e os bytes de chave bd fa 4b 25 be se a palavra pertencer à mensagem 2. Nada em C₁ ⊕ C₂ indica qual das mensagens contém “ the ”, nem nunca indicará: trocar a ordem das duas mensagens na íntegra não altera em nada o valor de C₁ ⊕ C₂. A dedução seguinte serve apenas para decidir que fragmentos pertencem à mesma mensagem. A página calcula ainda quantos caracteres recuperados estão certos porque conhece ambas as mensagens de antemão. Um analista externo dispõe apenas destas duas linhas e do sentido que o texto fizer.

$train, K_{32..36} = bd fa 4b 25 be$

Percurso de aprendizagem

Como se quebram os códigos

Referências (2)

The first insight's perfect secrecy and its cost in keys, and the Vigenère link: C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal 28(4), pp. 656–715, October 1949. §10 "Perfect Secrecy", Theorem 6 (pp. 679–682).
The second insight's Venona history: the additive key, the duplicate pages, Gardner's first message: "VENONA: An Overview," Cryptologic Almanac 50th Anniversary Series, Center for Cryptologic History, National Security Agency. DOCID 3575728, approved for release 2009.

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