Wanna laugh? Ou criptografia no refúgio dos elfos?

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).

As operações do AES

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).