Mostrar código-fonte de SHA-1

{{mais notas|data=março de 2016}}
{{Info
| tópico1          = Geral
| rótulo1          = '''Projetistas'''
| dados1           = [[Agência de Segurança Nacional]]
| rótulo2          = '''Primeira publicação'''
| dados2           = 1993 (SHA-0), 1995 (SHA-1)
| rótulo3          = '''Séries'''
| dados3           = ([[SHA-0]]), SHA-1, [[SHA-2]], [[SHA-3]]
| rótulo4          = '''Certificação'''
| dados4           = [[Federal Information Processing Standard|FIPS]] PUB 180-4, [[CRYPTREC]] (Monitorado)
| tópico5          = Detalhes
| rótulo5          = '''Tamanho do resumo'''
| dados5           = 160 bits
| rótulo6          = '''Estrutura'''
| dados6           = [[Construção Merkle–Damgård]]
| rótulo7          = '''Rodadas'''
| dados7           = 80
| tópico8          = Melhor criptoanálise pública
| dados8-estilo    = text-align:left;
| dados8           = 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.<ref name=google2017 />
}}

Em [[criptografia]], '''SHA-1''' é uma [[função hash criptográfica|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 [[Federal Information Processing Standard|Padrão Federal de Processamento de Informação]] dos Estados Unidos publicado pelo [[National Institute of Standards and Technology|Instituto Nacional de Padrões e Tecnologia]] (NIST).<ref>http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf</ref> 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.<ref name="sha1_obsoleto_thn">{{citar web|url=https://thehackernews.com/2022/12/goodbye-sha-1-nist-retires-27-year-old.html|título=Goodbye SHA-1: NIST Retires 27-Year-Old Widely Used Cryptographic Algorithm|publicado=The Hacker News|data=2022-12-16|arquivourl=https://web.archive.org/web/20221216082739/https://thehackernews.com/2022/12/goodbye-sha-1-nist-retires-27-year-old.html|arquivodata=2022-12-16}}</ref><ref name="sha1_obsoleto_nist">{{citar web|url=https://www.nist.gov/news-events/news/2022/12/nist-retires-sha-1-cryptographic-algorithm|título=NIST Retires SHA-1 Cryptographic Algorithm|publicado=NIST|data=2022-12-15|arquivourl=https://web.archive.org/web/20221216085439/https://www.nist.gov/news-events/news/2022/12/nist-retires-sha-1-cryptographic-algorithm|arquivodata=2022-12-16}}</ref>

SHA-1 produz um valor de dispersão de 160 [[bit]]s (20 [[byte]]s) 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 hash seguro|algoritmo de dispersão seguro]]" (''secure hash algorithm'' em inglês). Os quatro [[algoritmo]]s 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.<ref>{{Citar web|título = Cryptanalysis of SHA-1 - Schneier on Security|url= https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html|obra = www.schneier.com|acessadoem = 2015-08-09}}</ref> O NIST exigiu que várias aplicações utilizadas em agências federais mudassem para SHA-2 depois de 2010 devido à fraqueza descoberta.<ref>{{Citar web|título = NIST.gov - Computer Security Division - Computer Security Resource Center|url= http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html|obra = csrc.nist.gov|acessadoem = 2015-08-09|arquivourl = https://web.archive.org/web/20110625054822/http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html|arquivodata = 2011-06-25|urlmorta = yes}}</ref> 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''.<ref>{{Citar web|título = NIST Hash Workshop Liveblogging (5) - Schneier on Security|url= http://www.schneier.com/blog/archives/2005/11/nist_hash_works_4.html|obra = www.schneier.com|acessadoem = 2015-08-09}}</ref> 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.<ref>{{Citar web|título = SHA1 Deprecation Policy - Windows PKI blog - Site Home - TechNet Blogs|url= http://blogs.technet.com/b/pki/archive/2013/11/12/sha1-deprecation-policy.aspx|obra = blogs.technet.com|acessadoem = 2015-08-09|arquivourl = https://web.archive.org/web/20131113032317/http://blogs.technet.com/b/pki/archive/2013/11/12/sha1-deprecation-policy.aspx|arquivodata = 2013-11-13|urlmorta = yes}}</ref> [[Mozilla]] também pretende parar de aceitar certificados baseados em SSL até 2017.<ref>{{Citar web|título = 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|url= https://bugzilla.mozilla.org/show_bug.cgi?id=942515|obra = bugzilla.mozilla.org|acessadoem = 2015-08-09}}</ref><ref>{{Citar web|título = CA:Problematic Practices - MozillaWiki|url= https://wiki.mozilla.org/CA:Problematic_Practices#SHA-1_Certificates|obra = wiki.mozilla.org|acessadoem = 2015-08-09}}</ref><ref>{{Citar web|título = Phasing Out Certificates with SHA-1 based Signature Algorithms|url= https://blog.mozilla.org/security/2014/09/23/phasing-out-certificates-with-sha-1-based-signature-algorithms/|obra = Mozilla Security Blog|acessadoem = 2015-08-09}}</ref>

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.<ref name=google2017>{{Citar web|url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html|titulo=Announcing the first SHA1 collision|data=23 de fevereiro de 2017|acessodata=|website=Google Online Security Blog|último =|primeiro =|arquivourl=|arquivodata=|urlmorta=}}</ref> Como prova de conceito, foram distribuídos dois diferentes arquivos PDF que produzem o mesmo hash SHA-1.<ref>{{citar web|url=https://shattered.io/ | titulo=SHAttered |acessodata=23 de fevereiro de 2017}}</ref>

== A função de dispersão SHA-1 ==
SHA-1 produz um resumo da mensagem baseado em princípios similares aos utilizados por [[Ronald Rivest|Ronald L. Rivest]], do [[Instituto de Tecnologia de Massachusetts|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 [[Agência de Segurança Nacional|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|data=junho de 2017}}

== Aplicações ==
[[Ficheiro:SHA-1.svg|thumb|266x266px|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; [[Ficheiro:Lll.png|frameless]]<math>_n</math> denota a rotação de bits à esquerda em ''n'' espaços; ''n'' varia para cada operação; W<sub>t</sub> é a palavra da mensagem expandida da rodada t; K<sub>t</sub> é a constante da rodada t; [[Ficheiro:Boxplus.png|frameless]] denota uma adição módulo 2<sup>32</sup>.]]

=== Criptografia ===
{{details|Funções Hash Criptográficas#Aplicações}}
SHA-1 faz parte de várias aplicações e protocolos de segurança amplamente utilizados, incluindo [[Transport Layer Security|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 [[Sistema de controle de versão|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.<ref>{{Citar web|título = debugmo.de :: Thank you, Datel.|url= http://debugmo.de/2008/03/thank-you-datel/|obra = debugmo.de|acessadoem = 2015-08-09}}</ref>

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),<ref>{{Citar web|título = NIST.gov - Computer Security Division - Computer Security Resource Center|url= http://csrc.nist.gov/groups/ST/hash/policy_2006.html|obra = csrc.nist.gov|acessadoem = 2015-08-09|arquivourl = https://web.archive.org/web/20140102194145/http://csrc.nist.gov/groups/ST/hash/policy_2006.html|arquivodata = 2014-01-02|urlmorta = yes}}</ref> apesar de que mais tarde isso foi relaxado.<ref>{{Citar web|título = NIST.gov - Computer Security Division - Computer Security Resource Center|url= http://csrc.nist.gov/groups/ST/hash/policy.html|obra = csrc.nist.gov|acessadoem = 2015-08-09|arquivourl = https://web.archive.org/web/20110609064344/http://csrc.nist.gov/groups/ST/hash/policy.html|arquivodata = 2011-06-09|urlmorta = yes}}</ref>

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

As funções de dispersão SHA têm sido utilizadas como base para as [[SHACAL|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 [[Unidade de disco rígido|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 [[Ataque da preimagem|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 [[Árvores de Merkle|Á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<sup>''L''</sup> 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<sup>''L/2''</sup> 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<sup>80</sup>.

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.<ref>{{Citar web|título = MD5 considered harmful today|url= http://www.win.tue.nl/hashclash/rogue-ca/|obra = www.win.tue.nl|acessadoem = 2015-08-09}}</ref>

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.<ref>{{citar web|url= http://www.schneier.com/book-ce.html|título = Learn to build cryptographic protocols that work in the real world|data = |acessadoem = |autor = |publicado = }}</ref> Esses ataques permitem que um atacante forje uma mensagem assinada apenas por um valor de dispersão chaveado - <math>SHA(mensagem||chave)</math> ou <math>SHA(chave||mensagem)</math> - 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: <math>SHA_d(mensagem) = SHA(SHA(0^b||mensagem))</math> (o tamanho de 0<sup>b</sup>, bloco zero, é igual ao tamanho do bloco da função de dispersão.

=== Ataques ===
Logo no início de 2005, [[Vincent Rijmen|Rijmen]] e [[Elisabeth Oswald|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<sup>80</sup> operações.<ref>{{Citar periódico|titulo = Update  on  SHA-1|url = http://eprint.iacr.org/2005/010|data = 2005-01-01|primeiro = Vincent|ultimo = Rijmen|autor2 = Elisabeth}}</ref>

Em fevereiro de 2005, um ataque feito por [[Xiaoyum Wang]], [[Yiqun Lisa Yin]] e [[Hongbo Yu]] foi anunciado.<ref name="schneier.com">{{Citar web|título = SHA-1 Broken - Schneier on Security|url= http://www.schneier.com/blog/archives/2005/02/sha1_broken.html|obra = www.schneier.com|acessadoem = 2015-08-09}}</ref> Os ataques podem achar colisões na versão completa de SHA-1, precisando de menos que 2<sup>69</sup> operações (Uma [[busca por força bruta]] precisaria de 2<sup>80</sup> 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".<ref>{{Citar periódico|titulo = Massachusetts Institute of Technology|url = https://en.wikipedia.org/w/index.php?title=Massachusetts_Institute_of_Technology&oldid=675033387|idioma = en}}</ref> Os autores apresentaram uma colisão para SHA-1 de 58 rodadas, encontrada com 2<sup>33</sup> 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."<ref>{{Citar web|título = Fixing a hole in security {{!}} ZDNet|url= http://www.zdnet.com/news/fixing-a-hole-in-security/141588|obra = ZDNet|acessadoem = 2015-08-09}}</ref>

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<sup>63</sup>.<ref>{{Citar web|título = New Cryptanalytic Results Against SHA-1 - Schneier on Security|url= http://www.schneier.com/blog/archives/2005/08/new_cryptanalyt.html|obra = www.schneier.com|acessadoem = 2015-08-09}}</ref> Em 28 de Dezembro de 2007, detalhes desse resultado foram explicados e verificados por Martin Cochran.<ref>{{Citar periódico|titulo = Notes  on  the  Wang  et  al. $2^{63}$  SHA-1  Differential  Path|url = http://eprint.iacr.org/2007/474|data = 2007-01-01|primeiro = Martin|ultimo = Cochran}}</ref>

Christophe De Cannière and Christian Rechberger melhoraram mais ainda o ataque sobre SHA-1 em "Finding SHA-1 Characteristics: General Results and Applications",<ref>{{Citar livro|título = Finding SHA-1 Characteristics: General Results and Applications|url = http://link.springer.com/chapter/10.1007/11935230_1|editora = Springer Berlin Heidelberg|data=2006-01-01|isbn = 978-3-540-49475-1|página = 1-20|nome = Christophe De|sobrenome = Cannière|nome2 = Christian|sobrenome2 = Rechberger|editor = Xuejia}}</ref> 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<sup>35</sup> avaliações de função de compressão. Uma vez que esse ataque precisa do equivalente a 2<sup>35</sup> avaliações, é considerado uma quebra teórica significativa.<ref>{{Citar web|título = IAIK - TU Graz :: SHA-1 Collision Search|url= http://www.iaik.tugraz.at/content/research/krypto/sha1/SHA1Collision_Description.php|obra = www.iaik.tugraz.at|acessadoem = 2015-08-09}}</ref> Seu ataque foi estendido para 73 rodadas (de 80) em 2010 por Grechinov.<ref>{{Citar periódico|titulo = Collisions  for 72-step   and 73-step  SHA-1:  Improvements  in  the  Method  of  Characteristics|url = http://eprint.iacr.org/2010/413|data = 2010-01-01}}</ref> 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.<ref>{{citar web|url=http://boinc.iaik.tugraz.at/sha1_coll_search/|título =|acessadoem =|autor =|publicado ={{ligação inativa|data=junho de 2017}}|arquivourl =https://web.archive.org/web/20090225115007/http://boinc.iaik.tugraz.at/sha1_coll_search/|arquivodata =25 de fevereiro de 2009|urlmorta =yes}}</ref>

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.<ref>{{Citar web|título = IT-News, c't, iX, Technology Review, Telepolis|url= http://www.heise-online.co.uk/security/SHA-1-hash-function-under-pressure--/news/77244|obra = heise online|acessadoem = 2015-08-09}}</ref><ref>{{Citar web|título = Crypto 2006 Rump Schedule|url= http://www.iacr.org/conferences/crypto2006/rumpsched.html|obra = www.iacr.org|acessadoem = 2015-08-09}}</ref>

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<sup>51</sup> até 2<sup>57</sup> operações.<ref><nowiki>http://eprint.iacr.org/2008/469.pdf</nowiki></ref> 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.<ref>{{Citar periódico|titulo = Classification and generation of disturbance vectors for collision attacks against SHA-1|url = http://link.springer.com/article/10.1007/s10623-010-9458-9|jornal = Designs, Codes and Cryptography|data = 2011-01-05|issn = 0925-1022|paginas = 247-263|volume = 59|numero = 1-3|doi = 10.1007/s10623-010-9458-9|idioma = en|primeiro = Stéphane|ultimo = Manuel}}</ref>

Cameron McDonald, Philip Hawkes e Josef Pieprzyk apresentaram um ataque de colisão de valores de dispersão com complexidade 2<sup>52</sup> na ''Rump Session'' da Eutocrypt 2009.<ref><nowiki>http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf</nowiki></ref> No entanto, o artigo acompanhante, "Diferential Path for SHA-1 with complexity O(2<sup>52</sup>)" (Caminho Diferencial para SHA-1 com complexidade O(2<sup>52</sup>)) foi retirado devido a uma descoberta feita pelo autor de que suas estimativas estavam incorretas.<ref>{{Citar periódico|titulo = Differential  Path  for  SHA-1  with  complexity $O(2^{52})$|url = http://eprint.iacr.org/2009/259|data = 2009-01-01|primeiro = Cameron|ultimo = McDonald|autor2 = Philip}}</ref>

Até 2012, o ataque mais eficiente contra SHA-1 é considerado o de Marc Stevens<ref><nowiki>http://2012.sharcs.org/slides/stevens.pdf</nowiki></ref>, com um custo estimado de $2.77M para quebrar um único valor de dispersão, alugando força de CPU de servidores na nuvem.<ref>{{Citar web|título = When Will We See Collisions for SHA-1? - Schneier on Security|url= http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html|obra = www.schneier.com|acessadoem = 2015-08-09}}</ref> Stevens desenvolveu esse ataque em um projeto chamado HashClash,<ref>{{Citar web|título = Google Project Hosting|url= http://code.google.com/p/hashclash/|obra = code.google.com|acessadoem = 2015-08-09}}</ref> 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<sup>57.5</sup> compressões SHA-1. Ele estima que esse ataque pode ser estendido para uma colisão completa com complexidade em torno de 2<sup>61</sup>.

=== SHA-0 ===
Na CRYPTO 98, dois pesquisadores franceses, [[Florent Chanbaud]] e [[Antonie Joux]], apresentaram um ataque sobre SHA-0 ([http://fchabaud.free.fr/English/Publications/sha.pdf Chabaud and Joux, 1998]): colisões podem ser encontradas com complexidade de 2<sup>61</sup> 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<sup>51</sup> 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<sup>40</sup>, significantemente melhor que o ataque de Joux ''et al''.<ref><nowiki>http://www.freedom-to-tinker.com/archives/000664.html {{Wayback|url=http://www.freedom-to-tinker.com/archives/000664.html |date=20040821031401 }}</nowiki></ref>

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<sup>39</sup> operações.<ref name="schneier.com"/>

Outro ataque em 2008, aplicando-se o [[ataque do bumerangue]], baixava a complexidade de se encontrar colisões para 2<sup>33.6</sup>, que se estima levar uma hora em um computador mediano.<ref>{{Citar livro|título = Collisions on SHA-0 in One Hour|url = http://link.springer.com/chapter/10.1007/978-3-540-71039-4_2|editora = Springer Berlin Heidelberg|data=2008-01-01|isbn = 978-3-540-71038-7|página = 16-35|nome = Stéphane|sobrenome = Manuel|nome2 = Thomas|sobrenome2 = Peyrin|editor = Kaisa}}</ref>

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 ===
{{detalhes | 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 ([http://csrc.nist.gov/groups/STM/cavp/documents/shs/shaval.htm 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]].

 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 (criptografia)|efeito avalanche]]. Por exemplo, mudar <code>dog</code> to <code>cog</code> produz um hash com valores diferentes para 81 dos 160 bits.

 SHA1("The quick brown fox jumps over the lazy cog")
 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===
Segue o [[pseudocódigo]] para o algoritmo SHA-1:

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

 <span style="color: green;">''Inicializar variáveis:''</span>

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

 <span style="color: green;">''Pré-processando:''</span>
 anexar o bit '1' na mensagem i.e. adicionando 0x80 se os caracteres forem 8 bits.
 anexar 0 ≤ k &lt; 512 bits '0', daí o tamanho resultante da mensagem (em ''bits'')
    será [[modular arithmetic|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.

 <span style="color: green;">''Processar a mensagem em pedaços sucessivos de 512 bits:''</span>
 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

     <span style="color: green;">''Estender as dezesseis palavras de 32 bits em oitenta palavras de 32 bits:''</span>
     '''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

     <span style="color: green;">''Inicializa o valor hash para esse pedaço:''</span>
     a = h0
     b = h1
     c = h2
     d = h3
     e = h4

     Laço principal<span style="color: green;">'':''</span><ref>http://www.faqs.org/rfcs/rfc3174.html</ref>
     '''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

     <span style="color: green;">''Adicionar este hash do pedaço ao resultado obtido até agora:''</span>
     h0 = h0 + a
     h1 = h1 + b
     h2 = h2 + c
     h3 = h3 + d
     h4 = h4 + e

 <span style="color:green;">''Produzir o valor final do hash (big-endian) como um número de 160 bits:''</span>
 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 <code>k</code> são 2<sup>30</sup> as raízes quadradas de 2,3, 5 e 10. Os primeiros números iniciais <code>de h0</code> até <code>h3</code> são os mesmos do algoritmo MD5, e o quinto (para <code>h4</code>) é similar.

Em vez da formulação do FIPS PUB 180-1 original mostrada, as seguintes expressões equivalentes podem ser utilizadas para computar <code>f</code>  no laço principal acima:
 (0  ≤ i ≤ 19): f = d '''xor''' (b '''e''' (c '''xor''' d))                  <span style="color: green;">''(alternativa 1)''</span>
 (0  ≤ i ≤ 19): f = (b '''e''' c) '''xor''' (('''não''' b) '''e''' d)              <span style="color: green;">''(alternativa 2)''</span>
 (0  ≤ i ≤ 19): f = (b '''e''' c) + (('''não''' b) '''e''' d)                <span style="color: green;">''(alternativa 3)''</span>
 (0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       <span style="color: green;">''(alternativa 4)''</span>
  
 (40 ≤ i ≤ 59): f = (b '''e''' c) '''ou''' (d '''e''' (b '''ou''' c))              <span style="color: green;">''(alternativa 1)''</span>
 (40 ≤ i ≤ 59): f = (b '''e''' c) '''ou''' (d '''e''' (b '''xor''' c))             <span style="color: green;">''(alternativa 2)''</span>
 (40 ≤ i ≤ 59): f = (b '''e''' c) + (d '''e''' (b '''xor''' c))              <span style="color: green;">''(alternativa 3)''</span>
 (40 ≤ i ≤ 59): f = (b '''e''' c) '''xor''' (b '''e''' d) '''xor''' (c '''e''' d)        <span style="color: green;">''(alternativa 4)''</span>
 (40 ≤ i ≤ 59): f = vec_sel(c, b, c '''xor''' d)                 <span style="color: green;">''(alternativa 5)''</span>

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 <code>w[i]</code> em <code>w[i-3]</code>, permite a implementação eficiente de [[SIMD]] com um vetor de tamanho 4 como instruções [[X86|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}}

== Ver também ==
* [[MD5]]
* [[OpenSSL]]

{{Referências}}

== Bibliografia ==
* 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), [http://eprint.iacr.org/2004/146/ IACR.org]  (em inglês)
* Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0, CRYPTO 2005, [https://web.archive.org/web/20080725020713/http://www.cs.cmu.edu/~dbrumley/srg/spring06/sha-0.pdf CMU.edu]  (em inglês)
* Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full SHA-1, Crypto 2005 [http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf MIT.edu]  (em inglês)
* http://www.unixwiz.net/techtips/iguide-crypto-hashes.html  (em inglês)
* [http://frwebgate1.access.gpo.gov/cgi-bin/waisgate.cgi?WAISdocID=5963452267+0+0+0&WAISaction=retrieve "Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard"]{{Ligação inativa|1=data=julho de 2018 }}. ''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)

== Ligações externas ==
* [https://web.archive.org/web/20070113064108/http://csrc.nist.gov/CryptoToolkit/tkhash.html CSRC Cryptographic Toolkit] – Site oficial do [[National Institute of Standards and Technology|NIST]] para os Padrões de Hashes Seguros (em inglês)
* [http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf FIPS 180-4: Secure Hash Standard (SHS)] ([[Portable Document Format|PDF]], 1.7 MB) – Versão atual do Padrão de Hash Seguro (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), March 2012 (em inglês)
* RFC 3174 (com amostra de implementação em C) (em inglês)
* [http://www.zdnet.com/news/fixing-a-hole-in-security/141588 Entrevista com Yiqun Lisa Yin falando do ataque sobre SHA-1] (em inglês)
* [http://www.heise-online.co.uk/security/Hash-cracked--/features/75686 Explicação de ataques bem sucedidos sobre SHA-1] (3 pages, 2006) (em inglês)
* [http://www.cryptography.com/cnews/hash.html Pesquisa de Criptografia – Colisão Hash Q&amp;A] (em inglês)
* [http://www.OnlineHashcrack.com Online crack sobre Hash SHA1  usando Rainbow tables] (em inglês)
* [https://web.archive.org/web/20181103112717/http://hashproject.eu/ Hash Site do Projeto: Criptoanálise de SHA-1 baseada em software and hardware] (em inglês)
{{Hashes Criptográficos}}{{Criptografia}}

[[Categoria:Algoritmos de criptografia]]
[[Categoria:Criptografia]]