SHA-1 - SHA-1

Algoritmos Hash seguros
Conceitos
funções hash  · SHA  · DSA
Padrões principais
SHA-0  · SHA-1  · SHA-2  · SHA-3
SHA-1
Em geral
Designers Agencia de Segurança Nacional
Publicado pela primeira vez 1993 (SHA-0),
1995 (SHA-1)
Series ( SHA-0 ), SHA-1, SHA-2 , SHA-3
Certificação FIPS PUB 180-4, CRYPTREC (monitorado)
Detalhe de cifra
Tamanhos de resumo 160 bits
Tamanhos de bloco 512 bits
Estrutura Construção Merkle-Damgård
Rodadas 80
Melhor criptoanálise pública
Um ataque de Marc Stevens em 2011 pode produzir colisões hash com uma complexidade entre 2 60,3 e 2 65,3 operações. A primeira colisão pública foi publicada em 23 de fevereiro de 2017. SHA-1 está sujeito a ataques de extensão de comprimento .

Na criptografia , SHA-1 ( Secure Hash Algorithm 1 ) é uma função hash criptográfica que recebe uma entrada e produz um valor hash de 160 bits (20 bytes ) conhecido como resumo da mensagem - normalmente processado como um número hexadecimal , com 40 dígitos . Ele foi projetado pela Agência de Segurança Nacional dos Estados Unidos e é um Padrão Federal de Processamento de Informações dos EUA .

Desde 2005, o SHA-1 não é considerado seguro contra oponentes bem financiados; a partir de 2010, muitas organizações recomendaram sua substituição. O NIST suspendeu formalmente o uso de SHA-1 em 2011 e proibiu seu uso para assinaturas digitais em 2013. A partir de 2020, os ataques de prefixo escolhido contra SHA-1 são práticos. Como tal, é recomendável remover SHA-1 dos produtos o mais rápido possível e, em vez disso, usar SHA-2 ou SHA-3 . Substituir SHA-1 é urgente onde ele é usado para assinaturas digitais .

Todos os principais fornecedores de navegadores da web deixaram de aceitar os certificados SHA-1 SSL em 2017. Em fevereiro de 2017, a CWI Amsterdam e o Google anunciaram que realizaram um ataque de colisão contra o SHA-1, publicando dois arquivos PDF diferentes que produziram o mesmo hash SHA-1. No entanto, o SHA-1 ainda é seguro para HMAC .

A Microsoft descontinuou o suporte à assinatura de código SHA-1 para o Windows Update em 7 de agosto de 2020.

Desenvolvimento

Uma iteração dentro da função de compressão SHA-1:
A, B, C, D e E são palavras de 32 bits do estado;
F é uma função não linear que varia; denota uma rotação do bit à esquerda em n lugares; n varia para cada operação; W t é a palavra da mensagem expandida do round t; K t é a constante redonda do redondo t; denota módulo de adição 2 32 .




Adição

SHA-1 produz um resumo de mensagem baseado em princípios semelhantes aos usados ​​por Ronald L. Rivest do MIT no projeto dos algoritmos de resumo de mensagem MD2 , MD4 e MD5 , mas gera um valor de hash maior (160 bits vs. 128 bits).

O SHA-1 foi desenvolvido como parte do projeto Capstone do governo dos EUA . A especificação original do algoritmo foi publicada em 1993 sob o título Secure Hash Standard , FIPS PUB 180, pela agência de padrões do governo dos EUA NIST (National Institute of Standards and Technology). Esta versão agora é freqüentemente chamada de SHA-0 . Ele foi retirado pela NSA logo após a publicação e foi substituído pela versão revisada, publicada em 1995 no FIPS PUB 180-1 e comumente designada SHA-1 . SHA-1 difere de SHA-0 apenas por uma única rotação bit a bit na programação da mensagem de sua função de compressão . De acordo com a NSA, isso foi feito para corrigir uma falha no algoritmo original que reduzia sua segurança criptográfica, mas eles não forneceram nenhuma explicação adicional. As técnicas publicamente disponíveis de fato demonstraram um comprometimento do SHA-0, em 2004, antes do SHA-1 em 2017. Consulte #Ataques

Formulários

Criptografia

O SHA-1 faz parte de vários aplicativos e protocolos de segurança amplamente usados, incluindo TLS e SSL , PGP , SSH , S / MIME e IPsec . Esses aplicativos também podem usar MD5 ; ambos MD5 e SHA-1 são descendentes de MD4 .

SHA-1 e SHA-2 são os algoritmos hash exigidos por lei para uso em certos aplicativos do governo dos Estados Unidos , incluindo o uso em outros algoritmos e protocolos criptográficos, para a proteção de informações confidenciais não classificadas. O FIPS PUB 180-1 também incentivou a adoção e o uso do SHA-1 por organizações privadas e comerciais. SHA-1 está sendo retirado da maioria dos usos do governo; o Instituto Nacional de Padrões e Tecnologia dos EUA disse: "As agências federais devem parar de usar SHA-1 para ... aplicações que exigem resistência à colisão assim que possível e devem usar a família SHA-2 de funções hash para essas aplicações após 2010" (ênfase no original), embora isso tenha sido mais tarde relaxado para permitir que SHA-1 fosse usado para verificar assinaturas digitais antigas e carimbos de data / hora.

A principal motivação para a publicação do Secure Hash Algorithm foi o Digital Signature Standard , no qual está incorporado.

As funções hash SHA foram usadas como base para as cifras de bloco SHACAL .

Integridade de dados

Sistemas de controle de revisão como Git , Mercurial e Monotone usam SHA-1, não para segurança, mas para identificar revisões e garantir que os dados não tenham mudado devido a corrupção acidental. Linus Torvalds disse sobre o Git:

Se você tiver corrupção de disco, se houver corrupção de DRAM, se tiver qualquer tipo de problema, o Git irá notá-los. Não é uma questão de se , é uma garantia. Você pode ter pessoas que tentam ser maliciosas. Eles não terão sucesso. ... Ninguém conseguiu quebrar o SHA-1, mas o ponto é que o SHA-1, no que diz respeito ao Git, nem é um recurso de segurança. É puramente uma verificação de consistência. As partes de segurança estão em outro lugar, então muitas pessoas presumem que, como o Git usa SHA-1 e SHA-1 para coisas criptograficamente seguras, elas pensam que, tudo bem, é um recurso de segurança enorme. Não tem nada a ver com segurança, é apenas o melhor hash que você pode obter. ...
Eu garanto a você, se você colocar seus dados no Git, você pode confiar no fato de que cinco anos depois, após ter sido convertido de seu disco rígido para DVD para qualquer nova tecnologia e você copiá-lo junto, cinco anos depois você pode verificar que o os dados que você obtém são exatamente os mesmos dados que você introduz. ...
Uma das razões pelas quais me preocupo é com o kernel, tivemos uma invasão em um dos sites do BitKeeper onde as pessoas tentaram corromper os repositórios de código-fonte do kernel. No entanto, o Git não requer a segunda resistência de pré-imagem do SHA-1 como um recurso de segurança, já que ele sempre preferirá manter a versão mais antiga de um objeto em caso de colisão, evitando que um invasor sobrescreva os arquivos clandestinamente.

Criptoanálise e validação

Para uma função hash para a qual L é o número de bits no resumo da mensagem, encontrar uma mensagem que corresponda a um determinado resumo da mensagem sempre pode ser feito usando uma pesquisa de força bruta em aproximadamente 2 L avaliações. Isso é chamado de ataque de pré - imagem e pode ou não ser prático, dependendo de L e do ambiente de computação específico. No entanto, uma colisão , que consiste em encontrar duas mensagens diferentes que produzem o mesmo resumo de mensagem, requer em média apenas cerca de 1,2 × 2 L / 2 avaliações usando um ataque de aniversário . Portanto, a força de uma função hash é geralmente comparada a uma cifra simétrica de metade do comprimento do resumo da mensagem. O SHA-1, que tem um resumo da mensagem de 160 bits, foi originalmente pensado para ter uma força de 80 bits.

Em 2005, os criptógrafos Xiaoyun Wang , Yiqun Lisa Yin e Hongbo Yu produziram pares de colisão para SHA-0 e encontraram algoritmos que deveriam produzir colisões SHA-1 em muito menos do que as 2 80 avaliações originalmente esperadas .

Alguns dos aplicativos que usam hashes criptográficos, como armazenamento de senha, são afetados minimamente por um ataque de colisão. Construir uma senha que funcione para uma determinada conta requer um ataque preimage , bem como acesso ao hash da senha original, o que pode ou não ser trivial. Reverter a criptografia de senha (por exemplo, para obter uma senha para tentar contra a conta de um usuário em outro lugar) não é possível devido aos ataques. (No entanto, mesmo um hash de senha seguro não pode impedir ataques de força bruta em senhas fracas .)

No caso de assinatura de documento, um invasor não pode simplesmente falsificar uma assinatura de um documento existente: o invasor teria que produzir um par de documentos, um inócuo e outro prejudicial, e fazer com que o detentor da chave privada assinasse o documento inócuo. Existem circunstâncias práticas em que isso é possível; até o final de 2008, era possível criar certificados SSL forjados usando uma colisão MD5 .

Devido ao bloco e à estrutura iterativa dos algoritmos e à ausência de etapas finais adicionais, todas as funções SHA (exceto SHA-3) são vulneráveis ​​a ataques de extensão de comprimento e colisão parcial de mensagens. Esses ataques permitem que um invasor falsifique uma mensagem assinada apenas por um hash com chave - SHA ( mensagem || chave ) ou SHA ( chave || mensagem ) - estendendo a mensagem e recalculando o hash sem conhecer a chave. Uma melhoria simples para evitar esses ataques é fazer hash duas vezes: SHA d ( mensagem ) = SHA (SHA (0 b || mensagem )) (o comprimento de 0 b , bloco zero, é igual ao tamanho do bloco da função hash) .

Ataques

No início de 2005, Vincent Rijmen e Elisabeth Oswald publicaram um ataque a uma versão reduzida do SHA-1 - 53 de 80 rodadas - que encontra colisões com um esforço computacional de menos de 2 80 operações.

Em fevereiro de 2005, um ataque de Xiaoyun Wang , Yiqun Lisa Yin e Hongbo Yu foi anunciado. Os ataques podem encontrar colisões na versão completa do SHA-1, exigindo menos de 2 69 operações. (Uma busca de força bruta exigiria 2 80 operações.)

Os autores escrevem: "Em particular, nossa análise é construída sobre o ataque diferencial original em SHA-0, o ataque de quase colisão em SHA-0, as técnicas de colisão multibloco, bem como as técnicas de modificação de mensagem usadas no ataque de busca de colisão em MD5. Quebrar o SHA-1 não seria possível sem essas poderosas técnicas analíticas. " Os autores apresentaram uma colisão para SHA-1 de 58 rodadas, encontrada com 2 33 operações de hash. O artigo com a descrição completa do ataque foi publicado em agosto de 2005 na conferência CRYPTO.

Em uma entrevista, Yin afirma que, "Grosso modo, exploramos as duas fraquezas a seguir: uma é que a etapa de pré-processamento do arquivo não é complicada o suficiente; outra é que certas operações matemáticas nas primeiras 20 rodadas apresentam problemas de segurança inesperados."

Em 17 de agosto de 2005, uma melhoria no ataque SHA-1 foi anunciada em nome de Xiaoyun Wang , Andrew Yao e Frances Yao na Sessão Rump do CRYPTO 2005, reduzindo a complexidade necessária para encontrar uma colisão no SHA-1 para 2 63 . Em 18 de dezembro de 2007, os detalhes desse resultado foram explicados e verificados por Martin Cochran.

Christophe De Cannière e Christian Rechberger melhoraram ainda mais o ataque ao SHA-1 em "Finding SHA-1 Characteristics: General Results and Applications", recebendo o prêmio de melhor artigo na ASIACRYPT 2006. Uma colisão de dois blocos para o SHA-1 de 64 tiros foi apresentado, encontrado usando métodos não otimizados com 2 35 avaliações da função de compressão. Uma vez que este ataque requer o equivalente a cerca de 2 35 avaliações, é considerado uma quebra teórica significativa. Seu ataque foi estendido para 73 rodadas (de 80) em 2010 por Grechnikov. Para encontrar uma colisão real nas 80 rodadas completas da função hash, entretanto, uma quantidade enorme de tempo de computador é necessária. Para tanto, foi iniciada em 8 de agosto de 2007 uma busca de colisão pelo SHA-1 usando a plataforma de computação distribuída BOINC , organizada pela Graz University of Technology . O esforço foi abandonado em 12 de maio de 2009 devido à falta de progresso.

Na sessão Rump do CRYPTO 2006, Christian Rechberger e Christophe De Cannière afirmaram ter descoberto um ataque de colisão no SHA-1 que permitiria a um invasor selecionar pelo menos partes da mensagem.

Em 2008, uma metodologia de ataque de Stéphane Manuel relatou colisões de hash com uma complexidade teórica estimada de 2 51 a 2 57 operações. No entanto, ele posteriormente retirou essa afirmação após descobrir que os caminhos de colisão locais não eram realmente independentes e, finalmente, citou para o mais eficiente um vetor de colisão que já era conhecido antes deste trabalho.

Cameron McDonald, Philip Hawkes e Josef Pieprzyk apresentaram um ataque de colisão hash com complexidade reivindicada 2 52 na sessão Rump do Eurocrypt 2009. No entanto, o documento que o acompanha, "Caminho diferencial para SHA-1 com complexidade O (2 52 )" foi retirado devido à descoberta dos autores de que sua estimativa estava incorreta.

Um ataque contra o SHA-1 foi Marc Stevens com um custo estimado de $ 2,77 milhões (2012) para quebrar um único valor de hash alugando energia da CPU de servidores em nuvem. Stevens desenvolveu este ataque em um projeto chamado HashClash, implementando um ataque de caminho diferencial. Em 8 de novembro de 2010, ele alegou que teve um ataque de quase colisão totalmente funcional contra o SHA-1 completo funcionando com uma complexidade estimada equivalente a 2 57,5 compressões SHA-1. Ele estimou que esse ataque poderia ser estendido a uma colisão total com uma complexidade em torno de 2 61 .

O SHAppening

Em 8 de outubro de 2015, Marc Stevens, Pierre Karpman e Thomas Peyrin publicaram um ataque de colisão de freestart na função de compressão do SHA-1 que requer apenas 2 57 avaliações do SHA-1. Isso não se traduz diretamente em uma colisão na função de hash SHA-1 completa (em que um invasor não é capaz de escolher livremente o estado interno inicial), mas prejudica as reivindicações de segurança para SHA-1. Em particular, foi a primeira vez que um ataque a SHA-1 completo foi demonstrado ; todos os ataques anteriores eram muito caros para seus autores executá-los. Os autores chamaram esse avanço significativo na criptoanálise de SHA-1 de SHAppening .

O método foi baseado em seus trabalhos anteriores, bem como na técnica de aceleração de caminhos auxiliares (ou bumerangues) de Joux e Peyrin, e usando placas de GPU de alto desempenho / custo-benefício da NVIDIA . A colisão foi encontrada em um cluster de 16 nós com um total de 64 placas gráficas. Os autores estimaram que uma colisão semelhante poderia ser encontrada comprando US $ 2.000 de tempo de GPU no EC2 .

Os autores estimaram que o custo do aluguel de tempo de CPU / GPU EC2 suficiente para gerar uma colisão completa para SHA-1 no momento da publicação estava entre US $ 75K e 120K, e observaram que estava bem dentro do orçamento de organizações criminosas, não para mencionar as agências nacionais de inteligência . Como tal, os autores recomendaram que o SHA-1 fosse descontinuado o mais rápido possível.

SHAttered - primeira colisão pública

Em 23 de fevereiro de 2017, o CWI (Centrum Wiskunde & Informatica) e o Google anunciaram o ataque SHAttered , no qual eles geraram dois arquivos PDF diferentes com o mesmo hash SHA-1 em aproximadamente 2 63,1 avaliações SHA-1. Este ataque é cerca de 100.000 vezes mais rápido do que a força bruta de uma colisão SHA-1 com um ataque de aniversário , que foi estimado em 2 80 avaliações SHA-1. O ataque exigiu "o poder de processamento equivalente a 6.500 anos de cálculos de CPU única e 110 anos de cálculos de GPU única".

Ataque de quase colisão de aniversário - primeiro ataque prático com prefixo escolhido

Em 24 de abril de 2019, um artigo de Gaëtan Leurent e Thomas Peyrin apresentado no Eurocrypt 2019 descreveu um aprimoramento do ataque de prefixo escolhido anteriormente em funções de digestão semelhantes a Merkle-Damgård com base em cifras de bloco de Davies-Meyer . Com essas melhorias, este método é capaz de encontrar colisões de prefixo escolhido em aproximadamente 2 68 avaliações SHA-1. Isso é aproximadamente 1 bilhão de vezes mais rápido (e agora utilizável para muitos ataques direcionados, graças à possibilidade de escolher um prefixo, por exemplo código malicioso ou identidades falsas em certificados assinados) do que as avaliações de 2 77.1 do ataque anterior (mas sem prefixo escolhido, que foi impraticável para a maioria dos ataques direcionados porque as colisões encontradas foram quase aleatórias) e é rápido o suficiente para ser prático para invasores engenhosos, exigindo aproximadamente US $ 100.000 em processamento na nuvem. Este método também é capaz de encontrar colisões de prefixo escolhido na função MD5 , mas em uma complexidade de 2 46,3 não supera o melhor método anterior disponível em um nível teórico (2 39 ), embora potencialmente em um nível prático (≤2 49 ) Este ataque requer um requisito de memória de mais de 500 GB.

Em 5 de janeiro de 2020, os autores publicaram um ataque aprimorado. Neste artigo, eles demonstram um ataque de colisão de prefixo escolhido com uma complexidade de 2 63,4 , que no momento da publicação custaria 45k USD por colisão gerada.

SHA-0

No CRYPTO 98, dois pesquisadores franceses, Florent Chabaud e Antoine Joux , apresentaram um ataque ao SHA-0: as colisões podem ser encontradas com complexidade 2 61 , menos que 2 80 para uma função hash ideal do mesmo tamanho.

Em 2004, Biham e Chen encontraram quase colisões para SHA-0 - duas mensagens com hash para quase o mesmo valor; neste caso, 142 dos 160 bits são iguais. Eles também encontraram colisões completas de SHA-0 reduzidas a 62 de seus 80 tiros.

Posteriormente, em 12 de agosto de 2004, uma colisão para o algoritmo SHA-0 completo foi anunciada por Joux, Carribault, Lemuet e Jalby. Isso foi feito usando uma generalização do ataque de Chabaud e Joux. Encontrar a colisão teve complexidade 2 51 e levou cerca de 80.000 horas de processador em um supercomputador com 256 processadores Itanium 2 (equivalente a 13 dias de uso em tempo integral do computador).

Em 17 de agosto de 2004, na Sessão Rump do CRYPTO 2004, os resultados preliminares foram anunciados por Wang , Feng, Lai e Yu, sobre um ataque a MD5 , SHA-0 e outras funções hash. A complexidade de seu ataque a SHA-0 é 2 40 , significativamente melhor do que o ataque de Joux et al.

Em fevereiro de 2005, foi anunciado um ataque de Xiaoyun Wang , Yiqun Lisa Yin e Hongbo Yu, que poderia encontrar colisões no SHA-0 em 2 39 operações.

Outro ataque em 2008 aplicando o ataque de bumerangue reduziu a complexidade de encontrar colisões para 2 33,6 , o que foi estimado em 1 hora em um PC médio a partir do ano de 2008.

À luz dos resultados para SHA-0, alguns especialistas sugeriram que os planos para o uso de SHA-1 em novos criptossistemas deveriam ser reconsiderados. Depois que os resultados do CRYPTO 2004 foram publicados, o NIST anunciou que planejava descontinuar o uso do SHA-1 até 2010 em favor das variantes do SHA-2.

Validação oficial

As implementações de todas as funções de segurança aprovadas pelo FIPS podem ser oficialmente validadas por meio do programa CMVP , administrado em conjunto pelo Instituto Nacional de Padrões e Tecnologia (NIST) e o Communications Security Establishment (CSE). Para verificação informal, um pacote para gerar um grande número de vetores de teste é disponibilizado para download no site do NIST; a verificação resultante, no entanto, não substitui a validação CMVP formal, que é exigida por lei para certas aplicações.

Em dezembro de 2013, havia mais de 2.000 implementações validadas de SHA-1, com 14 delas capazes de lidar com mensagens com um comprimento em bits não múltiplo de oito (ver Lista de Validação SHS ).

Exemplos e pseudocódigo

Hashes de exemplo

Estes são exemplos de resumos de mensagens SHA-1 em hexadecimal e em binário Base64 para codificação de texto ASCII .

  • SHA1("The quick brown fox jumps over the lazy dog")
    • Hexadecimal de saída: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
    • Saída de binário Base64 para codificação de texto ASCII :L9ThxnotKPzthJ7hu3bnORuT6xI=

Mesmo uma pequena mudança na mensagem irá, com grande probabilidade, resultar em muitos bits mudando devido ao efeito de avalanche . Por exemplo, mudar dogpara cogproduz um hash com valores diferentes para 81 dos 160 bits:

  • SHA1("The quick brown fox jumps over the lazy cog")
    • Hexadecimal de saída: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
    • Saída de binário Base64 para codificação de texto ASCII :3p8sf9JeGzr60+haC9F9mxANtLM=

O hash da string de comprimento zero é:

  • SHA1("")
    • Hexadecimal de saída: da39a3ee5e6b4b0d3255bfef95601890afd80709
    • Saída de binário Base64 para codificação de texto ASCII :2jmj7l5rSw0yVb/vlWAYkK/YBwk=

Pseudocódigo SHA-1

Segue-se o pseudocódigo para o algoritmo SHA-1:

Note 1: All variables are unsigned 32-bit quantities and wrap modulo 232 when calculating, except for
        ml, the message length, which is a 64-bit quantity, and
        hh, the message digest, which is a 160-bit quantity.
Note 2: All constants in this pseudo code are in big endian.
        Within each word, the most significant byte is stored in the leftmost byte position

Initialize variables:

h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

ml = message length in bits (always a multiple of the number of bits in a character).

Pre-processing:
append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
   is congruent to −64 ≡ 448 (mod 512)
append ml, the original message length in bits, as a 64-bit big-endian integer. 
   Thus, the total length is a multiple of 512 bits.

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

    Message schedule: extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79
        Note 3: SHA-0 differs by not having this leftrotate.
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    Initialize hash value for this chunk:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Main loop:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f = (b and c) or (b and d) or (c and d) 
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Add this chunk's hash to result so far:
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Produce the final hash value (big-endian) as a 160-bit number:
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

O número hhé o resumo da mensagem, que pode ser escrito em hexadecimal (base 16).

Os valores constantes escolhidos usados ​​no algoritmo foram considerados nada na minha manga :

  • As quatro constantes de arredondamento ksão 2 30 vezes as raízes quadradas de 2, 3, 5 e 10. No entanto, foram arredondadas incorretamente para o inteiro mais próximo em vez de serem arredondadas para o inteiro ímpar mais próximo, com proporções equilibradas de zero e um bits. Além disso, escolher a raiz quadrada de 10 (que não é primo) tornou-a um fator comum para as duas outras raízes quadradas escolhidas dos primos 2 e 5, com propriedades aritméticas possivelmente utilizáveis ​​em rodadas sucessivas, reduzindo a força do algoritmo contra encontrar colisões em alguns bits.
  • Os primeiros quatro valores iniciais para h0através h3são os mesmos com o algoritmo MD5 e o quinto (para h4) é semelhante. No entanto, eles não foram devidamente verificados por serem resistentes à inversão das poucas primeiras rodadas para inferir possíveis colisões em alguns bits, utilizáveis ​​por ataques diferenciais multibloco.

Em vez da formulação do FIPS PUB 180-1 original mostrado, as seguintes expressões equivalentes podem ser usadas para calcular fno loop principal acima:

Bitwise choice between c and d, controlled by b.
(0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (alternative 1)
(0  ≤ i ≤ 19): f = (b and c) or ((not b) and d)           (alternative 2)
(0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (alternative 3)
(0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       (alternative 4)
 [premo08]
Bitwise majority function.
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (alternative 1)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (alternative 2)
(40 ≤ i ≤ 59): f = (b and c) xor (d and (b xor c))        (alternative 3)
(40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (alternative 4)
(40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d)                 (alternative 5)

Também foi mostrado que, para as rodadas 32-79, o cálculo de:

w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

pode ser substituído por:

w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) leftrotate 2

Essa transformação mantém todos os operandos de 64 bits alinhados e, ao remover a dependência de w[i]on w[i-3], permite uma implementação SIMD eficiente com um comprimento de vetor de 4 como as instruções SSE x86 .

Comparação de funções SHA

Na tabela abaixo, o estado interno significa a "soma hash interna" após cada compactação de um bloco de dados.

Comparação de funções SHA
Algoritmo e variante Tamanho de saída
(bits)
Tamanho do estado interno
(bits)
Tamanho do bloco
(bits)
Rodadas Operações Segurança contra ataques de colisão
(bits)
Segurança contra ataques de extensão de comprimento
(bits)
Desempenho no Skylake ( cpb mediano ) Publicado pela primeira vez
Mensagens longas 8 bytes
MD5 (como referência) 128 128
(4 × 32)
512 64 E, Xor, Rot, Add (mod 2 32 ), Ou ≤ 18
(colisões encontradas)
0 4,99 55,00 1992
SHA-0 160 160
(5 × 32)
512 80 E, Xor, Rot, Add (mod 2 32 ), Ou <34
(colisões encontradas)
0 ≈ SHA-1 ≈ SHA-1 1993
SHA-1 <63
(colisões encontradas)
3,47 52,00 1995
SHA-2 SHA-224
SHA-256
224
256
256
(8 × 32)
512 64 E, Xor, Rot, Add (mod 2 32 ), Ou, Shr 112
128
32
0
7,62
7,63
84,50
85,25
2004
2001
SHA-384
SHA-512
384
512
512
(8 × 64)
1024 80 E, Xor, Rot, Add (mod 2 64 ), Ou, Shr 192
256
128 (≤ 384)
0
5,12
5,06
135,75
135,50
2001
SHA-512/224
SHA-512/256
224
256
112
128
288
256
≈ SHA-384 ≈ SHA-384 2012
SHA-3 SHA3-224
SHA3-256
SHA3-384
SHA3-512
224
256
384
512
1600
(5 × 5 × 64)
1152
1088
832
576
24 E, Xor, Rot, Not 112
128
192
256
448
512
768
1024
8,12
8,59
11,06
15,88
154,25
155,50
164,00
164,00
2015
SHAKE128
SHAKE256
d (arbitrário)
d (arbitrário)
1344
1088
min ( d / 2, 128)
min ( d / 2, 256)
256
512
7,08
8,59
155,25
155,50

Implementações

Abaixo está uma lista de bibliotecas de criptografia que suportam SHA-1:

A aceleração de hardware é fornecida pelas seguintes extensões de processador:

Veja também

Notas

Referências

links externos