Comment Git gérerait-il une collision SHA-1 sur un blob?

Cela n'est probablement jamais arrivé dans le monde réel et ne se produira peut-être jamais, mais considérons ceci: disons que vous avez un référentiel git, faites un commit et obtenez très très malchanceux: l'un des blobs finit par avoir le même SHA-1 comme un autre qui est déjà dans votre référentiel. La question est de savoir comment Git gérerait cela? Tout simplement échouer? Trouver un moyen de lier les deux blobs et vérifier lequel est nécessaire en fonction du contexte?

Plus un casse-tête qu'un problème réel, mais j'ai trouvé le problème intéressant.

J'ai fait une expérience pour savoir exactement comment Git se comporterait dans ce cas. C'est avec la version 2.7.9 ~ rc0 + next.20151210 (version Debian). J'ai simplement réduit la taille de hachage de 160 bits à 4 bits en appliquant le diff suivant et en reconstruisant 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);
 }

Puis j'ai fait quelques commits et j'ai remarqué ce qui suit.

1. Si un blob existe déjà avec le même hachage, vous ne recevrez aucun avertissement. Tout semble aller bien, mais lorsque vous poussez, quelqu'un clone ou que vous revenez, vous perdrez la dernière version (conformément à ce qui est expliqué ci-dessus).
2. Si un objet arborescent existe déjà et que vous créez un blob avec le même hachage: tout semblera normal, jusqu'à ce que vous essayiez de pousser ou que quelqu'un clone votre référentiel. Ensuite, vous verrez que le dépôt est corrompu.
3. Si un objet commit existe déjà et que vous créez un blob avec le même hachage: identique à # 2 - corrompu
4. Si un blob existe déjà et que vous créez un objet commit avec le même hachage, il échouera lors de la mise à jour de la "ref".
5. Si un blob existe déjà et que vous créez un objet arborescent avec le même hachage. Il échouera lors de la création du commit.
6. Si un objet arborescent existe déjà et que vous créez un objet commit avec le même hachage, il échouera lors de la mise à jour de la "ref".
7. Si un objet arbre existe déjà et que vous créez un objet arbre avec le même hachage, tout semblera correct. Mais lorsque vous vous engagez, tout le référentiel fera référence à la mauvaise arborescence.
8. Si un objet commit existe déjà et que vous créez un objet commit avec le même hachage, tout semblera correct. Mais lorsque vous validez, la validation ne sera jamais créée et le pointeur HEAD sera déplacé vers une ancienne validation.
9. Si un objet commit existe déjà et que vous créez un objet arborescent avec le même hachage, il échouera lors de la création du commit.

Pour # 2, vous obtiendrez généralement une erreur comme celle-ci lorsque vous exécutez "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)

si vous supprimez le fichier, puis exécutez "git checkout file.txt".

Pour # 4 et # 6, vous obtiendrez généralement une erreur comme celle-ci:

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

lors de l'exécution de "git commit". Dans ce cas, vous pouvez généralement taper à nouveau "git commit" car cela créera un nouveau hachage (en raison de l'horodatage modifié)

Pour # 5 et # 9, vous obtiendrez généralement une erreur comme celle-ci:

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

lors de l'exécution de "git commit"

Si quelqu'un essaie de cloner votre référentiel corrompu, il verra généralement quelque chose comme:

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'

Ce qui "m'inquiète", c'est que dans deux cas (2,3) le référentiel devient corrompu sans aucun avertissement, et dans 3 cas (1,7,8), tout semble correct, mais le contenu du référentiel est différent de ce que vous attendez être. Les personnes clonant ou tirant auront un contenu différent de ce que vous avez. Les cas 4,5,6 et 9 sont corrects, car cela s'arrêtera avec une erreur. Je suppose que ce serait mieux s'il échouait avec une erreur au moins dans tous les cas.

Réponse originale (2012) (voir shattered.iocollision SHA1 2017 ci-dessous)

Cette ancienne réponse (2006) de Linus pourrait toujours être pertinente:

Nan. S'il a le même SHA1, cela signifie que lorsque nous recevons l'objet de l'autre extrémité, nous n'écraserons pas l'objet que nous avons déjà.

Donc, ce qui se passe, c'est que si jamais nous voyons une collision, l'objet "antérieur" dans un référentiel particulier finira toujours par remplacer. Mais notez que "plus tôt" est évidemment par référentiel, dans le sens où le réseau d'objets git génère un DAG qui n'est pas entièrement ordonné, donc si différents référentiels s'accorderont sur ce qui est "plus tôt" dans le cas de l'ascendance directe, si le l'objet est passé par des branches distinctes et non directement liées, deux dépôts différents peuvent évidemment avoir obtenu les deux objets dans un ordre différent.

Cependant, le "plus tôt remplacera" est vraiment ce que vous voulez du point de vue de la sécurité: rappelez-vous que le modèle git est que vous ne devez principalement faire confiance qu'à votre propre référentiel.
Donc, si vous faites un " git pull", les nouveaux objets entrants sont par définition moins fiables que les objets que vous avez déjà, et en tant que tel, il serait erroné de permettre à un nouvel objet de remplacer un ancien.

Vous avez donc deux cas de collision:

• le genre par inadvertance , où vous êtes en quelque sorte très très malchanceux, et deux fichiers finissent par avoir le même SHA1.
  À ce stade, ce qui se passe, c'est que lorsque vous validez 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-ou-index finit par pointer vers l' ancien objet .
  Vous ne le remarquerez pas immédiatement (puisque l'index correspondra à l'ancien objet SHA1, et cela signifie que quelque chose comme " git diff" utilisera la copie extraite), mais si vous faites un diff au niveau de l'arborescence (ou un clone) ou tirer, ou forcer un paiement), vous remarquerez soudainement que ce fichier a changé en quelque chosecomplètement différent de ce que vous attendiez.
  Vous remarquerez donc généralement ce type de collision assez rapidement.
  Dans les nouvelles connexes, la question est de savoir quoi faire à propos de la collision accidentelle.
  Tout d'abord, permettez-moi de rappeler aux gens que le type de collision accidentelle est vraiment vraiment vraiment très improbable, donc nous ne le verrons probablement jamais dans l'histoire complète de l'univers.
  Mais si cela se produit, ce n'est pas la fin du monde: ce que vous auriez probablement à faire est simplement de changer le fichier qui est entré en collision légèrement, et de forcer simplement un nouveau commit avec le contenu modifié (ajoutez un commentaire disant " /* This line added to avoid collision */") et apprenez ensuite à Git à propos du SHA1 magique qui s'est révélé dangereux.
  Donc, sur quelques millions d'années, nous devrons peut-être ajouter une ou deux valeurs SHA1 «empoisonnées» à git. Il est très peu probable qu'il s'agisse d'un problème de maintenance;)

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

La question de l'utilisation de SHA-256 est régulièrement évoquée, mais pas pour l'instant (2012).
Remarque: à partir de 2018 et Git 2.19 , le code est en cours de refactorisation pour utiliser SHA-256.

Remarque (Humour): vous pouvez forcer un commit sur un préfixe SHA1 particulier , avec le projet gitbrute de Brad Fitzpatrick ( bradfitz) .

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

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

Daniel Dinnyes souligne dans les commentaires de 7.1 Git Tools - Revision Selection , qui comprend:

Il est plus probable que tous les membres de votre équipe de programmation soient attaqués et tués par des loups dans des incidents non liés la même nuit.

Encore plus récemment (février 2017) a shattered.iodémontré la possibilité de forger une collision SHA1:
(voir beaucoup plus dans ma réponse séparée , y compris le post Google+ de Linus Torvalds)

• a / nécessite encore plus de 9 223 372 036 854 775 808 calculs SHA1. Cela a pris la puissance de traitement équivalente à 6 500 ans de calculs à processeur unique et à 110 ans de calculs à processeur unique.
• b / forgerait un fichier (avec le même SHA1), mais avec la contrainte supplémentaire son contenu et sa taille produiraient le SHA1 identique (une collision sur le contenu seul ne suffit pas): voir " Comment est calculé le hachage git? ") : un blob SHA1 est calculé en fonction du contenu et de la taille .

Voir " Durée de vie des fonctions de hachage cryptographiques " de Valerie Anita Aurora pour plus d'informations.
Dans cette page, elle note:

Google a passé 6500 années CPU et 110 années GPU pour convaincre tout le monde que nous devons cesser d'utiliser SHA-1 pour les applications critiques pour la sécurité.
Aussi parce que c'était cool

Voir plus dans ma réponse séparée ci-dessous .

Selon Pro Git :

S'il vous arrive de valider un objet qui a la même valeur SHA-1 qu'un objet précédent dans votre référentiel, 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 à nouveau d'extraire cet objet à un moment donné, vous obtiendrez toujours les données du premier objet.

Donc, cela n'échouera pas, mais cela ne sauvera pas non plus votre nouvel objet.
Je ne sais pas à quoi cela ressemblerait sur la ligne de commande, mais ce serait certainement déroutant.

Un peu plus loin, cette 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 pour obtenir une collision SHA-1. Si les 6,5 milliards d'humains sur Terre étaient en train de programmer, et chaque seconde, chacun produisait du code qui était l'équivalent de toute l'histoire du noyau Linux (1 million d'objets Git) et le poussait dans un énorme référentiel Git, cela prendrait 5 ans jusqu'à ce référentiel contient suffisamment d'objets pour avoir une probabilité de 50% de collision d'un seul objet SHA-1. Il est plus probable que tous les membres de votre équipe de programmation soient attaqués et tués par des loups dans des incidents non liés la même nuit.

Pour ajouter à ma réponse précédente de 2012 , il y a maintenant (février 2017, cinq ans plus tard), un exemple de collision SHA-1 réelle avec shattered.io , où vous pouvez créer deux fichiers PDF en collision: c'est-à-dire obtenir un SHA- 1 signature numérique sur le premier fichier PDF qui peut également être utilisée comme signature valide sur le deuxième fichier PDF.
Voir aussi « À la porte de la mort pendant des années, la fonction SHA1 largement utilisée est maintenant morte », et cette illustration .

Mise à jour du 26 février: Linus a confirmé les points suivants dans un post Google+ :

(1) Tout d'abord - le ciel ne tombe pas. Il y a une grande différence entre utiliser un hachage cryptographique pour des choses comme la signature de sécurité et en utiliser un pour générer un "identifiant de contenu" pour un système adressable au contenu comme git.

(2) Deuxièmement, la nature de cette attaque SHA1 particulière signifie qu'il est en fait assez facile de l'atténuer, et il y a déjà eu deux ensembles de correctifs publiés pour cette atténuation.

(3) Et enfin, il y a en fait une transition assez simple vers un autre hachage qui ne brisera pas le monde - ou même les anciens dépôts git.

Concernant cette transition, voir le Git 2.16 du T1 2018 ajoutant une structure représentant l'algorithme de hachage. La mise en œuvre de cette transition a commencé.

À partir de Git 2.19 (Q3 2018) , Git a choisi SHA-256 comme NewHash et est en train de l'intégrer au code (ce qui signifie que SHA1 est toujours la valeur par défaut (Q2 2019, Git 2.21), mais SHA2 sera le successeur)

Réponse originale (25 février) Mais:

• Cela permet de forger un blob, mais le SHA-1 de l'arbre changerait quand même car la taille du blob forgé pourrait ne pas être la même que celle d'origine: voir " Comment est calculé le hachage git? "; un blob SHA1 est calculé en fonction du contenu et de la taille .
  Il ne une question pour git-svnbien . Ou plutôt avec svn lui - même , comme on le voit ici .
• Comme je l'ai mentionné dans ma réponse d'origine , le coût d'une telle tentative est encore prohibitif pour le moment (6 500 années CPU et 100 années GPU) Voir aussi Valerie Anita Aurora dans " Durée de vie des fonctions de hachage cryptographique ".
• Comme indiqué précédemment, il ne s'agit pas de sécurité ou de confiance, mais de l'intégrité des données (déduplication et détection d'erreurs) qui peut être facilement détectée par un git fsck, comme l'a mentionné Linus Torvalds aujourd'hui. git fsckavertirait d'un message de validation avec des données opaques cachées après un NUL(bien qu'il NULne soit pas toujours présent dans un fichier frauduleux ).
  Tout le monde ne s'allume pas transfer.fsck, mais GitHub le fait: toute poussée serait abandonnée dans le cas d'un objet mal formé ou d'un lien rompu. Bien que ... il y a une raison pour laquelle ce n'est pas activé par défaut .
• un fichier pdf peut avoir des données binaires arbitraires que vous pouvez modifier pour générer un SHA-1 entrant en collision, par opposition au code source falsifié.
  Le problème réel de la création de deux référentiels Git avec le même hachage de validation de tête et un contenu différent. Et même alors, l' attaque reste alambiquée .
• Linus ajoute :

  L' intérêt d'un SCM est qu'il ne s'agit pas d'un événement ponctuel, mais d'une histoire continue. Cela signifie également fondamentalement qu'une attaque réussie doit fonctionner dans le temps et ne pas être détectable.
  Si vous pouvez tromper un SCM une fois, insérer votre code et qu'il soit détecté la semaine prochaine, vous n'avez rien fait d'utile. Tu t'es seulement brûlé.

Joey Hess essaie ces pdf dans un repo Git et il a trouvé :

Cela inclut deux fichiers avec le même SHA et la même taille, qui obtiennent des blobs différents grâce à la façon dont git ajoute l'en-tête au contenu.

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

Bien que l'ajout de données identiques à ces fichiers en collision génère d'autres collisions, les données en avance non.

Ainsi, le principal vecteur d'attaque (falsification d'un commit) serait :

• Générez un objet commit régulier;
• utiliser l'intégralité de l'objet commit + NUL comme préfixe choisi, et
• utilisez l'attaque de collision à préfixe identique pour générer les bons / mauvais objets en collision.
• ... et cela est inutile car les bons et les mauvais objets de commit pointent toujours vers le même arbre!

De plus, vous pouvez déjà détecter et détecter les attaques par collision cryptanalytique contre SHA-1 présentes dans chaque fichier avec cr-marcstevens/sha1collisiondetection

L'ajout d'une vérification similaire dans Git lui - même aurait un coût de calcul .

À propos du changement de hachage, Linux commente :

La taille du hachage et le choix de l'algorithme de hachage sont des problèmes indépendants.
Ce que vous feriez probablement est de basculer vers un hachage 256 bits, de l'utiliser en interne et dans la base de données native git, puis par défaut d' afficher uniquement le hachage sous la forme d'une chaîne hexadécimale de 40 caractères (un peu comme la façon dont nous abrégons déjà les choses dans de nombreuses situations).
De cette façon, les outils autour de git ne voient même pas le changement à moins qu'ils ne soient passés dans un --full-hashargument spécial " " (ou " --abbrev=64" ou autre) - la valeur par défaut étant que nous abrégons à 40).

Pourtant, un plan de transition (de SHA1 à une autre fonction de hachage) serait toujours complexe , mais activement étudié.
Une convert-to-object_idcampagne est en cours :

Mise à jour du 20 mars: GitHub détaille une éventuelle attaque et sa protection :

Les noms SHA-1 peuvent recevoir une approbation par le biais de divers mécanismes. Par exemple, Git vous permet de signer cryptographiquement un commit ou un tag. Cela ne signe que l'objet commit ou tag lui-même, qui à son tour pointe vers d'autres objets contenant les données de fichier réelles en utilisant leurs noms SHA-1. Une collision dans ces objets pourrait produire une signature qui semble valide, mais qui pointe vers des données différentes de celles prévues par le signataire. Dans une telle attaque, le signataire ne voit qu'une moitié de la collision et la victime voit l'autre moitié.

Protection:

La récente attaque utilise des techniques spéciales pour exploiter les faiblesses de l'algorithme SHA-1 qui trouvent une collision en beaucoup moins de temps. Ces techniques laissent un motif dans les octets qui peut être détecté lors du calcul du SHA-1 de l'une ou l'autre moitié d'une paire en collision.

GitHub.com effectue maintenant cette détection pour chaque SHA-1 qu'il calcule et abandonne l'opération s'il existe des preuves que l'objet est la moitié d'une paire en collision. Cela empêche les attaquants d'utiliser GitHub pour convaincre un projet d'accepter la moitié "innocente" de leur collision, ainsi que de les empêcher d'héberger la moitié malveillante.

Voir " sha1collisiondetection" de Marc Stevens

Encore une fois, avec Qit 2018 Git 2.16 ajoutant une structure représentant un algorithme de hachage, l'implémentation d'une transition vers un nouveau hachage a commencé.
Comme mentionné ci-dessus, le nouveau hachage pris en charge sera SHA-256 .

Je pense que les cryptographes feraient la fête.

Citation d'un 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.)

Il existe plusieurs modèles d'attaque différents pour les hachages comme SHA-1, mais celui généralement discuté est la recherche de collision, y compris l' outil HashClash de Marc Stevens .

"En 2012, l'attaque la plus efficace contre SHA-1 est considérée comme celle de Marc Stevens [34] avec un coût estimé à 2,77 millions de dollars pour casser une valeur de hachage unique en louant la puissance CPU des serveurs cloud."

Comme les gens l'ont souligné, vous pouvez forcer une collision de hachage avec git, mais cela n'écrasera pas les objets existants dans un autre référentiel. J'imagine mêmegit push -f --no-thin ne pas écraser les objets existants, mais pas sûr à 100%.

Cela dit, si vous pirater un dépôt distant , vous pouvez alors faire votre faux objet le plus ancien il y a , peut - être intégrer le code piraté dans un projet open source sur GitHub ou similaire. Si vous faites attention, vous pouvez peut-être introduire une version piratée téléchargée par les nouveaux utilisateurs.

Je soupçonne cependant que de nombreuses choses que les développeurs du projet pourraient faire pourraient exposer ou détruire accidentellement votre hack de plusieurs millions de dollars. En particulier, cela coûte beaucoup d'argent si un développeur, que vous n'avez pas piraté, exécute jamais ce qui précède git push --no-thinaprès avoir modifié les fichiers concernés, parfois même sans le--no-thin dépendre.