Detalhes

Categoria: Laboratório de Criptografia

Atualização: Quinta, 14 Janeiro 2010 13:57

Autor: Yugi

Acessos: 10209

2.1 Sobre a estrutura de cifragem do Astaroth

A cifragem é um processo bem simples, se comparada aos outros processos do criptossistema, consiste de uma rede feistel, utilização da função F e uma permutação de bits baseada na Tabela P. A seguir será apresentado um diagrama mostrando a cifragem em suas etapas.

      X1 = X1 ^ f(P(X2))

      X = X ^ K1
      X = X ^ K2
      X = X ^ K3
      .
      .
      .
      X = X ^ K16

      UPD(K)

* Onde X é bloco de 64-bits que deverá ser criptografado; X1 e X2 a divisão de X em dois valores de 32-bits; Kn um par de sub-chaves n; P uma permutação de bits usando a tabela P; UPD(K) chamada do algoritmo de atualização das sub-chaves.

Preferimos as palavras do próprio autor para explicar o processo de cifragem (perdoe-nos pelo plágio do texto!). Vê-se inicialmente que o bloco X que representa o texto claro é dividido em 2 blocos de 32 bits. O sub-bloco X1 é alterado por uma operação XOR com a permutação do sub-bloco X2 processada pela função F. Vê-se claramente aí o conceito de difusão: o bloco X2 interfere no bloco X1 e esta interação é bem complexa, pois depende inicialmente do conteúdo de X2 e em seguida da função F (4 SBOX’S e rotações dependentes de dados) e finalmente da chave através da tabela P. Em seguida ambos os blocos (X1 e X2) são cifrados 16 vezes cada um com chaves de 32 bits. A cifragem se dá através da operação XOR. A função UPD(K) se refere à atualização de sub-chaves; mas cuidemos primeiro da estrutura de cifra.

A operação XOR (ou-exclusivo) é muito usada em criptografia. Quase todos os algoritmos modernos a utilizam porque ela, além de outras boas características, é involutiva. O que é uma função involutiva? É aquela que tem como seu inverso ela própria. Por exemplo, considere o número 1425. Se fizermos um XOR com 3546 temos 2123. Assim temos que 2123 XOR 3546 resulta em 1425. A operação XOR é inversa dela mesma. Esta característica é muito importante, pois cifragem e decifragem podem utilizar quase o mesmo código e isto facilita a implementação do algoritmo de cifra além de fazer com que o tempo de cifragem e decifragem seja bastante parecido.

Quando o algoritmo ASTAROTH acaba de cifrar o bloco X temos que o sub-bloco X1 está cifrado por uma interação com X2 e pelas 16 sub-chaves subseqüentes que são de certa forma "quase aleatórias" devido à função de hashing. O bloco X2 está cifrado por 16 sub-chaves de 32 bits que também representam um produto "quase aleatório". Esta característica do ASTAROTH é muito boa. Vocês repararam que X1 está sob o efeito de difusão (interação de bits alheios ao bloco em uso) e confusão (interação complexa com a chave de cifra) enquanto X2 está apenas sob o efeito da confusão? Mas vocês podem perguntar: Tudo bem; e isto atrapalha alguma coisa na segurança da cifra?

A resposta será explicada detalhadamente. O empilhamento de funções XOR em seqüência não produz um ciframento seguro. Por que? Seja o bloco X1 = 167 e X2 = 183. Sejam 5 sub-chaves denominadas A, B, C, D e E relacionadas com X1 e X2. Com isto queremos dizer que vamos cifrar X1 com 5 chaves através da função XOR. O mesmo será feito com o bloco X2:

A tabela acima mostra que um bloco claro (X1 = 167) cifrado por várias operações XOR resulta em Y1 (695). Um bloco X2 (183) cifrado pelos mesmos valores em XOR produz Y2 (679). O XOR entre X1 e X2 (167 XOR 183) é igual a 16 e o XOR de Y1 e Y2 (695 e 679) também resulta em 16. O que terá acontecido? É simples. Como as chaves são iguais e a operação XOR é involutiva e não-difusa (não há interferência de bits alheios na mudança de cada bit) então a cadeia de variáveis (1527, 3026, 1457, 131 e 2311) resulta em um único XOR (que neste caso é 528). De fato, 167 XOR 528 é igual a 695 e 183 XOR 528 é igual a 679.

O leitor impaciente pode perguntar: Mas de que maneira isto pode mostrar a fraqueza da cifra ASTAROTH? No exemplo de raciocínio acima os números são pequenos e as sub-chaves são apenas 5. No ASTAROTH são 16 ciframentos para cada sub-bloco. O fato é que estes 16 ciframentos podem ser reduzidos em um único XOR, o que naturalmente torna a cifra muito fraca.

Mas como pode um criptoanalista se valer destas afirmações para quebrar a cifra? Varrer todas as chaves está fora de cogitação: são 256 bits, o que resulta em mais ou menos 1,157977 combinações de chaves possíveis. Porém o criptoanalista hábil pode quebrar a cifra com muito mais facilidade.

Lembre-se que para quebrar o algoritmo ASTAROTH estamos deixando de lado a função UPD(K) que é a função de atualização de sub-chaves.

Para iniciar vemos que o sistema cifra as mensagens em blocos de 64 bits. É natural que numa mensagem longa tenha muitos blocos de 64 bits cifrados; todos eles estão disponíveis para o criptoanalista. O criptoanalista deve dividir a mensagem em blocos de 64 bits e subdividi-los em sub-blocos de 32 bits.

Veja a tabela a seguir:

O criptoanalista deve calcular Y1, sendo que Y1 = C2.1 XOR C2.2. A variável Y1 representa o XOR entre B2.1 e B2.2 (Bi.j representa os blocos claros e Ci.j representa os blocos cifrados!). Esta é uma verdade que já foi explicada anteriormente. Ou seja, o criptoanalista já tem em suas mãos o ou-exclusivo entre dois textos claros e isto independente da chave utilizada pelo criptógrafo (lembre-se: desconsideramos a função UPD(K)!). Esta é a armadilha: as sub-chaves geradas são iguais para todos os blocos! Isto não é um defeito: todos os criptossistemas de blocos utilizam sub-chaves iguais para cifrar todos os blocos do texto claro; isto acontece no DES, no IDEA, no AES, etc... O fato é que devido à estrutura do ASTAROTH isto se transformou em uma perigosa armadilha que escapou aos olhos do autor do algoritmo. São estas interações surpreendentes que facilitam o trabalho do criptoanalista! Assim as 16 sub-chaves usadas para transformar B2.1 em C2.1 foram anuladas pela operação XOR entre C2.1 e C2.2! O que resta é o XOR entre dois textos claros: B2.1 e B2.2. Mas como separar estes dois textos claros e conseguir o texto original? E quanto aos blocos do tipo B1.j? Eles estão cifrados primeiramente pela função F(P(B2.j)) e em seguida pelas 16 sub-chaves; como decifrá-los?

De posse do XOR entre os textos claros (Y1 é o XOR entre B2.1 e B2.2) o criptoanalista pode separá-los por força bruta. Esta tarefa é relativamente simples visto que Y1 tem 32 bits o que dá 232 combinações, coisa simples até mesmo para um computador pessoal. Existem refinamentos que podem ser usados como tentar prever vogais e sílabas em posição fixa e extrair os resultados do XOR. Mas aí tem uma questão: se Y1 se dividir em B2.1 e B2.2, como saber se este é o resultado correto? Basta considerar o bloco cifrado C2.1 e C2.2. O XOR entre B2.1 e C2.1 (chamemos de Ch1) representa as 16 sub-chaves utilizadas para cifrar B2.1 em C2.1; o mesmo ocorre com B2.2 e C2.2 (Ch2). Ch1 deve ser exatamente igual a Ch2, pois as sub-chaves são necessariamente iguais para todos os blocos da mensagem. Se forem diferentes significa que a divisão de Y1 em B2.1 e B2.2 (ou generalizando, Yn em B2.j e B2.j+1) está incorreta. O próprio criptograma nos diz se estamos seguindo a pista certa ou não.

Uma vez descoberta a sub-chave que condensa as 16 sub-chaves do sistema que cifraram os blocos B2.j em C2.j (seja esta rotulada de CH) basta fazer a operação XOR entre todos os blocos C2.j e CH. Assim teremos metade do texto decifrado. A outra metade refere-se aos sub-blocos do tipo B1.j -> C1.j. Uma vez que sabemos o valor de B2.j bastaria calcular a função F(P(B2.j)) e fazer um XOR entre este resultado e o bloco C1.j. Obteríamos assim o bloco B1.j cifrado apenas pelas 16 sub-chaves e o decifraremos pelo mesmo processo utilizado por B2.j. Infelizmente (ou felizmente, conforme o ponto de vista) o criptoanalista não conhece a tabela de permutação P e não pode calcular diretamente F(P(B2.j)). Tentar todas as permutações possíveis está fora de cogitação. O número de possibilidades é realmente muito grande: 32! = 263130836933693530167218012160000000! Vejam que o problema do cálculo de F(P(B2.j)) não existiria se a tabela P fosse fixa!

Todavia, nesta fase, com a metade do texto decifrada, podemos mesmo adivinhar pedaços de palavras e através do palpite fazer o ou-exclusivo entre ele e o sub-bloco cifrado C1.j correspondente. O resultado (chamemos de BH+0) representa o XOR entre as 16 sub-chaves que cifraram os sub-blocos do tipo B1.j mais o XOR com F(P(B2.j)). Supondo que o palpite esteja certo se a sub-palavra encontrada em B1.j se encaixa perfeitamente em B2.j temos que encontrar o XOR entre C1.j+1 e o suposto B1.j+1. Se nossos palpites forem corretos temos que BH+1 é o XOR entre C1.j+1 e B1.j+1 e que representa as 16 sub-chaves em XOR com F(P(B2.j+1). O XOR entre BH+0 e BH+1 anula as 16 sub-chaves utilizadas para cifrar os blocos C1.j e C1.j+1. Temos que este resultado (seja rotulado de R) é o XOR entre F(P(B2.j) e F(P(B2.j+1)).

Em R nós temos o problema de separar os valores F(P(B2.j) e F(P(B2.j+1)). A partir de C1.j fazemos o XOR com R e anulamos F(P(B2.j)). O resultado S contém o XOR entre as 16 sub-chaves, B1.j e F(P(B2.j+1)). Como já conhecemos B1.J (por dedução a partir dos blocos B2.j) podemos anulá-lo através de um XOR com S. O que resta, o produto T, é o XOR entre F(P(B2.j+1)) e as 16 sub-chaves. Se tudo estiver certo basta fazer um XOR com T e C1.j+1; anularemos F(P(B2.j+1)) e teremos somente B1.j+1 em XOR com as 16 sub-chaves. Como já conhecemos B1.J+1 por dedução a partir de B2.j+1 descobrimos facilmente o XOR entre 16 sub-chaves utilizadas nos blocos do tipo B1.j, rotulado de Z. Uma vez conhecendo Z temos que fazer um XOR entre C1.j e o próprio Z. O resultado W é submetido a um XOR com o bloco B1.j correspondente: a resposta representa exatamente o valor da função F(P(B2.j)). Faremos o mesmo para todos os sub-blocos ainda não decifrados!

É importante frisar que não descobrimos diretamente a tabela P (nem a chave inicial do sistema e nem mesmo as sub-chaves, mas apenas o XOR entre elas!), contudo deduzimos com uma certa facilidade os fatores que impediam a nossa decifração sem chave. E realmente através destes passos o criptoanalista pode decifrar uma mensagem protegida com o ASTAROTH!