Detalhes

Categoria: Laboratório de Criptografia

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

Autor: Yugi

Acessos: 10265

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!