Autenticação Criptográfica

Resumão

MAC significa Código de Autenticação de Mensagem (Message Authentication Code). Este código é enviado junto com a mensagem, para provar sua integridade e autenticidade.

Integridade: Se algum bit da mensagem for alterado o MAC fica inválido. Semelhante a enviar a mensagem junto com sua hash.

Autenticidade: Apenas quem possui a chave criptográfica K é capaz de criar e verificar uma mensagem autenticada com esta chave.

A partir da chave e da mensagem criamos o código de autenticação, também chamado de TAG de autenticação. Enviamos o par (MENSAGEM, TAG) e quem recebe este par pode verificar a integridade e autenticidade da mensagem usando a chave K.

A chave K e a tag de autenticação precisam ambas ter comprimentos de acordo com o nível de segurança da aplicação.

Autenticação HMAC

A primeira opção é HMAC, que usa uma Função Hash para criar o código de autenticação. Eis o algoritmo:

se (comprimento(K) > Hash.Tamanho_Bloco) { K = Hash(K) }
enquanto (comprimento(K) < Hash.Tamanho_Bloco) { K = K || 00 }
K1 = K XOR 5C…5C
K2 = K XOR 36…36
TEMP = Hash(K2 || MENSAGEM)
TAG = Hash(K1 || TEMP)

Usamos uma chave para criar duas chaves diferentes. Cada uma é usada em uma etapa: criar uma hash da mensagem (TEMP) e tag de autenticação (TAG). Note que estamos utilizando o símbolo || com o significado de concatenação.

Antes de gerar K1 e K2, a chave K deve ter o tamanho do bloco da função hash. Este preenchimento do bloco permite pré-computar Hash(K1) e Hash(K2), acelerando a autenticação.

Se o comprimento da chave K for maior que o bloco de entrada da função hash (64 bytes/512 bits para SHA-256 ou 128 bytes/1024 bits SHA-512), primeiro realizamos a hash da chave.

Então, se o comprimento da cahve K for menor que o tamanho do bloco de entrada da função hash adicionamos zeros até completar o tamanho.

Podemos usar qualquer função hash com HMAC.

TAG =HMAC-SHA256(K, MENSAGEM)
TAG =HMAC-SHA512(K, MENSAGEM)

Obviamente vamos utilizar hashes que são criptograficamente seguras, por exemplo SHA2 e SHA3, e com comprimentos de saída adequados para o nível de segurança exigido pela aplicação. A chave K também precisa ser longa o suficiente para ser segura.

Autenticação KMAC

KMAC é uma extensão do padrão SHA3 usando XOFs (funções hash com saída de comprimento variável) baseada na esponja criptográfica Keccak.

Uma vantagem clara de usar KMAC, é que permite diferentes comprimentos de saída, gerando TAGs completamente diferentes para cada comprimento de saída.

KMAC é mais flexível e complicada que HMAC. Não vamos entrar em detalhes.

Podemos escolher entre os níveis de segurança máximos de 128 e 256 bits.

TAG =KMAC-128(K, MENSAGEM, COMPRIMENTO_TAG)
TAG =KMAC-256(K, MENSAGEM, COMPRIMENTO_TAG)

A chave K e a TAG precisam ter comprimentos compatíveis com o nível de segurança da aplicação e a função KMAC também precisa ser escolhida adequadamente. Ex: chave 256 bits e tag 256 bits só fazem sentido com KMAC-256.

Autenticação CBC-MAC

É possível também usar o sistema de autenticação CBC-MAC, que usa cifras em blocos como AES em modo CBC.

CBC-MAC possui características semelhantes a HMAC. Usa duas chaves diferentes K1 e K2, geradas a partir de uma chave mestre K. Primeiro calculamos Cn, o último bloco do modo CBC com a chave K1. Então criptografamos este bloco com a chave K2, gerando a tag de autenticação.

K1 = K XOR 5C…5C
K2 = K XOR 36…36
C0 = EK1(IV)
Ci = EK1(Pi XOR Ci-1)
Cn = EK1(Pn XOR Cn-1)
TAG = EK2(Cn)

A tag de autenticação tem o mesmo comprimento do bloco da cifra, 128 bits no caso de AES.

TAG = CBC-MAC-AES(K, MENSAGEM)

Porque não usar HMAC ou KMAC sempre? Em sistemas embarcados com pouca memória de programa, por exemplo, pode ser inviável implementar uma cifra (como AES-128) e também uma hash (como SHA2 ou SHA3). Então usa-se a cifra para ambos criptografia e autenticação.

Vetor de inicialização e MACs

Note que no modo CBC-MAC, deixamos explícito a existência de um vetor de inicialização (IV).

Este é um nonce, um número utilizado apenas uma vez com a chave K. Ele pode ser aleatório ou um contador incrementado a cada mensagem.

O nonce serve para que duas mensagens tenham tags diferentes, mesmo se o conteúdo seja idêntico.

HMAC e KMAC também podem utilizar um IV, basta colocá-lo logo antes da mensagem:

MENSAGEM = IV || MENSAGEM

Isso é semelhante ao CBC-MAC, que coloca o IV no bloco zero, antes da mensagem.

Se considerarmos os IV como sendo parte da mensagem, sua função é de fazer com que sempre tenhamos uma mensagem diferente sendo autenticada, gerando sempre uma tag diferente.

Note que o vetor de inicialização (IV) é enviado junto com a mensagem, ou seja, não é secreto. Em alguns casos ele não é transmitido, se pode ser identificado pelo contexto.

Links Externos

Wikipedia HMAC

HMAC – FIPS PUB 198-1 – The Keyed-Hash Message Authentication Code

KMAC – NIST 800-185 – SHA-3 Derived Functions

Wikipedia CBC-MAC

CBC-MAC – FIPS PUB 113 – Computer Data Authentication

Leia mais:

Veja mais posts na Categoria Criptografia!

Criptografia Modos de Operação

Resumão

Exitem diversos modos de operação de criptografia com os quais podemos utilizar cifras de blocos, como a Criptografia AES.

Cada um tem suas características, que os fazem mais ou menos adequados para certas aplicações.

Os modos de operação mais comuns são: ECB, CBC, OFB, CFB, CTR.

EBC – Electronic Codebook

Livro Eletrônico de Códigos.

Cada chave criptográfica possui um livro de códigos, que relaciona dados plenos com dados cifrados. Este modo de operação é o mais simples, mas dificilmente é recomendado.

Encriptar:
Ci = EK(Pi)

Para n blocos, envia-se:
C1, C2, …, Cn

Decriptar:
Pi = DK(Ci)

Note que este modo revela igualdade igualdade de blocos.

Este modo exige que as mensagens sejam de tamanho divisível pelo tamanho do bloco (16 bytes para AES). Caso contrário, a mensagem deve ser preenchida (padding). [TODO Link padding.]

CBC – Cipher Block Chaining

Cadeia de Blocos Cifrados.

Os dados plenos Pi são misturados (XOR) com a cifra Ci-1 do bloco anterior antes de encriptar.

Encriptar:
C0 = EK(IV)
Ci = EK(Pi XOR Ci-1)

Para n blocos, envia-se:
IV, C1, C2, …, Cn

Decriptar:
C0 = EK(IV)
Pi = DK(Ci) XOR Ci-1

Este modo utiliza um vetor de inicialização (IV) que deve ser um número utilizado apenas uma vez (nonce) para cada chave K, ou seja, cada mensagem criptografada com a chave K precisa de um IV diferente. O IV não precisa ser secreto, pode ser transmitido junto com a mensagem.

Se repetir o mesmo IV os dados cifrados revelam igualdade dos primeiros blocos e a diferença (XOR) do primeiro bloco diferente. Conhecendo uma mensagem, revela-se a outra, exceto depois do bloco diferente. Isso no melhor dos casos, ou seja, com uma cifra ideal. Algumas cifras são extremamente fracas caso houver repetição de IV.

Note que o primeiro bloco cifrado é misturado com C0, que é o IV encriptado. Não se envia C0.

Este modo, assim como ECB, também exige que as mensagens sejam de tamanho divisível pelo tamanho do bloco ou que o último bloco seja preenchido (padding).

OFB – Output Feedback

Realimentação da saída.

Este modo transforma uma cifra de blocos (block cipher) em uma cifra de corrente (stream cipher).

Os dados plenos Pi são misturados (XOR) com a fonte pseudo-aleatória Oi-1 para realizar a encriptação.

Encriptar:
O0 = EK(IV)
Oi = EK(Oi-1)
Ci = Pi XOR Oi-1

Para n blocos, envia-se:
IV, C1, C2, …, Cn

Decriptar (idêntico a encriptar):
O0 = EK(IV)
Oi = EK(Oi-1)
Pi = Ci XOR Oi-1

Este modo utiliza um vetor de inicialização (IV) que deve ser um número utilizado apenas uma vez (nonce) para cada chave K, ou seja, cada mensagem criptografada com a chave K precisa de um IV diferente. O IV não precisa ser secreto, pode ser transmitido junto com a mensagem.

Se repetir o mesmo IV os dados cifrados revelam igualdade dos blocos e a diferença (XOR) dos blocos diferentes. Conhecendo uma mensagem, revela-se a outra. [Novamente… Isso no melhor dos casos, ou seja, com uma cifra ideal. Algumas cifras são extremamente fracas caso houver repetição de IV.]

Este modo não exige preenchimento (padding). Se o último bloco não está completo com dados plenos, podemos enviar apenas estes bytes encriptados de Cn, ignorando o restante dos bytes. Note que isso revela o tamanho da mensagem. Se o tamanho da mensagem deve ser secreto ou obfuscado é necessário realizar o preenchimento (padding).

CFB – Cipher Feedback

Realimentação de cifra.

Este modo transforma uma cifra de blocos (block cipher) em uma cifra de corrente (stream cipher).

Os dados plenos Pi são misturados (XOR) com a cifra anterior Ci-1 para realizar a encriptação.

Encriptar:
C0 = IV
Ci = Pi XOR EK(Ci-1)

Para n blocos, envia-se:
IV, C1, C2, …, Cn

Decriptar (idêntico a encriptar):
C0 = IV
Pi = Ci XOR EK(Ci-1)

Este modo utiliza um vetor de inicialização (IV) que deve ser um número utilizado apenas uma vez (nonce) para cada chave K, ou seja, cada mensagem criptografada com a chave K precisa de um IV diferente. O IV não precisa ser secreto, pode ser transmitido junto com a mensagem.

Como no modo CBC, se repetir o mesmo IV os dados cifrados revelam igualdade dos primeiros blocos e a diferença (XOR) do primeiro bloco diferente. Conhecendo uma mensagem, revela-se a outra, exceto depois do bloco diferente. [Novamente… Isso no melhor dos casos, ou seja, com uma cifra ideal. Algumas cifras são extremamente fracas caso houver repetição de IV.]

Este modo não exige preenchimento (padding). Se o último bloco não está completo com dados plenos, podemos enviar apenas estes bytes encriptados de Cn, ignorando o restante dos bytes. Note que isso revela o tamanho da mensagem. Se o tamanho da mensagem deve ser secreto ou obfuscado é necessário realizar o preenchimento (padding).

Outros modos

Existem ainda outros modos de operação.

CTR (Counter): Usa um nonce (número usado apenas uma vez) em conjunto com um contador para gerar uma sequência pseudo-aleatória e realizar XOR com os dados plenos (parecido com o que acontece nos modos OFB e CFB).

CFB “parcial”: É possível usar blocos menores do que o bloco da cifra no modo CFB.

Links Externos

Wikipedia Block Cipher Modes of Operation

NIST Recommendation for Block Cipher Modes of Operation

Leia mais:

Veja mais posts na Categoria Criptografia!

Criptografia AES

Resumão

A criptografia AES é um padrão de criptografia simétrica em blocos.

A criptografia tem o objetivo de esconder uma mensagem de uma pessoa que não deve lê-la. Uma função criptográfica possui uma chave e uma função inversa. Existem dois tipos de criptografia: simétrica e assimétrica.

Criptografia simétrica tem a característica de que todas as pessoas realizando a comunicação devem possuir a mesma chave.

Mesma chave = Criptografia simétrica.

Atualmente existem dois padrões de função criptográfica simétrica considerados seguros: AES e 3DES (DES triplo). Recomenda-se sempre utilizar AES, pois é mais rápido e mais seguro que 3DES.

O padrão AES trabalha em blocos de dados de 128 bits (16 bytes), ou seja, a entrada e a saída da função criptográfica tem este tamanho, e pode utilizar chaves criptográficas de 128, 192 e 256 bits, dependendo do nível de segurança necessário para a aplicação.

O padrão 3DES trabalha com blocos de 64 bits (8 bytes) e possui chaves de 112 bits.

Se a aplicação exige n bits de segurança, utilize uma função criptográfica de segurança equivalente. Na dúvida ou se não estiver especificado, utilize 128 bits de segurança.

Na dúvida ou se não estiver especificado, utilize 128 bits de segurança.

Função criptográficaTamanho do bloco (Entrada/Saída)Tamanho da chave (Segurança)Função hash equivalente
3DES (DES triplo)64 bits (8 bytes)112 bitsSHA-224
SHA3-224
AES-128128 bits (16 bytes)128 bitsSHA-256
SHA3-256
AES-192128 bits (16 bytes)192 bitsSHA-384
SHA3-384
AES-256128 bits (16 bytes)256 bitsSHA-512
SHA3-512
Funções criptográficas simétricas seguras AES e 3DES, tamanho do bloco, tamanho da chave, segurança e funções hash de segurança equivalente.

Hash e Criptografia

Funções Hash e Funções de Criptografia tem objetivos diferentes.

A hash serve para gerar um valor associado a uma mensagem. Qualquer outra pessoa pode calcular esse valor a partir da mensagem, desde que conheça qual algoritmo usar.

A criptografia serve para esconder uma mensagem de quem não possua a chave utilizada para encriptar. Mesmo sabendo o algoritmo utilizado, sem saber a chave deve ser muito difícil (praticamente impossível) determinar qual a mensagem a partir dela encriptada.

Ainda, diferente de uma função hash, uma função de criptografia possui uma chave e uma função inversa. Uma função hash é utilizada por todos da mesma maneira para dar o mesmo resultado, enquanto uma função criptográfica pode ser utilizada com chaves diferentes, dando resultados diferentes. A operação inversa é importante pois quem recebe a mensagem criptografada deve ser capaz de, através da chave, reverter ela para a mensagem original.

Para uma função criptográfica ser considerada segura: sua segurança deve depender apenas da chave; a mensagem criptografada deve ser indistinguível de valores gerados aleatoriamente; e conhecendo a mensagem e a mensagem criptografada, não deve ser possível determinar a chave.

Padrão de Criptografia AES

O padrão AES (Advanced Encryption Standard – Padrão de Criptografia Avançado) é um padrão de criptografia simétrica de blocos.

“Simétrica” significa que a mesma chave é utilizada para encriptar e para decriptar. “Blocos” significa que ela opera em um número fixo de bits.

A criptografia AES opera em blocos de 128 bits (16 bytes), ou seja, pega um bloco como entrada e gera como saída outro bloco de mesmo tamanho, com os bits misturados de acordo com a chave utilizada.

A chave utilizada na criptografia AES pode ser de três tamanhos: 128, 192, 256 bits. O tamanho da chave é escolhido a partir do nível de segurança exigido pela aplicação.

Encriptar um bloco com o algoritmo da criptografia AES consiste em executar diversas rodadas (turnos) de quatro operações: AddRoundKey, SubBytes, ShiftRows, MixColumns. Cada uma dessas operações possui uma função dentro do algoritmo.

Cada uma dessas operações tem uma operação inversa, utilizada na decriptação.

Adicionar chave da rodada (AddRoundKey)

Faz-se XOR do bloco com um a chave da rodada.

Essa é a única parte do algoritmo AES onde a chave criptográfica é utilizada e é ela que faz cada chave dar uma saída diferente.

A “chave da rodada” é um valor obtido a partir da chave de criptográfica, utilizando o algoritmo de escalonamento de chaves (key sechedule).

Adição ou XOR?

Note que no nome “AddRoundKey” falamos em “adicionar”, mas a operação utilizada é XOR. Eis a explicação:

O padrão AES não pensa nos bytes como números, mas como polinômios em GF(28).

Cada bit representa um coeficiente do polinômio. Por exemplo o byte 00001001, em vez do número 1×23 + 1×20 = 9, é o polinômio 1×x3 + 1×x0 = x3 + 1.

Os coeficientes só podem ser 0 ou 1 e, quando fazemos adição, consideramos sempre módulo 2, ou seja 0+0=0, 1+0=1, 0+1=1 e 1+1=0, o que é igual a operação binária XOR.

Por que usar essa matemática esquisita? Ela tem vantagens, características interessantes, que são utilizadas!

Substituição não-linear (SubBytes)

Cada um dos 16 bytes do bloco são trocados por outros 16 bytes, de acordo com uma tabela de substituição.

Esta é a única operação não-linear do algoritmo AES. A existência de operações não-lineares dificultam a utilização de técnicas lineares de criptanálise.

Esta substituição faz difusão dos bits dentro de um byte, ou seja, espalha os bits dentro de um byte.

DE onde veio tal tabela?

Note que a tabela não foi simplesmente inventada.

Ela foi criada a partir de uma propriedade muito legal dos polinômios GF(28). Lembra?

Todo polinômio tem um inverso multiplicativo, ou seja, todo polinômio p possui um inverso q = 1/p tal que pq = 1.

Devemos considerar a multiplicação de p e q módulo (resto da divisão por) um outro polinômio, que deve ser irredutível. Polinômio irredutível é como se fosse um “polinômio primo”, não pode ser divisível por outro polinômio, similar a números primos não serem divisíveis por outros números. O polinômio do módulo utilizado no algoritmo é x8 + x4 + x3 + x + 1.

Esta é a parte não linear: o inverso.

Depois de tirar o inverso do byte, faz-se uma multiplicação dos bits por uma matriz e uma soma (XOR) com constante. Isso serve para atrapalhar alguma criptanalise de utilizar a relação de inverso recém utilizada.

Em vez de fazer todos esses cálculos toda vez, utilizamos uma tabela.

Trocar linhas (ShiftRows)

Considerando o bloco de 16 bytes como sendo uma matriz 4×4, esta operação troca a posição dos bytes de cada linha.

A primeira linha é mantida, a segunda linha é deslizada um byte, a terceira linha é deslizada dois bytes e a quarta linha é deslizada três bytes.

Não tem segredo!

Esta substituição faz difusão dos bits nas linhas, que são blocos de 32 bits (4 bytes).

Misturar colunas (MixColumns)

Novamente consideramos o bloco de 16 bytes como sendo uma matriz 4×4, esta operação mistura cada uma das colunas.

Esta mistura faz difusão dos bits nas colunas, que também são blocos de 32 bits (4 bytes).

Por algum motivo (qual?), essa operação não é realizada na última rodada.

Mas como se calcula?

Aqui não há uma operação equivalente ou uma tabela.

Selecionamos uma coluna, cada byte dessa coluna é considerado um coeficiente GF(28) de um polinômio de terceiro grau em Z. Essa é a parte esquisita, onde todo mundo quebra a cabeça: Os coeficientes do polinômio são polinômios.

Note que estou usando o Z maiúsculo para os polinômios-coluna com coeficientes em GF(28). Anteriormente usei x minúsculo para os polinômios-byte GF(28).

Reiterando a explicação: cada coeficiente do “polinômio-coluna-em-Z” é um “polinômio-byte-em-x”.

Fazemos uma multiplicação do polinômio-coluna pelo polinômio {3}Z3 + {1}Z2 + {1}Z + {2}, módulo ao polinômio é Z4 + 1.

Como os coeficientes estão em GF(28), multiplicações são sempre calculadas módulo algum polinômio irredutível de oitavo grau. Usamos o mesmo polinômio citado anteriormente: x8 + x4 + x3 + x + 1.

Então, se a coluna é formada por 255, 1, 2 e 3, o polinômio é
{255}Z3 + {1}Z2 + {2}Z + {3}.

Lembre-se que os coeficientes são, na verdade, polinômios em GF(28). Então o polinômio acima, na verdade é…
(x7+x6+x5+x4+x3+x2+x+1)Z3 + (1)Z2 + (x)Z + (x+1)

E o polinômio multiplicador {3}Z3 + {1}Z2 + {1}Z + {2}, na verdade é…
(x+1)Z3 + (1)Z2 + (1)Z + (x)

É isso ai, os coeficientes do polinômio em Z são polinômios em x.

Fazendo a multiplicação do polinômio-coluna com o polinômio 3Z3 + Z2 + Z + 2 obtemos um polinômio de sexto grau. Então fazemos a redução módulo Z4 + 1 e obtemos um polinômio de terceiro grau {231}Z3 + {248}Z2 + {255}Z + {31}.

Assim, depois da operação MixColumns, a coluna formada pelos números 255, 1, 2 e 3 é transformada na coluna 231, 248, 255 e 31.

Existe um atalho, que evita realizar as operações de multiplicação em Z e redução módulo Z4 + 1. Basta realizar uma multiplicação de um vetor (que representa a coluna) por uma matriz (que representa o polinômio multiplicador). Relembrando que os bytes sendo multiplicados, na verdade são polinômios em GF(28) e devem ser reduzidos módulo x8 + x4 + x3 + x + 1.

Número de rodadas

As quatro operações acima (AddRoundKey, SubBytes, ShiftRows, MixColumns) são realizadas diversas vezes, com o objetivo de realizar difusão (propagação de diferenças) e tornar mais difícil um ataque de criptanálise.

O número de rodadas executadas depende do tamanho da chave. Enquanto maior a chave, mais rodadas são necessárias.

Tamanho da chaveNúmero de rodadas
128 bits10
192 bits12
256 bits14
Número de rodadas da criptografia simétrica AES em relação ao tamanho da chave.

Links externos

Wikipedia AES

Especificação AES

Leia mais:

Veja mais posts na Categoria Criptografia!