TL;DR

Este artigo explora os fundamentos e aplicações práticas dos algoritmos de hash na cibersegurança, abrangendo:

• Definição e Funcionamento: Uma visão geral de como os hashes transformam dados de qualquer tamanho em uma pequena impressão digital única.
• Algoritmos Comuns: Discussão detalhada sobre MD5, SHA-1, SHA-256, SHA-3, e bcrypt, incluindo suas vantagens, vulnerabilidades e usos ideais.
• Árvores de Merkle: Explicação sobre como essas estruturas funcionam e seu papel essencial em tecnologias como blockchain.
• Implementações Práticas: Dicas sobre como implementar e utilizar hashes de forma segura em sistemas e aplicações, incluindo como verificar a integridade dos dados e proteger informações sensíveis.

O objetivo é fornecer uma compreensão abrangente que possa orientar escolhas informadas e seguras no uso de algoritmos de hash em projetos de TI e segurança de dados.

Introdução

Os hashes no dia-a-dia de cibersegurança é um assunto que, na maioria das vezes, é trivial, se limitando rasamente a senhas armazenadas e validação de arquivos. Porém, o entendimento de seu mecanismo (não necessariamente o domínio de seus modelos matemáticos complexos) leva a compreensão de seu uso e exploração de suas implementações (ou má implementações) que vão muito além do habitual discutido, passando até mesmo pela parte fundamental da cadeia blockchain. Este artigo foi escrito com o intuito de compartilhar meu centavo de conhecimento sobre o assunto de forma a contribuir um pouco mais com o entendimento dos principais algoritmos encontrados in the wild.

Algoritmos de hash são uma classe fundamental de funções usadas amplamente em computação e sistemas de segurança cibernética. Essencialmente, um algoritmo de hash é uma função que mapeia dados de tamanho arbitrário (“inputs”) para um conjunto de dados de tamanho fixo, conhecidos como “hash”. O resultado deste mapeamento, ou o valor de hash, é uma representação digital compacta do dado original.

O principal propósito dos algoritmos de hash é garantir a integridade dos dados, permitindo a verificação rápida de que o conteúdo não foi alterado desde a criação do hash. Isso é crucial em diversas aplicações, como na verificação de integridade de software durante downloads, na autenticação de usuários mediante a comparação de senhas hashadas, e na implementação de estruturas de dados eficientes como tabelas hash e árvores Merkle.

O uso adequado de algoritmos de hash contribui significativamente para a robustez dos sistemas de segurança, servindo como a primeira linha de defesa contra muitas formas de ataque cibernético que visam comprometer a integridade dos dados.

Árvores de Merkle

As árvores de Merkle, também conhecidas como árvores hash ou árvores de Merkle-Damgård, são uma estrutura de dados fundamental na criptografia e ciência da computação, usadas amplamente em sistemas de gerenciamento de dados distribuídos, como blockchain e sistemas de controle de versão.

Uma árvore de Merkle é uma árvore binária que permite a representação eficiente e segura de grandes conjuntos de dados, onde cada folha da árvore é um hash de blocos de dados e cada nó interno é um hash das concatenações dos hashes de seus nós filhos. A raiz da árvore, chamada de “raiz de Merkle”, atua como um resumo digital de todos os dados abaixo dela.

Funcionamento

O funcionamento das árvores de Merkle pode ser descrito nas seguintes etapas:

1. Hashing dos Dados: Inicialmente, pequenos blocos de dados são hashados individualmente. Estes hashes formam as folhas da árvore.

2. Construção da Árvore: A partir das folhas, a árvore é construída de baixo para cima. Cada nó na árvore é o hash da concatenação dos hashes de seus dois nós filhos. Esse processo continua até que apenas um nó (a raiz de Merkle) represente todos os dados.

3. Atualizações e Validações: Quando os dados são atualizados, apenas o caminho do dado alterado até a raiz precisa ser recalculado, economizando tempo e recursos computacionais. Para validar um conjunto de dados, basta verificar se o hash na raiz ainda representa corretamente todos os dados abaixo dela.

Esta lógica pode ser facilmente implementada em programação, em qualquer linguagem, podemos utilizar a biblioteca hashlib do Python para implementá-la:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import hashlib

def hash_dados(data):
    """Hash uma string usando SHA-256 e retorna o digesto hexadecimal."""
    hasher = hashlib.sha256()
    hasher.update(data.encode('utf-8'))
    return hasher.hexdigest()

class ArvoreMerkle:
    def __init__(self):
        self.folhas = []
        self.niveis = []

    def adiciona_folha(self, data):
        """Adiciona um bloco de dados à árvore criando uma nova folha."""
        dado_hash = hash_dados(data)
        self.folhas.append(dado_hash)
        self.constroi_arvore()

    def constroi_arvore(self):
        """Método privado para construir a árvore a partir das folhas atuais."""
        niveis = [self.folhas]
        while len(niveis[-1]) > 1:
            novo_nivel = []
            # Emparelhar e criar o hash dos pais
            for i in range(0, len(niveis[-1]), 2):
                esquerda = niveis[-1][i]
                direita = niveis[-1][i + 1] if i + 1 < len(niveis[-1]) else esquerda  # Duplica o último se número ímpar de folhas
                novo_nivel.append(hash_dados(esquerda + direita))
            niveis.append(novo_nivel)
        self.niveis = niveis

    def get_raiz(self):
        """Retorna a raiz da árvore de Merkle."""
        return self.niveis[-1][0] if self.niveis else None

    def verifica_folha(self, indice_folha):
        """Verifica uma folha e seus dados recalculando até a raiz."""
        if indice_folha >= len(self.folhas) or indice_folha < 0:
            return False
        hash_atual = self.folhas[indice_folha]
        for i in range(len(self.niveis) - 1):
            # Determinar o índice do irmão
            indice_irmao = indice_folha + 1 if indice_folha % 2 == 0 else indice_folha - 1
            if indice_irmao >= len(self.niveis[i]):
                indice_irmao = indice_folha  # Se fora de limite, usar o próprio hash
            hash_irmao = self.niveis[i][indice_irmao]
            # Calcular o hash do pai
            if indice_folha % 2 == 0:
                hash_atual = hash_dados(hash_atual + hash_irmao)
            else:
                hash_atual = hash_dados(hash_irmao + hash_atual)
            indice_folha //= 2
        return hash_atual == self.get_raiz()

# Exemplo de uso
if __name__ == "__main__":
    arvore = ArvoreMerkle()
    blocos_de_dados = ["bloco1", "bloco2", "bloco3", "bloco4"]
    for bloco in blocos_de_dados:
        arvore.adiciona_folha(bloco)

    print("Raiz da Merkle:", arvore.get_raiz())
    # Verificando o terceiro bloco ('bloco3')
    print("Verificação do bloco3:", arvore.verifica_folha(2))

Onde:

• hash_dados: Esta função recebe uma string como entrada e aplica uma função de hash SHA-256, retornando o resultado em hexadecimal.
• ArvoreMerkle: É a classe que representa a árvore de Merkle. Ela mantém uma lista de hashes das folhas e uma lista de níveis que representam os diferentes níveis da árvore até a raiz.
• adiciona_folha: Adiciona uma nova folha à árvore. Cada folha é um hash dos dados fornecidos.
• constroi_arvore: Constrói a árvore combinando os hashes das folhas e formando novos níveis até que apenas um hash, a raiz, reste.
• get_raiz: Retorna o hash na raiz da árvore, que é o hash que representa todos os dados.
• verifica_folha: Verifica se os dados de uma folha específica são consistentes com a raiz da árvore, efetuando o recalculo a partir da folha até a raiz.

Integração da Árvore de Merkle em Blockchain

1. Organização dos Blocos:

   • Em um blockchain, cada bloco contém um conjunto de transações. Para cada bloco, uma árvore de Merkle é construída usando as transações como folhas. Isto é, cada transação é primeiro hashada, e esses hashes são usados como folhas na árvore de Merkle.

2. Criação da Raiz de Merkle:

   • Os hashes das transações (folhas) são então combinados e hashados repetidamente em pares, formando a estrutura de árvore até que um único hash, a “raiz de Merkle”, seja formado. Esta raiz é um resumo de todas as transações no bloco e é armazenada no cabeçalho do bloco junto com outros elementos, como o hash do bloco anterior, timestamp, e nonce.

3. Verificação de Transações:

   • Quando um nó na rede blockchain precisa verificar a existência e integridade de uma transação específica, ele pode fazer isso sem baixar todas as transações de um bloco. Em vez disso, o nó pode simplesmente obter o caminho necessário dos hashes que levam da transação (folha) até a raiz de Merkle. Este caminho é conhecido como “prova de Merkle”.

4. Prova de Merkle:

   • Para verificar uma transação, o nó só precisa da transação em questão, da raiz de Merkle do bloco (que é publicamente conhecida e armazenada no cabeçalho do bloco) e da sequência de hashes do caminho de Merkle. Se, ao recombinar os hashes no caminho com o hash da transação original, o nó chegar à raiz de Merkle que corresponde à raiz armazenada no cabeçalho do bloco, a transação é confirmada como válida e não alterada.

Exemplo Prático de Uso em Blockchain

Suponhamos que queremos verificar a transação “bloco3” no blockchain:

• A transação é hashada, e junto com os hashes necessários dos irmãos no caminho para a raiz, é reconstruída a árvore até o topo.
• Se a reconstrução chegar à mesma raiz de Merkle que está no cabeçalho do bloco, a transação é considerada válida e integra. Isso é feito sem a necessidade de processar ou mesmo conhecer todas as outras transações no bloco.

Benefícios no Blockchain

• Eficiência: A verificação de transações pode ser realizada rapidamente e com um mínimo de dados necessários, ideal para redes descentralizadas onde a largura de banda e o armazenamento podem ser limitados.
• Segurança: A raiz de Merkle fornece um resumo criptográfico seguro de todas as transações, garantindo que qualquer alteração nas transações em um bloco seja facilmente detectada.
• Descentralização: Permite que cada nó verifique a integridade dos dados independentemente, sem depender de uma autoridade central.
• Escalabilidade: As árvores de Merkle são excepcionalmente adequadas para sistemas com grandes volumes de dados devido à sua capacidade de realizar verificações de integridade de maneira eficaz e eficiente.

Aplicações Práticas

1. Blockchain e Criptomoedas: Conforme vimos acima, as árvores de Merkle são uma peça essencial na estrutura do blockchain. Elas permitem a rápida e eficiente verificação da existência e integridade dos dados sem necessidade de baixar todo o blockchain. Isso é crucial para os nós de “light client” em redes como Bitcoin e Ethereum.

2. Sistemas de Controle de Versão: Em sistemas de controle de versão, como o Git, as árvores de Merkle são utilizadas para gerenciar as versões dos arquivos. Cada commit é representado como uma árvore de Merkle, permitindo que alterações sejam rastreadas de maneira eficiente e segura.

3. Sistemas de Arquivos Distribuídos: Em sistemas de arquivos distribuídos, como o IPFS (InterPlanetary File System), as árvores de Merkle facilitam a verificação rápida de que os dados recebidos de outros nós são completos e não corrompidos.

4. Deduplicação de Dados: As árvores de Merkle ajudam a identificar dados duplicados em diferentes blocos de um sistema, permitindo a reutilização de hashes armazenados para otimizar o armazenamento.

Aplicações Práticas dos Algoritmos de Hash

Os algoritmos de hash são uma ferramenta fundamental na segurança da informação, fornecendo uma maneira de criar uma assinatura digital única para dados de qualquer tamanho. Esta assinatura, ou valor de hash, desempenha um papel crucial em diversas aplicações, desde o armazenamento seguro de senhas até a verificação da integridade de software e a implementação de sistemas de assinatura digital.

Uma das aplicações mais críticas dos algoritmos de hash é no armazenamento seguro de senhas. Ao armazenar senhas, é imperativo que elas não sejam guardadas em texto claro para proteger contra a exposição direta em caso de uma violação de dados. Os algoritmos de hash transformam senhas em um conjunto indecifrável de caracteres.

Hashes também são amplamente utilizados para verificar a integridade de dados e software, assegurando que os arquivos não foram alterados desde sua criação. Este processo é essencial em ambientes onde os dados precisam ser transferidos via redes potencialmente inseguras.

De modo geral, seguindo o seguinte fluxo:

• Hashing de Arquivos: Um hash é calculado para o arquivo original e armazenado ou transmitido juntamente com o arquivo.
• Verificação: Quando o arquivo é recebido, ou antes de ser executado, um novo hash é gerado e comparado com o original. Se os hashes coincidirem, o arquivo não foi alterado; se diferirem, indica uma possível corrupção ou manipulação.

Os hashes também são fundamentais na implementação de assinaturas digitais e certificados, usados para verificar a autenticidade de documentos digitais e a identidade dos comunicadores.

• Criação de Assinaturas: Um hash do conteúdo a ser assinado é primeiro gerado. Esse hash é então criptografado com a chave privada do remetente, formando a assinatura digital.
• Verificação da Assinatura: Para verificar a assinatura, o receptor recalcula o hash do conteúdo e o compara com o hash descriptografado usando a chave pública do remetente. Se os hashes coincidirem, a assinatura é considerada válida.

Funcionamento Geral de um Algoritmo de Hash

Um algoritmo de hash recebe como entrada uma quantidade de dados de tamanho variável e produz uma saída de tamanho fixo, conhecida como valor de hash ou simplesmente hash. O processo é realizado por uma função, que executa cálculos específicos para transformar a entrada em uma string de bits de tamanho fixo. A natureza desses cálculos depende do algoritmo específico, mas geralmente envolve operações como permutações, substituições e combinações projetadas para serem rápidas de executar e capazes de dispersar uniformemente os valores de entrada ao longo do espaço de saída do hash.

Exemplo: Considere uma função de hash simples projetada para strings. Uma abordagem rudimentar pode envolver a conversão de cada caractere em seu código ASCII correspondente, somando esses valores e então aplicando um módulo com um número primo para garantir um valor de saída fixo. Claro, essa é uma simplificação e não seria segura para aplicações reais, mas ilustra o conceito de transformar uma entrada variável em uma saída de tamanho fixo.

Propriedades Desejáveis de um Bom Algoritmo de Hash

Para ser considerado seguro e eficiente, um algoritmo de hash deve exibir várias propriedades críticas:

1. Determinismo: A mesma entrada sempre deve produzir a mesma saída. Isso é essencial para verificar a integridade dos dados, pois qualquer alteração na entrada resultaria em um hash completamente diferente.

2. Eficiência: O algoritmo deve poder processar grandes quantidades de dados rapidamente, retornando o hash sem atrasos significativos. Isso é vital para aplicações que requerem processamento em tempo real ou que lidam com grandes volumes de dados.

3. Irreversibilidade (Resistência a pré-imagem): Deve ser computacionalmente inviável determinar a entrada original a partir de seu hash. Isso protege contra tentativas de reconstruir os dados apenas pelo conhecimento de seu hash, um aspecto crítico na proteção de informações sensíveis como senhas.

4. Resistência a colisões: Idealmente, deve ser impossível ou extremamente difícil encontrar duas entradas diferentes que resultem no mesmo hash. Isso impede ataques onde um invasor poderia substituir um item legítimo por outro malicioso que resulte no mesmo valor de hash.

5. Sensibilidade a pequenas mudanças na entrada: Um bom algoritmo de hash deve ter o que é frequentemente chamado de “efeito avalanche”, onde uma pequena mudança na entrada (como alterar um único bit) causa uma mudança significativa e imprevisível no hash resultante. Isso aumenta a segurança ao tornar as tentativas de adivinhar a entrada original mediante pequenas modificações impraticáveis.

Essas propriedades garantem que os hashes possam ser usados em contextos onde a segurança é crítica, como na assinatura digital de contratos eletrônicos ou na proteção contra a manipulação de registros digitais.

Os algoritmos de hash podem ser classificados em duas categorias principais: hashes criptográficos e não criptográficos. Ambos são projetados para transformar dados de entrada em uma string de saída de tamanho fixo, mas diferem significativamente em termos de finalidade, complexidade e segurança.

Hashes Não Criptográficos

Hashes não criptográficos são utilizados principalmente para fins de verificação rápida de dados e para a implementação eficiente de estruturas de dados como tabelas hash, usadas em algoritmos de pesquisa e armazenamento de dados. Eles são projetados para serem extremamente rápidos e minimizar colisões. No entanto, não são adequados para armazenar informações sensíveis, pois não são projetados para serem resistentes a ataques que tentam recuperar a entrada original ou encontrar colisões.

Exemplos de Hashes Não Criptográficos:

• FNV (Fowler-Noll-Vo): Popular para hash de strings em bases de dados e tabelas hash devido à sua simplicidade e velocidade.
• MurmurHash: Amplamente usado em sistemas distribuídos para particionamento de dados devido à sua eficiência e distribuição uniforme.

Esses algoritmos são ideais para aplicações onde a velocidade é mais crítica do que a segurança, como caches, sistemas de detecção de duplicatas, e certas aplicações de rede.

Hashes Criptográficos

Hashes criptográficos, por outro lado, são projetados para oferecer segurança. Eles são uma peça fundamental da infraestrutura de segurança sendo usados em funções como a verificação de integridade de dados, autenticação e assinaturas digitais. Estes algoritmos possuem propriedades específicas, como resistência a colisões e irreversibilidade, que os tornam resistentes a tentativas de reversão ou de encontrar duas entradas que produzam o mesmo hash.

Exemplos de Hashes Criptográficos:

• MD5: Embora agora seja considerado inseguro e suscetível a ataques de colisão, foi amplamente usado no passado.
• SHA-1: Similar ao MD5 em termos de uso, mas também comprometido por vulnerabilidades de segurança conhecidas.
• SHA-256: Parte da família SHA-2, esses algoritmos são atualmente recomendados para novos sistemas devido à sua robustez contra as vulnerabilidades encontradas em precursores como SHA-1 e MD5.
• Bcrypt: Projetado especificamente para hashing de senhas, inclui mecanismos como salting e key stretching para proteger contra ataques de força bruta e rainbow tables.

Os algoritmos de hash criptográficos são essenciais para garantir a confidencialidade e integridade dos dados em muitas aplicações de segurança. Eles são projetados para serem lentos propositalmente (como no caso do Bcrypt) ou computacionalmente intensivos para tornar inviável a execução de ataques de força bruta.

Aspectos Técnicos dos Algoritmos

Construção de Merkle–Damgård

A construção de Merkle–Damgård é uma técnica utilizada para construir funções de hash criptográfico a partir de uma função de compressão. Essa construção garante que mesmo pequenas funções de compressão possam ser usadas para processar mensagens de tamanho arbitrário, mantendo propriedades desejáveis como a resistência a colisões e a pré-imagem.

Funcionamento:

• Padding da Mensagem: Primeiramente, a mensagem original é estendida (padding) para garantir que seu tamanho seja um múltiplo do tamanho do bloco da função de compressão. Normalmente, isso inclui adicionar um bit ‘1’ seguido por uma série de ‘0’s e o comprimento da mensagem original.
• Inicialização: Um valor inicial (IV) é definido. Este valor é fixo para um dado algoritmo de hash.
• Processamento em Blocos: A mensagem padronizada é processada em blocos sequenciais utilizando a função de compressão. Cada bloco é combinado com o estado resultante do bloco anterior (ou o IV, para o primeiro bloco) para produzir um novo estado.
• Finalização: O estado final após o processamento do último bloco é o hash da mensagem completa.

Essa construção é usada em muitos algoritmos populares de hash, como MD5, SHA-1 e SHA-2, mas tem vulnerabilidades conhecidas, especialmente em relação a extensões de mensagens e colisões.

Estrutura de Esponja

A estrutura de esponja é uma abordagem alternativa à construção de Merkle–Damgård, usada para construir funções de hash, PRNGs, e cifras de fluxo. SHA-3 (Keccak) utiliza essa construção.

Funcionamento:

• Configuração do Estado: A esponja começa com um “estado” inicial que é uma matriz de bits maior do que o hash de saída desejado.
• Fase de Absorção: Durante a absorção, a entrada é processada em blocos que são XORed em uma parte do estado, seguida de uma função de permutação aplicada a todo o estado.
• Fase de Espremedura: Após toda a entrada ser absorvida, a saída (hash) é “espremida” do estado. A função de permutação é aplicada entre as leituras dos blocos de saída até que o comprimento desejado do hash seja alcançado.

Essa construção é projetada para ser resistente a uma ampla gama de ataques, inclusive aqueles que exploram vulnerabilidades em construções baseadas em Merkle–Damgård.

Salting

Salting é uma técnica usada para melhorar a segurança de hashes armazenados, especialmente senhas. Um “salt” é uma sequência aleatória de bits criada para cada entrada (senha) antes de aplicar a função de hash.

Importância:

• Prevenção de Ataques de Rainbow Table: Sem salting, hashes idênticos podem ser pré-computados e armazenados em tabelas (rainbow tables) para reversão rápida. O salting adiciona um elemento único a cada hash, tornando esses ataques inviáveis.
• Dificuldade de Adivinhação: Mesmo se duas entradas forem idênticas, seus hashes serão diferentes devido aos diferentes salts, complicando tentativas de adivinhação.

Implementação:

• Gerar um salt aleatório para cada nova senha a ser hashada.
• Combinar o salt com a senha antes da aplicação do hash.
• Armazenar o salt com o hash na base de dados para o mesmo poder ser usado na verificação da senha.

Strengthening

Key stretching é uma técnica usada para fortalecer hashes fracos (potencialmente derivados de senhas fracas) ao tornar o processo de hashing intencionalmente mais lento.

Técnicas Comuns:

• PBKDF2 (Password-Based Key Derivation Function 2): Aplica uma função de hash múltiplas vezes para aumentar o custo computacional de geração de cada hash.
• Bcrypt: Utiliza um custo de trabalho configurável e uma função baseada em Blowfish, iterando sobre uma função de compressão múltiplas vezes.
• Scrypt: Aumenta a complexidade ao exigir não apenas tempo de CPU, mas também uma quantidade significativa de memória.

Vantagens:

• Protege contra ataques de força bruta, aumentando significativamente o tempo necessário para testar cada senha possível.
• Permite que sistemas e protocolos ajustem o custo computacional à medida que o hardware evolui.

Essas técnicas são cruciais para a segurança de sistemas que dependem de senhas e outras formas de autenticação baseada em segredos que podem ser vulneráveis a ataques se não forem adequadamente protegidas.

Algoritmos de Hash Criptográficos Mais Comuns

MD5 (Message Digest Algorithm 5)

MD5 é um algoritmo de hash criptográfico que gera um hash de 128 bits (16 bytes). Desenvolvido por Ronald Rivest em 1991, era amplamente utilizado para garantir a integridade dos dados. Embora comprometido em termos de segurança, sua estrutura é uma excelente introdução ao design de funções de hash criptográficas.

Funcionamento:

Conforme a RFC1321, o MD5 é calculado da seguinte forma:

1. Padding: A mensagem é estendida para que seu comprimento seja congruente a 448, modulo 512. Isso significa que a mensagem original é seguida por um bit ‘1’, depois por vários bits ‘0’, e finalmente pelo comprimento original da mensagem em 64 bits.

2. Inicialização de Buffers: Quatro variáveis de estado (buffers) são inicializadas. Estas são tratadas como registros de 32 bits:

   • A = 0x67452301
   • B = 0xefcdab89
   • C = 0x98badcfe
   • D = 0x10325476

3. Processamento em Blocos: A mensagem padronizada é então processada em blocos de 512 bits. Cada bloco de 512 bits é dividido em 16 blocos de 32 bits. A transformação do MD5 usa uma função auxiliar principal que tem quatro funções auxiliares (F, G, H e I).

• Funções Auxiliares:

  • F(X,Y,Z) = (X ∧ Y) ∨ (¬X ∧ Z)
  • G(X,Y,Z) = (X ∧ Z) ∨ (Y¬∧Z)
  • H(X,Y,Z) = X ⊕ Y ⊕Z
  • I(X,Y,Z) = Y ⊕ (X ∨ ¬Z)

Cada rodada (total de 4 rodadas) utiliza uma função diferente e opera em todos os blocos de 32 bits. A cada passo, uma das funções auxiliares é aplicada e o resultado é somado com um dos blocos de entrada, uma constante específica da rodada, e uma parte do buffer. Depois, o resultado é rotacionado por um número específico de bits e somado ao buffer.

• Constantes de Rodada: Cada rodada utiliza uma constante diferente, sendo valores fixos derivados dos senos de ângulos. Isso garante a aleatoriedade na transformação.

• Rotações de Bits: As rotações são especificadas para cada operação nas rodadas. Por exemplo, na primeira rodada, você pode rotacionar o resultado em 7 bits, então em 12 bits no próximo passo, e assim por diante.

1. Saída do Hash: Após todas as rodadas serem processadas, os quatro buffers (A, B, C, D) contêm o hash final. Eles são concatenados para formar um hash de 128 bits, sendo o MD5.

SHA-1 (Secure Hash Algorithm 1)

SHA-1 produz um hash de 160 bits e é estruturalmente similar ao MD5, porém com uma ênfase maior na segurança, apesar de também ter sido comprometido por vulnerabilidades.

Funcionamento:

Conforme a RFC3174, o MD5 é calculado da seguinte forma:

1. Padding da Mensagem: Primeiramente, a mensagem original é preparada para garantir que seu tamanho seja congruente a 448 mod 512. Isso é feito adicionando um bit ‘1’ seguido por zeros e, finalmente, o tamanho da mensagem original em bits é anexado ao final (64 bits). Esse passo garante que o tamanho total da mensagem seja um múltiplo de 512 bits.

2. Inicialização das Variáveis: No SHA-1, utilizamos cinco variáveis de 32 bits inicializadas com os seguintes valores hexadecimais:

• A = 0x67452301
• B = 0xEFCDAB89
• C = 0x98BADCFE
• D = 0x10325476
• E = 0xC3D2E1F0

Estes valores são constantes iniciais definidas pela especificação SHA-1.

1. Processamento dos Blocos: Cada bloco de 512 bits da mensagem padronizada é processado em uma série de etapas. Primeiro, o bloco é dividido em 16 palavras de 32 bits. Essas palavras são então expandidas para 80 palavras por meio de uma operação de XOR (exclusive or) dos quatro valores anteriores:

• Para i de 16 até 79:
  • W[i]=(W[i−3]⊕W[i−8]⊕W[i−14]⊕W[i−16])<<<1

Onde <<< denota uma rotação à esquerda.

1. Rodadas de Hashing: SHA-1 processa essas 80 palavras em cinco rodadas de 16 operações cada. Cada rodada usa uma função diferente:

• Funções para cada rodada:
  • f(t,B,C,D)=(B∧C)∨(¬B∧D) (0 ≤ t ≤ 19)
  • f(t,B,C,D)=B⊕C⊕D (20 ≤ t ≤ 39)
  • f(t,B,C,D)=(B∧C)∨(B∧D)∨(C∧D) (40 ≤ t ≤ 59)
  • f(t,B,C,D)=B⊕C⊕D (60 ≤ t ≤ 79)

E uma constante K diferente é usada em cada rodada:

• K = 0x5A827999 (0 ≤ t ≤ 19)
• K = 0x6ED9EBA1 (20 ≤ t ≤ 39)
• K = 0x8F1BBCDC (40 ≤ t ≤ 59)
• K = 0xCA62C1D6 (60 ≤ t ≤ 79)

Para cada palavra W[i]:

• Temp = (A <<< 5) + f(t, B, C, D) + E + W[i] + K
• E = D
• D = C
• C = B <<< 30
• B = A
• A = Temp

1. Atualização das Variáveis: Após o processamento de cada bloco de 512 bits, os valores de A, B, C, D e E são adicionados aos valores acumulados das variáveis correspondentes.

2. Output do Hash: Após todos os blocos serem processados, o resultado é concatenado das variáveis A, B, C, D e E para formar o digest SHA-1 de 160 bits.

SHA-2 (Secure Hash Algorithm 2)

SHA-2 inclui várias funções: SHA-224, SHA-256, SHA-384 e SHA-512. Os métodos são semelhantes, mas diferem principalmente no tamanho dos blocos e dos hashes.

Funcionamento:

Conforme a RFC6234 que resume as RFCs da familia SHA-2, o SHA-256 é calculado da seguinte forma:

1. Preparação da Mensagem: Primeiro, a mensagem original é preparada para garantir que seu comprimento seja um múltiplo de 512 bits. Isso é feito adicionando um bit ‘1’ seguido de ‘0’s suficientes e finalmente o tamanho da mensagem original em bits é anexado no final (64 bits). O objetivo é fazer com que o comprimento total seja congruente a 448 mod 512.

2. Inicialização das Variáveis: O SHA-256 utiliza oito variáveis de estado inicializadas com valores específicos derivados das raízes quadradas dos primeiros oito números primos:

• A = 0x6a09e667
• B = 0xbb67ae85
• C = 0x3c6ef372
• D = 0xa54ff53a
• E = 0x510e527f
• F = 0x9b05688c
• G = 0x1f83d9ab
• H = 0x5be0cd19

1. Processamento dos Blocos: Cada bloco de 512 bits da mensagem processada é dividido em 16 palavras iniciais de 32 bits. Estas 16 palavras são expandidas para 64 palavras usando a seguinte fórmula:

• Para i de 16 até 63:
  • W[i]=σ1​(W[i−2])+W[i−7]+σ0​(W[i−15])+W[i−16]

Onde:

• σ0​(x)=(x⋙7)⊕(x⋙18)⊕(x≫3)
• σ1​(x)=(x⋙17)⊕(x⋙19)⊕(x≫10)

1. Rodadas de Compressão: O SHA-256 usa 64 rodadas de compressão. Em cada rodada, as seguintes fórmulas são aplicadas:

• T1=H+Σ1​(E)+Ch(E,F,G)+K[i]+W[i]
• T2=Σ0​(A)+Maj(A,B,C)
• Depois, as variáveis são atualizadas:
  • H=G
  • G=F
  • F=E
  • E=D+T1
  • D=C
  • C=B
  • B=A
  • A=T1+T2

Onde:

• Σ0​(x)=(x⋙2)⊕(x⋙13)⊕(x⋙22)
• Σ1​(x)=(x⋙6)⊕(x⋙11)⊕(x⋙25)
• Ch(x,y,z)=(x∧y)⊕(¬x∧z)
• Maj(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)
• K[i] é uma constante específica da rodada.

1. Output do Hash: Após todas as rodadas, as variáveis A, B, C, D, E, F, G e H são somadas aos seus respectivos valores antes do início do bloco. O resultado do hash será a concatenação dessas oito variáveis após o processamento de todos os blocos.

SHA-3 (Secure Hash Algorithm 3)

SHA-3, também conhecido como Keccak, é a adição mais recente, utilizando uma abordagem completamente diferente conhecida como “sponge construction”.

Funcionamento:

SHA-3 opera usando uma estrutura de dados chamada “estado”, que é uma matriz de 5x5 palavras de 64 bits cada (totalizando 1600 bits no estado). A entrada é processada em blocos de tamanho específico, e a saída é produzida “espremendo” o estado. De forma simplificada, abaixo, seguem as etapas de como o SHA-3-256 é calculado:

1. Inicialização: O estado inicial é configurado com todos os bits zerados.

2. Absorção: A entrada é dividida em blocos de tamanho r (taxa de bits), que para o SHA-3-256 é 1088 bits. Cada bloco é XORed em uma parte do estado, seguido por uma permutação do estado completo.

3. Permutação: A permutação é a parte central do SHA-3, envolvendo várias operações detalhadas:

• Theta (Θ): Cada bit no estado é atualizado com base em dois cálculos que envolvem suas colunas.
• Rho (ρ) e Pi (π): Bits são rotacionados e reposicionados em todo o estado para proporcionar difusão.
• Chi (χ): Uma função não-linear que atualiza cada bit com base em uma função de três bits na mesma linha.
• Iota (ι): Uma constante é XORed no estado para evitar simetrias.

1. Espremedura: Após a fase de absorção, a saída (hash) é produzida lendo blocos de bits do estado e continuando com a permutação até que a quantidade de bits desejada seja alcançada.

Fórmulas das Operações de Permutação

Aqui estão algumas das fórmulas mais relevantes para entender o SHA-3:

• Theta (Θ):

1
2
3
4
5

C[x]=estado[x,0]⊕estado[x,1]⊕estado[x,2]⊕estado[x,3]⊕estado[x,4]

D[x]=C[x−1]⊕rotl(C[x+1],1)

estado[x,y]←estado[x,y]⊕D[x]

• Rho (ρ) e Pi (π): A rotação é específica para cada bit e segue um padrão predeterminado. Pi rearranja os bits com base numa fórmula que troca as coordenadas dos bits.

• Chi (χ):

  estado[x,y]←estado[x,y]⊕((¬estado[x+1,y])∧estado[x+2,y])

• Iota (ι): Uma constante de rodada é XORed no bit [0,0] do estado para cada rodada da permutação.

Algoritmos de Hash Específicos para Senhas

Os algoritmos de hash específicos para senhas como bcrypt, scrypt e Argon2 são projetados para proteger senhas armazenadas contra ataques de força bruta e outros tipos de ataques. Eles são essenciais na segurança de dados, especialmente em sistemas onde senhas precisam ser armazenadas de forma segura.

Bcrypt

Funcionamento:

Bcrypt é uma função de hash adaptativa criada por Niels Provos e David Mazières baseada no algoritmo Blowfish. Ele incorpora um custo de trabalho (também conhecido como fator de carga), que permite ajustar o custo computacional necessário para gerar o hash. Bcrypt executa as seguintes etapas:

• Gera um salt (sequência aleatória) para cada senha, evitando assim ataques de rainbow table.
• Usa o salt e a senha para produzir um hash através de uma série de transformações criptográficas baseadas em Blowfish.
• O número de rodadas de hash é ajustável, aumentando exponencialmente a dificuldade de ataque à medida que a capacidade computacional dos atacantes aumenta.

Vantagens:

• Resistente a ataques de rainbow table devido ao salting.
• Adapta-se ao aumento da capacidade de processamento ao permitir ajustar o número de rodadas.
• Amplamente suportado e testado em muitos sistemas e frameworks.

Quando Utilizar:

Bcrypt é ideal para sistemas que necessitam de um equilíbrio entre segurança e desempenho. É adequado para a maioria das aplicações web onde as senhas precisam ser armazenadas de forma segura.

Scrypt

Funcionamento:

Desenvolvido por Colin Percival, scrypt é uma função de hash que, além de ser computacionalmente intensiva, também é intensiva em termos de uso de memória. O algoritmo realiza o hash da senha usando um salt e realiza muitas iterações de uma função derivada de senha, projetada para usar uma grande quantidade de memória, além de CPU.

Vantagens:

• Resistente a ataques tanto de força bruta como de hardware especializado, como ASICs e FPGAs, devido ao seu alto requisito de memória.
• Configurável para exigir quantidades significativas tanto de memória quanto de tempo, aumentando assim a segurança contra vários tipos de ataques.

Quando Utilizar:

Scrypt pode ser usado em ambientes onde há uma preocupação particular com ataques que utilizam hardware especializado para quebrar senhas. É ideal para sistemas onde a segurança extra justifica o uso adicional de recursos.

Argon2

Funcionamento:

Argon2, vencedor da Password Hashing Competition em 2015, foi projetado para ser o estado da arte em hashing de senhas. Ele vem em duas variantes principais: Argon2d e Argon2i.

Argon2d oferece maior resistência contra ataques de GPU e é otimizado para aplicações onde a ameaça é principalmente de atacantes que podem fazer muitas tentativas offline.

Argon2i é otimizado para aplicações que requerem resistência contra ataques de tradeoff de tempo-memória e é mais adequado para senhas e chaves criptográficas.

• Usa memória, CPU e paralelismo para complicar os ataques.
• Incorpora um salt e um parâmetro de paralelismo para permitir o uso de múltiplos núcleos de processamento.

Vantagens:

• Oferece proteção contra uma ampla gama de ataques potenciais, incluindo ataques que usam GPUs e ASICs.
• Permite ajuste fino do uso de memória, do custo computacional e do paralelismo.

Quando Utilizar:

Argon2 é recomendado para novos sistemas que necessitam do mais alto nível de proteção para senhas. Sua capacidade de ajuste e resistência a vários tipos de ataques o torna adequado para sistemas que priorizam a segurança.

Ataques Comuns Contra Algoritmos de Hash

Os algoritmos de hash são fundamentais para a segurança de dados em muitas aplicações, como autenticação, integridade de arquivos, e assinatura digital. No entanto, eles podem ser vulneráveis a diversos tipos de ataques.

Ataques de Colisão

Um ataque de colisão ocorre quando dois dados diferentes produzem o mesmo hash. Este é um problema significativo, especialmente para funções de hash criptográfico, ao comprometer a integridade dos dados e a segurança das comunicações digitais.

Os atacantes utilizam métodos matemáticos ou de força bruta para encontrar dois inputs distintos que resultem no mesmo hash. Isso pode ser feito através de ajustes sistemáticos nos dados de entrada até que uma colisão seja encontrada.

Exemplo Real: Vulnerabilidade no MD5 (Caso Flame)

O malware Flame usou um ataque de colisão para falsificar um certificado da Microsoft, permitindo que o malware se disfarçasse como uma atualização de software legítima da Microsoft.

Utilizando uma vulnerabilidade no algoritmo MD5, os atacantes conseguiram criar um certificado digital falso que parecia ser emitido pela Microsoft. A colisão permitiu que o certificado falso passasse as verificações de autenticidade, enganando sistemas e softwares de segurança.

Ataques de Pré-imagem e Segunda Pré-imagem

Ataque de Pré-imagem:

Tentativa de encontrar uma entrada que corresponda a um hash específico. O objetivo é reverter a hash para a entrada original, comprometendo a irreversibilidade da função de hash.

Ataque de Segunda Pré-imagem:

Similar ao ataque de pré-imagem, mas em vez de tentar reverter o hash para qualquer entrada, o atacante tenta encontrar uma nova entrada que não seja a original mas que produza o mesmo hash.

Esses ataques exigem capacidade computacional significativa, pois o atacante precisa calcular o hash de muitas entradas potenciais até encontrar uma que coincida com o hash alvo.

Exemplo Real: Vulnerabilidade SHA-1 (SHAttered)

Em 2017, pesquisadores do Google e do CWI Amsterdam demonstraram o primeiro ataque prático de colisão contra o algoritmo SHA-1, conhecido como SHAttered.

Embora tecnicamente um ataque de colisão, o caso SHAttered é relevante aqui devido à sua proximidade com conceitos de pré-imagem, pois mostrou como duas entradas diferentes poderiam ser criadas para gerar o mesmo hash SHA-1, comprometendo assim a integridade de documentos que dependiam desta função para segurança.

Rainbow Tables e Salting

Rainbow tables são grandes pré-computações de pares de hashes e suas entradas correspondentes. Elas são usadas para reverter hashes de maneira eficiente, especialmente para senhas, reduzindo significativamente o tempo necessário para quebrar um hash comum.

Ao usar uma rainbow table, um atacante pode simplesmente procurar o hash na tabela para encontrar a entrada correspondente rapidamente, sem a necessidade de calcular o hash durante o ataque.

Mitigação com Salting

Ao adicionar um salt à senha antes de hashá-la, cada hash se torna único mesmo para senhas idênticas entre diferentes usuários. Isso torna ineficaz o uso de rainbow tables, pois o atacante teria que gerar uma nova rainbow table para cada salt diferente, o que é impraticável devido ao enorme espaço e tempo de computação necessários.

Exemplo Real: Ataque à rede LinkedIn em 2012

Em 2012, a LinkedIn sofreu uma violação de dados em que cerca de 6,5 milhões de hashes de senha SHA-1, sem salting, foram roubados e mais tarde vazados.

Os atacantes usaram rainbow tables para decifrar rapidamente as senhas, uma vez que a ausência de salting tornou as hashes vulneráveis a esse tipo de ataque. A facilidade de acesso às rainbow tables e a falta de salting resultaram em um grande número de senhas sendo rapidamente comprometidas.

Comparativo dos Principais Algoritmos de Hash

A escolha de um algoritmo de hash depende da necessidade específica de segurança, performance e uso de recursos. Enquanto MD5 e SHA-1 são mais rápidos, eles são recomendados apenas para aplicações não seguras devido às suas vulnerabilidades conhecidas. SHA-256 e SHA-3 oferecem um excelente equilíbrio entre segurança e eficiência, sendo ideais para aplicações críticas. Já o bcrypt, embora lento, é a escolha ideal para o armazenamento seguro de senhas devido à sua resistência a ataques de força bruta.

Tabela Comparativa

Conclusão

Este artigo, proporcionou uma exploração não tão superficial sobre o papel vital que os algoritmos de hash desempenham no campo da cibersegurança, abrangendo desde o armazenamento seguro de senhas até a integridade de software e sistemas de assinaturas digitais. Os hashes, frequentemente percebidos como ferramentas simples para a validação de dados, revelam uma complexidade e uma aplicabilidade muito maiores quando examinados mais de perto.

Além disso, a discussão sobre as árvores de Merkle ressalta como os hashes podem ser estrategicamente utilizados para otimizar a verificação e o armazenamento de grandes volumes de dados, uma técnica que tem sido indispensável no desenvolvimento de tecnologias de blockchain e outros sistemas distribuídos.

Portanto, a compreensão aprofundada sobre os hashes enriquece nosso conhecimento técnico.

Referências

• RFC1321
• RFC3174
• RFC6234
• https://msrc.microsoft.com/blog/2012/06/flame-malware-collision-attack-explained/
• https://shattered.io/
• https://en.wikipedia.org/wiki/2012_LinkedIn_hack