Por que o Git usa uma função hash criptográfica?

139

Por que o Git usa SHA-1 , uma função hash criptográfica, em vez de uma função hash não criptográfica mais rápida?

Pergunta relacionada:

Pergunta sobre estouro de pilha Por que o Git usa SHA-1 como números de versão? pergunta por que o Git usa SHA-1 em vez de números seqüenciais para confirmações.

Praxeolitic
fonte
Pessoalmente, acho que mesmo o uso de SHA-1 quebrado sobre SHA-2 era uma otimização prematura.
CodesInChaos
7
@CodesInChaos: além disso, inserir qualquer algoritmo específico no código foi uma violação horrível dos princípios de DI. Deve ser em um XML arquivo de configuração em algum lugar ;-)
Steve Jessop
Atualização em dezembro de 2017 com o Git 2.16 (primeiro trimestre de 2018): está em andamento um esforço para oferecer suporte a um SHA alternativo: consulte " Por que o Git não usa o SHA mais moderno? ".
VonC
Não existem bons hashes sem criptografia de 160 bits ou mais. A maioria são funções de 32 bits, 64 ou 128 bits altamente otimizadas. 128 bits está bom, mas sinto que 128 bits está um pouco baixo para um grande projeto como o git. Se um hash rápido e de alta qualidade de 224/256 bits fosse lançado, provavelmente seria o ideal.
Bryc 16/04/19

Respostas:

197

TLDR;


Você pode verificar isso com o próprio Linus Torvalds, quando ele apresentou o Git ao Google em 2007 :
(grifo meu)

Verificamos as somas de verificação que são consideradas criptograficamente seguras. Ninguém conseguiu quebrar o SHA-1, mas o ponto é que, no que diz respeito ao git , o SHA-1 nem sequer é um recurso de segurança. É puramente uma verificação de consistência .
As peças de segurança estão em outro lugar. Muitas pessoas assumem que, já que o git usa SHA-1 e SHA-1 é usado para coisas criptograficamente seguras, elas acham que é um enorme recurso de segurança. Não tem nada a ver com segurança, é apenas o melhor hash que você pode obter.

Ter um bom hash é bom para poder confiar nos seus dados ; também existem outros recursos bons; isso significa que quando fazemos hash nos objetos, sabemos que o hash está bem distribuído e não precisamos nos preocupar com certos problemas de distribuição .

Internamente, do ponto de vista da implementação, podemos confiar que o hash é tão bom que podemos usar algoritmos de hash e saber que não há casos ruins.

Portanto, existem alguns motivos para gostar do lado criptográfico também, mas é realmente sobre a capacidade de confiar em seus dados.
Garanto que, se você colocar seus dados no git, poderá confiar no fato de que cinco anos depois, depois de convertidos do disco rígido em DVD para qualquer nova tecnologia e copiada, cinco anos depois, poderá verificar os dados que deseja. voltar são exatamente os mesmos dados que você coloca. E isso é algo que você realmente deve procurar em um sistema de gerenciamento de código-fonte .


Atualização em dezembro de 2017 com o Git 2.16 (primeiro trimestre de 2018): este esforço para oferecer suporte a um SHA alternativo está em andamento: consulte " Por que o Git não usa o SHA mais moderno? ".


Eu mencionei em " Como o git lidaria com uma colisão SHA-1 em um blob? ", Que você poderia criar um commit com um prefixo SHA1 específico (ainda um empreendimento extremamente caro).
Mas o ponto permanece, como Eric Sink menciona no livro " Git: Cryptographic Hashes " ( controle de versão por exemplo (2011) :

É bastante importante que o DVCS nunca encontre dois dados diferentes que tenham o mesmo resumo. Felizmente, boas funções de hash criptográfico são projetadas para tornar essas colisões extremamente improváveis.

É mais difícil encontrar um bom hash não criptográfico com baixa taxa de colisão, a menos que você considere pesquisas como " Como encontrar hashes não criptográficos de última geração com programação genética ".

Você também pode ler " Considere o uso do algoritmo de hash não criptográfico para acelerar o hash ", que menciona, por exemplo, " xxhash ", um algoritmo Hash não criptográfico extremamente rápido, trabalhando em velocidades próximas aos limites da RAM.


Discussões sobre a alteração do hash no Git não são novas:

(Linus Torvalds)

Não há realmente nada restante do código do mozilla, mas ei, eu comecei com ele. Em retrospecto, eu provavelmente deveria ter começado com o código asm do PPC que já fazia o bloqueio de maneira sadia - mas isso é algo do tipo "retrospectiva 20/20".

Além disso, ei, o código mozilla sendo uma pilha horrível de lixo foi o motivo de eu estar tão convencida de que poderia melhorar as coisas. Portanto, esse é um tipo de fonte, mesmo que seja mais sobre o lado motivacional do que qualquer código restante real;)

E você precisa ter cuidado sobre como medir o ganho real de otimização

(Linus Torvalds)

Eu garanto que você melhora as coisas apenas porque faz com que o gcc gere um código de merda, que oculta alguns dos problemas do P4.

(John Tapsell - johnflux)

O custo de engenharia para atualizar o git do SHA-1 para um novo algoritmo é muito maior . Não tenho certeza de como isso pode ser feito bem.

Antes de tudo, provavelmente precisamos implantar uma versão do git (vamos chamá-la de versão 2 para esta conversa) que permite que haja um espaço para um novo valor de hash, mesmo que ele não leia ou use esse espaço - ele apenas usa o valor do hash SHA-1 que está no outro slot.

Dessa forma, quando finalmente implantarmos uma versão mais recente do git, vamos chamá-la de versão 3, que produz hashes SHA-3, além dos hashes SHA-1, as pessoas que usam a versão 2 do git poderão continuar a interoperar.
(Embora, nesta discussão, eles possam estar vulneráveis ​​e as pessoas que dependem de seus patches somente para SHA-1 possam estar vulneráveis.)

Em resumo, mudar para qualquer hash não é fácil.


Atualização em fevereiro de 2017: sim, em teoria é possível calcular um SHA1 em colisão: shattered.io

Como o GIT é afetado?

O GIT depende fortemente do SHA-1 para a identificação e verificação de integridade de todos os objetos de arquivo e confirmações.
É essencialmente possível criar dois repositórios GIT com o mesmo cabeçalho de confirmação e conteúdo diferente, como um código-fonte benigno e um backdoored.
Um invasor pode servir de maneira seletiva para qualquer repositório para usuários de destino. Isso exigirá que os invasores calculem sua própria colisão.

Mas:

Esse ataque exigiu 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.

Então, não vamos entrar em pânico ainda.
Veja mais em " Como o Git lidaria com uma colisão SHA-1 em um blob? ".

VonC
fonte
8
Parece que a recente colheita de funções hash não criptográficas de alta qualidade, como xxhash, saiu um pouco tarde demais - logo após o git.
Praxeolitic
3
@Praxeolitic de fato. Houve discussões sobre a substituição do SHA1 por outro hash, mas isso exigiria bastante trabalho, para algo que, por enquanto, está funcionando bem.
VonC
"sabemos que o hash está bem distribuído e não precisamos nos preocupar com certos problemas de distribuição" - por que isso é um problema para o scm?
roded
@roded a taxa de colisão é baixa o suficiente para ser adequada para um SCM em que os dados geralmente não são aleatórios, mas arquivos de teste.
VonC
1
Na verdade, há um motivo de segurança para o uso de um hash criptográfico. Quando um autor (digamos Linus) quer cortar um release (digamos Linux), as pessoas querem saber o código-fonte baixado corresponde ao que o autor pretendia incluir no release. Para esse fim, o último hash de confirmação no release é marcado e a tag é assinada. Se a cadeia de hash de confirmação que termina na tag não fosse criptograficamente segura, a fonte poderia ser alterada para algo diferente do que o autor pretendia.
Christopher King