Question Comment Git gérerait 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 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, comment Git gérerait-il 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.


492
2018-02-22 09:42


origine


Réponses:


J'ai fait une expérience pour savoir exactement comment Git se comporterait dans ce cas. Ceci 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 git de reconstruction:

--- 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 quand vous poussez, quelqu'un clone, ou vous retournez, vous perdrez la dernière version (en ligne avec ce qui est expliqué ci-dessus).
  2. Si un objet arbre existe déjà et que vous faites un blob avec le même hachage: Tout semblera normal, jusqu'à ce que vous essayiez de pousser ou que quelqu'un clone votre dépôt. Ensuite, vous verrez que le repo est corrompu.
  3. Si un objet commit existe déjà et que vous faites 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 du "ref".
  5. Si un blob existe déjà et que vous créez un objet arborant le même hachage. Il échouera lors de la création du commit.
  6. Si un objet arbre existe déjà et que vous créez un objet commit avec le même hachage, il échouera lors de la mise à jour de "ref".
  7. Si un objet d'arbre existe déjà et que vous créez un objet d'arbre avec le même hachage, tout semblera correct. Mais quand vous vous engagez, tout le référentiel référencera le mauvais arbre.
  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 vous engagez, le commit ne sera jamais créé et le pointeur HEAD sera déplacé vers un ancien commit.
  9. Si un objet commit existe déjà et que vous créez un objet arbre avec le même hachage, il échouera lors de la création de la validation.

Pour # 2 vous aurez typiquement une erreur comme celle-ci quand vous lancez "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 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 "git commit" à nouveau 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 "m'inquiète" c'est que dans deux cas (2,3) le dépôt 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 ok, car il s'arrêtera avec une erreur. Je suppose que ce serait mieux si elle échouait avec une erreur au moins dans tous les cas.


635
2018-01-04 20:15



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

Cette ancienne réponse (2006) de Linus pourrait encore être pertinent:

Nan. S'il a le même SHA1, cela signifie que lorsque nous recevons l'objet de l'autre bout, nous le ferons ne pas écraser l'objet que nous avons déjà.

Donc, ce qui se passe est que si jamais nous voyons une collision, l'objet "plus tôt" dans un référentiel particulier finira toujours par surcharger. 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é, alors que différents référentiels seront d'accord sur ce qui est "plus tôt" dans le cas d'ascendance directe. objet est venu à travers des branches distinctes et non directement liées, deux repos différents peuvent évidemment avoir obtenu les deux objets dans un ordre différent.

Cependant, le "override override" est tout à fait ce que vous voulez du point de vue de la sécurité: souvenez-vous que le modèle git est que vous ne devriez faire confiance qu'à votre posséder 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 avez déjà, et en tant que tels, il serait faux de permettre à un nouvel objet de   remplacez un ancien.

Donc, vous avez deux cas de collision:

  • la genre involontaire, où vous êtes en quelque sorte très malchanceux, et deux fichiers finissent par avoir le même SHA1.
      À ce stade, ce qui se passe est que lorsque vous commettez 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-ou-index finira par pointer vers le vieux objet.
      Vous ne 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 une extraction), 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 à propos de la collision par inadvertance ..
      Tout d'abord, permettez-moi de rappeler aux gens que le type de collision par inadvertance est vraiment vraiment Il est fort probable que nous ne le verrons jamais dans l’histoire complète de l’univers.
      Mais si ça arrive, ce n'est pas la fin du monde: Ce que vous devez probablement faire, c'est simplement changer le fichier qui est entré en collision légèrement, et forcer simplement un nouvel commit avec le contenu modifié (ajouter un commentaire disant "/* This line added to avoid collision */") Ensuite, enseignez git à propos de la magie SHA1 qui s'est avérée dangereuse.
      Ainsi, 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 attaquant type de collision parce que quelqu'un a cassé (ou brutalement forcé) SHA1.
      Celui-ci est clairement un lot plus probable que le type involontaire, mais par définition, il est toujours un dépôt "distant". Si l'attaquant avait accès au dépôt local, il aurait des moyens beaucoup plus faciles de vous faire du tort.
      Donc, dans ce cas, la collision est entièrement un non-problème: vous obtiendrez un "mauvais" référentiel différent de celui que l’attaquant a voulu, mais puisque vous n'utiliserez jamais réellement son objet en collision, il est Littéralement pas différent de l'attaquant n'ayant pas trouvé de collision du tout, mais en utilisant simplement l'objet que vous aviez déjà (c'est-à-dire qu'il est équivalent à 100% à la collision "triviale" du fichier identique générant le même SHA1).

le question de l'utilisation de SHA-256 est régulièrement mentionné, mais n'agit pas pour le moment.


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

gitbrute brute-force une paire d'horodateurs auteur + committer de telle sorte que le commit git obtenu ait le préfixe désiré.

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


Daniel Dinnyes fait remarquer dans les commentaires à 7.1 Outils Git - Sélection de révision, qui comprend:

Une probabilité plus élevée existe que chaque membre de votre équipe de programmation soit attaqué et tué par des loups dans des incidents sans rapport le même soir.


Même plus récemment (février 2017) shattered.io démontré la possibilité de forger une collision SHA1:
(voir beaucoup plus dans mon réponse séparée, y compris le post Google+ de Linus Torvalds)

  • 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 années de calculs à un seul processeur et 110 années de calculs à un seul GPU.
  • b / forgerait un fichier (avec le même SHA1), mais avec la contrainte supplémentaire son contenu et la taille produirait le même SHA1 (une collision sur le contenu seul ne suffit pas): voir "Comment est calculé le git hash?"): une le blob SHA1 est calculé en fonction du contenu et Taille.

Voir "Durée de vie des fonctions de hachage cryptographiques" de 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 séparée ci-dessous.


233
2018-02-22 09:53



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 déjà l'objet précédent dans votre base de données Git et supposera qu'il a déjà été écrit. Si vous essayez à nouveau de récupérer cet objet, vous obtiendrez toujours les données du premier objet.

Donc, cela n'échouerait pas, mais cela ne sauverait pas non plus votre nouvel objet.
Je ne sais pas comment cela se passerait 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 l'ensemble de l'histoire du noyau Linux (1 million d'objets Git) et le poussait dans un énorme dépôt Git, il faudrait 5 ans ce référentiel contenait suffisamment d'objets pour avoir une probabilité de 50% qu'une seule collision d'objet SHA-1. Une probabilité plus élevée existe que chaque membre de votre équipe de programmation soit attaqué et tué par des loups dans des incidents sans rapport le même soir.


41
2018-02-22 09:52



Ajouter à ma réponse précédente de 2012, il y a maintenant (cinq ans plus tard, février 2017) un exemple de collision SHA-1 avec shattered.ion où vous pouvez créer deux fichiers PDF en collision: vous obtenez une signature numérique SHA-1 sur le premier fichier PDF qui peut également être utilisée comme une signature valide sur le deuxième fichier PDF.
Voir également "À la porte de la mort depuis 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 par le contenu comme git.

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

(3) Et enfin, il y a en fait une transition relativement simple vers un autre hachage qui ne va pas casser le monde - ou même de vieux dépôts git.

En ce qui concerne cette transition, voir Q1 2018 Git 2.16 ajouter une structure représentant l'algorithme de hachage. La mise en œuvre de cette transition a commencé.


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

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   différents blobs grâce à la façon dont git ajoute l’en-tête à la   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

L'ajout de données identiques à ces fichiers en collision génère   d'autres collisions, les données qui précèdent ne le sont pas.

Alors le le principal vecteur d'attaque (forger un commit) serait:

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

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

Ajout d'un chèque similaire dans Git lui-même aurait un coût de calcul.

En changeant le 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, c'est de passer à un hachage de 256 bits.   en interne et dans la base de données native git, puis par défaut seulement    montrer le hash comme une chaîne hexadécimale de 40 caractères (un peu comme   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, sauf si passé dans   certains spéciaux "--full-hash"argument (ou"--abbrev=64" ou peu importe -   le défaut étant que nous abrégeons à 40).

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


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

Les noms SHA-1 peuvent être assignés par le biais de divers mécanismes. Par exemple, Git vous permet de signer cryptographiquement un commit ou un tag. Cela ne fait que signer 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:

L'attaque récente utilise des techniques spéciales pour exploiter les faiblesses de l'algorithme SHA-1 qui détectent une collision beaucoup moins rapidement. 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'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 est prouvé 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 et de les empêcher 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é.


19
2018-02-25 00:05



Je pense que les cryptographes célébreraient.

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 en force brute nécessiterait 2 ^ 80 opérations.)


6
2018-02-22 10:37



Il existe plusieurs modèles d’attaque différents pour les hachages tels que SHA-1, mais la plus courante est la recherche de collision, y compris celle de Marc Stevens. HashClash outil.

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

Comme le font remarquer les gens, vous pouvez forcer une collision de hachage avec git, mais cela ne remplacera pas les objets existants dans un autre référentiel. J'imagine même git push -f --no-thin ne va pas écraser les objets existants, mais pas sûr à 100%.

Cela dit, si vous piratez un dépôt distant, vous pouvez faire de votre faux objet le plus ancien , 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 téléchargée par les nouveaux utilisateurs.

Je soupçonne cependant que beaucoup de 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 pèse lourd si un développeur, que vous n'avez pas piraté, exécute ce qui précède. git push --no-thin après avoir modifié les fichiers affectés, parfois même sans --no-thin en fonction, dépendemment.


5
2017-12-19 11:28