Arquitetura Pipeline para Implementação do Sistema Criptográfico AES

Prévia do material em texto

UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
Centro de Tecnologia e Ciências
Faculdade de Engenharia 
Departamento de Engenharia de Sistema e Computação
Arquitetura de Computadores
Profª Luiza de Macedo Mourelle
Trabalho
Arquitetura Pipeline para Implementação do
Sistema Criptográfico AES
Aluno: Andressa da Silva Siqueira
Matricula: 2006.1.03249.11
Email: siq.andressa@gmail.com
Sumário
1.	Introdução	3
2.	Descrição do trabalho	3
2.1.	Pipeline	3
2.2.	Sistema AES	4
2.2.1.	O Concurso AES	4
2.2.2.	Descrição de Cifra	5
2.2.2.1.	Etapa AddRoundKey	6
2.2.2.2.	Etapa de SubBytes	6
2.2.2.3.	Etapa de ShiftRows	7
2.2.2.4.	Etapa de MixColumns	8
3.	Pipeline e AES	8
Arquitetura com Pipeline Interno	8
Arquitetura com Pipeline completo	8
4.	Implementação da AES na arquitetura Pipeline	9
5.	Conclusão	10
Bibliografia	12
Introdução
O sistema criptográfico Advanced Encryption Standard (AES) especifica um algoritmo criptográfico, aprovado como padrão pelo National Institute of Standards and Technology (NIST), que pode ser usado para proteger dados eletrônicos. O algoritmo AES é um cifrador de bloco simétrico que pode criptografar e decriptografar informação. O AES especifica o algoritmo de Rijndael, um cifrador de bloco simétrico que pode processor bloco de dados de 128 bits, utilizando chaves cifradoras de 128, 192 e 256 bits. Rijndael foi projetado para tratar tamanhos de bloco e de chaves adicionais, mas eles não são adotados neste padrão. De acordo com o tamanho da chave, o algoritmo recebe o nome AES-128, AES-192 e AES-256. A entrada e a saída do algoritmo AES consistem, cada uma, de sequências de 128 bits. Essas sequências serão referidas como blocos. A entrada, saída e chave cifradora são processadas como arranjos de bytes. Internamente, as operações do algoritmo AES são realizadas num arranjo de bytes de duas dimensões chamado State. O State consiste de quatro linhas de bytes, cada uma contendo Nb bytes, onde Nb é o tamanho do bloco dividido por 32. No arranjo State denominado pelo símbolo s, cada byte tem dois índices, com sua linha r no intervalo 0 <= r < 4 e sua coluna c no intervalo 0 <= c < Nb. Isto permite que um byte do State seja referenciado ou como sr,c ou s[r,c]. O cifrador é descrito em pseudo-código no Algoritmo Cipher, abaixo. As transformações individuais – SubBytes(), ShiftRows(), MixColumns() e AddRoundKey() – processam o State. 
Algoritmo Cipher (byte in [4*Nb], byte out [4*Nb], word w[Nb *(Nr + 1)])
begin
byte State [4,Nb]
State = in
AddRoundKey (State, w[0, Nb – 1])
for round = 1 step 1 to Nr – 1
SubBytes (State)
ShiftRows (State)
MixColumns (State)
AddRoundKey (State, w[round * Nb, (round + 1) * Nb –1])
end for
SubBytes (State)
ShiftRows (State)
AddRoundKey (State, w[Nr * Nb, (Nr + 1) * Nb – 1])
out = State
end
Descrição do trabalho
Pipeline
Pipeline é uma técnica de hardware que permite que a CPU realize a busca de uma ou mais instruções além da próxima a ser executada. Estas instruções são colocadas em uma fila de memória dentro do processador (CPU) onde aguardam o momento de serem executadas, só poderá começar quando a outra instrução acabar só assim da sequência ao procedimento.
Ou seja, é o processo pelo qual uma instrução de processamento é subdivida em etapas, uma vez que cada uma destas etapas é executada por uma porção especializada da CPU, podendo colocar mais de uma instrução em execução simultânea. Isto traz um uso mais racional da capacidade computacional com ganho substancial de velocidade. Entre os problemas enfrentados estão a dependência de instruções anteriores e desvios que dificultam o processo, bem como a diferença de complexidade de instruções que fazem com que as mesmas possam levar um tempo variável para execução.
A técnica de pipeline é utilizada para acelerar a velocidade de operação da CPU, uma vez que a próxima instrução a ser executada está normalmente armazenada dentro da CPU e não precisa ser buscada da memória, normalmente muito mais lenta que a CPU.
Até o 386, os processadores da família x86 eram capazes de processar apenas uma instrução de cada vez. Uma instrução simples podia ser executada em apenas um ciclo de clock, enquanto instruções mais complexas demoravam vários ciclos de clock para serem concluídas. Para melhorar o desempenho do 486, a Intel resolveu usar o pipeline, uma técnica inicialmente usada em processadores RISC.
Sistema AES
Em Criptografia, o Advanced Encryption Standard (AES, ou Padrão de Criptografia Avançada, em português), também conhecido por Rijndael, é uma cifra de bloco adotada como padrão de criptografia pelo governo dos Estados Unidos. Espera-se que seja utilizado em todo o mundo e analisada extensivamente, assim como foi seu predecessor, o Data Encryption Standard (DES). O AES foi anunciado pelo NIST (Instituto Nacional de Padrões e Tecnologia dos EUA) como U.S. FIPS PUB (FIPS 197) em 26 de Novembro de 2001, depois de 5 anos de um processo de padronização. Tornou-se um padrão efetivo em 26 de Maio de 2002. Em 2006, o AES já era um dos algoritmos mais populares usados para criptografia de chave simétrica.
O Concurso AES
Em 1997 o governo americano, através do NIST (National Institute of Standards and Technology), lançou um processo de seleção que definiria um novo algoritmo de chave simétrica para proteger informações do governo federal. Este novo algoritmo criptográfico substituiu o DES (Data Encryption Standard), que havia sido quebrado pela máquina DES Cracker, construída pela ONGElectronic Frontier Foundation com apenas 250 mil dólares.
Em setembro de 1997 o NIST indicou as condições necessárias para a candidatura de algoritmos: 
Divulgação pública
Direitos autorais livres
Os algoritmos deveriam ser de chave privada (simétricos) e suportar blocos de 128 bits e chaves de 128, 192 e 256 bits. 
Em agosto de 1998, na Primeira Conferência dos Candidatos ao AES, apresentaram-se 15 candidatos: Cast-256, Crypton, Deal, DFC, E2, Frog, HPC, LOKI97, Magenta, MARS, RC6, Rijndael, Safer+, Serpent e Twofish. 
O NIST solicitou aos membros da comunidade criptográfica mundial uma análise dos algoritmos candidatos. Em 1999, na Segunda Conferência dos Candidatos AES, através da análise obtida foram selecionados 5 finalistas: MARS, RC6, Rijndael, Serpent e Twofish. Posteriormente esses 5 algoritmos sofreram novas análises.
Três anos e meio após o início do concurso, o NIST chega à escolha do vencedor: Rijndael. O nome é uma fusão de Vincent Rijmen e Joan Daemen, os dois belgas criadores do algoritmo.
Segundo o NIST, o Rijndael combina as características de segurança, desempenho, facilidade de implementação e flexibilidade, apresenta alta resistência a ataques como "power attack" e "timing attack" e exige pouca memória, o que o torna adequado para operar em ambientes restritos como "smart cards", PDAs e telefones celulares.
Descrição de Cifra
Estritamente falando, o AES não é exatamente o Rijndael (embora na prática possam ser permutados) já que o Rijndael suporta uma maior gama de tamanhos do bloco e da chave. O AES tem um tamanho de bloco fixo em 128 bits e uma chave com tamanho de 128, 192 ou 256 bits, enquanto o Rijndael pode ser especificado com chaves e tamanhos de bloco de qualquer múltiplo de 32 bits, com um mínimo de 128 bits e um máximo de 256 bits.
A chave é expandida usando-se o escalonamento de chaves do Rijndael. A maioria dos cálculos do AES é feita em um corpo finito próprio.
O AES opera sobre um arranjo bidimensional de bytes com 4x4 posições, denominado de estado (as versões do Rijndael com um tamanho de bloco maior têm colunas adicionais no estado). Para criptografar, cada turno do AES (exceto o último) consiste em quatro estágios:
AddRoundKey - cada byte do estado é combinado com a subchave própria do turno (RoundKey); cada subchave é derivada da chave principal usando o algoritmo de escalonamento de chaves.
SubBytes - é uma etapa de substituição não linear onde cada byte é substituído por outro de acordo com uma tabela de referência.
ShiftRows - é uma etapa de transposição onde cada fileira do estado é deslocadade um determinado número de posições.
MixColumns - é uma operação de mescla que opera nas colunas do estado e combina os quatro bytes de cada coluna usando uma transformação linear.
O turno final substitui o estágio de MixColumns por um novo estágio de AddRoundKey.
Etapa AddRoundKey
Na etapa de AddRoundKey, a sub-chave é combinada com o estado. Para cada turno, uma sub-chave é derivada da chave principal usando o escalonamento de chaves do Rijndael; cada sub-chave é do mesmo tamanho que o estado. A sub-chave é somada combinando cada byte do estado com o byte correspondente do sub-chave, utilizando a operação XOR bit a bit.
Etapa de SubBytes
Na etapa de SubBytes, cada byte no arranjo é atualizado usando uma S-box de 8 bits. Para evitar os ataques baseados em propriedades algébricas simples, a S-box é construída combinando-se uma função inversora com uma transformação afim invertível. A S-box é escolhida também de forma a evitar qualquer ponto fixo.
A S-box é construída através de duas operações:
Inicializar as células por linhas com a célula mais à esquerda contendo no nibble superior o número de linha. 
Substituir cada célula não nula pelo seu inverso multiplicativo correspondente no polinômio característico do byte
A cada Byte (b7 b6 ... b0) aplicar a transformação .
Figura 1 - S-box utilizada na AES
Etapa de ShiftRows
A etapa de ShiftRows opera sobre as linhas do estado, deslocando os bytes em cada linha de um determinado número de posições. No AES, a primeira linha fica inalterada. Cada byte da segunda linha é deslocado à esquerda de uma posição. Similarmente, a terceira e quarta fileiras são deslocadas de duas e de três posições respectivamente. Para o bloco de bits de tamanho 128 e 192 bits, o padrão de deslocamento é mesmo. Desta forma, cada coluna do estado ao fim da etapa de ShiftRows fica composta por bytes de todas as coluna do estado da entrada.
No caso de blocos de 256 bits, a primeira fileira fica inalterada, deslocando-se a segunda, terceira e quarta fileiras. O deslocamento é de 1, 2 e 4 bytes respectivamente - embora esta mudança se aplique somente ao Rijndael quando usado com um bloco de 256 bits, o que não ocorre no AES.
Etapa de MixColumns
Na etapa de MixColumns, os quatro bytes de cada coluna do estado são combinados usando uma transformação linear invertível. Junto com o ShiftRows, o MixColumns fornece difusão à cifra. Cada coluna é tratada como um polinômio em e é então multiplicado em módulo pelo polinômio fixo . A etapa de MixColumns pode também ser vista como uma multiplicação matricial no campo finito de Rijndael.
Pipeline e AES 
O núcleo para o cifrador AES utiliza funções específicas implementadas em hardware para a melhor performance. Entre elas esta o pipeline. 
Pipeline: Replicação das rodadas e registradores entre, aumentando a vazão dos dados no circuito do cifrador. 
Esse recurso é muito utilizado em smartphones e tabletes, pois eles necessitam de segurança durante o trafego de dados.
Arquitetura com Pipeline Interno 
Usada em aplicações com relativa alta velocidade, aproximadamente 1 Gbit/s para implementações em FPGA, e as suas limitações estão presentes no tamanho da pastilha e seu custo.
É a extensão da arquitetura básica de interação, cujo é acrescido registradores pipeline que são introduzidas dentro da rodada da cifra. Tanto um resultado, dois blocos de dados podem ser processados simultaneamente aumentado à freqüência do clock. Mantém-se e somente um pequeno incremento no tamanho da pastilha.
Arquitetura com Pipeline completo
Usado para aplicações com alta taxas vazão de encriptação e decriptação, superior a 10 Gbit/s, tamanho do circuito, a área usada e seu custo são elevados em relação as outras versões. Nesta arquitetura, todas as rodadas são desdobradas os registradores introduzidos entre 2 duas rodadas consecutivas e dentro das cifras da rodada. As características 91 destacadas desta arquitetura em todos os ciclos de clock, tanto na cifragem como de decifragem um bloco de dados é feito por completo.
Implementação da AES na arquitetura Pipeline 
A criptografia em hardware é mais segura que aquela desenvolvida em software, pois dificuldade a quebra da chave e/ou descobrir como foi realizada a implementação. Uma forma de implementar a AES em hardware é utilizar o FPGA utilizando a linguagem de de descrição de hardware, VHDL.
O hardware desenvolvido é modular o que permite a implementação de pipelines de vários níveis e com o aumento no número de níveis de pipeline tem-se uma maior velocidade na entrega e/ou recebimento das palavras
Tabela 1- Comparação entre as implementações com pipeline
Por outro lado a latência, que está ligada ao processamento da palavra, aumenta significativamente.
Figura 2 - Funcionamento do Pipeline de 5 níveis
A primeira linha representa os 11 ciclos de expansão da chave. A segunda linha representa a cifragem da primeira palavra recebida. A terceira linha representa a cifragem da segunda palavra recebida, e assim por diante até a sexta linha. A sétima linha representa que o hardware não possui capacidade para receber nenhuma outra palavra durante 6 ciclos de clock (representados pelos quadrados pretos) até que alguma das linhas esteja disponível para que uma palavra possa ser carregada e processada.
A expansão das chaves ocorre da seguinte maneira:
1) É recebido um bloco (palavra) que representa a chave de entrada e é composta de 4 linhas e 4 colunas. 
2) As primeiras operações serão feitas sobre a quarta coluna, da seguinte forma: 
3) É feita uma rotação na quarta coluna de modo que a célula que está acima de todas as outras fique abaixo delas. 
4) A partir do resultado da rotação é feita a substituição utilizando a tabela S-Box 
5) Após a substituição é feita uma operação de Ou-Exclusivo com a primeira coluna da matriz de constantes e, em seguida, é feita uma operação de Ou-Exclusivo com a primeira coluna do bloco inicial. 
6) Tem-se assim a primeira coluna do próximo bloco de chave. 
7) A segunda coluna do bloco de chave é o resultado de uma operação Ou-Exclusivo entre a primeira coluna do novo bloco (calculada no passo 6) e a segunda coluna do bloco inicial. 
8) A terceira coluna do bloco de chave é o resultado de uma operação Ou-Exclusivo entre a segunda coluna do novo bloco (calculada em 7) e a terceira coluna do bloco inicial. 
9) A quarta coluna do bloco de chave é o resultado de uma operação Ou-Exclusivo entre a terceira coluna do novo bloco (calculada em 8) e a quarta coluna do bloco inicial. 
10) Tem-se, assim, um segundo bloco formado por 4 linhas e 4 colunas com 8 bits em cada uma das células e que será a chave da primeira rodada. 
11) A partir do bloco da primeira rodada (calculado em 10) inicia-se todo este procedimento utilizando a quarta coluna. As operações se repetem até que todas as chaves estejam calculadas.
Conclusão 
Implementando AES em hardware utilizando o pipeline temos uma melhora significativa no recebimento e leitura dos blocos de entrada. 
Essa implementação possibilita maior nível de segurança no trafego de dados em rede dificultando o roubo de informações.
x