Laboratórios

Detalhes

Categoria: Laboratório de Criptografia

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

Autor: Yugi

Acessos: 9835

1. PREÂMBULO

O Criptossistema ASTAROTH do companheiro da ALDEIA NUMABOA Cristiano Campos Neves (com documento na página do laboratório da Aldeia datado de 14 de março de 2005) é um algoritmo muito interessante. Desde logo venho dar os parabéns ao seu autor pelo trabalho feito e, principalmente, por colaborar com o laboratório da Aldeia.

É de iniciativas assim que o Brasil precisa para crescer em tecnologia, mormente na ciência de proteção à informação e privacidade, na qual o país é consumidor de tecnologias estrangeiras. Não importa se o seu trabalho é realmente um sistema criptográfico excelente, pois, ao contrário do que possa parecer, construir um criptossistema seguro é uma tarefa extremamente difícil. Isto se deve às inúmeras armadilhas que o arsenal criptoanalítico reserva para o criptógrafo entusiasmado.

Estas considerações não pretendem definir um roteiro de estudo sucinto sobre o sistema ASTAROTH. Pretendo com estas breves palavras alertar os visitantes da aldeia e interessados na ciência criptográfica sobre os perigos e as sutis armadilhas embutidas nos algoritmos mais "bonitos e criativos".

Eu, Yugi Tumro, que também tenho trabalhos no laboratório da Aldeia, assim como o nosso amigo Cristiano Campos Neves, pretendo contribuir com a evolução criptológica deste laboratório. Espero que este breviário sobre o criptossistema ASTAROTH possa despertar o interesse de seu autor e de todos os entusiastas da criptologia.

YUGI TUMRO

2. NOTAS INICIAIS SOBRE O ASTAROTH

Conforme o material disponível na aldeia o autor do ASTAROTH, Cristiano Campos Neves, define o sistema como um cifrário de blocos de 64 bits e chaves de 256 bits. A chave é “expandida” através de uma função hashing que representa um conjunto de 16 pares de chaves de 32 bits, ou seja, 32 chaves de 32 bits, o que representa o hashing de 1024 bits.

Para a geração de sub-chaves é utilizada uma tabela TR que indica um índice de rotação entre 0 e 31. A função F é o coração do sistema sendo utilizada na cifragem, decifragem e geração de sub-chaves. É dita função teoricamente irreversível, pois o parâmetro de entrada (necessariamente um sub-bloco de 32 bits) interage com ele mesmo e com as 4 caixas de substituição do sistema (estas caixas de substituição têm entrada de 8 bits e saída de 32 bits!).

      1) y = -x 
      2) y = (y - S3[x3]) << (S0[x4] mod 32) 
      3) y = (y - S2[x2]) << (S1[x3] mod 32) 
      4) y = (y ^ S1[x1]) >> (S2[x2] mod 32) 
      5) y = (y + S0[x4]) >> (S3[x1] mod 32) 
      6) f(x) = y 

Vê-se que a função F realiza operações XOR, soma, subtração, rotação para a esquerda e para a direita. Parecem não haver falhas potenciais nesta função, visto que os parâmetros x1, x2, x3 e x4 garantem um certa "recursividade" da função. A diversidade de operações pode garantir uma transformação na qual o livro de códigos claro não é facilmente associado ao livro de código cifrado. Neste caso o livro de códigos tem 232 elementos e depende fortemente da estrutura das 4 SBOX’S do sistema. Um repertório de 232 elementos pode ser mapeado facilmente visto que esta função não utiliza nenhuma chave. Algumas questões cruciais ainda podem surgir: Se as SBOX’S não forem escolhidas com cuidado as operações de rotação para direita e para a esquerda podem ser demasiadamente repetidas. Isto se dá pelo fato de que o parâmetro Sn[Xi] é um número de 32 bits e o parâmetro de rotação é um número de 5 bits. A SBOX Si não pode ter todos os elementos possíveis de 32 bits e então somente 256 são escolhidos (exatamente compatível com o parâmetro de entrada da função Xi). Se os números da SBOX não forem criteriosamente escolhidos (ou aleatoriamente, com algumas ressalvas...) podem existir vários pontos Xi da SBOX que resultam no mesmo índice de rotação. Mas isto já é esperado, pois são 256 saídas e 32 índices! Certo é que sim; todavia cada índice deveria aparecer mais ou menos 8 vezes, mas de acordo com a SBOX escolhida um índice pode aparecer 12 ou mais vezes e outro índice pode aparecer 4 ou menos vezes, inclusive nenhuma vez. Tudo isto é um grande presente para o criptoanalista profissional. Pode-se checar as 4 SBOX’S para ver se isto ocorre mas isto foge ao escopo deste trabalho. De nossa parte vale o alerta! Pode-se ainda verificar que a partir da rotação para direita ou esquerda não podemos determinar o valor de Xi pois este pode ter 256 valores diferentes enquanto as rotações só podem ter 32 valores distintos.

Uma sugestão para evitar os problemas descritos anteriormente é criar 4 tabelas de rotação (SBOX’S de 32 elementos cada, representando cada uma um anagrama do conjunto {0,1,...,31}) e utilizar como índice de entrada o valor Xi (de 0 a 255) em módulo de 32. Esta estratégia deve surtir melhor efeito visto que as 4 tabelas de rotação podem ser construídas aleatoriamente com segurança ou ainda herdar parâmetros da chave. Além disto o processamento deve ser mais rápido pois é mais fácil fazer a operação Z mod 32 quando Z é menor ou igual a 255 do que quando Z vale 232 – 1 que é o caso da função F, visto que as SBOX’S S0, S1, S2 e S3 contém números de 32 bits. Em contraponto o sistema deve necessitar de mais memória para guardar as 4 novas SBOX’S.

Vamos nos ater agora ao cálculo de sub-chaves:

      K = S[I mod 4][x] << TR[I]
      K = f(K) >> TR[I]
      K = f(K) << TR[I]
      K = K ^ CBC
      Y = K * K
      CBC = ((CBC – Y2) << TR[I]) ^ Y1

Apesar de não ter testado este código de geração de sub-chaves ele parece funcionar bem. Sendo x o parâmetro de entrada (8 bits) ele representa uma posição em uma das 4 SBOX’S do sistema. O parâmetro de rotação é fixo para cada operação da mesma volta, mas isto não parece atrapalhar o processo. O uso da função F amarra a SBOX corrente com ela mesma e com as outras 3. O realimentador CBC contribui para o efeito avalanche. Realmente o autor Cristiano Campos Neves mostrou toda a sua criatividade na exposição desta rotina de geração de sub-chaves. Particularmente o cálculo do CBC (vetor de realimentação) representa um ponto importante desta rotina. Através do CBC o primeiro byte vai influenciar todos os outros. Infelizmente se temos duas chaves iguais até o 20º byte e diferentes daí por diante o CBC só vai alterar as chaves a partir do 21º byte. Isto pode ser contornado iniciando o vetor CBC com uma função que envolva todos os 256 bits da chave inicial em vez de iniciar o vetor CBC com zero. Este cálculo também pode ser, opcionalmente, uma função hashing.

É importante notar que a função F, que teoricamente é irreversível, torna o cálculo inverso das sub-chaves para a chave também teoricamente irreversível devido às interações de chamada àquela função. Entretanto como a função F é passível de mapeamento pode ser que exista uma maneira de se determinar estatisticamente alguns bits da chave inicial a partir das sub-chaves geradas, da estrutura interna das SBOX’S e da tabela de rotação TR. Este é um trabalho que demanda tempo, equipamento técnico e pessoal especializado para ser feito, entretanto, para uma equipe profissional, o mesmo pode ser realizado em tempo relativamente hábil. Não abordaremos este assunto por fugir ao escopo deste trabalho; trata-se neste caso de se embrenhar nas águas inóspitas e profundas da criptoanálise!

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!

2.2 Considerações sobre a função UPD(k)

A função UPD(k) representa a atualização de sub-chaves do sistema ASTAROTH. Segundo o autor do algoritmo a atualização de sub-chaves obedece ao esquema:

Kx = Kx ^ -P(Kx)

* Onde Kx repesenta uma sub-chave x, P(Kx) a permutação bit a bit da chave Kx utilizando a tabela P.

O símbolo ^ representa a operação XOR (ou-exclusivo). O que o autor não deixou claro é o – antes de P(Kx). Geralmente, em criptografia, os blocos são representados por números inteiros sem sinal. Assim, por exemplo, um bloco de 32 bits deve estar no intervalo [0, 4294967295]. Logo considerar como negativo a saída da função P para um XOR não produz efeito. Se o "-" foi um erro tipográfico (estou apenas supondo que seja...) então a atualização de sub-chaves fica assim:

Kx = Kx XOR P(Kx)

É uma estratégia interessante pois a tabela P não é fixa mas é determinada pela chave inicial. Contudo, uma vez determinada, a tabela P continua igual mesmo considerando-se a atualização de sub-chaves.

Fica evidente que com a função UPD(K) não teremos sucesso com a estratégia criptoanalítica descrita anteriormente. É necessário enfatizar, porém, que neste caso o ASTAROTH não é mais um autêntico criptossistema de blocos porque procura através da função UPD(K) "imitar" uma cifra de fluxo.

De minha parte eu fiz a experiência de gerar uma chave K (1234567890) e uma tabela P (que o autor do algoritmo apresentou no descritivo de seu trabalho) e utilizar a função Kx = Kx XOR P(Kx). Gerei através deste processo um arquivo de 10 Mbytes e o submeti a uma bateria de testes estatísticos para avaliar o grau de aleatoriedade desta função. Trata-se da bateria de testes DIEHARD desenvolvida por Marsaglia, pesquisador da Flórida, e foi popularizada no Brasil pelo ITA (Instituto tecnológico de aeronáutica).

Os resultados foram catastróficos. O leigo não precisa entender como os testes são feitos. Basta observar o parâmetro –P. Ele deve ser maior que 0.025 e menor do que 9.975. Isto não ocorre no resultado do teste em anexo significando que a função UPD(K) não tem um comportamento aleatório.

Pode-se alegar que a função possa se comportar aleatoriamente através do empilhamento das 16 sub-chaves que serão utilizadas para cada bloco; isto até pode ser verdadeiro mas de qualquer forma o processo de atualização de sub-chaves não é seguro isoladamente. Assim sendo, se descobrirmos uma maneira de desmontar o sobreciframento das 16 sub-chaves o processo continua falho. A verdade é que, através deste escalonamento de sub-chaves, não se produz uma estrutura de dados randômica; e este é o coração de uma cifra de fluxo.

3. CONCLUSÃO FINAL

Gostaria de agradecer a vovó Vicki pela oportunidade de debater a criptografia através da Aldeia Numaboa. Espero também ter contribuído com os interessados em criptologia.

Quero agradecer o companheiro Cristiano Campos Neves pela contribuição criptográfica prestada à Aldeia através do ASTAROTH. Espero que a exposição deste trabalho possa ajudá-lo a melhorar o sistema ou criar outros sistemas mais sólidos. Eu o incentivo a prosseguir visto que você mostrou excelente criatividade para compor o cifrário ASTAROTH.

Que este trabalho seja útil a todos os criptólogos!

YUGI TUMRO

Observação da vó: Os testes DIEHARD fornecidos pelo Yugi estão no arquivo zipado que se encontra à disposição dos interessados na seção de downloads. Aproveitando o embalo, quero agradecer a contribuição do autor. Grande Yugi!