# SHA-1

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 Federal de Processamento de Informação dos Estados Unidos publicado pelo Instituto Nacional de Padrões e Tecnologia (NIST). Em dezembro de 2022 o NIST passou a recomendar a substituição da função SHA-1 por algoritmos mais novos e seguros, como SHA-2 e SHA-3, e que SHA-1 deixe de ser usado até 31 de dezembro de 2030.
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. O NIST exigiu que várias aplicações utilizadas em agências federais mudassem para SHA-2 depois de 2010 devido à fraqueza descoberta. 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. 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. Mozilla também pretende parar de aceitar certificados baseados em SSL até 2017.
Em 23 de fevereiro de 2017, o grupo CWI Amsterdam e a Google anunciaram um ataque prático de colisão contra o SHA-1. Como prova de conceito, foram distribuídos dois diferentes arquivos PDF que produzem o mesmo hash SHA-1.

## A função de dispersão SHA-1

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. $^[$

## Aplicações
### Criptografia

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.
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), apesar de que mais tarde isso foi relaxado.
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

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". 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

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 2$^L$ 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* 2$^{L/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 2$^{80}$.
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.
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. 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 0$^b$, bloco zero, é igual ao tamanho do bloco da função de dispersão.

### Ataques

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 2$^{80}$ operações.
Em fevereiro de 2005, um ataque feito por Xiaoyum Wang, Yiqun Lisa Yin e Hongbo Yu foi anunciado. Os ataques podem achar colisões na versão completa de SHA-1, precisando de menos que 2$^{69}$ operações (Uma busca por força bruta precisaria de 2$^{80}$ 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". Os autores apresentaram uma colisão para SHA-1 de 58 rodadas, encontrada com 2$^{33}$ 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."
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 2$^{63}$. Em 28 de Dezembro de 2007, detalhes desse resultado foram explicados e verificados por Martin Cochran.
Christophe De Cannière and Christian Rechberger melhoraram mais ainda o ataque sobre SHA-1 em "Finding SHA-1 Characteristics: General Results and Applications", 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 2$^{35}$ avaliações de função de compressão. Uma vez que esse ataque precisa do equivalente a 2$^{35}$ avaliações, é considerado uma quebra teórica significativa. Seu ataque foi estendido para 73 rodadas (de 80) em 2010 por Grechinov. 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.
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.
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 2$^{51}$ até 2$^{57}$ operações. 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.
Cameron McDonald, Philip Hawkes e Josef Pieprzyk apresentaram um ataque de colisão de valores de dispersão com complexidade 2$^{52}$ na Rump Session da Eutocrypt 2009. No entanto, o artigo acompanhante, "Diferential Path for SHA-1 with complexity O(2$^{52}$)" (Caminho Diferencial para SHA-1 com complexidade O(2$^{52}$)) foi retirado devido a uma descoberta feita pelo autor de que suas estimativas estavam incorretas.
Até 2012, o ataque mais eficiente contra SHA-1 é considerado o de Marc Stevens, com um custo estimado de $2.77M para quebrar um único valor de dispersão, alugando força de CPU de servidores na nuvem. Stevens desenvolveu esse ataque em um projeto chamado HashClash, 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 2$^{57.5}$ compressões SHA-1. Ele estima que esse ataque pode ser estendido para uma colisão completa com complexidade em torno de 2$^{61}$.

### SHA-0

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 2$^{61}$ 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 2$^{51}$ 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 é 2$^{40}$, significantemente melhor que o ataque de Joux et al.
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 2$^{39}$ operações.
Outro ataque em 2008, aplicando-se o ataque do bumerangue, baixava a complexidade de se encontrar colisões para 2$^{33.6}$, que se estima levar uma hora em um computador mediano.
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

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
### Hashes exemplo

Estes são exemplos de resumos de mensagens SHA-1 em hexadecimal e em binário Base64 para a codificação de texto ASCII.
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.
O hash da palavra de tamanho zero é:

### Pseudocódigo SHA-1

Segue o pseudocódigo para o algoritmo SHA-1:
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 2$^{30}$ 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:
Max Locktyukhin também mostrou que para as rodadas 32–79 a computação de:
pode ser substituída com:
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

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 | 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) | MD5 (como referencia) | 128 | 128 (4 × 32) | 512 | 2$^{64}$ − 1 | 64 | And, Xor, Rot, Add (mod 2$^{32}$), Or | <64 (colisões encontradas) | 335 |
| SHA-0 | SHA-0 | 160 | 160 (5 × 32) | 512 | 2$^{64}$ − 1 | 80 | And, Xor, Rot, Add (mod 2$^{32}$), Or | <80 (colisões encontradas) | - |
| SHA-1 | SHA-1 | 160 | 160 (5 × 32) | 512 | 2$^{64}$ − 1 | 80 | And, Xor, Rot, Add (mod 2$^{32}$), Or | <80 (ataque teórico em 2$^{61}$ operações) | 192 |
| SHA-2 | SHA-224 SHA-256 | 224 256 | 256 (8 × 32) | 512 | 2$^{64}$ − 1 | 64 | And, Xor, Rot, Add (mod 2$^{32}$), Or, Shr | 112 128 | 139 |
| SHA-2 | SHA-384 SHA-512 SHA-512/224 SHA-512/256 | 384 512 224 256 | 512 (8 × 64) | 1024 | 2$^{128}$ − 1 | 80 | And, Xor, Rot, Add (mod 2$^{64}$), 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 | - |
| SHA-3 | SHAKE128 SHAKE256 | d (arbitrario) d (arbitrario) | 1600 (5 × 5 × 64) | 1344 1088 | Ilimitado | 24 | And, Xor, Rot, Not | min (d/2, 128) min (d/2, 256) | - |