Como o Git lidaria com uma colisão SHA-1 em um blob?

Isso provavelmente nunca aconteceu no mundo real ainda, e pode nunca acontecer, mas vamos considerar isso: digamos que você tenha um repository git, faça um commit e tenha muito azar: um dos blobs acaba tendo o mesmo SHA-1 como outro que já está no seu repository. A questão é como o Git lidaria com isso? Simplesmente falha? Encontrar uma maneira de vincular os dois blobs e verificar qual deles é necessário de acordo com o contexto?

Mais um quebra-cabeças do que um problema real, mas achei a questão interessante.

Eu fiz uma experiência para descobrir exatamente como o Git se comportaria nesse caso. Isto é com a versão 2.7.9 ~ rc0 + next.20151210 (versão Debian). Eu basicamente reduzi o tamanho do hash de 160 bits para 4 bits aplicando o seguinte git de comparação e reconstrução:

--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c +++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c @@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou blk_SHA1_Update(ctx, padlen, 8); /* Output hash */ - for (i = 0; i < 5; i++) - put_be32(hashout + i * 4, ctx->H[i]); + for (i = 0; i < 1; i++) + put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000)); + for (i = 1; i < 5; i++) + put_be32(hashout + i * 4, 0); } 

Então eu fiz alguns commits e notei o seguinte.

  1. Se um blob já existir com o mesmo hash, você não receberá nenhum aviso. Tudo parece estar ok, mas quando você clica, alguém clona, ​​ou você reverte, você perderá a última versão (de acordo com o que foi explicado acima).
  2. Se um object de tree já existir e você fizer um blob com o mesmo hash: Tudo parecerá normal, até você tentar empurrar ou alguém clonar seu repository. Então você verá que o repo está corrompido.
  3. Se um object de commit já existir e você fizer um blob com o mesmo hash: mesmo que # 2 - corrompido
  4. Se um blob já existir e você fizer um object commit com o mesmo hash, ele falhará ao atualizar o "ref".
  5. Se um blob já existir e você fizer um object de tree com o mesmo hash. Ele falhará ao criar o commit.
  6. Se um object de tree já existir e você fizer um object de confirmação com o mesmo hash, ele falhará ao atualizar o "ref".
  7. Se um object de tree já existir e você fizer um object de tree com o mesmo hash, tudo parecerá ok. Mas quando você confirmar, todo o repository fará referência à tree errada.
  8. Se um object commit já existir e você fizer um object commit com o mesmo hash, tudo parecerá ok. Mas quando você confirmar, o commit nunca será criado, e o ponteiro HEAD será movido para um commit antigo.
  9. Se um object de confirmação já existir e você fizer um object de tree com o mesmo hash, ele falhará ao criar a confirmação.

Para o número 2, você normalmente receberá um erro assim ao executar "git push":

 error: object 0400000000000000000000000000000000000000 is a tree, not a blob fatal: bad blob object error: failed to push some refs to origin 

ou:

 error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000) 

se você excluir o arquivo e, em seguida, execute "git checkout file.txt".

Para os números 4 e 6, você normalmente receberá um erro como este:

 error: Trying to write non-commit object f000000000000000000000000000000000000000 to branch refs/heads/master fatal: cannot update HEAD ref 

ao executar "git commit". Neste caso, você pode tipicamente digitar "git commit" novamente, pois isso criará um novo hash (por causa do timestamp alterado)

Para os números 5 e 9, você normalmente receberá um erro como este:

 fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object 

ao executar "git commit"

Se alguém tentar clonar seu repository corrupto, ele normalmente verá algo como:

 git clone (one repo with collided blob, d000000000000000000000000000000000000000 is commit, f000000000000000000000000000000000000000 is tree) Cloning into 'clonedversion'... done. error: unable to read sha1 file of s (d000000000000000000000000000000000000000) error: unable to read sha1 file of tullebukk (f000000000000000000000000000000000000000) fatal: unable to checkout working tree warning: Clone succeeded, but checkout failed. You can inspect what was checked out with 'git status' and retry the checkout with 'git checkout -f HEAD' 

O que "me preocupa" é que em dois casos (2,3) o repository fica corrompido sem nenhum aviso, e em 3 casos (1,7,8), tudo parece ok, mas o conteúdo do repository é diferente do que você espera ser estar. As pessoas clonando ou puxando terão um conteúdo diferente do que você tem. Os casos 4,5,6 e 9 estão ok, pois vão parar com um erro. Eu suponho que seria melhor se falhasse com um erro pelo menos em todos os casos.

Resposta original (2012) (veja colisão shattered.io 2017 SHA1 abaixo)

Essa velha (2006) resposta de Linus ainda pode ser relevante:

Não. Se tiver o mesmo SHA1, significa que quando recebermos o object do outro lado, não sobrescreveremos o object que já temos.

Então, o que acontece é que, se alguma vez virmos uma colisão, o object “anterior” em qualquer repository específico sempre acabará substituindo. Mas note que “anterior” é obviamente por repository, no sentido de que a rede de objects git gera um DAG que não é totalmente ordenado, enquanto repositorys diferentes concordam sobre o que é “anterior” no caso de ancestralidade direta, se object veio através de ramos separados e não diretamente relacionados, dois repos diferentes podem, obviamente, ter obtido os dois objects em ordem diferente.

No entanto, o “anterior será substituído” é muito o que você quer do ponto de vista de segurança: lembre-se que o modelo git é que você deve confiar principalmente em seu próprio repository.
Portanto, se você fizer um ” git pull “, os novos objects recebidos serão, por definição, menos confiáveis ​​do que os objects que você já possui, e, como tal, seria errado permitir que um novo object substitua um antigo.

Então você tem dois casos de colisão:

  • o tipo inadvertido , onde você de alguma forma é muito infeliz, e dois arquivos acabam tendo o mesmo SHA1.
    Nesse ponto, o que acontece é que quando você comete esse arquivo (ou faz um ” git-update-index ” para movê-lo para o índice, mas ainda não está comprometido), o SHA1 do novo conteúdo será computado, mas como corresponde a um object antigo, um novo object não será criado e o commit-or-index acaba apontando para o object antigo .
    Você não notará imediatamente (já que o índice corresponderá ao object antigo SHA1, e isso significa que algo como ” git diff ” usará a cópia com check-out), mas se você alguma vez fizer um diff no nível da tree (ou você clone ou pull, ou forçar um checkout) você notará de repente que aquele arquivo foi alterado para algo completamente diferente do que você esperava.
    Então, você geralmente notaria esse tipo de colisão rapidamente.
    Em notícias relacionadas, a questão é o que fazer com a colisão inadvertida.
    Primeiro, deixe-me lembrar às pessoas que o tipo inadvertido de colisão é realmente muito improvável, então é bem provável que nunca o veremos na história completa do universo.
    Mas se isso acontecer, não é o fim do mundo: o que você provavelmente teria que fazer é apenas mudar o arquivo que colidiu um pouco, e apenas forçar um novo commit com o conteúdo alterado (adicione um comentário dizendo ” /* This line added to avoid collision */ “) e depois ensinar git sobre a magia SHA1 que foi mostrada como perigosa.
    Então, ao longo de um par de milhões de anos, talvez tenhamos que adicionar um ou dois valores SHA1 “envenenados” ao git. É muito improvável que seja um problema de manutenção;)

  • O agressor tipo de colisão porque alguém quebrou (ou forçado) SHA1.
    Este é claramente mais provável do que o tipo inadvertido, mas, por definição, é sempre um repository “remoto”. Se o atacante tivesse access ao repository local, ele teria maneiras muito mais fáceis de estragar você.
    Portanto, neste caso, a colisão é totalmente um não-problema : você obterá um repository “ruim” que é diferente do que o invasor pretendia, mas como você nunca utilizará o object em colisão, ele não é diferente do O atacante simplesmente não encontrou uma colisão , mas apenas usando o object que você já tinha (ou seja, é 100% equivalente à colisão “trivial” do arquivo idêntico que gera o mesmo SHA1).

A questão de usar o SHA-256 é regularmente mencionada, mas não aja por enquanto.


Nota (Humor): você pode forçar um commit a um prefixo SHA1 em particular, com o projeto gitbrute de Brad Fitzpatrick ( bradfitz ) .

gitbrute força bruta um par de timestamps autor + committer de tal forma que o commit resultante git tenha seu prefixo desejado.

Exemplo: https://github.com/bradfitz/deadbeef


Daniel Dinnyes aponta nos comentários para o 7.1 Git Tools – Seleção de Revisão , que inclui:

Existe uma probabilidade maior de que todos os membros de sua equipe de programação sejam atacados e mortos por lobos em incidentes não relacionados na mesma noite.


Até o mais recente (fevereiro de 2017) shattered.io demonstrou a possibilidade de forjar uma colisão SHA1:
(veja muito mais na minha resposta em separado , incluindo a postagem no Google+ de Linus Torvalds)

  • a / ainda requer mais de 9.223.372.036.854.775.808 computações SHA1. Isso levou o poder de processamento equivalente a 6.500 anos de cálculos de CPU única e 110 anos de cálculos de uma única GPU.
  • b / forjaria um arquivo (com o mesmo SHA1), mas com a restrição adicional seu conteúdo e tamanho produziriam o mesmo SHA1 (apenas uma colisão no conteúdo não é suficiente): consulte ” Como o hash git é calculado? “) : um blob SHA1 é calculado com base no conteúdo e tamanho .

Consulte ” Tempos de vida de funções hash criptográficas ” de Valerie Anita Aurora para saber mais.
Na página, ela observa:

O Google gastou 6500 anos de CPU e 110 anos de GPU para convencer a todos que precisamos parar de usar o SHA-1 para aplicativos críticos de segurança.
Também porque foi legal

Veja mais na minha resposta separada abaixo .

De acordo com o Pro Git :

Se acontecer de você cometer um object com hashes para o mesmo valor SHA-1 que um object anterior em seu repository, o Git verá o object anterior já em seu database do Git e assumirá que ele já está escrito. Se você tentar fazer o check out desse object novamente em algum momento, sempre obterá os dados do primeiro object.

Então, não falharia, mas também não salvaria seu novo object.
Eu não sei como isso ficaria na linha de comando, mas isso certamente seria confuso.

Um pouco mais abaixo, essa mesma referência tenta ilustrar a probabilidade de tal colisão:

Aqui está um exemplo para você ter uma ideia do que seria necessário para obter uma colisão SHA-1. Se todos os 6,5 bilhões de humanos na Terra estivessem programando, e a cada segundo, cada um produzindo código equivalente a todo o histórico do kernel do Linux (1 milhão de objects Git) e o colocando em um enorme repository Git, levaria 5 anos até esse repository continha objects suficientes para ter 50% de probabilidade de uma única colisão de object SHA-1. Existe uma probabilidade maior de que todos os membros de sua equipe de programação sejam atacados e mortos por lobos em incidentes não relacionados na mesma noite.

Para adicionar à minha resposta anterior de 2012 , há agora (fevereiro de 2017, cinco anos depois), um exemplo de colisão SHA-1 real com shattered.io n onde você pode criar dois arquivos PDF colidindo: que é obter um SHA- 1 assinatura digital no primeiro arquivo PDF que também pode ser usado como uma assinatura válida no segundo arquivo PDF.
Veja também ” Na porta da morte por anos, a function SHA1 amplamente usada está agora morta “, e esta ilustração .

Atualização de 26 de fevereiro: Linus confirmou os seguintes pontos em uma postagem no Google+ :

(1) Primeiro, o céu não está caindo. Há uma grande diferença entre usar um hash criptográfico para coisas como assinatura de segurança e usar um para gerar um “identificador de conteúdo” para um sistema endereçável por conteúdo como o git.

(2) Em segundo lugar, a natureza deste ataque SHA1 em particular significa que é realmente muito fácil mitigar, e já houve dois conjuntos de correções postados para essa mitigação.

(3) E, finalmente, há realmente uma transição razoavelmente direta para algum outro hash que não vai quebrar o mundo – ou mesmo os antigos repositorys git.

Com relação a essa transição, veja o Q1 2018 Git 2.16 adicionando uma estrutura representando o algoritmo hash. A implementação dessa transição foi iniciada.


Resposta original (25 de fevereiro) Mas:

  • Isto permite forjar um blob, no entanto, o SHA-1 da tree ainda muda, pois o tamanho do blob forjado pode não ser o mesmo que o original: veja ” Como o hash do git é calculado? “; um blob SHA1 é calculado com base no conteúdo e no tamanho .
    Ele tem algum problema para o git-svn embora . Ou melhor, com o próprio svn , como visto aqui .
  • Como mencionei na minha resposta original , o custo de tal tentativa ainda é proibitivo por enquanto (6.500 anos de CPU e 100 anos de GPU). Veja também Valerie Anita Aurora em ” Lifetimes of cryptographic hash functions “.
  • Como comentado anteriormente, não se trata de segurança ou confiança, mas de integridade de dados (deduplicação e detecção de erros) que podem ser facilmente detectados por um git fsck , como mencionado hoje por Linus Torvalds . git fsck avisa sobre uma mensagem de commit com dados opacos escondidos após um NUL (embora o NUL não esteja sempre presente em um arquivo fraudulento ).
    Nem todo mundo liga transfer.fsck , mas o GitHub faz: qualquer push seria abortado no caso de um object mal formado ou um link quebrado. Embora … haja uma razão pela qual isso não é ativado por padrão .
  • um arquivo pdf pode ter dados binários arbitrários que você pode alterar para gerar um código-fonte colidido SHA-1, em oposição ao forjado.
    O problema real na criação de dois repositorys Git com o mesmo hash head commit e conteúdos diferentes. E mesmo assim, o ataque continua complicado .
  • Linus acrescenta :

    O ponto principal de um SCM é que não se trata de um evento único, mas de um histórico contínuo. Isso também significa fundamentalmente que um ataque bem-sucedido precisa funcionar com o tempo e não ser detectável.
    Se você conseguir enganar um SCM uma vez, inserir seu código e ele for detectado na próxima semana, você não fez nada de útil. Você só se queimou.

Joey Hess experimenta o pdf em um repository do Git e ele descobriu :

Isso inclui dois arquivos com o mesmo SHA e tamanho, que recebem diferentes blobs graças ao modo como o git preenche o header do conteúdo.

 joey@darkstar:~/tmp/supercollider>sha1sum bad.pdf good.pdf d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a bad.pdf d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a good.pdf joey@darkstar:~/tmp/supercollider>git ls-tree HEAD 100644 blob ca44e9913faf08d625346205e228e2265dd12b65 bad.pdf 100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1 good.pdf 

Embora a anexação de dados idênticos a esses arquivos de colisão gerem outras colisões, os dados prepending não.

Então, o principal vetor de ataque (forjando um commit) seria :

  • Gere um object de commit regular;
  • use todo o object de commit + NUL como o prefixo escolhido, e
  • use o ataque de colisão com prefixo idêntico para gerar os objects bons / ruins de colisão.
  • … e isso é inútil porque os objects commit bons e ruins ainda apontam para a mesma tree!

Além disso, você já pode e detecta ataques de colisão criptoanalítica contra SHA-1 presente em cada arquivo com cr-marcstevens/sha1collisiondetection

Adicionar uma verificação semelhante no próprio Git teria algum custo de computação .

Ao mudar o hash, o Linux comenta :

O tamanho do hash e a escolha do algoritmo de hash são problemas independentes.
O que você provavelmente faria é mudar para um hash de 256 bits, usá-lo internamente e no database nativo git e, por padrão, mostrar apenas o hash como uma string hexadecimal de 40 caracteres (como se já abreviasse as coisas em muitas situações).
Dessa forma, as ferramentas em torno do git nem mesmo vêem a mudança a menos que sejam passadas em algum argumento especial ” --full-hash ” (ou ” --abbrev=64 ” ou qualquer outra coisa – sendo o padrão abreviar para 40).

Ainda assim, um plano de transição (de SHA1 para outra function hash) ainda seria complexo , mas seria estudado ativamente.
Uma campanha convert-to-object_id está em andamento :


Atualização 20 de março: GitHub detalha um possível ataque e sua proteção :

Os nomes SHA-1 podem ser atribuídos à confiança por meio de vários mecanismos. Por exemplo, o Git permite que você assine criptograficamente um commit ou tag. Ao fazer isso, assina apenas o próprio object de confirmação ou marca, o que, por sua vez, aponta para outros objects que contêm os dados reais do arquivo, usando seus nomes SHA-1. Uma colisão nesses objects poderia produzir uma assinatura que parece válida, mas que aponta para dados diferentes dos pretendidos pelo signatário. Em tal ataque, o signatário só vê metade da colisão e a vítima vê a outra metade.

Protecção:

O ataque recente usa técnicas especiais para explorar fraquezas no algoritmo SHA-1, que encontram uma colisão em muito menos tempo. Essas técnicas deixam um padrão nos bytes que podem ser detectados ao computar o SHA-1 de qualquer metade de um par em colisão.

O GitHub.com agora executa essa detecção para cada SHA-1 que ele calcula e aborta a operação se houver evidência de que o object é metade de um par em colisão. Isso impede que invasores usem o GitHub para convencer um projeto a aceitar a metade “inocente” de sua colisão, além de impedir que hospedem a metade maliciosa.

Veja ” sha1collisiondetection ” por Marc Stevens


Novamente, com o Q1 2018 Git 2.16 adicionando uma estrutura representando o algoritmo de hash, a implementação de uma transição para um novo hash foi iniciada.

Eu acho que criptógrafos celebravam.

Citação do artigo da Wikipedia sobre SHA-1 :

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

Existem vários modelos de ataque diferentes para hashes como o SHA-1, mas o que normalmente é discutido é a pesquisa de colisão, incluindo a ferramenta HashClash de Marc Stevens.

“A partir de 2012, o ataque mais eficiente contra o SHA-1 é considerado o de Marc Stevens [34], com um custo estimado de US $ 2,77 milhões para quebrar um único valor de hash alugando a energia da CPU dos servidores em nuvem.”

Como as pessoas apontaram, você pode forçar uma colisão de hash com o git, mas isso não sobrescreverá os objects existentes em outro repository. Eu imagino que mesmo o git push -f --no-thin não irá sobrescrever os objects existentes, mas não 100% de certeza.

Dito isso, se você invadir um repository remoto, poderá transformar o seu object falso no antigo, possivelmente incorporando o código hackeado em um projeto de código aberto no github ou similar. Se você fosse cuidadoso, talvez pudesse introduzir uma versão hackeada que os novos usuários baixaram.

Eu suspeito, no entanto, que muitas coisas que os desenvolvedores do projeto possam fazer podem expor ou destruir acidentalmente seu hack de vários milhões de dólares. Em particular, isso é um monte de dinheiro no ralo se algum desenvolvedor, que você não hackeou, executar o já mencionado git push --no-thin depois de modificar os arquivos afetados, às vezes até mesmo sem a dependência --no-thin .