Ferramentas para desenvolvedores · SHA calculadora de hash
Merkle–Damgård explicou: a construção por trás de SHA-1 e SHA-2
· Fundo
sha-256 criptografia APIs do navegador
Uma função de compactação de tamanho fixo não pode fazer hash de entrada arbitrária por conta própria. Merkle–Damgård encadeia bloco por bloco; este post explica a construção, sua ideia de prova e os pontos fracos que ela carrega.
Entrada arbitrária, saída fixa – o problema que toda função hash deve resolver primeiro
Uma função hash deve mapear uma entrada arbitrária para uma saída fixa. Uma mensagem de três bytes e uma mensagem de três megabytes devem produzir exatamente 256 bits de saída para SHA-256. O hash deve ser determinístico, para que a mesma entrada produza sempre a mesma saída. A saída deve parecer aleatória; alterar um único bit da entrada deve alterar aproximadamente metade dos bits de saída.
Estes são requisitos contraditórios à primeira vista, porque um único algoritmo rápido não pode lidar com mensagens de comprimento arbitrário e produzir saída uniforme de largura fixa. A construção Merkle-Damgård resolve isso usando repetidamente uma função de compactação de tamanho fixo, alimentando a saída de cada aplicativo na entrada do próximo. Esta construção é usada por SHA-1 e todos os SHA-2 (SHA-256, SHA-384 e SHA-512).
A função de compressão — um mixer de tamanho fixo que pega um estado e um bloco e retorna um novo estado
Uma função de compressão é a primitiva criptográfica central que alimenta um hash Merkle-Damgård. É necessário um estado de tamanho fixo, geralmente 256 bits para SHA-256 ou 512 bits para SHA-512, e um bloco de entrada de tamanho fixo, geralmente 512 bits para SHA-256 ou 1024 bits para SHA-512. A função de compactação os mistura usando operações bit a bit, rotações e pesquisas de tabela, produzindo um novo estado do mesmo tamanho. Esta função deve ser resistente a colisões: encontrar dois pares diferentes (estado, bloco) que produzam a mesma saída deve ser difícil.
A função de compressão em si não é uma função hash completa – ela não lida com comprimentos de entrada arbitrários e nem mesmo lida com a primeira entrada, que não possui estado anterior. Em vez disso, é o alicerce em torno do qual uma construção maior é construída. A função de compactação é a única operação criptográfica executada repetidamente; todo o resto é contabilidade que conecta essa função a um hash completo.
Encadeamento e vetor de inicialização — como os blocos se alimentam uns aos outros a partir de um estado inicial fixo
O vetor de inicialização é o estado inicial fixo, escolhido cuidadosamente para evitar simetrias ou fraquezas. Para SHA-256, o IV são oito palavras 32 bits derivadas das partes fracionárias das raízes quadradas dos primeiros oito números primos. Esses valores são arbitrários, mas determinísticos; portanto, cada implementação produz o mesmo resultado. O primeiro bloco de mensagem é misturado com o IV usando a função de compressão, produzindo um novo estado. O segundo bloco de mensagem é misturado com esse estado, produzindo outro novo estado, e assim por diante, em cada bloco da mensagem.
Este encadeamento é a parte crucial: a saída de um bloco depende de todos os blocos anteriores, portanto, alterar qualquer bit de qualquer bloco anterior altera todos os blocos subsequentes. No momento em que o bloco final é processado, o estado contém informações sobre cada bit da entrada. O preenchimento é o truque que faz essa construção soar. Uma mensagem nem sempre é dividida igualmente em blocos. A construção Merkle-Damgård usa fortalecimento MD: anexe um único bit à mensagem, depois anexe zeros até que reste quase um bloco completo e, em seguida, anexe o comprimento original da mensagem.
Preenchimento com o comprimento da mensagem – por que o fortalecimento do MD é o que faz a construção soar
O argumento de segurança para Merkle-Damgård diz que se a função de compressão for resistente a colisões, então todo o hash será resistente a colisões. A prova é uma redução: se você pudesse encontrar uma colisão no hash, você poderia extrair uma colisão na função de compressão, o que contradiz a suposição de que é difícil colidir com a função de compressão. A intuição é que qualquer colisão no hash deve eventualmente produzir uma colisão em uma das chamadas da função de compressão, porque o estado é transportado completamente.
As fraquezas em Merkle – Damgård foram descobertas ao longo do tempo, embora a construção básica seja sólida. A extensão de comprimento é uma delas: um invasor que vê o resumo de uma mensagem pode estender a mensagem e calcular um resumo válido para a mensagem mais longa sem saber nada sobre a entrada. Os segundos ataques de pré-imagem são outra: dada uma mensagem, encontrar uma mensagem diferente com o mesmo hash é mais fácil do que deveria ser para alguns tipos de mensagens. Essas fraquezas motivaram o projeto de SHA-3, que utiliza uma abordagem diferente chamada construção de esponja.
O preenchimento de codificação de comprimento separa mensagens preenchidas; uma prova de segurança completa está fora da evidência do repositório
A função de compactação para SHA-256 assume um estado de 256 bits (oito palavras de 32 bits) e um bloco de 512 bits. A operação usa rodadas 64, cada uma misturando o estado com uma constante e uma palavra do bloco. A mixagem usa operações bit a bit: XOR, AND, NOT. Ele usa rotações e deslocamentos que movem os bits sem alterar quais bits estão definidos. Ele usa pesquisas de tabela que fornecem mixagem não linear que XOR sozinho não consegue alcançar.
SHA-512 usa a mesma construção que SHA-256, mas com operações de 64 bits em vez de operações de 32 bits. O estado é 512 bits (oito palavras de 64 bits) e o tamanho do bloco é 1024 bits. A função de compactação tem rodadas 80 em vez de 64, e as constantes e pesquisas de tabela são diferentes. Para SHA-384, o estado e a função de compactação são iguais a SHA-512, mas apenas o primeiro 384 bits do estado final é gerado. Os últimos 128 bits são descartados. Esse truncamento é o motivo pelo qual SHA-384 é resistente à extensão de comprimento.
A extensão do comprimento é o limite de construção verificado; reivindicações de motivação multicolisão e SHA-3 são omitidas
A segurança de um hash Merkle-Damgård depende da posse de várias propriedades. A função de compressão deve ser resistente a colisões, portanto atacá-la diretamente é inviável. O esquema de preenchimento deve garantir que diferentes mensagens produzam diferentes formas de preenchimento, portanto, cada colisão no hash deve envolver uma colisão de função de compactação. O tamanho do bloco e o tamanho do estado devem ser grandes o suficiente para que a força bruta seja inviável. Um estado mais amplo amplia o espaço de pesquisa genérico, mas este artigo não anexa uma contagem de operações ou data de viabilidade sem uma derivação in-line e uma fonte revisada.
Se um invasor encontrar um ponto fraco na função de compactação ou se os computadores quânticos se tornarem práticos e puderem pesquisar um espaço não estruturado no tempo sqrt(2^n) em vez do tempo 2^n, as margens de segurança serão reduzidas. A fraqueza que motivou SHA-3 não foi uma quebra na função de compressão, mas sim o problema de extensão de comprimento e outras vulnerabilidades estruturais. Uma construção em esponja evita isso nunca publicando seu estado interno completo.
O que isso não cobre — as funções redondas específicas de SHA-256, abordadas em uma postagem separada
A maneira como a construção Merkle-Damgård lida com cada tamanho de entrada é a consequência prática de seu design. Divida a mensagem em blocos de 512 bits, preencha o último bloco, processe cada bloco por meio da função de compactação em sequência e produza o estado final. Para uma entrada de um byte, o preenchimento produz um bloco de 512 bits (um byte de mensagem, um bit de preenchimento, 447 bits de zeros e 64 bits para o comprimento). O número de compactações é o número de blocos de 512 bits, que é proporcional ao comprimento da mensagem.
Cada resumo que a calculadora de hash ToolAcre SHA produz vem desta construção. O resumo de 64 caracteres SHA-256 é o estado final de 256 bits impresso em hexadecimal. O resumo de 128 caracteres SHA-512 é o estado final de 512 bits impresso em hexadecimal. O resumo de 96 caracteres SHA-384 é o primeiro 384 bits do estado final de 512 bits. O preenchimento nos bastidores garante que cada mensagem possível produza exatamente o número certo de blocos e a largura de resumo correta. Esta é a construção Merkle–Damgård padrão em execução no navegador.
Conclusão: o mesmo esqueleto por trás de quatro algoritmos - cada resumo que a calculadora de hash ToolAcre SHA produz vem desta construção
Compreender a construção é útil para saber por que os resumos têm sempre a mesma largura e por que alterar um bit da entrada altera todo o resumo. A propriedade de encadeamento significa que cada bit da entrada afeta cada bit da saída por meio de uma série de operações de mixagem. Uma alteração de um bit no início da mensagem se propagará por todas as compactações subsequentes, de modo que o resumo final será completamente diferente. Essa propriedade é chamada de efeito avalanche e é uma assinatura de uma função hash sonora.
A construção Merkle-Damgård está em uso há décadas e constitui a base das funções hash mais amplamente implantadas. SHA-1 e SHA-2 são construídos com base nesta construção e muitos sistemas implantados dependem de suas saídas. A construção é estabelecida e não experimental, mas essa história não torna todo uso seguro; extensão de comprimento é um limite documentado. Compreender essa construção ajuda os desenvolvedores a entender por que certas propriedades de segurança são válidas e por que existem determinados vetores de ataque.