Rijndael é uma família de algoritmos de criptografia simétrica de bloco baseados no 3 DES, com cada algoritmo da família se diferenciando pelo tamanho de sua chave. Diferentemente do 3 DES, o Rijndael não se baseia na cifra de Feistel, tendo como fonte de sua inteligência apenas a rede de substituição-permutação (i.e. as S-Boxes).
O Rijndael foi escolhido em 2001 como o sucessor do 3 DES pelo NIST, quando ele ganhou o nome AES (Advanced Encryption Standard). Apenas três variações da família Rijndael (i.e. três tamanhos de chave) foram escolhidos para o AES: a de chaves de tamanho de 128, 192 e 256 bits. Essas variações são conhecidas respectivamente como AES-128, AES-192 e AES-256.
O algoritmo Rijndael funciona em rounds, de maneira semelhante ao DES, em que cada bloco de 128 bits (16 bytes) da entrada é submetido a quatro transformações diferentes. Elas são:
def Round(bloco, chave[i]):
SubBytes(bloco)
ShiftRows(bloco)
MixColumns(bloco)
AddRoundKey(bloco, chave[i])onde chaveé um vetor de subchaves gerado através de uma
rotina não-linear separada a partir da chave provida para o algoritmo. A
exceção para a descrição acima é o último round, onde a transformação
MixColumns não é aplicada, pelo simples fato de que ela é
sempre facilmente inversível e, portanto, não oferece segurança no
último round.
A transformação SubBytes, onde as S-Boxes são aplicadas,
é a única com boa não-linearidade, o que garante a segurança contra
ataques de criptanálise diferencial e linear.
As transformações ShiftRows, MixColumns são
lineares, servindo apenas para a difusão da informação. Apesar disso,
elas têm grande importância pois, caso elas não existissem, as
transformações ocorreriam todas em cada byte de forma independente,
então um criptanalista poderia analisar byte a byte, tendo um trabalho
muito mais fácil. Por conta da aplicação dessas transformações, cada
byte que passa pelas S-Boxes é uma função de todos os outros bytes do
round anterior, fazendo com que a complexidade algebráica da função que
mapeia o bloco de entrada ao bloco obtido no round aumente enormemente a
cada round.
A transformação AddRoundKey serve para que a cifra seja
específica sobre a chave dada.
Para garantir segurança e eficiência, tanto o número de rounds quanto o tamanho dos blocos varia de acordo com o tamanho da chave escolhido. Além disso, cada bloco é visto como uma matriz de 4x4 bytes.
Nessa transformação, cada um dos bytes do bloco é substituído por seu inverso no campo de Galois \(GF(2^8)\) sobre o polinômio primo \(m(x) = x^8+x^4+x^3+x+1\), equivalente a 11B em hex. Essa transformação é não-linear, mas pode ser implementada de forma muito eficiente através do algoritmo extendido de Euclides.
Então, cada um dos bytes do bloco é submetido à transformação linear inversível dada matricialmente por \[ \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \\ y_6 \\ y_7 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{bmatrix} \] onde \(x_i\) é o \(i\)-ésimo bit do bloco de entrada (após a inversão) e \(y_i\) é o \(i\)-ésimo bit do bloco de saída.
Cada resultado dessa transformação pode ser pré-calculado e tabelado, dando origem às S-Boxes do Rijndael. Note que aqui as S-Boxes são inversíveis, o que é uma grande diferença para o DES, onde as S-Boxes não eram inversíveis, e suas transformações deveriam ser eliminadas através de um XOR (rede de Feistel).
Nessa transformação aplicamos um shift circular para a esquerda em cada uma das linhas do bloco. O valor do shift circular (i.e. o número de casas que transladamos) depende do tamanho da chave, e é pré-tabelado.
Essa transformação difunde a informação de cada byte da entrada pelas linhas. Caso ela não existisse, as linhas seriam totalmente independentes, e o algoritmo degeneraria para quatro cifras separadas.
Nessa transformação, cada coluna de 4 bytes do bloco é vista como um vetor multiplicada por uma matriz fixa em \(GF(2^8)\) sobre o polinômio primo \(M(x) = x^4+1\).
Como cada entrada do vetor resultado da multiplicação de vetor com matriz envolve todos os bytes da coluna, essa transformação essencialmente toma cada coluna do bloco e mistura seus bytes de maneira inversível.
O polinômio \(M\) foi escolhido dessa maneira por motivos de eficiência, uma vez que o módulo de um termo por esse polinômio é simplesmente o mesmo termo com o expoente reduzido modularmente: \[ a_jx^j \text{ mod }M(x) = a_jx ^{j \text{ mod }4} \] Essa transformação é linear e inversível, e também serve para difundir a informação de cada byte da entrada pelas colunas.
Nessa transformação é realizado um XOR entre cada bloco e a subchave do round, que é obtida através da rotina de subchaves.
Essa transformação é linear é a própria inversa, pois\((B \oplus K) \oplus K = B\), e serve simplesmente para tornar o algoritmo dependente da chave, além de introduzir a inteligência contida na geração não-linear das subchaves. Como a informação da chave é introduzida round a round, entre operações que difundem muito a informação, temos como resultado a confusão da informação, tornando nebulosa a relação entre a chave e a saída do algoritmo.
A decriptografia do Rijndael se trata simplesmente da aplicação das inversas de cada transformação, em ordem reversa. Além disso, as subchaves devem ser utilizadas também em ordem reversa.
A inversa da transformação SubBytes consiste na inversão em \(GF(2^8)\) de cada byte sob o mesmo polinômio e então a aplicação da matriz inversa à usada na transformação original.
Esse resultado também pode ser pré-tabelado, ou obtido pela inversão das S-Boxes.
A inversa é simplesmente o mesmo shift, mas para a direita.
A inversa é a multiplicação das colunas pelo polinômio vetorial inverso \(c^{-1}(x)\).
Essa transformação é a própria inversa. Note que na decriptografia, devemos utilizar as subchaves em ordem inversa.
A rotina de geração das subchaves expande a chave provida para o algoritmo em um vetor de subchaves de dimensão igual ao número de rounds. Essa rotina é não-linear e emprega técnicas de difusão, tornando nebulosa a relação entre cada subchave e a chave original. Isso é feito para que mesmo que uma das subchaves seja obtida, a obtenção da chave original (e, portanto, das outras subchaves) seja muito difícil.
O melhor ataque (de chave única) que já foi desenvolvido para o AES é o ataque biclique, uma variante de meet-in-the-middle. Apesar de ele tecnicamente ser uma quebra, por ser melhor que a força bruta, sua complexidade é de \(2^{126.1}\), \(2^{189.7}\) e \(2^{254.5}\) para o AES-128, o AES-192 e o AES-256 respectivamente.
Ou seja, o ganho em tempo de execução em relação à força bruta é muito pequeno, então o ataque não é considerado uma vulnerabilidade significativa, e o AES ainda é, em geral, considerado seguro.