Uma Arquitetura de um Coprocessador Criptográfico para Algoritmo
Advanced Encryption Standard
-  AES

Tese de Mestrado de Anderson Cattelan Zigiotto
             


Neste trabalho é proposta uma arquitetura de um coprocessador dedicado para executar as funções de cifragem e decifragem de acordo com a norma AES, com chave criptográfica de 128 bits. O circuito foi implementado em um dispositivo lógico reconfigurável do tipo Field Programmable Gate Array – FPGA.

A arquitetura proposta foi projetada com a finalidade de reduzir a quantidade de recursos utilizados, de forma a ser implementada em um dispositivo de média densidade e baixo custo. Para a etapa de síntese foi utilizado um dispositivo Altera ACEX 1K50. O circuito sintetizado utiliza 1984 elementos lógicos e 6 blocos de memória embarcada, atingindo uma taxa de cifragem estimada de 91,8 megabits por segundo. O funcionamento do coprocessador foi comprovado através de teste funcional, utilizando os vetores de teste fornecidos pela norma.

This work proposes an architecture of a dedicated coprocessor to execute encryption and decryption operations according to the AES algorithm, with 128-bit cryptographic key. The circuit was implemented into a Field Programmable Gate Array- FPGA, a reconfigurable logic device.

The proposed architecture was designed to reduce the amount of resources used, so that it can be implemented into a mid-density, low-cost FPGA. For synthesis procedure, the target device was an Altera ACEX 1K50. The synthesized circuit uses 1984 logic elements and 6 embedded memory blocks, achieving an estimated throughput of 91.8 megabits per second. The coprocessor operation was confirmed with a functional test, using test vectors supplied by the standard.



Cripto_1a.gif                                 Cripto_2.gif
O sistema criptográfico. Pseudo-código do cifrador

Inicialmente o bloco de texto a ser cifrado é copiado para o estado, que é um arranjo de bytes, com quatro linhas e Nb colunas; sendo Nb o tamanho do bloco em palavras de 32 bits (para o AES, Nb = 4). O estado passa pela função cifragem (round) um certo número de vezes (Nr) que depende do tamanho da chave e do bloco. Se ambos forem iguais a 128 bits a função cifragem é realizada 10 vezes. Para cada função cifragem é utilizada uma sub-chave, obtida a partir da chave principal através dos processos de expansão e seleção de chaves.

Em cada função cifragem o estado sofre quatro transformações:

- SubBytes( ): é uma substituição não linear realizada independentemente em cada byte do estado, usando uma tabela de substituição, ou S-box;

- ShiftRows( ): os bytes das últimas três linhas do estado são deslocados ciclicamente para a esquerda de uma, duas e três posições para a segunda, terceira e quarta linhas, respectivamente

- MixColumns( ): esta função atua nas colunas do estado. Cada coluna, tratada como um polinômio de quatro termos no corpo finito GF(28), é multiplicada pelo polinômio fixo Critpo_e1.gif, módulo Cripto_e2.gif. Esta operação pode ser representada pela multiplicação matricial:

Cripto_e3.gif

- AddRoundKey( ): nesta operação, a sub-chave do round é adicionada ao estado. Esta adição é módulo 2, sendo realizada como uma simples operação OU-exclusivo  (XOR).

 
Na última iteração, a função MixColumns não é realizada. O cifrador inverso (decifrador) é obtido invertendo-se cada função bem como a sua ordem de execução.


   Cripto_4.gif                        Cripto_5.gif
Diagrama de blocos da arquitetura
proposta para o coprocessador
Representação da metodologia de trabalho e as ferramentas utilizadas no projeto.

   Cripto_6.gif                                Cripto_7.gif
Montagem para realização do teste experimental Placa de teste

Para a implementação do circuito na FPGA EP1K50 foram utilizados 1980 elementos lógicos e 6 EAB´s. As células lógicas restantes podem ser utilizadas para implementar uma interface com algum barramento padrão, como o ISA. A memória adicional pode ser utilizada como buffer ou ainda para aumentar a velocidade do cifrador, diminuindo o fator de multiplexação dos dados.

O desempenho do cifrador pode ser medido através da latência ou do throughput:

- Latência é definida como o tempo necessário para cifrar (decifrar) um bloco de mensagem original (mensagem cifrada).  Este valor depende do número de ciclos utilizados para cifrar cada bloco, e da duração de cada ciclo.

- Throughput é definido como o número de bits cifrados (decifrados) em uma unidade de tempo.

A cifragem de um bloco é feita em dez rounds, cada um destes necessita de quatro ciclos para ser realizado. Um ciclo adicional é necessário para a transformação inicial descrita no algoritmo. Assim, são necessários 41 ciclos para cifrar um bloco de mensagem. O tempo para carregar as palavras de chave e texto depende do barramento, portanto não é considerado no cálculo do desempenho do circuito. O período de cada ciclo do relógio depende do tempo de propagação do caminho crítico do circuito, ou seja, o tempo para que o sinal esteja estável. Este tempo, obtido por simulação, é de 48 ns. Assim, o throughput estimado é de:

Cripto_e4.gif

  Durante a fase final de avaliação dos candidatos a AES, alguns trabalhos foram realizados comparando a performance teórica dos algoritmos finalistas em hardware.  Os resultados obtidos nestes trabalhos podem ser tomados como ponto de partida para uma análise do desempenho da arquitetura proposta. No entanto, a comparação não pode ser direta, pois nesses trabalhos foram usadas tecnologias diferentes de FPGA’s e ASIC’s, com todos os recursos de hardware necessários para a implementação direta dos algoritmos. Além disso, alguns grupos implementam a geração de sub-chaves, outros não. Ainda, algumas arquiteturas possuem um barramento de dados de 128 bits, o que é inviável na prática. Apenas dois destes trabalhos utilizam FPGA’s da Altera, conseguindo taxas de cifragem estimadas de 232 e 268 Mb/s. Estes valores se aproximam da relação 4:1 esperada para comparação com a arquitetura proposta.

Existem alguns cores comerciais. A empresa HammerCores possui duas versões de seus cores  para o Rijndael. Uma versão rápida é otimizada para a família APEX 20KE, atingindo entre 690 e 900 Mb/s, e utiliza 20 blocos de memória.  A outra versão é mais lenta. Em um dispositivo da família 20KE-1, ela utiliza 593 elementos lógicos, 5 blocos de memória e a performance atinge 44 Mb/s. As sub-chaves são pré-computadas. Este processo economiza recursos, mas requer 260 ciclos para cada troca de chave.


               Artigos publicados

ZIGIOTTO, A. C. ; D'AMORE, R. . A Low-Cost FPGA Implementation of The Advanced Encryption Standard Algorithm. In: 15th Symposium on Integrated Circuits and Systems Design - SBCCI2002, 2002, Porto Alegre. Proceedings SBCCI2002. Los Alamito : IEEE Computer Society, 2002. v. 1. p. 191-196

ZIGIOTTO, A. C. ; D'AMORE, R. ; CUNHA, Wagner Chiepa . Implementação do Cifrador Rijndael em uma FPGA de Baixo Custo. In: Simpósio sobre Segurança em Informática, 2001, São José dos Campos. SSI'01, 2001. v. v.1. p. 10-16.