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

StackOverflow https://stackoverflow.com/questions/9392365

  •  29-10-2019
  •  | 
  •  

Pergunta

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 tenha muito azar:um dos blobs acaba tendo o mesmo SHA-1 de outro que já está no seu repositório.A questão é: como o Git lidaria com isso?Simplesmente falhar?Encontre 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.

Foi útil?

Solução

Fiz uma experiência para descobrir exatamente como o Git se comportaria neste caso. Isso é 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 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);
 }

Então eu 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ê perderá a versão mais recente (de acordo com o que é explicado acima).
  2. Se um objeto árvore já existe e você faz um blob com o mesmo hash: Tudo parecerá normal, até que você tente empurrar ou alguém clone seu repositório. Então você verá que o repo está corrompido.
  3. Se um objeto de confirmação já existe e você faz um blob com o mesmo hash: igual ao # 2 - corrompido
  4. Se um blob já existe e você cria um objeto de confirmação com o mesmo hash, ele falhará ao atualizar o "ref".
  5. Se um blob já existe e você faz um objeto árvore com o mesmo hash. Irá falhar ao criar o commit.
  6. Se um objeto árvore já existe e você faz um objeto de commit com o mesmo hash, ele falhará ao atualizar o "ref".
  7. Se um objeto árvore já existe e você faz um objeto árvore com o mesmo hash, tudo parecerá ok. Mas quando você confirma, todo o repositório fará referência à árvore errada.
  8. Se um objeto de confirmação já existe e você faz um objeto de confirmação com o mesmo hash, tudo parecerá ok. Mas quando você faz um commit, ele nunca será criado e o ponteiro HEAD será movido para um commit antigo.
  9. Se um objeto de confirmação já existe e você cria um objeto de árvore com o mesmo hash, ele falhará ao criar a confirmação.

Para o # 2, você normalmente obterá um erro como este 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 executar "git checkout file.txt".

Para # 4 e # 6, você normalmente obterá 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 simplesmente digitar "git commit" novamente, pois isso criará um novo hash (por causa do carimbo de data / hora alterado)

Para # 5 e # 9, você normalmente obterá 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 que seja. 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 irá parar com um erro. Suponho que seria melhor se falhasse com um erro, pelo menos em todos os casos.

Outras dicas

Resposta original (2012) (ver shattered.io Colisão SHA1 de 2017 abaixo)

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

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

Então o que acontece é que se alguma vez observarmos uma colisão, o objeto "anterior" em qualquer repositório específico sempre acabará sendo 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 repositórios diferentes concordem sobre o que é "anterior" no caso de ancestralidade direta, se 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, "anteriormente substituirá" é exatamente 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 ter repositório.
Então, se você fizer um "git pull", Os novos objetos recebidos sã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 substitua um antigo.

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

  • o tipo inadvertido, onde você de alguma forma tem muito azar e dois arquivos acabam tendo o mesmo SHA1.
    Nesse ponto, o que acontece é que quando você envia 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 corresponde a um objeto antigo, um novo objeto não será criado e o commit-ou-index acaba apontando para o velho objeto.
    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 uma comparação em nível de árvore (ou clonar ou extrair, ou forçar um check-out), de repente perceberá que esse arquivo mudou para algo completamente diferente do que você esperava.
    Portanto, você geralmente notaria esse tipo de colisão com bastante rapidez.
    Em notícias relacionadas, a questão é o que fazer em caso de colisão inadvertida.
    Em primeiro lugar, deixe-me lembrar às pessoas que o tipo de colisão inadvertida é realmente muito realmente muito improvável, então provavelmente nunca veremos isso em toda a história do universo.
    Mas se acontece, não é o fim do mundo: o que você provavelmente terá que fazer é apenas alterar o arquivo que colidiu levemente 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 ensine ao git sobre a magia SHA1 que se mostrou perigosa.
    Então, 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 tipo de colisão do atacante porque alguém quebrou (ou forçou brutalmente) SHA1.
    Este é claramente um 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 atrapalhar você.
    Então, neste caso, a colisão não é um problema:você obterá um repositório "ruim" diferente do que o invasor pretendia, mas já que você nunca usará o objeto em colisão dele, é literalmente não é diferente do atacante simplesmente não ter encontrado nenhuma colisão, mas apenas usando o objeto que você já tinha (ou seja, é 100% equivalente à colisão "trivial" do arquivo idêntico gerando o mesmo SHA1).

O questão de usar SHA-256 é mencionado regularmente, mas não é posto em prática por enquanto (2012).
Observação: começando em 2018 e Git 2.19, o código está sendo refatorado para usar SHA-256.

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

gitbrute força bruta um par de carimbos de data/hora de autor + committer, de modo que o commit git resultante tenha o prefixo desejado.

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

Daniel Dinnyes aponta nos comentários para 7.1 Ferramentas Git - Seleção de Revisão, 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.

Mesmo o mais recente (fevereiro de 2017) shattered.io demonstrou a possibilidade de forjar uma colisão SHA1:
(veja muito mais no meu resposta separada, incluindo a postagem de Linus Torvalds no Google+)

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

Ver "Vidas de funções hash criptográficas" de Valéria Anita Aurora para mais.
Nessa página, ela observa:

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

Veja mais no meu resposta separada abaixo.

De acordo com Pro Git :

Se acontecer de você confirmar um objeto que faz hashes para o mesmo valor SHA-1 de um objeto anterior em seu repositório, o Git verá o objeto anterior já em seu banco de dados Git e assumirá que já foi escrito. Se você tentar verificar esse objeto novamente em algum momento, sempre obterá os dados do primeiro objeto.

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

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

Aqui está um exemplo para lhe dar 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 estivesse produzindo código que era o equivalente a toda a história do kernel do Linux (1 milhão de objetos Git) e empurrando-o para um enorme repositório Git, levaria 5 anos até esse repositório continha objetos suficientes para ter 50% de probabilidade de uma única colisão de objeto 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 a minha resposta anterior de 2012, existe agora (fevereiro2017, cinco anos depois), um exemplo de colisão real do SHA-1 com quebrado.io, onde você pode criar dois arquivos PDF colididos:isto é, obter uma assinatura digital SHA-1 no primeiro arquivo PDF, que também pode ser usada como assinatura válida no segundo arquivo PDF.
Veja também "À beira 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) Em primeiro lugar – 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 específico significa que é realmente muito fácil de mitigar, e já foram publicados dois conjuntos de patches para essa mitigação.

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

Sobre essa transição, veja o Primeiro trimestre de 2018 Git 2.16 adicionando uma estrutura que representa o algoritmo hash.A implementação dessa transição já começou.

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

Resposta original (25 de fevereiro), mas:

Joey Hess tenta aqueles pdf em um repositório Git e ele encontrou:

Isso inclui dois arquivos com o mesmo SHA e tamanho, que recebem bolhas diferentes, graças à maneira como o Git preende 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 a anexar dados idênticos a esses arquivos em colisão gera outras colisões, os dados antecipados não.

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

  • Gere um objeto de commit regular;
  • use todo o objeto commit + NUL como 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 commit bons e ruins ainda apontam para a mesma árvore!

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

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

Ao alterar o hash, Comentários do Linux:

O tamanho do hash e a escolha do algoritmo de hash são questões independentes.
O que você provavelmente faria é mudar para um hash de 256 bits, usar isso internamente e no banco de dados git nativo e, em seguida, somente por padrão mostrar O hash como uma corda hexadecimal de 40 caracteres (como já abreviamos as coisas em muitas situações).
Dessa forma, as ferramentas em torno do git nem vêem a mudança, a menos que seja aprovado em algum especial "--full-hash" argumento (ou "--abbrev=64"Ou o que quer que seja - o padrão é que abrevamos para 40).

Ainda um o plano de transição (de SHA1 para outra função hash) ainda seria complexo, mas estudado ativamente.
A convert-to-object_id campanha é em andamento:

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

Os nomes SHA-1 podem receber confiança por meio 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 commit ou tag, 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 poderia produzir uma assinatura que parece válida, mas que aponta para dados diferentes daqueles pretendidos pelo signatário.Nesse tipo de ataque, o signatário vê apenas metade da colisão e a vítima vê a outra metade.

Proteção:

O ataque recente utiliza técnicas especiais para explorar fraquezas no algoritmo SHA-1 que encontra uma colisão em muito menos tempo.Essas técnicas deixam um padrão nos bytes que pode ser detectado ao calcular o SHA-1 de qualquer metade de um par em colisão.

GitHub.com agora executa essa detecção para cada SHA-1 que calcula e aborta a operação se houver evidência de que o objeto é 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.

Ver "sha1collisiondetection" por Marc Stevens

Novamente, com Primeiro trimestre de 2018 Git 2.16 adicionando uma estrutura que representa o algoritmo hash, a implementação de uma transição para um novo hash foi iniciada.
Como mencionado acima, o novo Hash suportado será SHA-256.

Acho que os criptógrafos iriam comemorar.

Citação de 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 de força bruta exigiria 2 ^ 80 operações.)

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

"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 de servidores em nuvem".

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

Dito isto, se você invadir um repositório remoto, poderá tornar seu objeto falso o mais antigo lá, possivelmente incorporando código hackeado em um projeto de código aberto no GitHub ou similar.Se você tomasse cuidado, talvez pudesse introduzir uma versão hackeada baixada por novos usuários.

Suspeito, no entanto, que muitas coisas que os desenvolvedores do projeto possam fazer podem expor ou destruir acidentalmente seu hack multimilionário.Em particular, é muito dinheiro desperdiçado se algum desenvolvedor, que você não hackeou, executar o mencionado acima git push --no-thin depois de modificar os arquivos afetados, às vezes até sem o --no-thin dependendo.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top