Neste artigo vou tentar debulhar, de leve, sem detalhes profundos, o padrão AES (Advanced Encryption Standard, que pode ser obtido aqui), mas acho necessário (e inconveniente, me desculpem) explicar as duas piadinhas contidas no título:
No ano em que escrevo esse texto houve um “ataque massivo”, no mundo tudo, de um ramsonware chamado Wanna Crypt0r, que ficou conhecido como “Wanna Cry?” (Quer chorar?). Daí o quase click bait “Wanna Laugh?” (Quer rir?)… A outra piadinha é com o nome do algoritmo original do AES, chamado de “Rijndael” (junção dos nomes de seus inventores) e o refúgio dos elfos no Senhor dos Anéis, “Rivendell”. Embora a pronúncia seja diferente, a grafia é bem parecida, não?
Criptografia simétrica de blocos
O objetivo de um algoritmo de criptografia de blocos, do qual o AES faz parte, é transformar um bloco de dados original (que é chamado de plain text ou, aqui, chamarei de “texto”) em um bloco de dados criptografado (chamado de cipher — e não estou falando do sacana que traiu Neo e a turma do Morpheus em Matrix — ou “texto cifrado”, que chamarei de “cifra”), mediante uma chave. O algoritmo, é claro, “embaralha” o texto e obtém uma cifra que não seja facilmente transformada de volta em texto, a não ser que a chave correta seja fornecida.
A maioria dos algoritmos de criptografia de blocos usa blocos de tamanho fixo, tanto para o texto, quando para a cifra e a chave. É o caso do AES que vem em 3 sabores: AES-128, AES-192 e AES-256. Os valores referem-se ao tamanho da chave. Tanto o texto quanto a cifra têm tamanhos fixos de 128 bits (ou 16 bytes). Neste ponto você pode estar um pouco confuso, afinal de contas, tanto o texto quanto a chave deveriam ter tamanhos arbitrários. Acontece que o algoritmo só lida com esses tamanhos fixos e deve ser usado diversas vezes para criptografar blocos maiores. Mais adiante digo como isso pode ser feito.
Quanto à chave, se ela tiver tamanho diferente do padrão, deve-se adequá-la e existem diversos métodos para fazer isso. Um deles é usar um hash ou um valor único correspondente ao texto da chave, ao invés da própria.
Como o AES-128 funciona?
A justificativa matemática por trás do AES (ou Rijndael) é complicada. É baseada num troço chamado “campo de Galois” e não é interessante explorar isso aqui neste pequeno artigo (que, provavelmente ficará grande demais para o meu gosto), mas como ele funciona, do ponto de vista do que ele faz, é simples: Consiste em executar uma sequência de passos n vezes, de acordo com o tamanho da chave. São 10 passos para chaves de 128 bits, 12 para chaves de 192 bits e 14 para 256. Daqui por diante, o meu foco estará restrito à chaves de 128 bits. Porque é o caso mais simples e porque o meu exemplo usará as instruções AES disponíveis nos mais recentes processadores Intel.
Tanto para o texto quanto para a cifra, o bloco de 128 bits é encarado como uma matriz de 4×4 bytes onde a orientação é feita por coluna. Ou seja, o byte 0 está na posição (0,0), o byte 1 na posição (0,1), o byte 2 em (0,2) e assim por diante. AES-128 realiza um conjunto de operações tomando as matrizes do texto e chave como entrada e obtém uma matriz cifra. Na realidade a especificação chama as matrizes intermediárias de estado (state), mas prefiro encará-las como se fossem matrizes crifra intermediárias ou texto intermediárias, de acordo com o ponto de vista.
Eis, em pseudo código, o conjunto de operações que o AES-128 usa para criptografar um texto:
AddRoundKey(); for (i = 0; i < 9; i++) { SubBytes(); ShiftRows(); MixColumns(); AddRoundKey(); } SubBytes(); ShiftRows(); AddRoundKey();
A operação AddRoundKey efetua a adição de cada byte do texto com cada byte da chave e obtém uma matriz intermediária. Essa “adição” é, na verdade, um “ou exclusivo” (XOR) entre os bytes (por isso o símbolo usado é ⨁). É bom notar que a primeira chamada apenas “adiciona” a chave ao texto.
Antes que a rotina acima possa ser usada outras 9 chaves são criadas com base na chave inicial, com o objetivo de adicionar entropia ao processo criptográfico. Cada chave “derivada” é usada em uma das 8 chamadas, dentro do loop, a AddRoundKey e na chamada final da mesma rotina. Esse processo de derivar novas chaves chama-se key expansion, ou expansão de chave.
Depois da primeira “adição”, a operação SubBytes efetua uma substituição dos bytes da matriz intermediária de acordo com a seguinte transformação:
Onde corresponde ao bit n do texto e
ao bit n do byte “substituído”. Essa substituição não precisa ser feita com cálculo matricial, podemos usar uma tabela de substituição, chamada de Reijndael subtitution box ou “S-Box”:
unsigned char sbox[] = { // 0 1 2 3 4 5 6 7 8 9 A B C D E F 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, //0n 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, //1n 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, //2n 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, //3n 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, //4n 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, //5n 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, //6n 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, //7n 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, //8n 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, //9n 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, //An 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, //Bn 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, //Cn 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, //Dn 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, //En 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 //Fn };
Agora temos uma matriz intermediária que não lembra em nada o texto, mas AES faz mais: A operação ShiftRows embaralha as linhas fazendo a rotação de cada uma para a esquerda. A primeira linha é deixada como está, a segunda é rotacionada em 1 byte a terceira em 2 e a quarta em 3 (veja a figura abaixo)
A operação MixColumns é a parte complicada de explicar e é a parte mais intimamente ligada aos “campos de Galois”. Trata-se de multiplicação polinomial que ocorre entre as colunas da matriz intermediária (veja a especificação para entender o “atalho” usado na multiplicação matricial).

No fim das contas, o bloco de 16 bytes final está criptografado. Depois dessa complicação toda, é muito difícil obter o texto a partir da cifra sem a chave e, mesmo assim, precisaremos realizar todas essas operações de forma inversa:
AddRoundKey(); for (i = 0; i < 9; i++) { InvShiftRows(); InvSubBytes(); AddRoundKey(); InvMixColumns(); } InvShiftRows(); InvSubBytes(); AddRoundKey();
Onde a chave é também expandida, mas informada na ordem inversa, ou seja, o último AddRoundKey é o XOR com a chave original. As operações InvShiftRows, InvSubBytes e InvMixColumns faz a operação inversa de suas irmãs… InvShiftRows é óbvia: O que foi rotacionado para a direita será rotacionado para a esquerda. Já InvSubBytes e InvMixColumns usam as funções inversas daquelas especificadas na criptografia. Assim como SubBytes, InvSubBytes pode ser implementado por uma consulta em tabela, chamada de “Inverse Subtitution Box” ou InvS-Box:
unsigned char invsbox[] = { // 0 1 2 3 4 5 6 7 8 9 A B C D E F 0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, //0n 0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, //1n 0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, //2n 0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, //3n 0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, //4n 0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, //5n 0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, //6n 0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, //7n 0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, //8n 0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, //9n 0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, //An 0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, //Bn 0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, //Cn 0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, //Dn 0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, //En 0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d //Fn };
As instruções AES
A Intel disponibiliza, em algumas arquiteturas (Haswell em diante), algumas instruções que efetuam os passos necessários para criptografar ou descriptografar blocos de 128 bits usando AES aproveitando-se do fato de que um registrador usado em SSE tem exatamente 128 bits de tamanho! A instrução AESENC é usada para os primeiros 9 passos e AESENCLAST para o último (onde falta o MixColumns). Existe também a instrução AESKEYGENASSIST, que auxilia na expansão da chave.
Já para a de-criptografia, existem as instruções AESDEC e AESDECLAST. O único problema é que a expansão da chave é diferente para esse processo por causa da maneira como a Intel implementou essas instruções! Para facilitar o processo a instrução AESIMC (que é a mesma InvMixColumns de antes) é usada para derivar a expansão reversa da chave.
Eis um exemplo de código usando essas instruções, sob a forma de funções intrínsecas:
// Compilar usando as chaves -maes e -msse2 (se no modo i386). #include <string.h> #include <x86intrin.h> // Criptografa um bloco. #define DO_ENC_BLOCK(m,k) \ do{ \ m = _mm_xor_si128 (m, k[0]); \ m = _mm_aesenc_si128 (m, k[1]); \ m = _mm_aesenc_si128 (m, k[2]); \ m = _mm_aesenc_si128 (m, k[3]); \ m = _mm_aesenc_si128 (m, k[4]); \ m = _mm_aesenc_si128 (m, k[5]); \ m = _mm_aesenc_si128 (m, k[6]); \ m = _mm_aesenc_si128 (m, k[7]); \ m = _mm_aesenc_si128 (m, k[8]); \ m = _mm_aesenc_si128 (m, k[9]); \ m = _mm_aesenclast_si128(m, k[10]); \ } while(0) // Decriptografa um bloco. #define DO_DEC_BLOCK(m,k) \ do{ \ m = _mm_xor_si128 (m, k[10]); \ m = _mm_aesdec_si128 (m, k[11]); \ m = _mm_aesdec_si128 (m, k[12]); \ m = _mm_aesdec_si128 (m, k[13]); \ m = _mm_aesdec_si128 (m, k[14]); \ m = _mm_aesdec_si128 (m, k[15]); \ m = _mm_aesdec_si128 (m, k[16]); \ m = _mm_aesdec_si128 (m, k[17]); \ m = _mm_aesdec_si128 (m, k[18]); \ m = _mm_aesdec_si128 (m, k[19]); \ m = _mm_aesdeclast_si128(m, k[0]); \ } while(0) // Conterá a chave expandida e a inversa. static __m128i key_schedule[20]; static __m128i aes_128_key_expansion(__m128i key, __m128i keygened) { keygened = _mm_shuffle_epi32(keygened, _MM_SHUFFLE(3, 3, 3, 3)); key = _mm_xor_si128(key, _mm_slli_si128(key, 4)); key = _mm_xor_si128(key, _mm_slli_si128(key, 4)); key = _mm_xor_si128(key, _mm_slli_si128(key, 4)); return _mm_xor_si128(key, keygened); } #define AES_128_key_exp(k, rcon) \ aes_128_key_expansion(k, \ _mm_aeskeygenassist_si128(k, rcon)) // Carrega a chave e a expande. void aes128_load_key(char *key) { key_schedule[0] = _mm_loadu_si128((const __m128i *) key); key_schedule[1] = AES_128_key_exp(key_schedule[0], 1); key_schedule[2] = AES_128_key_exp(key_schedule[1], 2); key_schedule[3] = AES_128_key_exp(key_schedule[2], 4); key_schedule[4] = AES_128_key_exp(key_schedule[3], 8); key_schedule[5] = AES_128_key_exp(key_schedule[4], 16); key_schedule[6] = AES_128_key_exp(key_schedule[5], 32); key_schedule[7] = AES_128_key_exp(key_schedule[6], 64); key_schedule[8] = AES_128_key_exp(key_schedule[7], 128); key_schedule[9] = AES_128_key_exp(key_schedule[8], 27); key_schedule[10] = AES_128_key_exp(key_schedule[9], 54); // A expansão inversa! key_schedule[11] = _mm_aesimc_si128(key_schedule[9]); key_schedule[12] = _mm_aesimc_si128(key_schedule[8]); key_schedule[13] = _mm_aesimc_si128(key_schedule[7]); key_schedule[14] = _mm_aesimc_si128(key_schedule[6]); key_schedule[15] = _mm_aesimc_si128(key_schedule[5]); key_schedule[16] = _mm_aesimc_si128(key_schedule[4]); key_schedule[17] = _mm_aesimc_si128(key_schedule[3]); key_schedule[18] = _mm_aesimc_si128(key_schedule[2]); key_schedule[19] = _mm_aesimc_si128(key_schedule[1]); } // Faz a criptografia de um texto e obtém a cifra. void aes128_enc(char *cipherText, char *plainText) { __m128i m = _mm_loadu_si128((__m128i *) plainText); DO_ENC_BLOCK(m, key_schedule); _mm_storeu_si128((__m128i *) cipherText, m); } // Faz a decriptografia de uma cifra e obtém o texto. void aes128_dec(char *plainText, char *cipherText) { __m128i m = _mm_loadu_si128((__m128i *) cipherText); DO_DEC_BLOCK(m, key_schedule); _mm_storeu_si128((__m128i *) plainText, m); }
As instruções AES da Intel são úteis em dois sentidos: As tabelas sbox e invsbox não estão visíveis porque estão dentro de seu processador e, portanto, não podem ser modificadas por um atacante. Além disso, as instruções usam SIMD, o que aceleram as coisas um cadinho.
Criptografando diversos blocos
Obviamente temos que dividir os dados que serão criptografados em blocos de 16 bytes. Cuidados devem ser tomados para o caso em que o tamanho de algum bloco seja menor que 16 bytes e algum esquema de padding deve ser feito. Fora isso, assumindo que todos os sub blocos tenham exatamente 16 bytes de tamanho, o método mais ingênuo é usar a mesma chave para todos. Esse método é chamado de ECB (Electronic CodeBook). Ele é “ingênuo” porque, com blocos diferentes do texto sendo criptografados pela mesma chave, usando o mesmo algoritmo, é possível (porém improvável) que um atacante consiga uma “dica” de qual seja a chave.
Para evitar isso, outro método bastante usado é o CBC (Cipher Block Chaining), onde o bloco cifrado anterior é usado como chave para criptografar o próximo. Junte esse encadeamento (chaining) e a complexidade do AES e fica muito difícil alguém obter alguma “dica” sobre a chave original.
O modo CBC exige, também, uma chave extra, não necessariamente secreta, e totalmente aleatória para garantir um melhor embaralhamento… chama-se IV (de Initialization Vector) e, geralmente, é criado por algum gerador de valores aleatórios criptográficos (como a instrução RDRAND, por exemplo). Daí a necessidade de usar um RNG confiável em processos de criptografia.
Existem outros esquemas, como CFB e CTR (dê uma olhada neste artigo para ver a diferença).