SHA-1

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de SHA1)
Ir para: navegação, pesquisa
SHA-1
Geral
Projetistas Agência de Segurança Nacional
Primeira publicação 1993 (SHA-0), 1995 (SHA-1)
Séries (SHA-0), SHA-1, SHA-2, SHA-3
Certificação FIPS PUB 180-4, CRYPTREC (Monitorado)
Detalhes
Tamanho do resumo 160 bits
Estrutura Construção Merkle–Damgård
Rodadas 80
Melhor criptanálise pública
Um ataque de 2011 feito por Marc Stevens pode produzir colisões de hash com complexidade entre 260.3 e 265.3 operações.[1] Nenhuma colisão ainda foi produzida de fato.

Em criptografia, SHA-1 é uma função de dispersão criptográfica (ou função hash criptográfica) projetada pela Agência de Segurança Nacional dos Estados Unidos e é um Padrão de Processamento de Informação Federal dos Estados Unidos publicado pelo Instituto Nacional de Padrões e Tecnologia (NIST).[2]

SHA-1 produz um valor de dispersão de 160 bits (20 bytes) conhecido como resumo da mensagem. Um valor de dispersão SHA-1 é normalmente tratado como um número hexadecimal de 40 dígitos.

A sigla SHA significa "algoritmo de dispersão seguro" (secure hash algorithm em inglês). Os quatro algoritmos SHA são estruturados diferentemente e nomeados SHA-0, SHA-1, SHA-2 e SHA-3. SHA-0 é a versão original da função de dispersão de 160 bits publicada em 1995 sob o nome "SHA": ela não foi adotada por muitas aplicações. Publicada em 1995, SHA-1 é muito similar à SHA-0, mas altera a especificação de dispersão do SHA original para corrigir as fraquezas alegadas. SHA-2, publicada em 2001, é significantemente diferente da função de dispersão SHA-1.

SHA-1 é a mais amplamente utilizada das funções de dispersão SHA existentes, sendo empregada em vários protocolos e aplicações amplamente utilizadas.

Em 2005, criptoanalistas descobriram ataques sobre SHA-1, sugerindo que o algoritmo poderia não ser seguro o suficiente para uso continuado.[3] O NIST exigiu que várias aplicações utilizadas em agências federais mudassem para SHA-2 depois de 2010 devido à fraqueza descoberta.[4] Apesar dos ataques bem sucedidos sobre o SHA-2 nunca terem sido relatados, ele é algoritmicamente similar ao SHA-1. Em 2012, segundo uma longa competição, o NIST selecionou um algoritmo adicional, o Keccak, para padronização sob o título de SHA-3.[5] Em novembro de 2013, a Google anunciou sua política de rebaixamento sobre o SHA-1, de acordo com a qual o Chrome irá deixar de aceitar certificados SHA-1 em SSL de forma gradual em 2017.[6] Mozilla também pretende parar de aceitar certificados baseados em SSL até 2017. [7] [8] [9]

A função de dispersão SHA-1[editar | editar código-fonte]

Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade. Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

SHA-1 produz um resumo da mensagem baseado em princípios similares aos utilizados por Ronald L. Rivest, do MIT, no projeto dos algoritmos de resumo de mensagens MD4 e MD5, mas com um design mais conservador.

A especificação original do algoritmo foi publicada em 1993 sob o título Padrão de Dispersão Seguro (Secure Hash Standard em inglês), FIPS PUB 180, pela agência do governo norte-americano NIST. Hoje, essa versão é geralmente chamada de SHA-0. Ela foi recolhida pela NSA logo após sua publicação e foi substituída por sua versão revisada, publicada em 1995 na FIPS PUB 180-1, e normalmente designada SHA-1. SHA-1 difere da SHA-0 apenas por uma única rotação bit a bit na sua função de compressão; isso foi feito, de acordo com a NSA, para corrigir uma falha no algoritmo original que reduzia sua segurança criptográfica. No entanto, a NSA não forneceu nenhuma explicação mais aprofundada nem identificou exatamente qual era a falha que foi corrigida. Fraquezas foram posteriormente relatadas em ambas SHA-0 e SHA-1. SHA-1 parece fornecer uma resistência maior contra ataques, corroborando com a declaração da NSA de que a mudança aumentou a segurança. [carece de fontes?]

Aplicações[editar | editar código-fonte]

Uma iteração dentro da função de compressão do 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; Lll.png_n denota a rotação de bits à esquerda em n espaços; n varia para cada operação; Wt é a palavra da mensagem expandida da rodada t; Kt é a constante da rodada t; Boxplus.png denota uma adição módulo 232.

Criptografia[editar | editar código-fonte]

Para obter mais detalhes sobre este tópico, veja Funções Hash Criptográficas#Aplicações.

SHA-1 faz parte de várias aplicações e protocolos de segurança amplamente utilizados, incluindo TLS e SSL, PGP, S/MIME e IPsec. Tais aplicações podem também usar MD5; Ambos MD5 e SHA-1 descendem de MD4. O hashing de SHA-1 também é utilizado em sistemas de controle de revisão distribuídos como Git, Mercurial e Monotone para identificar revisões, assim como detectar corrupção ou adulteração de dados. O algoritmo também foi utilizado no console de vídeo game Nintendo Wii para verificação de assinatura durante a inicialização do sistema, entretanto uma falha significativa nas primeiras implementações do firmware permitiam que um atacante ignorasse o esquema de segurança do sistema.[10]

SHA-1 e SHA-2 são os algoritmos de hash seguro exigidos por lei para uso em certas aplicações do governo norte-americano, incluindo seu uso com outros protocolos e algoritmos criptográficos, para a proteção de informação não-confidencial sensível. FIPS PUB-1 também estimulou a adoção e uso de SHA-1 por organizações privadas e públicas. SHA-1 está sendo retirada da maior parte de seu uso no governo; o NIST dos Estados Unidos disse: "Agências Federais devem suspender a utilização de SHA-1 para...aplicações que exigem resistência à colisão assim que possível, e devem usar a família de funções de dispersão SHA-2 para essas aplicações após 2010" (ênfase original)[11] , apesar de que mais tarde isso foi relaxado.[12]

Uma das principais motivações para a publicação do algoritmo de dispersão seguro foi o Padrão de Assinatura Digital, no qual está incorporado.

As funções de dispersão SHA têm sido utilizadas como base para as cifras de bloco SHACAL.

Integridade de dados[editar | editar código-fonte]

Sistemas de controle de revisão, tais como Git e Mercurial, utilizam SHA-1 não para segurança mas para garantir que os dados não foram alterados devido à corrupção acidental. Linus Torvalds disse sobre o Git: "Se você tiver corrupção de disco, se você tiver corrupção de DRAM, se você tiver quaisquer tipo de problemas, Git os perceberá. Não é uma questão de "se", é uma garantia. Você pode ter duas pessoas que estão tentando ser maliciosas. Elas não serão bem sucedidas. [...] Ninguém conseguiu quebrar SHA-1, mas a questão é que a SHA-1, até onde o que concerne ao Git, não é nem uma característica de segurança, é puramente uma checagem de consistência. As partes de segurança estão em outro lugar, daí um monte de pessoas assumem que já que Git utiliza SHA-1 e SHA-1 é usado para coisas criptograficamente seguras, elas acham que, OK, é uma grande e importante característica de sua segurança. Não tem nada a ver com segurança, é apenas o melhor hash que você pode conseguir. [...] Eu garanto a você, se você colocar seus dados no Git, você pode acreditar que após cinco anos, após eles serem convertidos de seu disco rígido para DVD para qualquer nova tecnologia e você o copiou junto, cinco anos depois você pode verificar que os dados que você consegue de volta são exatamente os mesmos que você colocou. [...] Uma das razões pela qual me importo é pelo kernel, tivemos uma quebra em um dos sites do BitKeeper em que pessoas tentavam corromper os repositórios do código fonte do kernel".[13] No entanto, sem a resistência de segunda preimagem do SHA-1, envios assinados e tags não poderiam mais garantir a segurança do estado do repositório já que eles só assinam a raiz da Árvore de Merkle.

Criptoanálise e validação[editar | editar código-fonte]

Para uma função de dispersão na qual L é o número de bits no resumo da mensagem, encontrar a mensagem que corresponde a um dado resumo de mensagem pode sempre ser feito utilizando-se de busca por força-bruta, que leva aproximadamente 2L avaliações. Isso é chamado de ataque da preimagem e pode ser ou não prático, dependendo de L e do ambiente de computação particular. O segundo critério, encontrar duas mensagens diferentes que produzam o mesmo resumo, o que chamamos de colisão, requer uma média de apenas 1,2* 2L/2 avaliações utilizando o ataque do aniversário. Para o último motivo, a força da função de dispersão é normalmente comparada com uma cifra simétrica com o tamanho igual à metade do resumo da mensagem. Com isso, SHA-1 foi originalmente projetada para ter uma força de 80 bits.

Criptógrafos produziram pares de colisão para SHA-0 e encontraram algoritmos que devem produzir colisões em SHA-1 em muito menos avaliações que as esperadas 280.

Em termos de segurança prática, uma grande preocupação sobre esses novos ataques é que eles podem pavimentar o caminho para outros mais eficientes. Se esse é o caso ainda está para ser visto, mas uma migração para valores de dispersão mais fortes é considerada prudente. Algumas das aplicações que utilizam valores de dispersão criptográficos, como armazenamento de senhas, são apenas minimamente afetados por um ataque de colisão. Construir uma senha que funcione para uma dada conta requer um ataque da preimagem, assim como acesso ao valor de dispersão da senha original, que pode ou não ser trivial. Reverter uma encriptação de senha (exemplo: obter uma senha para ser usada contra a conta do usuário em algum outro lugar) não é possível pelos ataques. (Entretanto, até um valor de dispersão de uma senha seguro não pode prevenir um ataque de força bruta em senhas fracas.)

No caso de assinatura de documentos, um atacante não poderia apenas falsificar uma assinatura de um documento existente - o atacante teria que produzir um par de documentos, um inofensivo e outro danificador,e então conseguir que o detentor da chave privada assinasse o documento inofensivo. Há circunstâncias práticas nas quais isso é possível; até o fim de 2008, era possível criar certificados SSL forjados utilizando-se uma colisão em MD5.[14]

Devido à estrutura iterativa e de blocos do algoritmo e à ausência de passos finais adicionais, todas as funções SHA são vulneráveis aos ataques de extensão de tamanho e de colisão parcial de mensagens.[15] Esses ataques permitem que um atacante forje uma mensagem assinada apenas por um valor de dispersão chaveado - SHA(mensagem||chave) ou SHA(chave||mensagem) - através do estendimento da mensagem e recálculo do valor de dispersão sem saber a chave. A melhoria mais simples para prevenir tais ataques é fazer o valor de dispersão duas vezes: SHA_d(mensagem) = SHA(SHA(0^b||mensagem)) (o tamanho de 0b, bloco zero, é igual ao tamanho do bloco da função de dispersão.

Ataques[editar | editar código-fonte]

Logo no início de 2005, Rijmen e Oswald publicaram um ataque sobre uma versão reduzida do SHA-1 - 53 de 80 rodadas - que achou colisões com um esforço computacional menor que 280 operações.[16]

Em fevereiro de 2005, um ataque feito por Xiaoyum Wang, Yiqun Lisa Yin e Hongbo Yu foi anunciado.[17] Os ataques podem achar colisões na versão completa de SHA-1, precisando de menos que 269 operações (Uma busca por força bruta precisaria de 280 operações).

Os autores escreveram: "Em particular, nossa análise é construída sobre o ataque diferencial original sobre o SHA-0, as técnicas de colisão multi-travas, assim como as técnicas de modificação de mensagem utilizadas no ataque de busca de colisão sobre o MD5. Quebrar o SHA-1 não seria possível sem essas poderosas técnicas analíticas".[18] Os autores apresentaram uma colisão para SHA-1 de 58 rodadas, encontrada com 233 operações. O documento com o ataque completamente descrito foi publicado em Agosto de 2005 durante a conferência CRYPTO.

Durante uma entrevista, Yin afirma que "Grosso modo, exploramos as duas seguintes fraquezas: Uma é que o tamanho do passo de preprocessamento do arquivo não é complicado o suficiente; a outra é que certas operações matemáticas nas primeiras vinte rodadas têm problemas de segurança inesperados."[19]

Em 17 de agosto de 2005, uma melhoria no ataque sobre SHA-1 foi anunciada em nome de Xiaoyun Wang, Andrew Yao e Frances Yao durante uma Rump Session da CRYPTO 2005, diminuindo a complexidade necessária para se encontrar colisões sobre SHA-1 para 263.[20] Em 28 de Dezembro de 2007, detalhes desse resultado foram explicados e verificados por Martin Cochran.[21]

Christophe De Cannière and Christian Rechberger melhoraram mais ainda o ataque sobre SHA-1 em "Finding SHA-1 Characteristics: General Results and Applications"[22] , recebendo o prêmio de melhor artigo científico em ASIACRYPT 2006. Uma colisão de dois blocos para uma SHA-1 de 64 rodadas foi apresentada, encontrada utilizando-se métodos não otimizados com 235 avaliações de função de compressão. Uma vez que esse ataque precisa do equivalente a 235 avaliações, é considerado uma quebra teórica significativa.[23] Seu ataque foi estendido para 73 rodadas (de 80) em 2010 por Grechinov.[24] Para se encontrar uma colisão efetiva numa função de dispersão completa de 80 rodadas, no entanto, quantidades massivas de tempo computacional são necessárias. Para este fim, uma busca de colisão para SHA-1 utilizando a plataforma de computação distribuída BOINC começou em 8 de Agosto de 2007, organizada pela Universidade de Tecnologia de Graz. Devido à falta de progresso, o plano foi abandonado em 12 de Maio de 2009.[25]

Na Rump Session da CRYPTO 2006, Christian Rechberger e Christophe de Cannière reivindicaram ter descoberto uma colisão sobre SHA-1 que permitiria que um atacante selecionasse pelo menos partes da mensagem.[26] [27]

Em 2008, uma metodologia de ataque feita por Stéphane Manuel reportou que colisões de valores de dispersão com uma complexidade teórica estimada de 251 até 257 operações.[28] Entretanto ele retirou posteriormente sua reivindicação após encontrar que caminhos de colisão locais não eram de fato independentes, e finalmente citando como o mais eficiente um vetor de colisão que já era conhecido antes desse trabalho.[29]

Cameron McDonald, Philip Hawkes e Josef Pieprzyk apresentaram um ataque de colisão de valores de dispersão com complexidade 252 na Rump Session da Eutocrypt 2009.[30] No entanto, o artigo acompanhante, "Diferential Path for SHA-1 with complexity O(252)" (Caminho Diferencial para SHA-1 com complexidade O(252)) foi retirado devido a uma descoberta feita pelo autor de que suas estimativas estavam incorretas.[31]

Até 2012, o ataque mais eficiente contra SHA-1 é considerado o de Marc Stevens[32] , com um custo estimado de $2.77M para quebrar um único valor de dispersão, alugando força de CPU de servidores na nuvem[33] . Stevens desenvolveu esse ataque em um projeto chamado HashClash[34] , implementando um ataque de caminho diferencial. Em 8 de Novembro de 2010, ele reivindicou que tinha um ataque de colisão aproximada totalmente funcional contra uma SHA-1 completa funcionando com uma complexidade estimada equivalente a 257.5 compressões SHA-1. Ele estima que esse ataque pode ser estendido para uma colisão completa com complexidade em tordo de 261.

SHA-0[editar | editar código-fonte]

Na CRYPTO 98, dois pesquisadores franceses, Florent Chanbaud e Antonie Joux, apresentaram um ataque sobre SHA-0 (Chabaud and Joux, 1998): colisões podem ser encontradas com complexidade de 261 para uma função de dispersão ideal do mesmo tamanho.

Em 2004, Biham e Chen encontraram colisões aproximadas para SHA-0 - suas mensagens que resultam num valor de dispersão com quase o mesmo valor; nesse caso, 142 dos 160 bits são iguais. Eles também encontraram colisões completas de SHA-0 reduzida para 62 rodadas (de 80).

Subsequentemente, em 12 de Agosto de 2004, uma colisão para o SHA-0 completo foi anunciada por Joux, Carribault, Lemuet e Jalby. Isso foi feito utilizando-se uma generalização do ataque de Chabaud e Joux. Encontrar uma colisão tinha complexidade de 251 e levava aproximadamente 80.000 horas de CPU em um supercomputador com 256 processadores Itanium 2 (equivalente a 13 dias de uso completo do computador).

Em 17 de Agosto de 2004, durante a Seção Garupa de CRYPTO 2004, resultados preliminares foram anunciados por Wang, Feng Lai e Yu, sobre um ataque sobre a MS5, SHA-0 e outras funções de dispersão. A complexidade do seu ataque sobre a SHA-0 é 240, significantemente melhor que o ataque de Joux et al.[35]

Em Fevereiro de 2005, um ataque feito por Wang, Yiqun Lisa Yin e Hongbo Yu foi anunciado. Tal ataque poderia encontrar colisões em SHA-0 em 239 operações.[36]

Outro ataque em 2008, aplicando-se o ataque do bumerangue, baixava a complexidade de se encontrar colisões para 233.6, que se estima levar uma hora em um computador mediano.[37]

Em luz a esses resultados para SHA-0, alguns especialistas sugeriram planos para o uso de SHA-1 em novos criptossistemas. Depois que os resultados da CRYPTO 2004 foram publicados, NIST anunciou que eles planejaram passar do uso da SHA-1 em 2010 em favor das variantes da SHA-2.

Validação oficial[editar | editar código-fonte]

Para obter mais detalhes sobre este tópico, veja Programa de Validação de Módulo Criptográfico.

Implementações de todas as funções aprovadas pelo FIPS podem ser validadas oficialmente através do programa CMVP, dirigido em conjunto pelo NIST e pelo Estabelecimento de Segurança e Comunicações (CSE, Communications Security Establishment em inglês). Para verificação informal, um pacote para se gerar uma grande número de vetores de teste é disponibilizado no site do NIST; a verificação resultante no entanto não substitui, em forma alguma, a validação formal CMVP, que é exigida por lei em certas aplicações.

A partir de Dezembro de 2013, há mais de 2000 implementações validadas de SHA-1, com 14 delas capazes de manusear mensagens com tamanho em bits não múltiplo de oito (lista de validação SHS).

Exemplos e pseudocódigos[editar | editar código-fonte]

Hashes exemplo[editar | editar código-fonte]

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

SHA1("The quick brown fox jumps over the lazy dog")
gives hexadecimal: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
gives Base64 binary to ASCII text encoding: L9ThxnotKPzthJ7hu3bnORuT6xI=

Até mesmo uma pequena mudança na mensagem irá, com probabilidade esmagadora, resultar em um hash completamente diferente, devido ao efeito avalanche. Por exemplo, mudar dog to cog produz um hash com valores diferentes para 81 dos 160 bits.

SHA1("The quick brown fox jumps over the lazy dog")
resulta no hexadecimal: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
resulta no binário Base64 para a codificação de texto em ASCII: 3p8sf9JeGzr60+haC9F9mxANtLM=

O hash da palavra de tamanho zero é:

SHA1("")
resulta no hexadecimal: da39a3ee5e6b4b0d3255bfef95601890afd80709
resulta no binário Base64 para a codificação de texto em ASCII: 2jmj7l5rSw0yVb/vlWAYkK/YBwk=

Pseudocódigo SHA-1[editar | editar código-fonte]

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


 Nota 1: Todas as variáveis são inteiros de 32 bits sem sinal e envolvidas em um módulo 232 quando calculadas, exceto
        ml o tamanho da mensagem, que é de 64 bits, e
        hh o tamanho do resumo da mensagem, que é de 160 bits.
Nota 2: TODAS as constantes deste pseudocódigo estão em big endian.
        Dentro de cada palavra, o byte mais significativo é guardado na posição mais à esquerda.

Inicializar variáveis:

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

ml = tamanho da mensagem em bits (sempre múltiplo do número de bits em um caractere).

Pré-processando:
anexar o bit '1' na mensagem i.e. adicionando 0x80 se os caracteres forem 8 bits. 
anexar 0 ≤ k < 512 bits '0', daí o tamanho resultante da mensagem (em bits)
   será congruente a 448 (mod 512)
anexar ml, em um inteiro big endian de 64 bits. Agora o tamanho da mensagem é um múltiplo de 512 bits.

Processar a mensagem em pedaços sucessivos de 512 bits:
quebrar a mensagem em pedaços de 512 bits
para cada pedaço
    quebrar o pedaço em dezesseis palavras de 32 bits em big endian w[i], 0 ≤ i ≤ 15

    Estender as dezesseis palavras de 32 bits em oitenta palavras de 32 bits:
    para i de 16 até 79
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) rotacionarparaesquerda 1

    Inicializa o valor hash para esse pedaço:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Laço principal:[38] 
    para i de 0 até 79
        se 0 ≤ i ≤ 19 então
            f = (b e c) ou ((não b) e d)
            k = 0x5A827999
        senão se 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        senão se 40 ≤ i ≤ 59
            f = (b e c) ou (b e d) ou (c e d) 
            k se0x8F1BBCDC
        senão se 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

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

    Adicionar este hash do pedaço ao resultado obtido até agora:
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Produzir o valor final do hash (big-endian) como um número de 160 bits:
hh = (h0 deslocamentoparaesquerda 128) ou (h1 deslocamentoparaesquerda 96) ou (h2 deslocamentoparaesquerda 64) ou (h3 deslocamentoparaesquerda 32) ou h4

O número hh é o resumo da mensagem, que pode ser escrito em hexadecimal (base 16), mas é normalmente escrito utilizando-se binário Base64 para codificação de texto em ASCII.

Os valores constantes utilizados são escolhidos para parecerem aleatórios: as quatro constantes da rodada k são 230 as raízes quadradas de 2,3, 5 e 10. Os primeiros números iniciais de h0 até h3 são os mesmos do algoritmo MD5, e o quinto (para h4) é similar.

Em vez da formulação do FIPS PUB 180-1 original mostrada, as seguintes expressões equivalentes podem ser utilizadas para computar f no laço principal acima:

(0  ≤ i ≤ 19): f = d xor (b e (c xor d))                  (alternativa 1)
(0  ≤ i ≤ 19): f = (b e c) xor ((não b) e d)              (alternativa 2)
(0  ≤ i ≤ 19): f = (b e c) + ((não b) e d)                (alternativa 3)
(0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       (alternativa 4)
 
(40 ≤ i ≤ 59): f = (b e c) ou (d e (b ou c))              (alternativa 1)
(40 ≤ i ≤ 59): f = (b e c) ou (d e (b xor c))             (alternativa 2)
(40 ≤ i ≤ 59): f = (b e c) + (d e (b xor c))              (alternativa 3)
(40 ≤ i ≤ 59): f = (b e c) xor (b e d) xor (c e d)        (alternativa 4)
(40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d)                 (alternativa 5)

Max Locktyukhin também mostrou que para as rodadas 32–79 a computação de:

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

pode ser substituída com:

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

Esta transformação mantém todos os operandos de 64 bits alinhados e, por remover a dependência de w[i] em w[i-3], permite a implementação eficiente de SIMD com um vetor de tamanho 4 como instruções x84 SSE.

Comparação de funções SHA[editar | editar código-fonte]

Na tabela abaixo, estado interno significa a "soma do hash interno" após cada compressão de bloco de dados.

Perceba que a performance irá variar não apenas entre algoritmos, mas também com a implementação e equipamento utilizados. A ferramenta OpenSSL vem com um comando embutido chamado "velocidade" que referencia os vários algoritmos no sistema do usuário.

Comparação de funções SHA
Algoritmo e variantes Tamanho da saída
(bits)
Tamanho do estado interno
(bits)
Tamanho do bloco
(bits)
Tamanho máximo de mensagem
(bits)
Rodadas Operações Segurança
(bits)
Performance Exemplo
(MiB/s)
MD5 (como referencia) 128 128
(4 × 32)
512 264 − 1 64 And, Xor, Rot,
Add (mod 232),
Or
<64
(colisões encontradas)
335
SHA-0 160 160
(5 × 32)
512 264 − 1 80 And, Xor, Rot,
Add (mod 232),
Or
<80
(colisões encontradas)
-
SHA-1 160 160
(5 × 32)
512 264 − 1 80 <80
(ataque teórico[39] em 261 operações)
192
SHA-2 SHA-224
SHA-256
224
256
256
(8 × 32)
512 264 − 1 64 And, Xor, Rot,
Add (mod 232),
Or, Shr
112
128
139
SHA-384
SHA-512
SHA-512/224
SHA-512/256
384
512
224
256
512
(8 × 64)
1024 2128 − 1 80 And, Xor, Rot,
Add (mod 264),
Or, Shr
192
256
112
128
154
SHA-3 SHA3-224
SHA3-256
SHA3-384
SHA3-512
224
256
384
512
1600
(5 × 5 × 64)
1152
1088
832
576
Ilimitado 24 And, Xor, Rot,
Not
112
128
192
256
-
SHAKE128
SHAKE256
d (arbitrario)
d (arbitrario)
1344
1088
min (d/2, 128)
min (d/2, 256)
-

Veja também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. Stevens, Marc. Attacks on Hash Functions and Applications (PDF) (em inglês) 19 de Junho de 2012. Visitado em 09 de Agosto de 2012.
  2. http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf
  3. Cryptanalysis of SHA-1 - Schneier on Security www.schneier.com. Visitado em 2015-08-09.
  4. NIST.gov - Computer Security Division - Computer Security Resource Center csrc.nist.gov. Visitado em 2015-08-09.
  5. NIST Hash Workshop Liveblogging (5) - Schneier on Security www.schneier.com. Visitado em 2015-08-09.
  6. SHA1 Deprecation Policy - Windows PKI blog - Site Home - TechNet Blogs blogs.technet.com. Visitado em 2015-08-09.
  7. 942515 – stop accepting SHA-1-based SSL certificates with notBefore >= 2014-03-01 and notAfter >= 2017-01-01, or any SHA-1-based SSL certificates after 2017-01-01 bugzilla.mozilla.org. Visitado em 2015-08-09.
  8. CA:Problematic Practices - MozillaWiki wiki.mozilla.org. Visitado em 2015-08-09.
  9. Phasing Out Certificates with SHA-1 based Signature Algorithms Mozilla Security Blog. Visitado em 2015-08-09.
  10. debugmo.de :: Thank you, Datel. debugmo.de. Visitado em 2015-08-09.
  11. NIST.gov - Computer Security Division - Computer Security Resource Center csrc.nist.gov. Visitado em 2015-08-09.
  12. NIST.gov - Computer Security Division - Computer Security Resource Center csrc.nist.gov. Visitado em 2015-08-09.
  13. https://www.youtube.com/watch?v=4XpnKHJAok8&t=56m20s
  14. MD5 considered harmful today www.win.tue.nl. Visitado em 2015-08-09.
  15. [1].
  16. Rijmen, Vincent; Elisabeth. (2005-01-01). "Update on SHA-1".
  17. SHA-1 Broken - Schneier on Security www.schneier.com. Visitado em 2015-08-09.
  18. "Massachusetts Institute of Technology" (em en).
  19. Fixing a hole in security | ZDNet ZDNet. Visitado em 2015-08-09.
  20. New Cryptanalytic Results Against SHA-1 - Schneier on Security www.schneier.com. Visitado em 2015-08-09.
  21. Cochran, Martin. (2007-01-01). "Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path".
  22. Cannière, Christophe De. In: Xuejia. Finding SHA-1 Characteristics: General Results and Applications. [S.l.]: Springer Berlin Heidelberg, 2006-01-01. p. 1-20. ISBN 978-3-540-49475-1
  23. IAIK - TU Graz :: SHA-1 Collision Search www.iaik.tugraz.at. Visitado em 2015-08-09.
  24. (2010-01-01) "Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics".
  25. [2].
  26. IT-News, c't, iX, Technology Review, Telepolis heise online. Visitado em 2015-08-09.
  27. Crypto 2006 Rump Schedule www.iacr.org. Visitado em 2015-08-09.
  28. http://eprint.iacr.org/2008/469.pdf
  29. Manuel, Stéphane. (2011-01-05). "Classification and generation of disturbance vectors for collision attacks against SHA-1" (em en). Designs, Codes and Cryptography 59 (1-3): 247-263. DOI:10.1007/s10623-010-9458-9. ISSN 0925-1022.
  30. http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf
  31. McDonald, Cameron; Philip. (2009-01-01). "Differential Path for SHA-1 with complexity $O(2^{52})$".
  32. http://2012.sharcs.org/slides/stevens.pdf
  33. When Will We See Collisions for SHA-1? - Schneier on Security www.schneier.com. Visitado em 2015-08-09.
  34. Google Project Hosting code.google.com. Visitado em 2015-08-09.
  35. http://www.freedom-to-tinker.com/archives/000664.html
  36. SHA-1 Broken - Schneier on Security www.schneier.com. Visitado em 2015-08-09.
  37. Manuel, Stéphane. In: Kaisa. Collisions on SHA-0 in One Hour. [S.l.]: Springer Berlin Heidelberg, 2008-01-01. p. 16-35. ISBN 978-3-540-71038-7
  38. http://www.faqs.org/rfcs/rfc3174.html
  39. http://2012.sharcs.org/slides/stevens.pdf

Referências[editar | editar código-fonte]

  • Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp56–71 (em inglês)
  • Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (appeared on CRYPTO 2004), IACR.org (em inglês)
  • Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0, CRYPTO 2005, CMU.edu (em inglês)
  • Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full SHA-1, Crypto 2005 MIT.edu (em inglês)
  • http://www.unixwiz.net/techtips/iguide-crypto-hashes.html (em inglês)
  • "Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard"Federal Register 59 (131): 35317–35318. 1994-07-11. Retrieved 2007-04-26. (em inglês)
  • A. Cilardo, L. Esposito, A. Veniero, A. Mazzeo, V. Beltran, E. Ayugadé, A CellBE-based HPC application for the analysis of vulnerabilities in cryptographic hash functions, High Performance Computing and Communication international conference, August 2010. (em inglês)

Links externos[editar | editar código-fonte]