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!

Funções HASH Criptográficas

Resumão

Uma função hash processa uma mensagem de tamanho arbitrário (qualquer número de bytes) e cria a partir dela uma sequência de bytes de tamanho fixo.

Ela deve ser uma função unidirecional, ou seja, não deve ser possível (ao menos na prática) realizar sua inversa. Deve dar resultados iguais para mensagens iguais e resultados claramente diferentes para mensagens diferentes. Mesmo para mensagens parecidas (trocando ou adicionando um bit ou uma letra) a diferença no resultado deve ser bem evidente.

Atualmente existem dois padrões de função hash considerados criptograficamente seguros: SHA2 e SHA3.

Ambos padrões definem hashes de diferentes tamanhos de saída e, consequentemente, diferentes níveis de segurança criptográficos: 224, 256, 384 e 512 bits.

Para uma aplicação que exige n bits de segurança criptográfica, usa-se uma hash com 2n bits de saída. Por exemplo, se eu preciso de 128 bits de segurança eu vou utilizar SHA-256 (SHA2) ou SHA3-256, que possuem o dobro de bits de saída.

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

HashSaídaSegurançaUsado em conjunto
com criptografia
SHA-224
SHA3-224
224 bits112 bits3DES (DES triplo)
SHA-256
SHA3-256
256 bits128 bitsAES-128
SHA-384
SHA3-384
384 bits192 bitsAES-192
SHA-512
SHA3-512
512 bits256 bitsAES-256
Hashes criptográficas seguras SHA2 e SHA3, tamanho da saída, segurança e algorítimos de criptografia com segurança equivalente.

Para que serve uma função Hash?

As funções hash servem ser utilizadas para diferentes propósitos.

Integridade de dados. Pode ser utilizada para confirmar que uma mensagem (ou arquivo) foi enviado corretamente. Quem envia a mensagem manda junto sua hash. Quem recebe a mensagem calcula a hash da mensagem e compara com a recebida.

Assinatura digital. Diretamente assinar digitalmente uma mensagem (ou arquivo) de tamanho arbitrário é complicado. Especialmente se muito grande exigiria chaves criptográficas tão grande quanto as mensagens. A assinatura digital então é realizada sobre a hash da mensagem, que tem um comprimento fixo.

Funções Hash Criptográficas

Funções hash criptográficas, além de associar uma saída de tamanho fixo com uma mensagem de tamanho arbitrário, tem objetivo de resistir a ataques criptográficos. Dessa forma elas podem ser utilizadas em conjunto com esquemas de criptografia.

Para isso ela deve resistir a três diferentes ataques: pré-imagem, segunda pré-imagem e colisão. Eles são discutidos abaixo.

Ataque Pré-imagem de Hash

Deve ser muito difícil (praticamente impossível) de encontrar uma mensagem x que gere uma hash pré-definida y. Ou seja, a função hash não deve ser invertível.

Por exemplo, o só o gênio da lâmpada poderia atender a este desejo:
“Eu quero encontrar uma mensagem cujo valor da SHA3-256 é e05dbb98c0c3665c1c95290a8c2245ba32ad7e366502f2a5fdb37b4001054692.”
Talvez nem ele.

Resposta: Uma palavra, dez letras, sem acentos, tudo minúsculo. Se calcular SHA3-224 dá 80ab895e2f664ab13a76581f41e8226a85540d5d9617eab2c29a5792.
Quer tentar? Você tem 2610 = 141.167.095.653.376 chances. Calculadora online SHA3-256.

Alguém capaz de realizar a pré-imagem, pode descobrir qual a mensagem a partir de sua hash.

De onde vem esse nome “pré-imagem”? Vem do conteúdo de matemática chamado funções. Uma função y = f(x) tem seu domínio (valores de x) e sua imagem (valores de y). Para uma função hash, o algoritmo é f, o domínio são as mensagens x e a imagem são os valores das hashes y. Pré-imagem significa ter a imagem e, a partir dela, determinar o domínio correspondente (como uma função inversa).

Ataque Segunda Pré-imagem de Hash

Se eu tenho uma mensagem x1 que tem uma hash y, deve ser muito difícil (praticamente impossível) de encontrar uma mensagem diferente x2 que dê a mesma hash y.

Pode soar muito parecido com o anterior. Sim, é!

Mas este ataque considera que o atacante conhece a mensagem original e quer descobrir uma segunda mensagem com mesma hash. Ou seja, conhecer a mensagem não deve dar nenhuma vantagem adicional para um ataque.

Eis aqui mais um pedido para o gênio da lâmpada:
“Eu quero uma mensagem diferente que dê a mesma SHA3-256 que ‘Olá, banco! Envie R$1.000,00 para Oscar. Obrigado!’ “

Alguém capaz de realizar a segunda pré-imagem, pode forjar assinaturas digitais. Pode trocar a mensagem assinada por uma outra mensagem, sem que isso seja percebido.

De onde vem esse nome “segunda pré-imagem”? Já temos uma pré-imagem: a pré-imagem de y é x1. Mas queremos uma segunda pré-imagem x2.

Ataque Colisão de Hash

Deve ser muito difícil (praticamente impossível) de encontrar duas mensagens diferentes x1 e x2 que dão uma mesma hash y.

Pode soar muito parecido com o anterior. Sim, é!

Mas este ataque não faz nenhuma restrição com respeito as mensagens, nem ao valor da hash.

Eis aqui mais um pedido para o gênio da lâmpada:
“Eu quero duas mensagens diferentes que dão a mesma SHA3-256. Não importa qual valor final da hash.”

Alguém capaz de realizar colisões pode gerar muita confusão e dor de cabeça em sistemas que dependem de hashes.

De onde vem esse nome “colisão”? Imagine que as mensagens são carros e o resultado da hash seja a vaga do estacionamento que devem usar. Mesmo quando da mesma marca, modelo, ano… são carros diferente e vão estacionar em vagas diferentes. Dois carros querendo entrar na mesma vaga geram uma colisão.

Links Externos

Wikipedia SHA2

Especificação SHA2

Wikipedia SHA3

Especificação SHA3

Leia mais:

Veja mais posts na Categoria Criptografia!

Software R no Ubuntu Linux

Instalando software R

É fácil instalar o software R no Ubuntu Linux. Use o comando abaixo:

$ sudo apt install r-base

Executável em linguagem R

No Linux podemos criar scripts (programas executáveis em arquivos de texto) e marcá-los com uma configuração para que possam ser executados facilmente. Basta usar o comando chmod. Assim podemos executar o programa com o comando ./PROGRAMA.

$ chmod +x PROGRAMA
$ ./PROGRAMA

Linux, a linguagem é R!

Mas e se o programa estiver escrito na linguagem do software R? Como fazer para o Linux saber que deve ser executado com na linguagem de programação R?

Basta colocar a seguinte primeira linha do programa em software R:

#!/usr/bin/r
# Programa ...
print(1+1)

#!/usr/bin/r – faz o Linux saber que o programa está escrito na linguagem do software R, já com opções adequadas para execução de scripts.

Outra opção, que imprime os comandos e as respostas intermediárias é o seguinte:

#!/usr/bin/R --vanilla -q -f
# Programa ...
print(1+1)

#!/usr/bin/R – faz o Linux saber que o programa está escrito na linguagem do software R.

--vanilla – faz o R não salvar, nem restaurar, o espaço de trabalho.

-q – faz o R não imprimir a versão

-f – indica que o R deve ler o próprio arquivo sendo executado (./PROGRAMA)

Para explorar mais opções verifique o manual do programa R. Só não se esqueça de deixar a opção -f por último!

man R

Memória de programa AVR/ATmega328P

Sempre que utilizamos strings e arrays constantes em nossos programas, por padrão elas vão parar na memória RAM. Como tempo pouca memória RAM, seria ótimo conseguir colocar isso na memória de programa, liberando a preciosa RAM para as variáveis.

Neste post vemos como fazer isso nos microcontroladores AVR, como o ATmega328P do Arduino Uno.

Continue lendo “Memória de programa AVR/ATmega328P”

Reduzindo o programa AVR/ATmega328P

O seu programa está grande demais? Muito lento para gravar o microcontrolador? Não cabe na memória? Vamos reduzir o programa!

Há alguns truques simples para reduzir o tamanho dos programas e, se não está utilizando todos, as chances são que seu executável está maior do que o necessário.

Vejamos como podemos reduzir o tamanho do programa gerado pelo compilador.

Continue lendo “Reduzindo o programa AVR/ATmega328P”

O Jogo de dados de Mozart – Probabilidade no Ensino Médio

Você sabia que podemos compor músicas jogando dados?
E isso tem tudo a ver com Matemática e Probabilidade!

Este vídeo faz parte da minha pesquisa de mestrado.
Espero que gostem e bons estudos!

Compilando código C/C++ com Makefile

Neste post mostramos como criar um Makefile para realizar a compilação de programas C/C++.

Makefiles são muito bons pra automatizar a execução de comandos, evitando ter que digitá-los toda vez.

Também gerenciam dependências entre arquivos, recompilando apenas o que é necessário.

Continue lendo “Compilando código C/C++ com Makefile”

TDD: Testando código C/C++ com Gcov

No post anterior (TDD: Testando código C/C++ com Boost.Test), explicamos como se cria uma suíte de testes com a biblioteca Boost.Test. Muito útil para testar a funcionalidade correta do código.

Neste post mostramos como utilizar o Gcov para verificar se todo o código é executado pelos testes. Criamos uma biblioteca simples e um conjunto de testes para ela.

Ferramentas de code coverage (cobertura de código) como Gcov são muito utilizados para “Desenvolvimento a partir de testes” (TDD – Test Driven Development).

No TDD desenvolvemos os códigos e seus testes em paralelo, para verificar que o código funciona e, no futuro, poder verificar se alguma mudança no código tenha causado um bug.

A análise da cobertura de código auxilia no TDD, identificando partes do código que não estão sendo testadas por completo.

Continue lendo “TDD: Testando código C/C++ com Gcov”

TDD: Testando código C/C++ com Boost.Test

Neste post mostramos como utilizar a biblioteca Boost.Test para testar seus códigos. Podemos compilar a biblioteca junto aos testes, sendo também possível utilizar uma versão pré-compilada para melhorar o tempo de compilação.

Bibliotecas de teste são muito utilizados para “Desenvolvimento a partir de testes” (TDD – Test Driven Development).

No TDD desenvolvemos os códigos e seus testes em paralelo, para verificar que o código funciona e, mais importante, no futuro poder facilmente verificar se alguma mudança no código tenha causado um bug.

Continue lendo “TDD: Testando código C/C++ com Boost.Test”

initramfs e fsck: Ubuntu Linux não inicia

O Ubuntu Linux não inicia e aparece um tal de initramfs! O que fazer?

Um computador meu estava parado por uns tempos, estava com algum problema. Travava, reiniciava do nada… De repente não ligava mais.

Então resolvi reviver ele: Levei na manutenção, deram um jeito nele e fizeram ele iniciar. Bastava remover um dos pentes de memória RAM, que estava com problemas. Agora ele liga e a tela do bootloader do Ubuntu Linux aparece.

Terminal com initramfs

Mas quando tentamos iniciar o sistema, em vez da interface gráfica, aparece o terminal: uma tela preta com algumas linhas escritas, aguardando algum comando:

(initramfs) _

No meio do texto temos escrito:
“The root filesystem on /dev/sda2 requires a manual fsck

Tradução livre:
“A raiz do sistema de arquivos em /dev/sda2 requer um fsck manual”

FSCK (File System ChecK) é uma ferramenta que chega e corrige o sistema de arquivos.

Depois de tantos travamentos e reinicializações inesperadas causadas pelo pente de RAM defeituoso, o sistema de arquivos ficou corrompido. O bootloader está pedindo para manualmente executarmos a verificação do sistema de arquivos.

Como corrigir

Para fazer isso executamos o seguinte comando:

fsck -C -V /dev/sda2

Um simples “fsck /dev/sda2” já resolveria, mas queremos ver o progresso (-C) e ver as explicações do que está sendo feito (-V), então adicionamos essas duas opções. Para ver as opções digite “fsck –help”.

Durante a execução do comando, algumas vezes (ou muitas vezes se o bicho estiver feio) aparece uma mensagem, aguardando interação, perguntando se alguns arquivos podem ser apagados, pois estão com algum defeito, não possuem referência ou alguma outra coisa. Basta apertar ENTER para confirmar e ele será apagado.

Coloque um peso na tecla caso se incomode em apertar ENTER muitas vezes.

Depois de algum tempo… O programa termina e basta reiniciar o computador com o comando

reboot

E agora?

O sistema provavelmente vai iniciar normalmente. Recomendo fazer um backup dos seus dados imediatamente e caso acontecer novamente também reinstalar o sistema.

Se ainda assim não iniciar, você vai ter que usar uma “versão live” do Ubuntu Linux para fazer um backup dos seus dados e então reinstalar o sistema.

Se você tem este problema, do Ubuntu Linux não iniciar e mostrar a tela do intramfs, esse post vai ajudar a solucionar.