A Colisão SHAttered do SHA-1, Explicada

A 23 de fevereiro de 2017, investigadores do Cryptology Group do CWI Amesterdão e da Google publicaram dois ficheiros PDF diferentes que partilham o mesmo hash SHA-1. Para ambos, o resumo é 38762cf7f55934b34d179ae6a4c80cadccbb7f0a. O projeto chamou-se SHAttered e foi a primeira vez que alguém produziu uma colisão prática e pública para a função de hash SHA-1 completa. Pode descarregar os dois ficheiros e confirmar por si: shattered-1.pdf e shattered-2.pdf. São documentos visivelmente distintos e, ainda assim, o SHA-1 não consegue distingui-los.

Aquele facto único pôs fim a uma longa discussão sobre se ainda era seguro confiar no SHA-1. Este artigo percorre o que é uma colisão, por que motivo o SHA-1 caiu, o que a equipa construiu de facto e o que mudou a seguir.

O que é uma colisão de hash e por que importa

Uma função de hash criptográfica recebe uma entrada de qualquer tamanho e devolve uma impressão digital de comprimento fixo. O SHA-1 produz 160 bits, habitualmente escritos como 40 caracteres hexadecimais. Esperam-se três propriedades: não se consegue inverter a saída de volta à entrada, não se consegue encontrar uma segunda entrada que produza um dado resumo, e não se conseguem encontrar duas entradas quaisquer com o mesmo valor. Esta última propriedade é a resistência a colisões.

As colisões existem sempre, num sentido matemático. Há uma infinidade de entradas possíveis e apenas um número finito de saídas de 160 bits, por isso algumas entradas têm forçosamente de partilhar resumo. A promessa de segurança não é que as colisões não existam. É que encontrar uma deve ser tão caro que nenhum atacante realista o consiga fazer. O SHAttered quebrou essa promessa para o SHA-1.

Por que importa isto fora de um laboratório? As assinaturas digitais, os certificados e as verificações de integridade raramente assinam o documento em si. Assinam o seu hash. Uma assinatura, um identificador de commit no Git, a impressão digital de um certificado, a garantia de que um ficheiro não mudou: tudo reduz o ficheiro a um hash e confia que esse hash é único daquele ficheiro. Se dois ficheiros partilharem um hash, uma assinatura sobre um é igualmente válida sobre o outro. A ligação entre o que foi aprovado e o que foi recebido quebra-se em silêncio.

Por que o SHA-1 era vulnerável

O SHA-1 foi publicado pela NSA e normalizado pelo NIST em 1995. Assenta na construção de Merkle-Damgard, processando a mensagem em blocos e misturando cada bloco num estado interno através de uma sequência de adições, rotações e operações ao nível dos bits.

Os problemas começaram cedo. Em 2005, um grupo de investigadores liderado por Wang mostrou que era possível encontrar colisões com um esforço bastante abaixo do que um ataque genérico do aniversário exigiria sobre um hash de 160 bits. Era um resultado teórico, muito além do equipamento da época, mas marcou o SHA-1 como enfraquecido. Ao longo da década seguinte, criptanalistas, entre eles Marc Stevens, refinaram ataques diferenciais que exploram a forma como pequenas diferenças, cuidadosamente escolhidas, se propagam pela função de ronda, estreitando a distância entre a teoria e um ataque construível.

A fraqueza central é estrutural. A função de ronda do SHA-1 não difunde as diferenças com força suficiente para impedir que um atacante construa dois blocos de mensagem cujas perturbações internas se cancelem no final. Uma vez conseguido esse cancelamento, é possível forçar o estado interno a convergir, e a colisão segue-se.

O que a equipa do SHAttered fez de facto

O ataque foi uma colisão de prefixo idêntico. Os dois PDF começam exatamente com os mesmos bytes. Os investigadores calcularam depois um par de sequências de blocos de quase-colisão, cuidadosamente construídas, que, anexadas a esse prefixo partilhado, conduzem o estado interno do SHA-1 ao mesmo valor. Como os estados internos coincidem no ponto em que terminam os blocos da colisão, tudo o que se anexe a seguir mantém os hashes iguais, consequência direta do desenho de Merkle-Damgard.

O formato PDF foi uma escolha deliberada. É flexível o suficiente para esconder os blocos da colisão dentro de um objeto que controla qual a imagem mostrada, de modo que o mesmo hash corresponde a dois documentos que apresentam conteúdo visível diferente. É isto que transforma um par abstrato de cadeias de bytes num cenário de abuso credível.

A equipa por detrás do trabalho incluiu investigadores do CWI Amesterdão e da Google, entre eles Marc Stevens, Pierre Karpman, Elie Bursztein, Ange Albertini e Yarik Markov. O documento completo, com a matemática e o detalhe de engenharia, está disponível aqui em shattered.pdf.

A escala do cálculo

O SHAttered não foi um atalho esperto que corre num portátil. Foi um cálculo genuinamente grande, e os números são o ponto central.

A Google descreveu o esforço como o equivalente a cerca de 6500 anos-CPU na primeira fase e 110 anos-GPU na segunda. Distribuído por uma grande frota de máquinas, isso são meses de trabalho, não séculos. A estrutura em fases é relevante: uma pesquisa dispendiosa produz primeiro uma configuração utilizável de quase-colisão, e depois uma segunda etapa, mais barata, fecha o par correspondente. As cerca de 9,2 quintiliões de avaliações de hash soam astronómicas, e são, mas ficam muito abaixo do muro da força bruta. Essa diferença é exatamente o que a criptanálise existe para encontrar.

Por que dois PDF com o mesmo hash são perigosos

Imagine um fluxo de assinatura. Um revisor aprova um contrato e um sistema assina o hash SHA-1 desse PDF. Com um par de colisão em mãos, um atacante pode preparar de antemão dois contratos que partilham um hash: um inofensivo, para ser aprovado, e um malicioso, para ser substituído mais tarde. A assinatura feita sobre o ficheiro aprovado valida na perfeição contra o ficheiro trocado, porque a assinatura só cobriu o hash, e o hash é idêntico.

A mesma lógica ameaça qualquer sistema que use o SHA-1 como identidade:

• Certificados. Uma autoridade de certificação que assine um certificado SHA-1 poderia ser levada a atestar um certificado em colisão que nunca pretendeu emitir.
• Distribuição de software. Uma soma de verificação SHA-1 que pretende provar a autenticidade de um descarregamento nada prova se existir uma carga em colisão.
• Controlo de versões. O Git identifica cada commit e cada objeto por um hash SHA-1. Uma colisão significa que duas árvores ou blobs diferentes podem reivindicar o mesmo identificador, o que põe em causa a integridade do repositório. A dependência do Git em relação ao SHA-1 foi imediatamente escrutinada após o anúncio.

O ataque não permite forjar um hash para um ficheiro arbitrário que já se tenha em mãos. Permite que um atacante que controla ambos os documentos produza um par correspondente desde o início. Em contextos de assinatura, custódia, notarização e cadeia de fornecimento, controlar ambos os documentos é uma situação perfeitamente comum, e foi isso que tornou o resultado tão incómodo.

Consequências reais e a passagem para o SHA-256

A aposentação do SHA-1 estava prevista no papel havia anos, mas o SHAttered transformou uma recomendação numa emergência. Um artefacto reproduzível é muito mais persuasivo do que uma estimativa de complexidade.

A resposta foi rápida e ampla. Os fabricantes de navegadores concluíram a remoção da confiança nos certificados TLS com SHA-1, e as autoridades de certificação completaram a migração para o SHA-256. Em poucos dias, o Git adicionou um detetor de colisões embutido, baseado na biblioteca sha1collisiondetection, que sinaliza entradas com as marcas desta classe de ataque, e o projeto iniciou um esforço mais longo rumo a um formato de objeto reforçado. Protocolos, gestores de pacotes e ferramentas de assinatura aceleraram as suas próprias retiradas do SHA-1.

O destino da maior parte dessa migração foi o SHA-256, parte da família SHA-2. O SHA-256 não tem qualquer ataque de colisão prático conhecido, dispõe de uma saída mais larga, de 256 bits, e de um desenho interno mais forte, razões pelas quais se tornou o padrão para certificados, assinaturas e verificações de integridade. Para uma visão de como estas peças encaixam, veja o artigo central de criptografia.

O que o SHAttered significa hoje

O SHA-1 não deve ser usado onde a resistência a colisões importa. Isso inclui assinaturas, certificados e qualquer verificação do género “isto foi adulterado?” sobre dados que um adversário possa influenciar. Para esses usos, o SHA-256 ou algo mais forte é o mínimo.

Há nuances que vale a pena manter claras. A resistência à pré-imagem do SHA-1, ou seja, a dificuldade de inverter um hash ou de coincidir com um hash que não se ajudou a criar, não foi quebrada. Por isso, um uso sem fim de segurança, como uma chave de desduplicação sobre dados de confiança, tem um perfil de risco diferente de uma assinatura. A orientação honesta continua simples: se a segurança depende do hash, abandone o SHA-1.

A lição mais ampla sobreviveu à quebra concreta. As primitivas criptográficas envelhecem. Um ataque que parece puramente teórico, como o resultado de 2005, tende a aproximar-se da prática à medida que a análise se afina e o equipamento fica mais barato. O SHAttered é a ilustração mais limpa desse arco: doze anos entre estar enfraquecido no papel e existirem dois ficheiros reais, com um único hash, descarregáveis hoje.

Se quiser ver a quebra com os próprios olhos, obtenha shattered-1.pdf e shattered-2.pdf, calcule o sha1sum de cada um e observe dois documentos diferentes a devolver o mesmo resumo de 40 caracteres.

Perguntas frequentes

O SHAttered quebrou o SHA-1 por completo?

A sua resistência a colisões foi quebrada na prática, que é a propriedade que protege assinaturas e certificados. O ataque produz um par de ficheiros com um hash coincidente. Não inverte hashes nem permite a um atacante coincidir com um ficheiro em cuja criação não participou, pelo que a resistência à pré-imagem do SHA-1 permanece intacta. Para qualquer coisa sensível à segurança, essa distinção não o salva: passe para o SHA-256.

Alguém pode usar isto para forjar um hash de um ficheiro que eu já tenho?

Não. O SHAttered é uma colisão de prefixo idêntico, o que significa que o atacante constrói ambos os documentos em conjunto para que partilhem um hash. Não consegue pegar num ficheiro existente que você controla e fabricar um segundo ficheiro que lhe corresponda. O perigo vive em fluxos onde é o atacante a fornecer os documentos, como assinatura, notarização ou custódia.

Por que os investigadores usaram ficheiros PDF?

O PDF é flexível o suficiente para embutir os blocos da colisão dentro de um objeto que seleciona qual o conteúdo apresentado, de modo que um único hash pode corresponder a dois documentos com aspeto diferente no ecrã. Isso torna a ameaça concreta: modela um ficheiro inofensivo a ser aprovado e um malicioso a ser trocado sob a mesma assinatura. O par está em shattered-1.pdf e shattered-2.pdf.

O SHA-256 é afetado pelo mesmo ataque?

Não. O SHAttered explora fraquezas específicas da função de ronda do SHA-1 e da sua saída de 160 bits. O SHA-256 usa um desenho diferente, com um resumo de 256 bits, e não tem qualquer ataque de colisão prático conhecido, razão pela qual se tornou o substituto padrão em navegadores, autoridades de certificação e controlo de versões.