Criptografia chave simétrica de bloco e de fluxo

Este artigo descreve o que são os algoritmos de chave simétrica, no que são baseados e suas aplicações. Descreve os algoritmos simétricos de bloco e de fluxo. Pode ser considerado uma continuação do artigo "Introdução a criptografia".

[ Hits: 168.720 ]

Por: Elgio Schlemer em 09/03/2009 | Blog: http://gravatai.ulbra.tche.br/~elgio


Anexo A: problema do XOR



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.
Figura 2: Tabela Verdade
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:

int x;

x = x ^ x;

/* Em C, assim como em PHP, o circunflexo representa a operação XOR. Neste caso o X recebe o resultado de XOR dele com ele mesmo. Sabe-se que isto será ZERO, logo é uma maneira mais divertida de se fazer x= 0 :-D
*/


Vamos destacar portanto esta propriedade de forma matemática:

A xor A = 0

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:

A xor 0 = A

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:

C1 = M1 xor k
C2 = M2 xor 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:

C1 xor C2

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:

C1 xor C2 = (M1 xor k) xor (M2 xor k)

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

C1 xor C2 = M1 xor M2 xor k xor k = M1 xor M2 xor 0

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.

Página anterior    

Páginas do artigo
   1. Introdução
   2. Algoritmos simétricos de bloco
   3. Algoritmos simétricos de fluxo
   4. Algoritmo de fluxo RC4
   5. Conclusão e referências
   6. Anexo A: problema do XOR
Outros artigos deste autor

Iptables protege contra SYN FLOOD?

Estrutura do IPTables 2: a tabela nat

Fundamentos da criptografia assimétrica

Túneis cifrados com SSH

Armazenamento de senhas no Linux

Leitura recomendada

Detectando vulnerabilidades com o Nessus

Defesa pessoal com o GPG, Nautilus Scripts, partições encriptadas e leves doses de paranoia

Detectando vulnerabilidades com o Nessus

Metasploit Adobe Exploit

Bind: Explorando e evitando falhas

  
Comentários
[1] Comentário enviado por elgio em 09/03/2009 - 15:08h

***** ERRATA: No desenho da Figura 1 onde lê-se Bytes na verdade são bits. 288 Bits, 320 Bits

[2] Comentário enviado por gustavs em 29/04/2009 - 22:06h

Muito bom! Não conhecia praticamente nada de criptografia, agora me interessei.
Recomenda alguma leitura nesse assunto ?

[3] Comentário enviado por adrianoturbo em 02/05/2009 - 14:24h

Interessante a utilização do XOR.

[4] Comentário enviado por grandmaster em 05/05/2009 - 21:06h

Muito legal o artigo. Bem interessante.

Renato de Castro Henriques
CobiT Foundation 4.1 Certified ID: 90391725
http://www.renato.henriques.nom.br

[5] Comentário enviado por thiagods.ti em 17/06/2009 - 16:12h

Teus artigos geralmente são bons, hoje foi só ver que você lançou um artigo novo que a primeira coisa que eu faço quando tenho tempo é ler.

Parabéns =)

[6] Comentário enviado por Credmann em 21/06/2009 - 17:35h

Este artigo é quase a resposta da minha dúvida:
Qual criptografia tem melhor desempenho numa sessão interativa SSH?

[7] Comentário enviado por leomarcsys em 05/01/2012 - 18:30h

Há uma imprecisão quanto a informação sobre os tamanhos de bloco do AES.
O algoritmo de Rijndael, vencedor do concurso do nist para a definição do AES, prevê tamanhos variados de blocos e de chaves, no entanto o fips-197 que especifica o AES define apenas o tamanho de bloco como 128 bits.
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts