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

Provavelmente isso nunca aconteceu no mundo real ainda, e pode nunca acontecer, mas vamos considerar o seguinte: digamos que você tenha um repositório git, faça um commit e fique muito azarado: um dos blobs acaba tendo o mesmo SHA-1 como outro que já está no seu repositório. A questão é: como o Git lidaria com isso? Simplesmente falhar? 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.

Fiz um experimento para descobrir exatamente como o Git se comportaria nesse caso. Esta é a versão 2.7.9 ~ rc0 + next.20151210 (versão Debian). Basicamente, reduzi o tamanho do hash de 160 para 4 bits aplicando o seguinte diff e reconstruindo o git:

--- 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);
 }

Depois fiz alguns commits e notei o seguinte.

1. Se já existir um blob com o mesmo hash, você não receberá nenhum aviso. Tudo parece estar bem, mas quando você pressiona, alguém clona ou reverte, você perde a versão mais recente (de acordo com o explicado acima).
2. Se um objeto em árvore já existir e você criar um blob com o mesmo hash: tudo parecerá normal, até você tentar empurrar ou alguém clonar seu repositório. Então você verá que o repositório está corrompido.
3. Se um objeto de confirmação já existe e você cria um blob com o mesmo hash: o mesmo que o número 2 - corrompido
4. Se um blob já existir e você criar um objeto de confirmação com o mesmo hash, ele falhará ao atualizar o "ref".
5. Se já existir um blob e você criar um objeto de árvore com o mesmo hash. Falha ao criar a confirmação.
6. Se um objeto em árvore já existir e você fizer um objeto de confirmação com o mesmo hash, ele falhará ao atualizar o "ref".
7. Se um objeto em árvore já existir e você criar um objeto em árvore com o mesmo hash, tudo parecerá correto. Mas quando você confirma, todo o repositório faz referência à árvore errada.
8. Se um objeto de confirmação já existir e você criar um objeto de confirmação com o mesmo hash, tudo parecerá correto. Mas quando você confirma, a confirmação nunca será criada e o ponteiro HEAD será movido para uma confirmação antiga.
9. Se um objeto de confirmação já existir e você criar um objeto de árvore com o mesmo hash, ele falhará ao criar o commit.

Para o número 2, você normalmente receberá um erro como esse ao executar o "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 executar "git checkout file.txt".

Para os nºs 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". Nesse caso, você pode digitar apenas "git commit" novamente, pois isso criará um novo hash (devido ao carimbo de data / hora alterado)

Para os nºs 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 repositório corrompido, 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 repositório fica corrompido sem nenhum aviso e em 3 casos (1,7,8) tudo parece ok, mas o conteúdo do repositório é diferente do que você espera. ser estar. As pessoas que clonam ou puxam terão um conteúdo diferente do que você possui. Os casos 4,5,6 e 9 estão corretos, pois parará com um erro. Suponho que seria melhor se falhasse com um erro, pelo menos em todos os casos.

Resposta original (2012) (ver shattered.iocolisão SHA1 2017 abaixo)

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

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

Então, o que acontece é que, se alguma vez vermos uma colisão, o objeto "anterior" em qualquer repositório específico sempre será substituído. Mas observe que "anterior" é obviamente por repositório, no sentido de que a rede de objetos git gera um DAG que não está totalmente ordenado; portanto, embora diferentes repositórios concordem sobre o que é "anterior" no caso de ancestralidade direta, se o Como o objeto veio através de ramificações separadas e não diretamente relacionadas, dois repositórios diferentes podem obviamente ter obtido os dois objetos em ordem diferente.

No entanto, o "anterior substituirá" é muito o que você deseja do ponto de vista de segurança: lembre-se de que o modelo git é que você deve confiar principalmente apenas em seu próprio repositório.
Portanto, se você fizer um " git pull", os novos objetos recebidos serão, por definição, menos confiáveis ​​do que os objetos que você já possui e, como tal, seria errado permitir que um novo objeto substituísse um antigo.

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

• do tipo inadvertido , em que você, de alguma forma, é muito azarado e dois arquivos acabam tendo o mesmo SHA1. completamente diferente do que você esperava. Então você geralmente notaria esse tipo de colisão rapidamente. Em notícia relacionada, a questão é o que fazer sobre a colisão acidental .. Primeiro, deixe-me lembrar as pessoas de que o tipo inadvertida de colisão é realmente realmente maldita improvável, por isso vamos muito provavelmente nunca vê-lo em toda a história Do universo.
  Nesse momento, o que acontece é que, quando você confirma esse arquivo (ou faz um " git-update-index" para movê-lo para o índice, mas ainda não foi confirmado), o SHA1 do novo conteúdo será calculado, mas, como ele corresponde a um objeto antigo, um novo objeto não será criado e o commit-ou-index acaba apontando para o objeto antigo .
  Você não notará imediatamente (já que o índice corresponderá ao objeto antigo SHA1, e isso significa que algo como " git diff" usará a cópia com check-out), mas se você fizer um diff no nível da árvore (ou fizer um clone ou puxar ou forçar um check-out), você notará repentinamente que esse arquivo mudou para algo
  
  
  
  Mas se isso acontecer, não é o fim do mundo: o que você provavelmente precisará fazer é apenas alterar o arquivo que colidiu levemente e forçar um novo commit com o conteúdo alterado (adicione um comentário dizendo " /* This line added to avoid collision */") e depois ensine o git sobre a mágica SHA1 que se mostrou perigosa.
  Assim, ao longo de alguns 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 atacante tipo de colisão porque alguém quebrou (ou com força bruta) o SHA1.
  Este é claramente muito mais provável do que o tipo inadvertido, mas, por definição, é sempre um repositório "remoto". Se o invasor tivesse acesso ao repositório local, ele teria maneiras muito mais fáceis de estragar tudo.
  Portanto, neste caso, a colisão não é um problema : você receberá um repositório "ruim" que é diferente do que o invasor pretendia, mas como você nunca usará o objeto em colisão, literalmente não é diferente do atacante simplesmente não ter encontrado uma colisão, mas apenas usando o objeto que você já tinha (ou seja, é 100% equivalente à colisão "trivial" do arquivo idêntico que gera o mesmo SHA1).

A questão do uso do SHA-256 é mencionada regularmente, mas não é adotada por enquanto (2012).
Nota: a partir de 2018 e do Git 2.19 , o código está sendo refatorado para usar o SHA-256.

Nota (Humor): você pode forçar uma confirmação para um prefixo SHA1 específico , com o projeto gitbrute de Brad Fitzpatrick ( bradfitz) .

gitbrute brute - força um par de registros de data e hora do autor e do commit, de forma que o commit do git resultante tenha o prefixo desejado.

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

Daniel Dinnyes aponta nos comentários para 7.1 Git Tools - Revision Selection , que inclui:

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

Até os mais recentes (fevereiro de 2017) shattered.iodemonstraram a possibilidade de forjar uma colisão com SHA1:
(veja muito mais em minha resposta separada , incluindo a postagem do Google+ de Linus Torvalds)

• a / ainda requer mais de 9.223.372.036.854.775.808 cálculos de 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 GPU única.
• b / forjaria um arquivo (com o mesmo SHA1), mas com a restrição adicional, seu conteúdo e tamanho produziriam o SHA1 idêntico (uma colisão apenas no conteúdo não é suficiente): consulte " Como é calculado o hash do git? ") : um blob SHA1 é calculado com base no conteúdo e tamanho .

Consulte " Vida útil das funções de hash criptográfico " da Valerie Anita Aurora para obter mais informações.
Nessa página, ela observa:

O Google passou 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 em minha resposta separada abaixo .

De acordo com o Pro Git :

Se você confirmar um objeto com hash no mesmo valor SHA-1 que um objeto anterior em seu repositório, o Git verá o objeto anterior já no seu banco de dados Git e assumirá que ele já foi gravado. Se você tentar verificar o objeto novamente em algum momento, sempre obterá os dados do primeiro objeto.

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

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

Aqui está um exemplo para lhe dar uma idéia do que seria necessário para obter uma colisão com SHA-1. Se todos os 6,5 bilhões de humanos na Terra estivessem programando, e a cada segundo, cada um estivesse produzindo código equivalente a toda a história do kernel do Linux (1 milhão de objetos Git) e inserindo-o em um enorme repositório Git, levaria 5 anos até esse repositório continha objetos suficientes para ter uma probabilidade de 50% de uma única colisão de objeto SHA-1. Existe uma probabilidade maior de que todos os membros da 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 , existe agora (fevereiro de 2017, cinco anos depois), um exemplo de colisão SHA-1 com shattered.io , onde você pode criar dois arquivos PDF em colisão: que é obter um SHA- 1 assinatura digital no primeiro arquivo PDF que também pode ser abusada como uma assinatura válida no segundo arquivo PDF.
Veja também " À porta da morte há anos, a função SHA1 amplamente utilizada agora está morta ", e esta ilustração .

Atualização 26 de fevereiro: Linus confirmou os seguintes pontos em uma postagem do 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 como o git.

(2) Em segundo lugar, a natureza desse ataque SHA1 específico significa que é realmente muito fácil mitigar, e já houve dois conjuntos de patches publicados para essa mitigação.

(3) E, finalmente, há realmente uma transição razoavelmente direta para algum outro hash que não quebrará o mundo - ou até mesmo repositórios git antigos.

Sobre essa transição, consulte o primeiro trimestre de 2018 Git 2.16 adicionando uma estrutura representando o algoritmo de hash. A implementação dessa transição foi iniciada.

Iniciando o Git 2.19 (terceiro trimestre de 2018) , o Git escolheu SHA-256 como NewHash e está no processo de integrá-lo ao código (o que significa que o SHA1 ainda é o padrão (Q2 2019, Git 2.21), mas o SHA2 será o sucessor)

Resposta original (25 de fevereiro) Mas:

• Isso permite forjar um blob, no entanto, o SHA-1 da árvore ainda muda, pois o tamanho do blob forjado pode não ser o mesmo que o original: consulte " Como é calculado o hash do git? "; um blob SHA1 é calculado com base no conteúdo e tamanho .
  Ele tem algum problema para git-svnque . Ou melhor, com o próprio svn , como pode visto aqui .
• Como mencionei na minha resposta original , o custo dessa tentativa ainda é proibitivo por enquanto (6.500 anos de CPU e 100 anos de GPU). Veja também Valerie Anita Aurora em " Vida útil das funções de hash criptográfico ".
• Como comentado anteriormente, não se trata de segurança ou confiança, mas da integridade dos dados (deduplicação e detecção de erros) que podem ser facilmente detectados por um git fsck, conforme mencionado hoje por Linus Torvalds . git fsckalertaria sobre uma mensagem de confirmação com dados opacos ocultos após a NUL(embora NULnem sempre esteja presente em um arquivo fraudulento ).
  Nem todo mundo liga transfer.fsck, mas o GitHub faz: qualquer push será abortado no caso de um objeto malformado ou um link quebrado. Embora ... haja um motivo para isso não ser ativado por padrão .
• um arquivo pdf pode ter dados binários arbitrários que você pode alterar para gerar um SHA-1 em colisão, em oposição ao código-fonte forjado.
  O problema real na criação de dois repositórios Git com o mesmo cabeçalho de confirmação de hash 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ê consegue enganar um SCM uma vez, insira seu código e ele é detectado na próxima semana, você não fez nada de útil. Você só se queimou.

Joey Hess experimenta esses pdf em um repositório Git e descobriu :

Isso inclui dois arquivos com o mesmo SHA e tamanho, que recebem blobs diferentes, graças à maneira como o git anexa o cabeçalho ao 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

Enquanto o acréscimo de dados idênticos a esses arquivos em colisão gera outras colisões, o acréscimo de dados não.

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

• Gere um objeto de confirmação regular;
• use o objeto de confirmação inteiro + NUL como o prefixo escolhido e
• use o ataque de colisão com prefixo idêntico para gerar os objetos bons / ruins em colisão.
• ... e isso é inútil porque os objetos de confirmação bons e ruins ainda apontam para a mesma árvore!

Além disso, você já pode e detecta ataques de colisão criptoanalítica contra o 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 .

Sobre a alteração de 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 banco de dados nativo do git e, por padrão, mostrar apenas o hash como uma sequência hexadecimal de 40 caracteres (tipo como já abreviamos as coisas em muitas situações).
Dessa forma, as ferramentas em torno do git nem veem a mudança, a menos que sejam aprovadas em algum --full-hashargumento " " especial (ou " --abbrev=64" ou qualquer outra coisa - o padrão é que abreviamos para 40).

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

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

Os nomes SHA-1 podem receber confiança confiada através de vários mecanismos. Por exemplo, o Git permite que você assine criptograficamente um commit ou tag. Fazer isso assina apenas o próprio objeto de confirmação ou marcação, que por sua vez aponta para outros objetos que contêm os dados reais do arquivo usando seus nomes SHA-1. Uma colisão nesses objetos pode produzir uma assinatura que pareça válida, mas que aponte para dados diferentes do que o signatário pretendeu. Nesse ataque, o assinante vê apenas metade da colisão e a vítima vê a outra metade.

Proteção:

O ataque recente usa técnicas especiais para explorar pontos fracos 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 calcular o SHA-1 de qualquer metade de um par em colisão.

Agora, o GitHub.com realiza essa detecção para cada SHA-1 calculado e interrompe a operação se houver evidência de que o objeto é metade de um par em colisão. Isso impede que os invasores usem o GitHub para convencer um projeto a aceitar a metade "inocente" de sua colisão, além de impedir que eles hospedem a metade maliciosa.

Ver " sha1collisiondetection" por Marc Stevens

Novamente, com o primeiro trimestre de 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.
Como mencionado acima, o novo Hash suportado será o SHA-256 .

Eu acho que os criptografadores comemorariam.

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

Em fevereiro de 2005, foi anunciado um ataque de Xiaoyun Wang, Yiqun Lisa Yin e Hongbo Yu. 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 geralmente discutido é a pesquisa de colisões, incluindo a ferramenta HashClash de Marc Stevens .

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

Como as pessoas apontaram, você pode forçar uma colisão de hash com o git, mas isso não substituirá os objetos existentes em outro repositório. Eu imagino mesmogit push -f --no-thin que nem substituirá os objetos existentes, mas não tenho 100% de certeza.

Dito isto, se você invadir um repositório remoto, poderá tornar seu objeto falso o mais antigo existente , possivelmente incorporação de código invadiu um projeto open source no GitHub ou similar. Se você fosse cuidadoso, talvez pudesse introduzir uma versão invadida que os novos usuários baixaram.

Suspeito, no entanto, que muitas coisas que os desenvolvedores do projeto possam fazer possam expor ou destruir acidentalmente seu hack de vários milhões de dólares. Em particular, é muito dinheiro pelo ralo, se algum desenvolvedor, que você não invadiu, executar o mencionado acima git push --no-thindepois de modificar os arquivos afetados, às vezes até sem a --no-thindependência.