Criptografia chave simétrica de bloco e de fluxo

Este anexo foi separado do restante do artigo para não tornar sua leitura muito maçante. Destina-se a explicar matematicamente os problemas de uma cifra usando meramente XOR, sem o cuidado da chave infinita.

Antes de falar dos problemas, voltemos a Tabela Verdade reproduzida na Figura 2 e repetida a seguir. Vamos destacar algumas propriedades do XOR.

Observe pela tabela que sempre que dois bits são iguais (0 xor 0 ou 1 xor 1) o resultado será 0. Desta forma é possível concluir que uma informação operada por XOR com ela mesma resultará em ZERO. De fato, para instigar a curiosidade mostrando que tem sempre outra maneira de se fazer, frequentemente em C eu ofereço este trecho de código:



Vamos destacar portanto esta propriedade de forma matemática:


Da mesma forma, observe que sempre que o bit A for 0, o bit B foi repetido na saída (0 XOR 0 = 0, 0 XOR 1 = 1). Logo, pode-se concluir que:


Destacada estas propriedades, vamos a um exemplo de uma pequena cifragem usando XOR.

Posso usar o XOR e estipular uma frase como chave, exemplo "Linux", em uma chave de cinco letras. Claro que ela é pequena, mas mesmo que fosse uma frase com centenas de caracteres o problema que descreverei permanecerá. Usei 5 letras apenas para facilitar.

Linux em binário fica:

   'L' =  76 = 01001100             
   'i' = 105 = 01101001             
   'n' = 110 = 01101110             
   'u' = 117 = 01110101             
   'x' = 120 = 01111000   

De sorte que minha chave k seria a sequência de 40 bits 01001100 01101001 01101110 01110101 01111000. Com esta pequena sequência eu posso cifrar apenas 5 bytes de mensagem e terei que repetir a chave a partir do sexto byte, conforme o exemplo para cifrar "VivaoLinux":

MSG   = 'V' 'i' 'v' 'a' 'o' 'L' 'i' 'n' 'u' 'x'
CHAVE = 'L' 'i' 'n' 'u' 'x' 'L' 'i' 'n' 'u' 'x'

Cifraria o 'V' de Vivao (86 em ascii) com o 'L' da chave, o 'i' com o 'i' e assim por diante. Quanto a chave terminar, a repito, causando a repetição da chave, o que decididamente não pode.

Se um atacante souber que a palavra "Vivao" foi cifrada com a mesma sequência de bits que a palavra "Linux" , poderá anular o efeito da chave, devido a comutatividade do XOR.

Vamos chamar "Vivao" de M1 e "Linux" de M2, pois são blocos que foram cifrados do mesmo jeito. Desta forma chamaremos C1 o resultado de M1 cifrado e de C2 o resultado de M2 cifrado. O ideal seria cifrar M1 com k1 e M2 com k2, ou seja, não repetir a chave. Mas neste caso iremos cifrar M1 com k e M2 igualmente com k:


O atacante não conhece k, mas poderá capturar o tráfego e ter C1 e C2 para si. De posse destas duas mensagens e sabendo que ambas foram cifradas com um mesmo k, ele pode fazer:


Esta operação eliminará a chave, pois C1 é o resultado de (M1 xor k) e C2 é o resultado de (M2 xor k). Substituindo na fórmula:


O xor é comutativo e na expressão acima se tem k xor k o que dá 0. Logo, o atacante será capaz de fazer:


Qualquer coisa xor 0 é qualquer coisa, então o atacante foi capaz de calcular M1 xor M2, ambos desconhecidos para ele. Mas se ele tiver uma vaga ideia do que seja M1 poderá descobrir M2.

Esta é uma das fraquezas do XOR que podem resultar em análise de frequência e permitir descobrir com sucesso a chave depois de analisar alguns casos. O padrão de comunicação WEP, que usa o RC4, comete o vacilo de repetir chave e por isto ele é vulnerável. Em um extenso comentário meu anexado ao artigo Introdução a criptografia eu descrevo com maiores detalhes o furo do WEP.