Introdução à Criptografia – Parte 3

E vamos chegando agora na terceira e última etapa da minha série de artigos com uma introdução à criptografia para desenvolvedores. Na parte 1, falamos bastante sobre criptografia simétrica, enquanto na parte 2 falamos de criptografia assimétrica. Em ambos os casos estávamos falando de criptografia reversível, ou seja, que você pode criptografar e descriptografar. Nesta parte 3 quero falar do terceiro grupo de algoritmos de criptografia mais famoso que são os algoritmos de dispersão ou hashing, que são algoritmos especiais que não permitem qualquer tipo de reversão, ou seja, são de “mão única”, você criptografa e não tem mais como descriptografar.

Mas afinal, isso faz algum sentido? Por que eu usaria um algoritmo desses?

Tudo isso você vai entender neste artigo.

#1 – O que é Hashing?

Hashing (“dispersão”) é um conceito computacional onde para uma dada sequência de bytes de tamanho variável, seja gerada uma sequência de bytes de tamanho fixo. Sim isso é bem vago e não parece muito útil, mas você está enganado.

Os valores de hash são gerados a partir de uma função hash, que é responsável por transformar a sequência original em uma sequência determinística e exclusiva para cada entrada. Ou ao menos esse é o objetivo sempre (nem sempre alcançável).

Inicialmente as funções hash eram usadas para construir hash tables ou tabelas de dispersão. A ideia era resolver um problema clássico de encontrar informações sem ter de vasculhar linearmente em toda coleção. Uma primeira abordagem criada para resolver essa questão foi a árvore binária de busca, que possui uma complexidade de desenvolvimento razoável e uma complexidade média de O(h/2), onde h é a altura da árvore, bem melhor que a complexidade O(n) de buscar algo em um array não ordenado (n = número de elementos) ou O(n/2) de buscar algo com busca binária em um array ordenado. A performance de inserção da primeira opção é ruim, a performance de busca da segunda é horrível e a performance das sucessivas reordenações da terceira opção é pior ainda.

Caso não saiba nada sobre complexidade de algoritmos e notação Big O, o vídeo abaixo dá uma introdução.

No entanto, as tabelas hash vão muito além disso com uma ideia completamente diferente. Imagine que você tenha uma função matemática que transforma o dado que você deseja guardar em uma sequência binária de tamanho fixo (independente do tamanho original do dado), que pode ser usada, por exemplo, para determinar a posição do dado na sua coleção?

Mais tarde, quando for procurar por algum dado, basta aplicar essa função novamente no input da pesquisa para se achar a localização exata novamente daquele dado. Obviamente nem tudo são flores e existem diversas preocupações adicionais que devemos ter com valores e funções hash. Mas o nosso interesse nesse tópico é mais focado na aplicação de hashing na criptografia.

#2 – Hashing Criptográfico

Funções hash são funções criptográficas, mas não deve ser confundido com criptografia em si. Via de regra, encriptação é uma tarefa de mão dupla que você usa sempre que precisa armazenar com segurança uma informação, mas precisa recuperá-la mais tarde através de uma chave simétrica ou privada. Já o hash, é comumente utilizado quando você necessita comparar informações.

Na criptografia usamos hashes para diversos fins e existem diversas funções de hashing disponíveis. A ideia aqui é que uma função hash criptográfica sempre:

gere uma sequência binária de tamanho fixo para qualquer tamanho de entrada;
gere sempre a mesma sequência de bits para a mesma entrada (determinístico);
gere uma sequência binária única para cada entrada única (sem colisões);
não permite conhecer a entrada original a partir de seu hash (mão única);
não permita modificar mensagens sem modificar o hash dela;
seja inviolável através de força bruta e cripto-análise;
um bit diferente na entrada deve produzir um hash completamente diferente (avalanche effect)
tenha uma performance boa;

Como exemplo, use este site aqui BCrypt Generator. O Bcrypt é um dos algoritmos de hashing mais famosos da atualidade, sendo muito utilizado para comparação de senhas em aplicações com autenticação (falarei mais a seguir). Experimente informar uma string qualquer no primeiro campo e clique no botão de Encrypt. Verá que o resultado será uma string indecifrável. Mude apenas uma letra da sua string e encripte de novo, veja o quanto muda. Experimente também colocar uma string muito grande, verá que a saída tem sempre o mesmo tamanho, isso é hashing.

Mas Luiz, tem um campo de decrypt ali ao lado, hashes não eram indecifráveis?

E são! Aquela seção de decrypt exige que você forneça o hash e a string original. O que ela faz nada mais é do que gerar o hash novamente sobre a string informada e comparar com o hash informado, para ver se são o mesmo. E é exatamente assim que é utilizado em sistemas com autenticação, como falarei mais adiante.

Mas este é apenas um dos usos de hashing na computação, vejamos mais alguns.

#3 – Aplicações de Hashing

Índice de Pesquisa

Não nos importa muito aqui em segurança, mas talvez seja o uso mais comum de hashing em estruturas de dados em Java como HashSet (que usa o hashcode do objeto como chave para evitar duplicações), HashMap (que usa o hashcode do objeto como chave e como índice de busca), o Map do JavaScript, o mapping do Solidity e o Dictionary do C# (que funcionam análogos ao HashMap do Java).

Ou seja, toda vez que uma chave é adicionada em um “mapa” desses, é gerado um hash da chave que fica em um índice apontando para o valor da mesma. Mais tarde, quando pesquisando-se no “mapa”, gera-se o hash do valor fornecido e compara-se com o índice, para encontrar exatamente o valor que se deseja. Com isso mantemos um tempo constante de busca O(1) ao invés de um tempo linear O(n) que teríamos sem o índice.


//exemplo JS = Map usa hashtable internamente
const map1 = new Map();

map1.set('a', 1);
map1.set('b', 2);
map1.set('c', 3);

console.log(map1.get('a'));

//exemplo JS = Map usa hashtable internamente

const map1 = new Map();

map1.set('a', 1);

map1.set('b', 2);

map1.set('c', 3);

console.log(map1.get('a'));

Pseudo-aleatoriedade

Também não nos importa muito em segurança, mas dada uma chave inicial pode desencadear uma função hash recursiva que gere bits pseudo-aleatórios. Isso pode ser útil em algumas situações que precisamos de aleatoriedade.

Autenticação

Muito popular em sistemas operacionais modernos e em qualquer banco de dados que armazene senhas, jamais guarda-se a senha em texto plano, mas sim o hash da mesma. Quando o usuário vai se autenticar novamente, aplica-se a função hash sobre a senha que ele informou e compara-se com o hash existente no banco de dados para aquele usuário.

Sendo o hash uma função de mão única, não há como recuperar uma senha, sendo obrigado a gerar uma nova caso o cliente se esqueça. O uso de Salt Numbers é recomendado para evitar ataques de aniversário com Rainbow Tables (tabelas de hashes já computados para senhas comuns), sendo que um salt number nada mais é do que bytes adicionais anexados ao final da mensagem que será encriptada. Abaixo exemplo retirado da documentação do pacote Bcrypt JS para JavaScript. O Bcrypt é um dos algoritmos de criptografia mais populares para autenticação atualmente.


//encrypt
const bcrypt = require('bcryptjs');
const hash = bcrypt.hashSync("password", 10);
// salve o hash como a senha do user no banco

//decrypt
// carregue o hash salvo do user no banco
bcrypt.compareSync("password", hash); // true
bcrypt.compareSync("wrong_password", hash); // false

//encrypt

const bcrypt = require('bcryptjs');

const hash = bcrypt.hashSync("password", 10);

// salve o hash como a senha do user no banco

//decrypt

// carregue o hash salvo do user no banco

bcrypt.compareSync("password", hash); // true

bcrypt.compareSync("wrong_password", hash); // false

Consistência

Esse é o uso mais difundido e você já foi impactado por ele mesmo sem notar.

No CPF, os dois últimos números são os dígitos verificadores, certo? Na verdade o CPF tem apenas 9 dígitos, os 2 finais são fruto de uma função hash que tem como entrada os 9 primeiros.

Nos boletos, temos um dígito verificador antes do preço a ser pago (última seção). Aquele dígito é fruto de uma função hash em cima dos números anteriores à ele, para que os sistemas bancários possam facilmente saber se houve erro de digitação ou leitura do boleto na hora do pagamento.

Na blockchain, cada transação possui um hash baseado nos dados da mesma. Além disso, os hashes das transações aliado ao hash do bloco anterior são usados para gerar o hash do novo bloco que está sendo minerado, o que garante a consistência da transação, do bloco e da blockchain um todo (cadeia de blocos). Assim, caso qualquer dado seja adulterado ou forjado, é muito fácil de matematicamente saber. Se quiser saber mais como isso funciona na prática, a playlist abaixo pode ajudar.

Outra aplicação é o chamado checksum, com aplicações populares como CRC. Esse tipo de técnica é muito utilizada para verificar se arquivos foram corrompidos em download (bit torrent e git usam) intencionalmente ou não (a polícia forense faz isso em HDs coletados em investigações). Caso contrário, os arquivos deveriam ser verificados bit a bit e seria inviável pois não teria como enviar o código de verificação junto do arquivo, pois eles teriam o mesmo tamanho.

Ou seja, em todos estes casos, sempre que queremos verificar se uma informação está correta, podemos reaplicar a função hashing sobre a mesma informação para ver se produz o mesmo resultado. Para que funcione dessa forma, os algoritmos devem ser públicos e a maioria dos populares, como CRC, jamais devem ser vistos como criptografia, pois o foco não é segurança, mas consistência.

Assinatura Digital

Em transferência de arquivos sigilosos pela Internet ou autenticação de requisições, como por exemplo quando transferimos documentos ao governo usando assinatura digital, costuma-se utilizar métodos mais elaborados do que funções hash simples. Construções como HMAC em conjunto com MD5 e SHA-1 obrigam o hash a ser montando anexando uma senha à mensagem, definida pelo usuário e que garante a autenticidade e consistência daquela requisição, uma vez que apenas o emissor tem a senha secreta. Isso é muito útil, por exemplo, para evitar aceitar requisições forjadas por pessoas não idôneas, garantindo consistência e autenticação de uma vez só.

Também não é incomum o uso de função hash sobre um hash já calculado, para diminuir ainda mais as chances de descoberta por força bruta, o que é feito por exemplo pelo algoritmo Bcrypt em seus vários rounds. Abaixo, um exemplo de assinatura digital para podermos enviar uma ordem de compra de criptomoedas na corretora Binance. Repare como é usada uma secret key no processo de assinatura com protocolo HMAC, visando que somente o dono da conta possa enviar ordens em nome dele próprio.


async function newOrder() {
    const data = {
        symbol: "BTCUSDT",
        side: "BUY",
        type: 'MARKET',
        quantity: "1",
        timestamp: Date.now()
    };

    const signature = crypto
        .createHmac('sha256', "your secret key here")
        .update(`${new URLSearchParams(data)}`)
        .digest('hex');

    const newData = { ...data, signature };
    const qs = `?${new URLSearchParams(newData)}`;

    const result = await axios.post(
        `${process.env.API_URL}/v3/order${qs}`, 
        {}, 
        { headers: { 'X-MBX-APIKEY': 'your access key here' } }
    );
    console.log(result.data);
}