Que se passerait-il réellement si j'avais une collision de hachage lors de l'utilisation de git?

Par exemple, j'arrive à valider deux fichiers avec la même somme de contrôle sha1, est-ce que git le remarquerait ou corromprait l'un des fichiers?

Est-ce que git pourrait être amélioré pour vivre avec ça, ou devrais-je changer pour un nouvel algorithme de hachage?

(Veuillez ne pas dévier cette question en expliquant à quel point c'est improbable - Merci)

Choisir des atomes sur 10 lunes

Un hachage SHA-1 est une chaîne de 40 caractères hexadécimaux ... soit 4 bits par caractère fois 40 ... 160 bits. Maintenant, nous savons que 10 bits équivaut à environ 1000 (1024 pour être exact), ce qui signifie qu'il y a 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 hachages SHA-1 différents ... 10 ⁴⁸ .

De quoi est cet équivalent? Eh bien, la Lune est composée d'environ 10 ⁴⁷ atomes. Donc, si nous avons 10 lunes ... et que vous choisissez au hasard un atome sur l'une de ces lunes ... puis allez-y et choisissez à nouveau un atome aléatoire sur eux ... alors la probabilité que vous choisissiez le même atome deux fois , est la probabilité que deux commits git donnés aient le même hachage SHA-1.

En développant là-dessus, nous pouvons poser la question ...

De combien de commits avez-vous besoin dans un référentiel avant de commencer à vous inquiéter des collisions?

Cela concerne les «attaques d'anniversaire», qui à leur tour font référence au «paradoxe de l'anniversaire» ou au «problème de l'anniversaire», qui stipule que lorsque vous choisissez au hasard dans un ensemble donné, vous avez étonnamment besoin de quelques choix avant d'être plus probable qu'improbable d'avoir choisi quelque chose deux fois. Mais «étonnamment peu» est un terme très relatif ici.

Wikipédia a un tableau sur la probabilité de collisions avec Birthday Paradox . Il n'y a pas d'entrée pour un hachage de 40 caractères. Mais une interpolation des entrées pour 32 et 48 caractères nous amène dans la plage de 5 * 10 ²² git commits pour une probabilité de 0,1% de collision. C'est cinquante mille milliards de milliards de commits différents, ou cinquante Zettacommits , avant que vous n'ayez atteint même 0,1% de chances d'avoir une collision.

La somme des octets des hachages seuls pour ces commits représenterait plus de données que toutes les données générées sur Terre pendant un an, c'est-à-dire que vous auriez besoin de générer du code plus rapidement que YouTube diffuse la vidéo. Bonne chance avec ça. :RÉ

Le fait est qu'à moins que quelqu'un ne provoque délibérément une collision, la probabilité qu'une collision se produise au hasard est tellement faible que vous pouvez ignorer ce problème.

« Mais quand une collision ne se produit, alors ce qui se passe réellement? »

Ok, supposons que l'improbable se produise, ou supposons que quelqu'un ait réussi à personnaliser une collision de hachage SHA-1 délibérée . Que se passe-t-il alors?

Dans ce cas, il y a une excellente réponse où quelqu'un a expérimenté là-dessus . Je vais citer cette réponse:

1. Si un objet blob existe déjà avec le même hachage, vous n'obtiendrez aucun avertissement. Tout semble aller bien, mais lorsque vous poussez, que quelqu'un clone, ou que vous revenez, vous perdez la dernière version (conformément à ce qui est expliqué ci-dessus).
2. Si un objet d'arborescence existe déjà et que vous créez un objet blob avec le même hachage: tout vous 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.
3. Si un objet de validation existe déjà et que vous créez un objet blob avec le même hachage: identique à # 2 - corrompu
4. Si un objet blob existe déjà et que vous créez un objet de validation avec le même hachage, il échouera lors de la mise à jour de "ref".
5. Si un objet blob existe déjà et que vous créez un objet d'arborescence avec le même hachage. Il échouera lors de la création du commit.
6. Si un objet d'arborescence existe déjà et que vous créez un objet de validation avec le même hachage, il échouera lors de la mise à jour de "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 référencera la mauvaise arborescence.
8. Si un objet de validation existe déjà et que vous créez un objet de validation avec le même hachage, tout semblera correct. Mais lorsque vous vous engagez, la validation ne sera jamais créée et le pointeur HEAD sera déplacé vers une ancienne validation.
9. Si un objet de validation existe déjà et que vous créez un objet d'arborescence avec le même hachage, il échouera lors de la création de la validation.

Comme vous pouvez le constater, certains cas ne sont pas bons. Surtout les cas n ° 2 et n ° 3 gâchent votre référentiel. Cependant, il semble que le défaut reste dans ce référentiel, et l'attaque / improbabilité bizarre ne se propage pas à d'autres référentiels.

De plus, il semble que le problème des collisions délibérées soit reconnu comme une menace réelle, et par exemple, GitHub prend des mesures pour l'empêcher .

Si deux fichiers ont la même somme de hachage dans git, il traitera ces fichiers comme identiques. Dans le cas absolument improbable que cela se produise, vous pouvez toujours revenir en arrière d'un commit et changer quelque chose dans le fichier pour qu'il ne se heurte plus ...

Voir le message de Linus Torvalds dans le fil de discussion «Vous commencez à penser à sha-256?» dans la liste de diffusion git .

Il n'est pas vraiment possible de répondre à cette question avec le bon "mais" sans expliquer aussi pourquoi ce n'est pas un problème. Ce n'est pas possible de faire cela sans vraiment avoir une bonne idée de ce qu'est vraiment un hash. C'est plus compliqué que les cas simples auxquels vous pourriez avoir été exposé dans un programme CS.

Il y a ici un malentendu fondamental de la théorie de l'information. Si vous réduisez une grande quantité d'informations en une plus petite quantité en rejetant une certaine quantité (c'est-à-dire un hachage), il y aura un risque de collision directement lié à la longueur des données. Plus les données sont courtes, moins elles seront probables. Maintenant, la grande majorité des collisions seront du charabia, ce qui les rendra beaucoup plus susceptibles de se produire (vous ne vérifieriez jamais le charabia ... même une image binaire est quelque peu structurée). En fin de compte, les chances sont faibles. Pour répondre à votre question, oui, git les traitera de la même manière, changer l'algorithme de hachage n'aidera pas, il faudra une "deuxième vérification" d'une sorte, mais finalement, vous auriez besoin d'autant de données de "vérification supplémentaire" comme la longueur des données pour être sûr à 100% ... gardez à l'esprit que vous seriez 99,99999 .... à un très long nombre de chiffres ... sûr avec une simple vérification comme vous le décrivez. Les SHA-x sont des hachages cryptographiquement forts, ce qui signifie qu'il n'est généralement pas difficile de créer intentionnellement deux ensembles de données source qui sont tous les deux TRÈS SIMILAIRES et ont le même hachage. Un peu de changement dans les données devrait créer plus d'un (de préférence autant que possible) bits de changement dans la sortie de hachage, ce qui signifie également qu'il est très difficile (mais pas tout à fait impossible) de revenir du hachage à l'ensemble complet de collisions, et ainsi extraire le message d'origine de cet ensemble de collisions - toutes sauf quelques-unes seront du charabia, et de celles qui ne le sont pas, il y en a encore un grand nombre à parcourir si la longueur du message est d'une longueur significative. L'inconvénient d'un hachage cryptographique est qu'il est lent à calculer ... en général.

Alors, qu'est-ce que tout cela signifie pour Git? Pas tant. Les hachages se font si rarement (par rapport à tout le reste) que leur pénalité de calcul est globalement faible pour les opérations. Les chances de frapper une paire de collisions sont si faibles que ce n'est pas une chance réaliste de se produire et de ne pas être détecté immédiatement (c'est-à-dire que votre code arrêterait probablement soudainement la construction), permettant à l'utilisateur de résoudre le problème (sauvegarder une révision, et effectuez à nouveau le changement, et vous obtiendrez presque certainement un hachage différent à cause du changement d'heure, qui alimente également le hachage dans git). Il y a plus de chances que ce soit un réel problème pour vous si vous stockez des binaires arbitraires dans git, ce qui n'est pas vraiment son modèle d'utilisation principal. Si vous voulez faire cela ... il vaut probablement mieux utiliser une base de données traditionnelle.

Il n'est pas faux de penser à cela - c'est une bonne question que beaucoup de gens se font passer pour "si peu probable que cela ne vaille pas la peine d'y penser" - mais c'est vraiment un peu plus compliqué que cela. Si cela se produit, cela devrait être très facilement détectable, ce ne sera pas une corruption silencieuse dans un flux de travail normal.

Est-ce que git pourrait être amélioré pour vivre avec ça, ou devrais-je changer pour un nouvel algorithme de hachage?

Les collisions sont possibles pour n'importe quel algorithme de hachage, donc changer la fonction de hachage n'exclut pas le problème, cela le rend juste moins susceptible de se produire. Vous devriez donc choisir une très bonne fonction de hachage (SHA-1 l'est déjà, mais vous avez demandé à ne pas être dit :)

Vous pouvez voir une bonne étude dans " Comment Git gérerait-il une collision SHA-1 sur un objet blob? ".

Puisqu'une collision SHA1 est maintenant possible (comme je le fais référence dans cette réponse avec shattered.io ), sachez que Git 2.13 (Q2 2017) améliorera / atténuera la situation actuelle avec une variante de "détection de tentative de création de collisions" de l' implémentation SHA-1 par Marc Stevens (CWI) et Dan Shumow (Microsoft) .

Voir commit f5f5e7f , commit 8325e43 , commit c0c2006 , commit 45a574e , commit 28dc98e (16 mars 2017) par Jeff King ( peff) .
^{(Fusionné par Junio ​​C Hamano - gitster- dans commit 48b3693 , 24 mars 2017)}

Makefile: faire DC_SHA1la valeur par défaut

Nous utilisions par défaut l'implémentation SHA1 de la bibliothèque OpenSSL.
Comme nous essayons d'être prudents contre les attaques par collision après la récente annonce "brisée", changez la valeur par défaut pour encourager les gens à utiliser plutôt l'implémentation DC_SHA1.
Ceux qui veulent utiliser l'implémentation d'OpenSSL peuvent le demander explicitement en OPENSSL_SHA1=YesPleaseexécutant " make".

Nous n'avons pas réellement de collision d'objet Git, donc le mieux que nous puissions faire est d'exécuter l'un des PDF brisés via test-sha1. Cela devrait déclencher le contrôle de collision et mourir.

Git pourrait-il être amélioré pour vivre avec cela, ou devrais-je passer à un nouvel algorithme de hachage?

Mise à jour de décembre 2017 avec Git 2.16 (Q1 2018): cet effort de prise en charge d'un SHA alternatif est en cours: voir " Pourquoi Git n'utilise-t-il pas un SHA plus moderne? ".

Vous pourrez utiliser un autre algorithme de hachage: SHA1 n'est plus le seul pour Git.

Git 2.18 (Q2 2018) documente ce processus.

Voir commit 5988eb6 , commit 45fa195 (26 mars 2018) par Ævar Arnfjörð Bjarmason ( avar) .
^{(Fusionné par Junio ​​C Hamano - gitster- dans commit d877975 , 11 avril 2018)}

doc hash-function-transition: clarifier ce que signifie SHAttered

Essayez de clarifier ce que l'attaque SHAttered signifie en pratique pour Git.
La version précédente du texte ne faisait aucune mention du fait que Git avait déjà une atténuation pour cette attaque spécifique, qui, selon les chercheurs de SHAttered, détectera les attaques par collision cryptanalytique.

J'ai peut-être mal compris certaines nuances, mais pour autant que je sache, ce nouveau texte résume avec précision la situation actuelle avec SHA-1 dans git. Ie git n'utilise plus vraiment SHA-1, il utilise Hardened-SHA-1 (ils produisent juste les mêmes sorties 99,99999999999 ...% du temps).

Ainsi, le texte précédent était incorrect en affirmant que:

[...] En conséquence [de SHAttered], SHA-1 ne peut plus être considéré comme sécurisé cryptographiquement [...]

Ce n'est pas le cas. Nous avons une mesure d'atténuation contre SHAttered, mais nous considérons qu'il est prudent de s'orienter vers NewHashdes vulnérabilités futures dans SHA-1 ou Hardened-SHA-1.

Ainsi, la nouvelle documentation se lit maintenant:

Git v2.13.0 et les versions ultérieures sont ensuite déplacées vers une implémentation SHA-1 renforcée par défaut, qui n'est pas vulnérable à l'attaque SHAttered.

Ainsi Git a en effet déjà migré vers un nouveau hachage qui n'est pas SHA-1 et ne partage pas ses vulnérabilités, sa nouvelle fonction de hachage se trouve juste à produire exactement la même sortie pour toutes les entrées connues, à l'exception de deux PDF publiés par le SHAttered chercheurs, et la nouvelle implémentation (écrite par ces chercheurs) prétend détecter les futures attaques par collision cryptanalytique.

Quoi qu'il en soit, il est considéré comme prudent de passer de toute variante de SHA-1 à un nouveau hachage. Il n'y a aucune garantie que les futures attaques contre SHA-1 ne seront pas publiées à l'avenir, et ces attaques peuvent ne pas avoir d'atténuation viables.

Si SHA-1 et ses variantes devaient être vraiment cassés, la fonction de hachage de Git ne pourrait plus être considérée comme sécurisée cryptographiquement. Cela aurait un impact sur la communication des valeurs de hachage, car nous ne pouvions pas croire qu'une valeur de hachage donnée représentait la bonne version connue du contenu que le locuteur voulait.

Remarque: ce même document maintenant (Q3 2018, Git 2.19) fait explicitement référence au "nouveau hachage" en tant que SHA-256 : voir " Pourquoi Git n'utilise-t-il pas un SHA plus moderne? ".

Google affirme maintenant que la collision SHA-1 est possible sous certaines conditions préalables: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Puisque git utilise SHA-1 pour vérifier l'intégrité des fichiers, cela signifie que l'intégrité des fichiers dans git est compromise.

OMI, git devrait certainement utiliser un meilleur algorithme de hachage car une collision délibérée est désormais possible.

Une collision de hachage est si peu probable qu'elle est époustouflante! Les scientifiques du monde entier s'efforcent d'en atteindre un, mais n'y sont pas encore parvenus. Pour certains algorithmes tels que MD5, ils ont réussi.

Quelles sont les chances?

SHA-256 a 2 ^ 256 hachages possibles. Cela fait environ 10 ^ 78 . Ou pour être plus graphique, les chances d'une collision sont d'environ

1: 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

Les chances de gagner à la loterie est d' environ 1: 14 Mio . La chance d'une collision avec SHA-256 est comme gagner à la loterie sur 11 jours consécutifs !

Explication mathématique: 14000000 ^ 11 ~ 2 ^ 256

De plus, l' univers compte environ 10 ^ 80 atomes. C'est juste 100 fois plus qu'il n'y a de combinaisons SHA-256.

Collision MD5 réussie

Même pour MD5, les chances sont minimes. Cependant, les mathématiciens ont réussi à créer une collision:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

a le même MD5 que

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70

Cela ne signifie pas que MD5 est moins sûr maintenant que son algorithme est fissuré. Vous pouvez créer des collisions MD5 exprès, mais le risque d'une collision MD5 accidentelle est toujours de 2 ^ 128, ce qui est encore beaucoup.

Conclusion

Vous n'avez pas à vous soucier des collisions. Les algorithmes de hachage sont le deuxième moyen le plus sûr de vérifier la similitude des fichiers. Le seul moyen le plus sûr est une comparaison binaire.

Eh bien, je suppose que nous savons maintenant ce qui se passerait - vous devriez vous attendre à ce que votre référentiel soit corrompu ( source ).

J'ai récemment trouvé une publication du 29/04/2013 dans un groupe de discussion BSD à

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

où l'affiche prétend:

J'ai rencontré une fois une collision de hachage, en utilisant git rebase.

Malheureusement, il ne fournit aucune preuve de sa réclamation. Mais peut-être que vous aimeriez essayer de le contacter et lui poser des questions sur ce supposé incident.

Mais à un niveau plus général, en raison de l'attaque d'anniversaire, une chance de collision de hachage SHA-1 est de 1 en pow (2, 80).

Cela semble beaucoup et est certainement bien plus que le nombre total de versions de fichiers individuels présents dans tous les référentiels Git du monde combinés.

Cependant, cela ne s'applique qu'aux versions qui restent réellement dans l'historique des versions.

Si un développeur compte beaucoup sur le rebasage, chaque fois qu'un rebase est exécuté pour une branche, tous les commits de toutes les versions de cette branche (ou partie rebasée de la branche) reçoivent de nouveaux hachages. La même chose est vraie pour chaque fichier modifié avec "git filter-branch". Par conséquent, "rebase" et "filter-branch" peuvent être de gros multiplicateurs pour le nombre de hachages générés au fil du temps, même si tous ne sont pas réellement conservés: Fréquemment, après rebasage (en particulier dans le but de "nettoyer" une branche ), la branche d'origine est jetée.

Mais si la collision se produit pendant le rebase ou la branche de filtre, elle peut encore avoir des effets néfastes.

Une autre chose serait d'estimer le nombre total d'entités hachées dans les référentiels git et de voir à quelle distance elles sont de pow (2, 80).

Disons que nous avons environ 8 milliards de personnes, et toutes utiliseraient git et conserveraient leurs versions dans 100 dépôts git par personne. Supposons en outre que le référentiel moyen a 100 commits et 10 fichiers, et qu'un seul de ces fichiers change par commit.

Pour chaque révision, nous avons au moins un hachage pour l'objet tree et l'objet commit lui-même. Avec le fichier modifié, nous avons 3 hachages par révision, et donc 300 hachages par référentiel.

Pour 100 dépôts de 8 milliards de personnes, cela donne du pow (2, 47) qui est encore loin d'être du pow (2, 80).

Cependant, cela n'inclut pas l'effet multiplicateur supposé mentionné ci-dessus, car je ne sais pas comment l'inclure dans cette estimation. Cela pourrait peut-être augmenter considérablement les chances de collision. Surtout si de très grands référentiels qui ont une longue histoire de commit (comme le noyau Linux) sont rebasés par de nombreuses personnes pour de petits changements, qui créent néanmoins des hachages différents pour tous les commits affectés.