Um arquivo pode ser alterado maliciosamente de maneira a manter seu Hash SHA-1 original?

33

De acordo com este artigo e muitos outros, o SHA-1 não é seguro.

No meu caso, não estou preocupado com senhas ou certificados digitais. Estou preocupado com a integridade do arquivo.

É razoavelmente possível que um arquivo (por exemplo, uma imagem ISO ou arquivo executável) seja alterado maliciosamente de uma maneira que:

  • Mantém o hash SHA-1 do arquivo original e
  • Mantém o conteúdo geral e a operação do arquivo (mas é claro que agora inclui conteúdo malicioso que não existia originalmente)

Do meu ponto de vista, alterar um arquivo de maneira a gerar uma colisão SHA-1 tornaria o arquivo totalmente inútil. O ISO ficaria totalmente corrompido ou o arquivo executável seria tão completamente embaralhado que nem seria mais um arquivo executável.

Mas, do jeito que eu vejo, pode estar errado. Até agora, não encontrei nada nas pesquisas do Google com relação à adequação contínua do SHA-1 para verificação de arquivos. Alguma ideia?

misha256
fonte
7
A resposta é "depende". Se o ISO continha muitos jpegs ou arquivos de filme - junto com o executável de destino, é possível. Você pode modificar bastante os arquivos JPEG, sem alterar o tamanho ou a aparência visual. Por fim, quanto maior o arquivo, mais você precisa brincar e maior a chance de uma colisão não destrutiva.
Paul
7
@cpast exatamente, muitos sites listam hashes SHA-1 para permitir que você verifique seu download. Pensando nisso, parece muito mais provável que um hacker comprometa um site alterando o conteúdo e o hash publicado. Então você está realmente ferrado.
misha256
1
Apenas para minha informação, minha pergunta é sobre o SHA-1 especificamente porque é bastante comum, especialmente com downloads do Microsoft / MSDN. É claro que alguns sites publicam hashes MD5, outros SHA256, etc.
misha256
2
A questão é, por que você quer usar um hash que tem quaisquer vulnerabilidades conhecidas, quando existem alternativas que são tão rápido, fácil de usar, e amplamente disponível que não o fazem (por exemplo. SHA-256) ? Além disso, há um motivo pelo qual os criptografadores declaram um hash inseguro depois que apenas uma vulnerabilidade é encontrada: o histórico mostrou que, quando um é encontrado, outros seguem rapidamente. A famosa citação de Bruce Schneier é "Os ataques sempre melhoram, nunca pioram"
BlueRaja - Danny Pflughoeft 16/15
3
@ misha256 Esses hashes sha1 são para você verificar a corrupção do download, não a segurança. Se você quer segurança, em seguida, usar gpg assinado arquivos
Daenyth

Respostas:

41

Ainda ninguém conseguiu isso com o SHA-1. É possível em teoria, mas ainda não é prático. Os relatórios sobre insegurança no SHA-1 apenas significam que o nível de segurança não é tão alto quanto gostaríamos e isso significa que não temos tantos anos antes que precisamos nos preocupar com isso como pensávamos.

É mais difícil produzir um arquivo com o mesmo hash SHA-1 que um arquivo específico do que criar dois arquivos com o mesmo hash SHA-1. E, tanto quanto sabemos, ninguém em nenhum lugar do mundo realizou ainda essa tarefa mais fácil. Isso não significa que não pode acontecer amanhã.

David Schwartz
fonte
Existe mesmo um ataque conhecido ao SHA-1 por colisões com um determinado arquivo? Fiquei com a impressão de que esse ataque não foi encontrado para tanto MD5 ou SHA-1 (há apenas um ataque de colisão, não uma segunda-preimage ataque)
cpast
@cpast, o malware Flame usou uma colisão MD5 para parecer ser da Microsoft e seqüestrar o Windows Update. Eles poderiam ter um monte de certificados da Microsoft para escolher, mas não estavam apenas tentando encontrar dois arquivos com o mesmo MD5.
Aron Foster
2
@ Aron Não, isso não foi um exemplo de colisão com um determinado arquivo. Com o Flame, a Microsoft tinha um servidor de licenciamento que assinaria certificados X.509 de acordo com uma solicitação de assinatura de certificado, o que significa que o invasor controla o que está sendo assinado dentro de alguns limites. Não havia um certificado preexistente com o qual eles encontraram uma colisão; A Microsoft assinou CSRs de clientes como parte da ativação, o que permite o uso de um ataque de colisão (que não é um ataque de segunda pré-imagem).
cpast
2
@OlivierDulac Não, de fato nunca foi feito. Não há colisões SHA-1 conhecidas. O custo estimado é apenas uma estimativa - não é que alguém fez isso e isso é o quanto nós pensamos que custo, é que ninguém tenha feito isso, mas nós pensamos que este é o quanto ela iria custar.
cpast
4
@cpast Não sabemos ao certo se foi feito ou não, mas um ataque de US $ 3 milhões é inferior a 0,03% do orçamento anual da NSA (na verdade, o ataque deve ser mais barato, pois eles já possuem o hardware e não o fazem tem que alugar). É razoável concluir que, como eles têm os meios e a motivação para fazê-lo, provavelmente já o fizeram. Lembre-se de Flame .
Bain
26

É teoricamente possível, mas ainda não foi feito.

O que você está procurando é chamado de "colisão de hash:" dois arquivos com o mesmo hash. Códigos de hash criptográficos como o SHA-1 geralmente são projetados para dificultar isso. Como o SHA-1 é um código de 160 bits, serão necessárias em média 2 ^ 159 tentativas de força bruta para encontrar uma duplicata. Se for encontrado um algoritmo que, com confiabilidade, é melhor do que aquele em relação a um hash criptográfico, o hash é considerado "quebrado".

MD-5 é um exemplo de um hash muito quebrado. Deveria ter uma força de 128 bits, exigindo em média 2 ^ 127 tentativas. Como é o abuso de vulnerabilidades conhecidas, o número real de tentativas necessárias pode ser tão baixo quanto 2 ^ 47. Isso é MUITO menor que 2 ^ 127. De fato, isso foi feito em menos de um dia em um cluster de computação moderno.

Dou esse exemplo porque é o mais próximo de como você deseja usar o SHA-1. No entanto, essa não é a abordagem mais comum usada pela análise criptográfica para garantir que os hashes não sejam quebrados. Eles geralmente permitem uma colisão entre dois arquivos, conforme escolhido pelo invasor, em vez de você escolher um arquivo e o invasor procurar correspondê-lo. Esse tipo de ataque tem a vantagem de ser mais fácil de comparar. Se eu achar que é "difícil" decifrar seu arquivo, isso significa que outro arquivo é igualmente forte? Esse ataque no qual o invasor escolhe os dois arquivos garante que capturamos o pior do pior.

Esse tipo de ataque permite um truque interessante conhecido como " ataque de aniversário ". Para encurtar a história, usar o ataque de aniversário reduz pela metade a força do algoritmo; portanto, o SHA-1 requer 2 ^ 80 tentativas (em média) e o MD5 requer 2 ^ 64 tentativas (em média). Estes são metade de 160 e 128, respectivamente.

O SHA-1 tem ataques conhecidos que diminuem sua força de 2 ^ 80 para 2 ^ 69. Isso não vai importar muito para você. 2 ^ 69 tentativas é muito tempo.

No entanto, a partir da história, descobrimos que os algoritmos de hash não são quebrados espontaneamente, mas com o tempo. Ninguém quebra um algoritmo como o MD-5, passando de 2 ^ 64 para 2 ^ 47 durante a noite. Isso acontece com o tempo, pois muitas pessoas publicam artigos sobre a matemática que estão usando contra ela. Geralmente, é possível observar a complexidade dos ataques diminuir lentamente desde o início do algoritmo (onde o melhor ataque geralmente é o ataque de aniversário).

O fato de estarmos vendo algumas mudanças nas colisões sugere que o SHA-1 está vendo a luz no fim do túnel. Ainda é forte, mas pode haver um desejo de ir até o mais novo SHA-3, que atualmente é muito mais seguro.

Você realmente deve tomar essas decisões da perspectiva do modelo de ameaça. Quanto dano pode ser causado por um invasor se ele sofrer uma dessas colisões. Seus atacantes fazem scripts de crianças com acesso a alguns laptops ou governos com clusters de supercomputação inteiros à sua disposição. Qual o tamanho de uma janela de tempo que um invasor precisa interromper o hash antes de ser inútil (muitos usos de criptografia envolvem uma "mudança de proteção", como rotação de senha). Tudo isso afetará a seriedade com que você deve considerar colisões.

Cort Ammon
fonte
8
Em relação ao parágrafo do ataque de aniversário, 2 ^ 80 é a raiz quadrada de 2 ^ 160, não a metade (que seria 2 ^ 159).
Andrew Morton
A pergunta é sobre ataques de segunda pré-imagem, mas sua resposta é sobre colisões. Ataques de pré-imagem contra SHA-1 & mdash; e até MD5 & mdash; são absurdamente impraticáveis. (Há um ataque preimage 2 ^ 123 contra MD5, mas com SHA-1 você está preso com a força bruta 2 ^ 160.)
Matt Nordhoff
"Como o SHA-1 é um código de 160 bits, serão necessárias em média 2 ^ 159 tentativas de força bruta para encontrar uma duplicata." Mas um código 2 ^ 2 leva 2 ^ 2 palpites. Não estou vendo por que você -1. "Resumindo," ... "reduz pela metade a força do algoritmo, então o SHA-1 requer 2 ^ 80" ... "MD5 requer 2 ^ 64" ... "Estes são metade de 160 e 128, respectivamente." Aqui você deveria ter -1'ed. Os bits aumentam exponencialmente a força; portanto, reduzir pela metade a força de um hash de 160 bits o trataria como um hash de 159 bits, e não um hash de 80 bits. Cada bit dobra o desafio de um ataque de força bruta.
TOOGAM 18/03/2015
@TOOGAM: Ele disse 'em média'; em várias tentativas, apenas 50% do espaço principal deve ser pesquisado em média para ter sucesso em um ataque de força bruta. Quanto ao comentário pela metade, o comentário de Andrew Morton acima explica isso; deve ser a raiz quadrada, não a metade, da complexidade.
Reid
@AndrewMorton bom ponto, eu não estava claro com a minha redação. Acho que a literatura alterna entre o número de estados e o logaritmo de base 2 do número de estados com bastante frequência. Minha redação se referia a reduzir pela metade o número de bits, porque as pessoas tendem a falar sobre "força" em número de bits. Eu estava tão acostumado a mudar de um lado para o outro que o fiz inconscientemente. Vou editar para remover a confusão.
Cort Ammon
8

As falhas do SHA-1 discutidas nesse artigo são muito específicas: elas permitem que os atacantes criem duas coisas com o mesmo valor (isso é chamado de "ataque de colisão"). No entanto, um ataque de colisão exige que o invasor controle os dois arquivos envolvidos. Se o invasor não controlar o arquivo original, um ataque de colisão não permitirá que ele encontre outro arquivo com o mesmo valor de hash.

O motivo disso para TLS / SSL (e assinaturas em geral) é que, com esses, um invasor geralmente pode controlar os dois arquivos. Um certificado TLS é criado principalmente pela pessoa que o solicita (os bits que eles não controlam costumam ser previsíveis); portanto, as colisões permitem que ele faça um certificado legítimo e um ilegítimo, obtenha o legítimo assinado e transfira a assinatura.

Para arquivos, a mesma situação nem sempre se aplica. Se sua preocupação é que a pessoa que cria o arquivo é o atacante (por exemplo, eles obtêm uma coisa independentemente verificada como boa e, em seguida, enviam a carga útil maligna com o mesmo hash), o ataque SHA-1 se aplica e você deve procurar no sentido de eliminá-lo (embora ainda não seja crítico, como David Schwartz mencionou). Se o arquivo original for confiável, um invasor não poderá aplicar os ataques SHA-1 atualmente conhecidos, embora você ainda deva pensar em eliminá-lo se puder (se tiver uma opção, use um hash sem ataques conhecidos como SHA- 2)


Em resposta a "a colisão não será útil" - Embora um ataque não exija que um invasor possa obter uma colisão útil , geralmente não é tão difícil transformar "colisão" em "colisão útil". Muitos formatos de arquivo têm uma quantidade razoável de espaço em que você pode ter o que quiser, sem afetar a funcionalidade do arquivo; um invasor normalmente pode modificá-lo para obter uma colisão (se as colisões forem praticamente localizáveis), mantendo a parte funcional como ela quer que seja. A diferença entre "ataque acadêmico" e "ataque prático" pode ser grande; a diferença entre "qualquer colisão" e "colisão útil" é geralmente muito menor.


O problema mais sério, que não tem relação com a escolha do algoritmo, é como você está obtendo o hash. Tudo o que um hash faz é mudar o problema de "obter o arquivo real" para "obter o valor real do hash"; um valor de hash enviado do mesmo servidor e pelo mesmo tipo de conexão que o arquivo é totalmente inútil contra modificações maliciosas (qualquer invasor que possa violar o arquivo pode violar o hash). Hashes são úteis apenas para isso se você puder confiar mais no hash do que no arquivo; embora às vezes seja o caso (torrents, espelhos), eles costumam ser usados ​​quando não é o caso. Portanto, você deve ter muito cuidado com isso sempre que usar hashes para verificação de integridade.

cpast
fonte
5

Você precisa diferenciar entre um ataque de colisão e um ataque de pré - imagem . Encontrar duas mensagens com o mesmo valor de hash é um ataque de colisão.
Substituir uma mensagem específica em particular (aqui: um executável) por outra mensagem com o mesmo hash é um (segundo) ataque de pré-imagem.

O SHA-1 é quebrado na medida em que um ataque de colisão pode ser feito em 2 52 operações, de acordo com um artigo da Wikipedia que não fornece uma citação para esse número (o melhor ataque que eu sei que é realmente credível é o de Marc Stevens , que leva 2 60 operações). Mas vamos assumir o caso pessimista de 2 52 .

Isso é preocupante porque um ataque nessa escala não é apenas teoricamente concebível, mas de fato perfeitamente possível em menos de um dia em um equipamento com várias GPUs. Obviamente, isso é um problema para aplicativos em que "qualquer duas" mensagens serão exibidas. Mesmo o número 2 60 dado por Stevens (que é 256 vezes mais trabalho) é perfeitamente viável se o atacante estiver disposto a gastar algum dinheiro extra com o problema ou se estiver disposto a passar um ano.
Que é exatamente o tipo de coisa que não impedirá que alguém envolvido em espionagem ou cibercrime forja certificados.

Agora, um ataque de pré-imagem tem um expoente duas vezes maior, assumindo 2 52 para o ataque de colisão, que seria 2 104 operações, o que é um estádio totalmente diferente.

Isso não é apenas impraticável (uma máquina que é um bilhão de vezes mais rápida do que a mencionada no parágrafo anterior ainda levaria cerca de 6 milhões ou mais anos), mas, dados nossos meios insignificantes de gerar energia, isso é totalmente impossível.

Fazer um cálculo tão grande exigiria uma fonte de energia muito maior do que qualquer coisa que possamos dedicar a uma única operação. Não, não é exatamente uma fonte de energia do tamanho do sol, mas ainda é muito grande .

Você pode realisticamente esperar obter algo entre 10 e 50 GFLOPS de um Watt. Supondo que algum tipo de milagre aconteça e os processadores consigam milhares de vezes mais eficiência energética durante a noite, pode-se assumir 1 SHA ≈ 1 FLOP (bastante otimista!). Isso significa que, para realizar 2 104 cálculos de hash em 10 anos, você precisa de uma usina de 10 12 W. Para executar o ataque dentro de 1 ano, você precisa de uma usina de 10 13 W. Isso é cerca de 50 vezes o que todas as usinas nucleares dos EUA, França e Japão podem produzir juntas, apenas para forjar um único hash.

Isso não vai acontecer , existem maneiras muito mais fáceis de atingir o mesmo objetivo (explorar o servidor que armazena o hash original e substituí-lo, chantagear alguém etc.).

Damon
fonte
"... maneiras muito mais fáceis de conseguir a mesma coisa ..." Como ilustrado em xkcd.com/538
Ralph J
2

O ponto geral do artigo mencionado na pergunta é: O SHA1 está obsoleto e deve ser eliminado gradualmente enquanto você ainda tem tempo para fazê-lo sem problemas. Em algumas áreas, o tempo está se esgotando desde que o Google e a Microsoft impõem prazos.

Regra geral para a tecnologia obsoleta :

  • Se você criar um novo design ou adicionar recursos, não o utilize (SHA1).
  • Se você mantiver algo antigo, planeje quando substituí-lo (SHA1).

Citação resumida da postagem de blog de Bruce Schneier em 2012: "O ponto é que nós, na comunidade, precisamos iniciar a migração para longe do SHA-1 e do SHA-2 / SHA-3 agora."

jmn
fonte
2

Para a parte de colisão de hash SHA-1 da sua pergunta, isso foi abordado por algumas das respostas.

No entanto, grande parte disso depende do tipo de arquivo com o qual estamos trabalhando:

Mantém o conteúdo geral e a operação do arquivo (mas é claro que agora inclui conteúdo malicioso que não existia originalmente no conteúdo alterado)

O que isso significa varia muito no que está detectando as alterações:

  • Se for um executável assinado, não há uma chance (razoável): você teria que obter duas colisões de hash de alguma forma: o SHA-1 do arquivo e a assinatura .exe interna.
  • Se for um executável não assinado. Operação.
  • Se for um arquivo de código-fonte ou estrutura semelhante (.cs, .c, .h, .cpp, .rb, .yml, .config, .xml, .pl, .bat, .ini) as adições, modificações ou remoções pode ser restrito a sintaxe de comentário válida, de modo que a alteração não seja discernível para a maioria dos usos (compilando ou executando, não abrindo com um editor de texto).
  • Se for um formato .iso ou .zip ou outro contêiner, também é mais improvável, pois a maioria das alterações aleatórias corromperão o contêiner. É possível: adicionar uma entrada de arquivo falsa ou alterar um conteúdo dentro do contêiner e verificar novamente, mas você está adicionando uma camada de complexidade e adicionando tempo adicional para verificar o resultado, além de ter graus de liberdade limitados com relação a como e quais conteúdos podem ser alterados.
  • Se for um texto ou formato semelhante a texto, eles podem ser alterados quase da maneira que você quiser enquanto ainda é um arquivo 'válido', embora o conteúdo provavelmente seja perceptível.
  • Com muitos formatos, como .rtf, .doc, .html, .xslx e outros formatos de marcação, eles podem ser adicionados ou modificados de maneiras que serão indetectáveis ​​pelos analisadores, além do comprimento (ou mesmo com um comprimento restrito) , menos liberdade) os arquivos podem ser alterados para (eventualmente) obter uma colisão de hash enquanto ainda não são apenas um arquivo válido, mas não são visivelmente alterados de qualquer maneira que seria visível para os aplicativos típicos com os quais eles seriam usados.

Então, o que resta é como obter colisões em qualquer estrutura que não seja corrompida e talvez com um certo grau de indetectável:

  1. Faça as alterações funcionais que desejar (talvez inserção de conteúdo malicioso) e faça outras alterações para manter a validade específica do formato do arquivo
  2. Adicione uma seção que não funcione (entre os blocos de comentários, no final de um arquivo de texto com 3k retornos de carro acima, isole um bloco de comentários atual)
  3. Adicione ou selecione um caractere / ponto de código / byte para modificação e tente todas as combinações válidas possíveis (nem toda combinação de bytes é válida para codificações diferentes, por exemplo).
  4. Recompute o hash, veja se a colisão corresponde.
  5. caso contrário, vá para 3.

Digamos que você tenha um computador super rápido e um arquivo pequeno, de modo que a modificação com uma sequência de bytes válida e a recálculo do hash leve 1 milissegundo (provavelmente exigindo algum hardware dedicado). Se a distribuição de hash for perfeitamente aleatória e distribuída por todo o intervalo, você terá uma colisão com o SHA-1 a cada 2^160tentativa (força bruta).

2^160/1000/60/60/24/365.24 
= 4.63x10^37 years 
= 46,300,000,000,000,000,000,000,000,000,000,000,000 years 
= 46 undecillion years.

Mas hey, vamos tentar os 2^60e 2^52versões, e fingir que eles nos permitem modificar o arquivo de qualquer maneira que nós gostamos (não) e que, também, pode ser feito em 1ms cada tentativa:

2^52 yields 142,714 years 
/*humans might still be around to care, but not about these antiquated formats*/
2^60 yields 3.65x10^7 years = 36,500,000 years 
/*machines will probably have taken over anyway*/

Mas ei, você pode ter sorte. Realmente, realmente, mais do que qualquer coisa que as pessoas chamam de milagres.

Ehryk
fonte
0

Na verdade, você pode satisfazer uma dessas condições por vez, mas não as duas .. é possível obter o mesmo hash para dois arquivos diferentes, mas alguém pode alterar um arquivo e tentar obter o mesmo hash é praticamente impossível, pois Pelo que sei

Anthony Guess
fonte
1
Praticamente impossível ainda . Com poder de computação suficiente, tudo é possível.
-6

Sim, é possível. Pense em como os vírus funcionam nos EXEs. A carga útil do malware é anexada ao EXE original, para que o programa ainda faça o que originalmente fez, mas também se espalhe como vírus. Agora, para manter o mesmo hash, você precisará de preenchimento adicional especificamente criado .

Isso significa que o arquivo seria maior. Porém, no caso de um EXE, talvez você possa remover parte do código menos utilizado, para que o programa pareça funcionar apenas inicialmente. No caso de um JPEG, você pode compactar ainda mais a imagem ou usar uma imagem completamente diferente. Para um ISO, você pode remover conjuntos de arquivos. Os cálculos necessários para replicar o hash seriam mais difíceis e talvez matematicamente impossíveis para casos específicos, mas ainda seriam possíveis em geral.

Ken
fonte
7
-1 tudo neste post é completamente inventado. Os ataques de extensão de comprimento não "mantêm o mesmo hash" (o hash apenas muda de uma maneira conhecida) . Além disso, não há razão para que um vírus tenha que remover "o código menos usado" (como isso determinaria o que é isso?) . E o que os jpegs têm a ver com alguma coisa !?
BlueRaja - Danny Pflughoeft
2
Este é apenas totalmente errado, eu não posso nem começar a sugerir correções sem reescrever toda a resposta
Mark K Cowan
2
-1 Não está certo. aka "Nem mesmo errado" (Wolfgang Pauli)
Olivier Dulac
1
Bem, poderíamos começar com o fato de que, se algo é possível em geral , obviamente é possível em um caso específico . O oposto nem sempre é verdadeiro: é fácil imaginar um problema que possa ser resolvido para um caso específico, mas geralmente não.
a CVn