As funções de hash explicadas
Quando descarrega software e compara uma soma de verificação, inicia sessão com uma palavra-passe, assina um documento ou acrescenta um bloco ao Bitcoin, há uma função de hash a trabalhar. Ela transforma qualquer quantidade de dados numa impressão digital curta e de tamanho fixo, o resumo, de uma forma que não pode ser desfeita nem falsificada. A ideia é simples, mas as exigências a um bom hash são rigorosas, e dois dos mais usados, o MD5 e o SHA-1, não lhes sobreviveram.
Uma impressão digital para dados
Uma função de hash recebe uma entrada de qualquer comprimento e devolve um resumo de comprimento fixo: 256 bits no caso do SHA-256, escritos como 64 algarismos hexadecimais. A mesma entrada dá sempre o mesmo resumo, por isso o resumo pode representar os dados. Se dois ficheiros têm o mesmo resumo SHA-256, pode ter a certeza de que são idênticos, e se um bit de uma transferência ficou danificado, o seu resumo deixa de coincidir com o que o editor indicou. Como há muito mais entradas possíveis do que resumos, muitas entradas têm de partilhar cada resumo; um bom hash limita-se a tornar impossível encontrar qualquer uma delas.
Três promessas
Um hash criptográfico faz três promessas. Resistência à pré-imagem: dado um resumo, não se consegue encontrar uma entrada que o produza. Resistência à segunda pré-imagem: dada uma entrada, não se consegue encontrar outra entrada com o mesmo resumo. Resistência a colisões: não se consegue encontrar duas entradas quaisquer com o mesmo resumo. Para um hash ideal com n bits, os melhores ataques consistem em adivinhar: cerca de 2ⁿ tentativas para uma pré-imagem e cerca de 2ⁿᐟ² para uma colisão. Diz-se que um hash está quebrado quando alguém encontra um método muito mais rápido do que isso.
O efeito avalanche
Mude um bit da entrada e cada bit do resumo deve inverter-se com uma probabilidade de metade, independentemente dos outros. Assim, uma pequena alteração na mensagem dá um resumo que parece não ter qualquer relação com o original, e o resumo não revela nada sobre a parte da entrada que mudou. O SHA-256 consegue isto executando 64 rondas que rodam, somam e combinam as suas oito palavras de 32 bits, de modo que, ao fim de poucas rondas, cada bit da entrada já influenciou cada palavra. Uma simples soma dos bytes, pelo contrário, muda exatamente na medida em que a entrada mudou, e por isso denuncia tudo.
Por dentro do SHA-256
O SHA-256 começa por preencher a mensagem: acrescenta um bit 1, zeros e o comprimento da mensagem, até que o total seja um múltiplo de 512 bits. Depois processa a mensagem 512 bits de cada vez. Cada bloco é expandido em 64 palavras, que são misturadas num estado de oito palavras de 32 bits, que parte de valores fixos tirados das raízes quadradas dos oito primeiros números primos. O estado após o último bloco é o resumo. Este desenho encadeado, que tem o nome de Ralph Merkle e Ivan Damgård, é partilhado pelo MD5, pelo SHA-1 e pelo SHA-512; o mais recente SHA-3, normalizado em 2015, usa uma construção diferente chamada esponja.
O ataque do aniversário
Num grupo de 23 pessoas, a probabilidade de duas fazerem anos no mesmo dia é pouco superior a metade, embora o ano tenha 365 dias, porque o que conta é o número de pares, que cresce com o quadrado do tamanho do grupo. As colisões num hash seguem a mesma regra. Entre 2ᵏ resumos possíveis, espera-se uma colisão ao fim de cerca de √(π/2 · 2ᵏ) entradas aleatórias. Para 32 bits, isso dá cerca de 82 000 entradas, feitas num instante; para 128 bits, dá cerca de 2⁶⁴, o que está ao alcance de grandes esforços de computação. É por isso que os 128 bits do MD5 nunca foram generosos, e é por isso que o SHA-256 duplica o comprimento para oferecer uma segurança de 128 bits.
MD5 e SHA-1: quebrados
Ron Rivest concebeu o MD5 em 1991, e a NSA concebeu o SHA-1, publicado em 1995. Em 2004, Xiaoyun Wang e os seus colegas mostraram como criar colisões de MD5 rapidamente e, em 2008, investigadores usaram-nas para falsificar um certificado em que os navegadores confiavam. O software de espionagem Flame, de 2012, usou uma colisão de MD5 para se fazer passar por uma atualização da Microsoft. O SHA-1 caiu em 2017, quando a Google e o CWI Amsterdam publicaram dois ficheiros PDF diferentes com o mesmo resumo SHA-1, após cerca de 2⁶³ cálculos. Ambos continuam a servir para detetar erros acidentais, mas não para nada que um atacante possa visar.
Onde se usam os hashes
As assinaturas digitais assinam o hash de um documento e não o próprio documento. O Git identifica cada ficheiro e cada commit pelo seu hash, e os mineradores de Bitcoin procuram cabeçalhos de bloco cujo duplo hash SHA-256 comece com uma longa sequência de zeros. Os sites nunca devem guardar palavras-passe, apenas um hash delas; mas, como as pessoas escolhem palavras-passe curtas, esse hash tem de ser lento e com sal, com métodos como o bcrypt, o scrypt ou o Argon2, para que adivinhar se torne caro. As somas de verificação como o CRC-32, usado em ficheiros ZIP, imagens PNG e Ethernet, também são hashes, concebidos para detetar ruído e não atacantes.
Experimente
Abra o laboratório de funções de hash para calcular o hash do seu próprio texto com SHA-256, SHA-512, SHA-1, MD5, CRC-32 e uma soma de bytes de brincadeira. Altere um carácter e conte os bits invertidos, faça o teste da avalanche ao longo de mil alterações de um bit para ver a curva em forma de sino em torno de metade do resumo, e encontre colisões reais nos primeiros 8 a 32 bits de um resumo para ver o ataque do aniversário em ação.
Perguntas frequentes
Calcular um hash é o mesmo que cifrar?
Não. A cifragem foi feita para ser desfeita por quem tem a chave; um hash não usa chave e ninguém o pode desfazer. A cifragem mantém uma mensagem secreta, enquanto um hash dá apenas uma impressão digital que permite verificar uma mensagem que já tem.
Quanto tempo levaria a encontrar uma colisão do SHA-256?
Com o ataque do aniversário, cerca de 2¹²⁸ hashes, um número com 39 algarismos. Mesmo que todos os computadores da Terra não fizessem mais nada, demoraria muitíssimo mais do que a idade do universo. Não se conhece nenhum atalho.
Porque é que dois hashes do mesmo texto nunca diferem?
Uma função de hash é determinística: não tem aleatoriedade nem chave, por isso os mesmos bytes dão sempre o mesmo resumo. Pequenas diferenças que não se veem, como um espaço no fim, uma quebra de linha diferente ou outra forma Unicode de uma letra acentuada, dão de facto um resumo diferente.
O que é um sal?
Um valor aleatório guardado junto ao hash de uma palavra-passe e misturado nele. Assim, dois utilizadores com a mesma palavra-passe obtêm hashes diferentes, e um atacante não pode usar uma única tabela pré-calculada de palavras-passe comuns para todas as contas.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o laboratório de funções de hash