Comment git gérerait-il une collision SHA-1 sur un blob?
Cela ne s'est probablement jamais produit dans le monde réel, et peut ne jamais arriver, mais considérons ceci: disons que vous avez un dépôt git, faites un commit, et soyez très malchanceux: l'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érerait-il cela? Simplement pas? 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.
6 réponses
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 + suivant.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);
}
Ensuite, j'ai fait quelques commits et j'ai remarqué ce qui suit.
- si un blob existe déjà avec le même hachage, vous n'obtiendrez aucun avertissement. Tout semble être ok, mais quand vous poussez, quelqu'un clone, ou vous revenir, vous perdrez la dernière version (en ligne avec ce qui est expliqué ci-dessus).
- si un objet tree 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 repo est corrompu.
- si un objet commit existe déjà et que vous créez un blob avec le même hachage: identique à #2-corrupt
- 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 du "ref".
- si un blob existe déjà et que vous créez un objet arborescence avec le même hachage. Il échouera lors de la création du commit.
- si un objet arborescence existe déjà et que vous créez un objet commit avec le même hachage, il échouera lors de la mise à jour du "ref".
- si un objet tree existe déjà et que vous créez un objet tree avec le même hachage, tout semblera correct. Mais lorsque vous validez, tout le référentiel référencera le mauvais arbre.
- si un l'objet commit existe déjà et vous faites un objet commit avec le même hachage, tout semblera ok. Mais lorsque vous validez, le commit ne sera jamais créé et le pointeur HEAD sera déplacé vers un ancien commit.
- si un objet commit existe déjà et que vous créez un objet arborescence 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 et puis "git checkout fichier.txt".
Pour #4 et # 6, Vous obtiendrez généralement une erreur comme ceci:
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 simplement taper à nouveau "git commit" car cela créera un nouveau hachage (à cause de l'horodatage Modifié)
Pour #5 et # 9, Vous obtiendrez généralement une erreur comme ceci:
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 me "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 ok, mais le contenu du référentiel est différent de ce que vous attendez. Les personnes clonant ou tirant auront un contenu différent de ce que vous avez. Les cas 4,5,6 et 9 sont ok, car il s'arrêtera avec une erreur. Je suppose que ce serait mieux si cela échouait avec une erreur au moins dans tous les cas.
Réponse originale (2012) (voir shattered.io 2017 sha1 collision ci-dessous)
Cette réponse ancienne (2006) de Linus pourrait toujours être pertinente:
Non. S'il a le même SHA1, cela signifie que lorsque nous recevons l'objet de l'autre extrémité, nous Pas écraserons l'objet que nous avons déjà.
Donc, ce qui se passe, c'est que si jamais nous voyons une collision, l'objet "précédent" dans un référentiel particulier finira toujours par être remplacé. Mais note 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 alors que différents référentiels seront d'accord sur ce qui est "plus tôt" dans le cas de l'ascendance directe, si l'objet est venu par des branches séparées et non directement liées, deux repos différents peuvent évidemment avoir obtenu les deux objets
Cependant, le "earlier will override" est très bien ce que vous voulez du point de vue de la sécurité: rappelez-vous que le modèle git est-ce que vous devez principalement faire confiance uniquement à votrepropre 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 faux d'autoriser un nouvel objet à remplacer une ancienne.Vous avez donc deux cas de collision:
Le type par inadvertance , où vous êtes en quelque sorte très très malchanceux, et deux fichiers finissent par avoir le même SHA1.
À ce point, ce qui se passe 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 comme il correspond à un ancien objet, un nouvel objet ne sera pas créé, et le commit-or-index finit par pointer vers l'objetold .
Vous ne 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 jamais vous faites un diff au niveau de l'arbre (ou vous faites un clone ou un pull, ou forcez une caisse) vous remarquerez soudainement que ce fichier a changé en quelque chose complètement différent de ce que vous attendiez.
Donc, vous remarquerez généralement ce genre de collision assez rapidement.
Dans les nouvelles connexes, la question Est de savoir quoi faire au sujet de la collision par inadvertance..
Tout d'abord, permettez-moi de rappeler aux gens que le type de collision par inadvertance est vraiment vraimentvraiment sacrément improbable, donc nous allons tout à fait probablement jamais voir dans l'histoire de l'univers.
Mais Si cela arrive, ce n'est pas la fin du monde: ce que vous auriez probablement à faire, c'est simplement changer le fichier qui est légèrement entré en collision, et forcer un nouveau commit avec le contenu modifié (ajouter un commentaire disant "/* This line added to avoid collision */") et ensuite enseigner à git le sha1 magique qui s'est
Donc, sur quelques millions d'années, peut-être que nous devrons ajouter une ou deux valeurs SHA1 "empoisonnées" à git. Il est très peu probable que ce soit un problème de maintenance;)Le type de collision attaquant parce que quelqu'un a cassé (ou brutalement forcé) SHA1.
Celui-ci est clairement un lot 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.
Donc dans ce cas, , la collision est entièrement non-problème: vous aurez un "mauvais" référentiel qui est différent de ce que l'attaquant voulait, mais puisque vous n'utiliserez jamais réellement son objet en collision, c'est littéralement pas différent de l'attaquant n'ayant tout simplement pas trouvé de collision , mais simplement en utilisant 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).
La question de l'utilisation de SHA-256 est régulièrement mentionnée, mais n'agit pas pour maintenant.
Remarque (Humour): vous pouvez forcer une validation à un particulier SHA1 préfixe, avec le projet gitbrute à partir de Brad Fitzpatrick (bradfitz).
Gitbrute brute-force une paire d'horodatages author+committer de telle sorte que le commit git résultant ait le préfixe souhaité.
Exemple: https://github.com/bradfitz/deadbeef
Daniel Dinnyes points dans les commentaires pour 7.1 outils Git-sélection de révision , qui comprend:
Il existe une probabilité plus élevée que chaque membre de votre équipe de programmation soit attaqué et tué par des loups dans des incidents non liés la même nuit.
, Même le plus récemment (février 2017) shattered.io démontré la possibilité de forger une SHA1 collision:
(voir beaucoup plus dans mon réponse séparée, y compris Google+de Linus Torvalds post)
- a / nécessite toujours plus de 9 223 372 036 854 775 808 calculs SHA1. Cela a pris la puissance de traitement équivalente à 6 500 ans de calculs à un seul processeur et 110 ans de calculs à un seul GPU.
- B / forgeerait un fichier (avec le même SHA1), mais avec la contrainte supplémentaire son contenu et la taille produiraient le même SHA1 (une collision sur le contenu seul ne suffit pas): voir "comment le hachage git est-il calculé?"): un blob SHA1 est calculé en fonction du contenu et Taille .
Voir " durées de vie des fonctions de hachage cryptographiques " depuis Valerie Anita Aurora pour plus.
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 de sécurité.
Aussi parce que c'était cool
Voir plus dans mon réponse distincte ci-dessous.
Selon Pro Git:
Si vous validez 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 de vérifier à nouveau cet objet à un moment donné, vous obtiendrez toujours les données du premier objet.
Donc, il n'échouerait pas, mais il ne sauvegarderait pas votre nouvel objet non plus.
Je ne sais pas comment cela aurait l'air sur la ligne de commande, mais ce serait certainement déroutant.
Un peu plus bas, 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 tous les 6,5 milliards d'humains sur Terre programmaient, 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 Git dans le dépôt, il faudrait 5 ans avant que ce dépôt contienne suffisamment d'objets pour avoir une probabilité de 50% d'une collision d'objet SHA-1 unique. Il existe une probabilité plus élevée que chaque membre de votre équipe de programmation soit attaqué et tué 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év. 2017, cinq ans plus tard), un exemple de collision SHA-1 réelle avec shattered.ion où vous pouvez créer deux fichiers PDF en collision: c'est-à-dire obtenir une signature numérique SHA-1 sur le premier fichier PDF qui peut également être abusé comme une signature valide sur le second fichier PDF.
Voir aussi ", À la porte de la mort pendant des années, largement utilisé SHA1 fonction est maintenant dead", et ce illustration .
Mise à jour 26 de février: Linus a confirmé les points suivants dans un message Google + :
(1) Tout d'abord-le ciel ne tombe pas. Il y a une grande différence entre l'utilisation d'un hachage cryptographique pour des choses comme la signature de sécurité, et l'utilisation d'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 à atténuer contre, et il y a déjà eu deux ensembles de correctifs affichés pour cette atténuation.
(3) et enfin, il y a en fait une transition assez simple vers un autre hachage qui ne cassera pas le monde - ou même les anciens dépôts git.
En ce qui concerne cette transition, voir le Q1 2018 git 2.16 ajout d'une structure représentant l'algorithme de hachage. La mise en œuvre de cette transition a commencé.
Réponse originale (25ème de Février) Mais:
- cela permet de forger un blob, mais le SHA-1 de l'arbre changerait toujours puisque la taille du blob forgé pourrait ne pas être la même que celle d'origine: voir " Comment le hachage git est-il calculé?"; un blob SHA1 est calculé en fonction du contenu et de la taille .
Il a un problème pourgit-svnbien que . Ou plutôt avec svn lui-même, comme vu ici. - Comme je l'ai mentionné dans ma réponse originale , le le coût d'une telle tentative est encore prohibitif pour l'instant (6 500 années CPU et 100 années GPU) Voir aussi Valerie Anita Aurora dans "durées de vie des fonctions de hachage cryptographique".
- Comme indiqué précédemment, ce ne concerne pas la sécurité ou la confiance, mais 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 mentionné par Linus Torvalds aujourd'hui. {[2] } avertirait d'un message de validation avec des données opaques cachées après unNUL(bien queNULn'est pas toujours présent dans un frauduleuses fichier).
Tout le monde ne s'allume pastransfer.fsck, mais GitHub le fait: toute poussée serait annulée dans le cas d'un objet mal formé ou d'un lien cassé. Bien... il y a une raison pour laquelle n'est pas activé par défaut . - un fichier pdf peut contenir des données binaires arbitraires que vous pouvez modifier pour générer un SHA-1 en collision, par opposition au code source falsifié.
Le problème réel dans la création de deux Git dépôts avec la même tête commettre hachage et des contenus différents. Et même alors, l'attaque reste alambiquée . -
Linus ajoute:
L'ensemble point D'un SCM est qu'il ne s'agit pas d'un événement ponctuel, mais une constante de l'histoire. Cela signifie aussi fondamentalement qu'un une attaque réussie doit fonctionner au fil du temps et ne pas être détectable.
Si vous pouvez tromper un SCM une fois, insérez votre code, et il obtient détecté la semaine prochaine, vous n'ai rien fait d'utile. Vous n' brûlées vous-même.
Joey Hess essaie ces pdf en un repo Git et , il a trouvé:
Cela inclut deux fichiers avec le même SHA et la même taille, qui obtiennent différents blobs 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
Tout en ajoutant des données identiques à ces fichiers en collision génère autres collisions, ajout de données ne fait pas.
Donc le vecteur principal d'attaque (forger un commit) serait :
- génère un objet commit régulier;
- utilise l'objet commit entier + NUL comme préfixe choisi, et
- utilisez l'attaque de collision à préfixe identique pour générer les objets bons/mauvais qui entrent en collision.
- ... et c'est inutile car les bons et les mauvais objets commit pointent toujours vers le même arbre!
De plus, vous avez déjà peut et détecter des attaques de collision cryptanalytique contre SHA-1 présent dans chaque fichier avec cr-marcstevens/sha1collisiondetection
Ajouter une vérification similaire dans Git lui-même aurait un coût de calcul .
Lors de la modification du hachage, commentaires Linux :
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 passer à un hachage 256 bits, utilisez-le en interne et dans la base de données git native, et puis par défaut seulement afficher le hachage comme une chaîne hexadécimale de 40 caractères (un peu comme la façon dont nous déjà abréger les choses dans de nombreuses situations).
De cette façon les outils autour de git ne voient même pas le changement à moins d'être transmis un argument spécial "--full-hash" (ou "--abbrev=64" ou autre - la valeur par défaut étant que nous abrégeons à 40).
Pourtant, un plan de transition (de SHA1 à une autre fonction de hachage) serait toujours complexe , mais activement étudié.
Un convert-to-object_id campagne de est en cours:
Mise à jour du 20 mars: GitHub détaille une attaque possible et sa protection:
Les noms SHA-1 peuvent être attribués confiance par divers mécanismes. Par exemple, Git vous permet de signer cryptographiquement un commit ou une balise. 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 du signataire prévu. Dans une telle attaque, le signataire ne voit que la moitié de la collision, et la victime voit l'autre moitié.
Protection:
L'attaque récente 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 peuvent être détectés lors du calcul du SHA-1 de l'une ou l'autre moitié d'un collision paire.
GitHub.com effectue maintenant cette détection pour chaque SHA-1 qu'il calcule, et interrompt 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, tout en les empêchant d'héberger la moitié malveillante.
Voir "sha1collisiondetection" par Marc Stevens
Encore une fois, avec Q1 2018 git 2.16 en ajoutant une structure représentant l'algorithme de hachage, l'implémentation d'une transition vers un nouveau hachage a commencé.
Je pense que les cryptographes célébreraient.
Citation de article de Wikipédia sur SHA-1:
En février 2005, une attaque par 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.
Comme les gens l'ont souligné, vous pourriez forcer une collision de hachage avec git, mais cela n'écrasera pas les objets existants dans un autre référentiel. J'imagine que même git push -f --no-thin n'écrasera pas les objets existants, mais pas sûr à 100%.
Cela dit, si vous piratez un référentiel distant, vous pouvez faire de votre faux objet l'ancien là , en intégrant éventuellement du code piraté dans un projet open source sur github ou similaire. Si vous étiez prudent, vous pourriez peut-être introduire une version piratée que les nouveaux utilisateurs ont téléchargée.
Je soupçonne cependant que beaucoup les choses que les développeurs du projet pourraient faire pourraient exposer ou détruire accidentellement votre bidouille de plusieurs millions de dollars. En particulier, c'est beaucoup d'argent dans le drain si un développeur, que vous n'avez pas piraté, exécute jamais le git push --no-thin mentionné ci-dessus après avoir modifié les fichiers affectés, parfois même sans le --no-thin dépendant.