Comment git gère-t-il une collision SHA-1 sur un blob ?

Question

Cela ne s'est probablement jamais produit dans le monde réel, et ne se produira peut-être jamais, mais considérons ceci : disons que vous avez un dépôt git, que vous faites un commit, et que vous êtes très très malchanceux : un des blobs finit par avoir le même SHA-1 qu'un autre qui est déjà dans votre dépôt. La question est : comment git gère-t-il cette situation ? Simplement en échouant ? Trouverait-il un moyen de lier les deux blobs et de vérifier lequel est nécessaire en fonction du contexte ?

C'est plus un casse-tête qu'un problème réel, mais j'ai trouvé la question intéressante.

Answer 1

Ce ancienne réponse de Linus pourrait encore être pertinente :

Non. S'il a le même SHA1, cela signifie que lorsque nous recevrons l'objet de l'autre côté, nous allons pas écraser l'objet que nous avons déjà.

Donc ce qui se passe est que si nous voyons une collision, l'objet "antérieur" dans un dépôt particulier finira toujours par prévaloir. Mais notez que "plus tôt" est évidemment par dépôt, dans le sens où le réseau d'objets git génère un DAG qui n'est pas complètement ordonné, donc alors que différents dépôts seront d'accord sur ce qui est "plus tôt" dans le cas d'une ascendance directe, si l'objet est venu par des branches séparées et non directement liées, deux dépôts différents peuvent évidemment avoir obtenu les deux objets dans un ordre différent.

Cependant, l'option "earlier will override" correspond tout à fait à ce que vous voulez du point de vue de la sécurité : rappelez-vous que le modèle git est que vous ne devez faire confiance qu'à votre propre dépôt.
Donc si vous faites un " git pull "Les nouveaux objets entrants sont par définition moins fiables que les objets que vous possédez déjà. remplacer un ancien objet.

Vous avez donc deux cas de collision :

• le site genre involontaire où vous êtes en quelque sorte très très malchanceux, et deux fichiers finissent par avoir le même SHA1.
  À ce moment-là, lorsque vous livrez ce fichier (ou faites un " git-update-index "pour le déplacer dans l'index, mais pas encore validé), le SHA1 du nouveau contenu sera calculé, mais puisqu'il correspond à un ancien objet, un nouvel objet ne sera pas créé, et le commit-or-index finit par pointer vers l'objet vieux objet .
  Vous ne le remarquerez pas immédiatement (puisque l'index correspondra à l'ancien objet SHA1, ce qui signifie que quelque chose comme " git diff " utilisera la copie extraite), mais si vous faites un diff au niveau de l'arbre (ou si vous faites un clone ou un pull, ou si vous forcez un checkout), vous remarquerez soudainement que ce fichier a été changé en quelque chose comme complètement différent de ce que vous attendiez.
  Vous remarquerez donc généralement ce type de collision assez rapidement.
  Dans le même ordre d'idées, la question est de savoir ce qu'il faut faire de la collision involontaire
  Tout d'abord, permettez-moi de rappeler aux gens que la collision par inadvertance est vraiment, vraiment vraiment très peu probable, donc nous ne le verrons probablement jamais dans toute l'histoire de l'univers.
  Mais si ça arrive, ce n'est pas la fin du monde : Ce qu'il faut faire, c'est modifier légèrement le fichier qui est entré en collision, et forcer une nouvelle livraison avec le contenu modifié. (ajouter un commentaire disant " /* This line added to avoid collision */ ") et ensuite enseigner à git le SHA1 magique qui s'est avéré être dangereux.
  Ainsi, dans quelques millions d'années, nous devrons peut-être ajouter une ou deux valeurs SHA1 "empoisonnées" à git. Il est très peu probable que ce soit un problème de maintenance ;)

• Le site Type de collision de l'attaquant parce que quelqu'un a cassé (ou forcé brutalement) SHA1.
  Celui-ci est clairement un lot plus probable que le type par inadvertance, mais par définition, il s'agit toujours d'un dépôt "distant". Si l'attaquant avait accès au référentiel local, il aurait des moyens beaucoup plus faciles de vous bousiller.
  Donc dans ce cas, la collision n'est absolument pas un problème vous obtiendrez un "mauvais" dépôt, différent de ce que l'attaquant voulait, mais puisque vous n'utiliserez jamais son objet de collision, c'est littéralement Ce n'est pas différent de l'attaquant qui n'a pas trouvé de collision du tout. mais en utilisant simplement l'objet que vous aviez déjà (c'est-à-dire que c'est 100% équivalent à la collision "triviale" du fichier identique générant le même SHA1).

Le site question de l'utilisation de SHA-256 est régulièrement mentionné, mais n'est pas mis en œuvre pour l'instant.

---

Note (Humour) : vous pouvez forcer un commit à un SHA1 particulier, avec le projet gitbrute de Brad Fitzpatrick ( bradfitz ) .

gitbrute force brutalement une paire d'horodatages auteur+committer de sorte que le commit git résultant ait le préfixe désiré.

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

Answer 2

Selon Pro Git :

Si vous livrez un objet qui a la même valeur SHA-1 qu'un objet précédent dans votre dépôt, Git verra l'objet précédent déjà dans votre base de données Git et supposera qu'il a déjà été écrit. Si vous essayez de récupérer cet objet à un moment donné, vous obtiendrez toujours les données du premier objet.

Donc ça n'échouerait pas, mais ça ne sauvegarderait pas non plus votre nouvel objet.
Je ne sais pas comment cela se présenterait sur la ligne de commande, mais cela prêterait certainement à confusion.

Un peu plus loin, la même référence tente d'illustrer la probabilité d'une telle collision :

Voici un exemple pour vous donner une idée de ce qu'il faudrait faire pour obtenir une collision SHA-1. Si les 6,5 milliards d'humains sur Terre programmaient, et que chaque seconde, chacun produisait du code équivalent à l'histoire entière du noyau Linux (1 million d'objets Git) et le poussait dans un énorme dépôt Git, il faudrait 5 ans pour que ce dépôt contienne suffisamment d'objets pour avoir une probabilité de 50 % d'une seule collision d'objets SHA-1. Il existe une probabilité plus élevée que tous les membres de votre équipe de programmation soient attaqués et tués par des loups dans des incidents sans lien entre eux, la même nuit.

Answer 3

Je pense que les cryptographes fêteraient ça.

Citation de Article de Wikipedia sur SHA-1 :

En février 2005, une attaque de Xiaoyun Wang, Yiqun Lisa Yin et Hongbo Yu a été annoncée. Les attaques peuvent trouver des collisions dans la version complète de SHA-1, nécessitant moins de 2^69 opérations. (Une recherche par force brute nécessiterait 2^80 opérations).