Jak Git poradziłby sobie z kolizją SHA-1 na obiekcie blob?

Prawdopodobnie nigdy się to nie zdarzyło w prawdziwym świecie i może się nigdy nie wydarzyć, ale zastanówmy się nad tym: powiedzmy, że masz repozytorium git, dokonaj zatwierdzenia i otrzymaj bardzo pecha: jedna z kropek kończy się tym samym SHA-1 jako kolejny, który jest już w twoim repozytorium. Pytanie brzmi, jak Git sobie z tym poradzi? Po prostu zawieść? Znajdź sposób na połączenie dwóch obiektów blob i sprawdzenie, który jest potrzebny zgodnie z kontekstem?

Bardziej łamigłówka niż rzeczywisty problem, ale uważam ten problem za interesujący.

Zrobiłem eksperyment, aby dowiedzieć się, jak Git zachowałby się w tym przypadku. Dotyczy to wersji 2.7.9 ~ rc0 + next.20151210 (wersja Debian). Zasadniczo właśnie zmniejszyłem rozmiar skrótu ze 160-bitowego do 4-bitowego, stosując następujący diff i przebudowując 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);
 }

Potem zrobiłem kilka zmian i zauważyłem następujące.

1. Jeśli obiekt blob już istnieje z tym samym hashem, nie otrzymasz żadnych ostrzeżeń. Wszystko wydaje się być w porządku, ale kiedy naciskasz, ktoś klonuje lub cofasz się, stracisz najnowszą wersję (zgodnie z tym, co wyjaśniono powyżej).
2. Jeśli obiekt drzewa już istnieje i utworzysz obiekt blob z tym samym hashem: wszystko będzie wydawać się normalne, dopóki nie spróbujesz pchnąć lub ktoś nie sklonuje twojego repozytorium. Wtedy zobaczysz, że repozytorium jest uszkodzone.
3. Jeśli obiekt zatwierdzenia już istnieje i utworzysz obiekt blob z tym samym hashem: taki sam jak # 2 - uszkodzony
4. Jeśli obiekt blob już istnieje i utworzysz obiekt zatwierdzenia z tym samym hashem, zakończy się niepowodzeniem podczas aktualizacji „ref”.
5. Jeśli obiekt blob już istnieje i utworzysz obiekt drzewa z tym samym hashem. Nie powiedzie się podczas tworzenia zatwierdzenia.
6. Jeśli obiekt drzewa już istnieje i utworzysz obiekt zatwierdzenia z tym samym hashem, zakończy się niepowodzeniem podczas aktualizacji „ref”.
7. Jeśli obiekt drzewa już istnieje i utworzysz obiekt drzewa z tym samym hashem, wszystko będzie wyglądało dobrze. Ale po zatwierdzeniu całe repozytorium będzie odnosić się do niewłaściwego drzewa.
8. Jeśli obiekt zatwierdzenia już istnieje i utworzysz obiekt zatwierdzenia z tym samym hashem, wszystko będzie wyglądało dobrze. Ale kiedy zatwierdzasz, zatwierdzenie nigdy nie zostanie utworzone, a wskaźnik HEAD zostanie przeniesiony do starego zatwierdzenia.
9. Jeśli obiekt zatwierdzenia już istnieje i utworzysz obiekt drzewa z tym samym hashem, zakończy się niepowodzeniem podczas tworzenia zatwierdzenia.

W przypadku nr 2 zazwyczaj pojawia się taki błąd, gdy uruchomisz polecenie „git push”:

error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin

lub:

error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)

jeśli usuniesz plik, a następnie uruchom „git checkout file.txt”.

W przypadku # 4 i # 6 zazwyczaj pojawia się taki błąd:

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

podczas uruchamiania „git commit”. W takim przypadku zazwyczaj możesz po prostu ponownie wpisać „git commit”, ponieważ spowoduje to utworzenie nowego skrótu (z powodu zmienionego znacznika czasu)

W przypadku nr 5 i nr 9 zazwyczaj występuje taki błąd:

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

podczas uruchamiania „git commit”

Jeśli ktoś spróbuje sklonować twoje uszkodzone repozytorium, zwykle zobaczy coś takiego:

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'

Martwi mnie to, że w dwóch przypadkach (2,3) repozytorium ulega uszkodzeniu bez ostrzeżeń, aw 3 przypadkach (1,7,8) wszystko wydaje się w porządku, ale zawartość repozytorium jest inna niż się tego spodziewasz być. Ludzie klonujący lub ciągnący będą mieć inną zawartość niż to, co masz. Przypadki 4,5,6 i 9 są w porządku, ponieważ zatrzyma się z błędem. Przypuszczam, że lepiej by było, gdyby błąd zawiódł co najmniej we wszystkich przypadkach.

Oryginalna odpowiedź (2012) (patrz shattered.iokolizja SHA1 2017 poniżej)

Ta stara odpowiedź Linusa (2006) może być nadal aktualna:

Nie. Jeśli ma ten sam SHA1, oznacza to, że gdy otrzymamy obiekt z drugiego końca, nie zastąpimy obiektu, który już mamy.

Tak więc dzieje się tak, że jeśli kiedykolwiek zobaczymy kolizję, „wcześniejszy” obiekt w danym repozytorium zawsze zostanie zastąpiony. Zauważ jednak, że „wcześniej” jest oczywiście dla repozytorium, w tym sensie, że sieć obiektów git generuje DAG, który nie jest w pełni uporządkowany, więc podczas gdy różne repozytoria uzgodnią, co jest „wcześniejsze” w przypadku bezpośredniego pochodzenia, jeśli obiekt przeszedł przez osobne i niezwiązane bezpośrednio gałęzie, dwa różne repo mogły oczywiście mieć dwa obiekty w innej kolejności.

Jednak „wcześniej zastąpi” jest bardzo dużo, co chcesz z punktu widzenia bezpieczeństwa: pamiętaj, że model jest git, że należy przede wszystkim zaufać tylko swoje własne repozytorium.
Więc jeśli wykonasz „ git pull”, nowe przychodzące obiekty są z definicji mniej godne zaufania niż obiekty, które już masz, i jako takie niewłaściwe byłoby zezwolenie nowemu obiektowi na zastąpienie starego.

Masz więc dwa przypadki kolizji:

• nieumyślne rodzaju , gdzie w jakiś sposób są bardzo pechowy, a dwa pliki skończyć o tej samej SHA1.
  W tym momencie dzieje się tak, że kiedy zatwierdzasz ten plik (lub wykonujesz „ git-update-index”, aby przenieść go do indeksu, ale jeszcze nie został on zatwierdzony), SHA1 nowej zawartości zostanie obliczony, ale ponieważ pasuje on do starego obiektu, nowy obiekt nie zostanie utworzony, a zatwierdzenie lub indeks kończy się wskazaniem na stary obiekt .
  Nie zauważysz od razu (ponieważ indeks będzie pasował do starego obiektu SHA1, a to oznacza, że ​​coś takiego jak „ git diff” użyje wypisanej kopii), ale jeśli kiedykolwiek zrobisz różnicę na poziomie drzewa (lub wykonasz klon lub pociągnij lub wymuś kasę) nagle zauważysz, że ten plik zmienił się na cośzupełnie inny niż się spodziewałeś.
  Dlatego na ogół dość szybko zauważysz tego rodzaju kolizje.
  W pokrewnych wiadomościach chodzi o to, co zrobić z nieumyślną kolizją.
  Po pierwsze, pozwólcie, że przypomnę ludziom, że taka nieumyślna kolizja jest naprawdę bardzo cholernie nieprawdopodobna, więc prawdopodobnie nigdy nie zobaczymy jej w całej historii Wszechświata.
  Ale jeśli tak się stanie, to nie koniec świata: najprawdopodobniej musiałbyś po prostu zmienić plik, który nieco się zderzył, i po prostu wymusić nowe zatwierdzenie ze zmienioną zawartością (dodaj komentarz z napisem „ /* This line added to avoid collision */”) i naucz git o magii SHA1, która okazała się niebezpieczna.
  Więc przez kilka milionów lat być może będziemy musieli dodać jedną lub dwie „zatrute” wartości SHA1 do git. Jest bardzo mało prawdopodobne, aby był to problem z konserwacją;)

• Rodzaj atakujący kolizji bo ktoś złamał (lub brute-przymusowe) SHA1.
  Ten jeden jest oczywiście dużo bardziej prawdopodobne niż w rodzaju niezamierzonego, ale z definicji to zawsze „remote” repozytorium. Gdyby atakujący miał dostęp do lokalnego repozytorium, miałby o wiele łatwiejsze sposoby, żeby cię spieprzyć.
  Tak więc w tym przypadku kolizja nie stanowi problemu : otrzymasz „złe” repozytorium, które różni się od zamierzonego przez atakującego, ale ponieważ nigdy nie użyjesz jego kolidującego obiektu, dosłownie nie różni się od napastnik po prostu nie znalazł kolizji, ale po prostu używając obiektu, który już miałeś (tj. jest w 100% równoważny „trywialnemu” zderzeniu identycznego pliku generującego ten sam SHA1).

Kwestia korzystania SHA-256 jest regularnie wspomniano, ale nie działają na Dotychczas (2012).
Uwaga: od 2018 r. I Gita 2.19 kod jest refaktoryzowany do użycia SHA-256.

Uwaga (humor): możesz wymusić zatwierdzenie określonego prefiksu SHA1 za pomocą projektu gitbrute z Brada Fitzpatricka ( bradfitz) .

gitbrute brute wymusza parę znaczników czasowych autor + osoba zatwierdzająca, tak aby wynikowy git commit miał żądany prefiks.

Przykład: https://github.com/bradfitz/deadbeef

Daniel Dinnyes zwraca uwagę w komentarzach do 7.1 Git Tools - Wybór wersji , który obejmuje:

Istnieje większe prawdopodobieństwo, że każdy członek zespołu programistycznego zostanie zaatakowany i zabity przez wilki w niepowiązanych zdarzeniach tej samej nocy.

Nawet ostatnio (luty 2017 r.) shattered.ioZademonstrowano możliwość sfałszowania zderzenia SHA1:
(zobacz więcej w mojej osobnej odpowiedzi , w tym postu Linusa Torvaldsa w Google+)

• a / nadal wymaga ponad 9 223 372 036 854 775 808 obliczeń SHA1. Zajęło to tyle samo mocy obliczeniowej, co 6500 lat obliczeń na jednym procesorze i 110 lat obliczeń na pojedynczym GPU.
• b / skułby jeden plik (z tym samym SHA1), ale z dodatkowym ograniczeniem jego zawartość i rozmiar dawałyby identyczny SHA1 (kolizja z samą treścią nie wystarczy): patrz „ Jak oblicza się hasz git? ”) : obiekt blob SHA1 jest obliczany na podstawie zawartości i rozmiaru .

Aby uzyskać więcej informacji, zobacz „ Żywotność kryptograficznych funkcji mieszających ” autorstwa Valerie Anita Aurora .
Na tej stronie zauważa:

Google spędził 6500 lat procesora i 110 lat procesora graficznego, aby przekonać wszystkich, że musimy przestać używać SHA-1 do aplikacji o kluczowym znaczeniu dla bezpieczeństwa.
Również dlatego, że było fajnie

Zobacz więcej w mojej osobnej odpowiedzi poniżej .

Według Pro Git :

Jeśli zdarzy ci się zatwierdzić obiekt, który ma skrót do tej samej wartości SHA-1, co poprzedni obiekt w repozytorium, Git zobaczy poprzedni obiekt już w bazie danych Git i założy, że został już zapisany. Jeśli w pewnym momencie spróbujesz ponownie sprawdzić ten obiekt, zawsze otrzymasz dane pierwszego obiektu.

Więc nie zawiedzie, ale też nie uratuje twojego nowego obiektu.
Nie wiem, jak by to wyglądało w wierszu poleceń, ale z pewnością byłoby to mylące.

Nieco dalej ta sama referencja próbuje zilustrować prawdopodobieństwo takiej kolizji:

Oto przykład, który daje wyobrażenie o tym, czego potrzeba, aby uzyskać kolizję SHA-1. Gdyby wszystkie 6,5 miliarda ludzi na Ziemi programowało i co sekundę, każdy produkowałby kod, który byłby ekwiwalentem całej historii jądra Linuksa (1 milion obiektów Git) i umieszczał go w jednym ogromnym repozytorium Git, zajęłoby to 5 lat repozytorium zawierało wystarczającą liczbę obiektów, aby prawdopodobieństwo 50% zderzenia pojedynczego obiektu SHA-1 było 50%. Istnieje większe prawdopodobieństwo, że każdy członek zespołu programistycznego zostanie zaatakowany i zabity przez wilki w niepowiązanych zdarzeniach tej samej nocy.

Aby dodać do mojej poprzedniej odpowiedzi z 2012 r. , Jest teraz (luty 2017 r., Pięć lat później) przykład rzeczywistej kolizji SHA-1 z shattered.io , w której można stworzyć dwa kolidujące pliki PDF: uzyskać SHA- 1 podpis cyfrowy na pierwszym pliku PDF, który może być również wykorzystany jako ważny podpis na drugim pliku PDF.
Zobacz także „ U drzwi śmierci od wielu lat powszechnie używana funkcja SHA1 jest już martwa ” i ta ilustracja .

Aktualizacja 26 lutego: Linus potwierdził następujące punkty w poście Google+ :

(1) Po pierwsze - niebo nie spada. Istnieje duża różnica między używaniem skrótu kryptograficznego do celów takich jak podpisywanie zabezpieczeń, a używaniem go do generowania „identyfikatora treści” dla systemu adresowanego do treści, takiego jak git.

(2) Po drugie, natura tego szczególnego ataku SHA1 oznacza, że ​​w rzeczywistości dość łatwo jest go zminimalizować, a dla tego ograniczenia opublikowano już dwa zestawy łatek.

(3) I wreszcie, istnieje właściwie dość proste przejście do jakiegoś innego skrótu, który nie złamie świata - ani nawet starych repozytoriów git.

Jeśli chodzi o to przejście, zobacz Git 2.16 z pierwszego kwartału 2018 r., Dodając strukturę reprezentującą algorytm mieszania. Rozpoczęto wdrażanie tego przejścia.

Począwszy od Gita 2.19 (III kwartał 2018 r.) , Git wybrał SHA-256 jako NewHash i jest w trakcie integracji go z kodem (co oznacza, że ​​SHA1 jest nadal domyślny (Q2 2019, Git 2.21), ale SHA2 będzie następcą)

Oryginalna odpowiedź (25 lutego) Ale:

• Pozwala to na sfałszowanie obiektu blob, jednak SHA-1 drzewa nadal się zmienia, ponieważ rozmiar sfałszowanego obiektu blob może nie być taki sam jak oryginalny: patrz „ Jak oblicza się wartość skrótu git? ”; obiekt blob SHA1 jest obliczany na podstawie zawartości i rozmiaru .
  To ma jakiś problem dla git-svnchociaż . A raczej z samym svn , jak widać tutaj .
• Jak wspomniałem w mojej pierwotnej odpowiedzi , koszt takiej próby jest na razie zaporowy (6500 lat procesora i 100 lat GPU) Zobacz także Valerie Anita Aurora w „ Czasach życia funkcji kryptograficznych funkcji skrótu ”.
• Jak skomentowano wcześniej, nie chodzi tu o bezpieczeństwo czy zaufanie, ale o integralność danych (usuwanie duplikacji i wykrywanie błędów), które mogą być łatwo wykryte przez git fsck, jak wspominał dziś Linus Torvalds . git fsckostrzegałby przed komunikatem zatwierdzenia z nieprzezroczystymi danymi ukrytymi po NUL(chociaż NULnie zawsze jest obecny w fałszywym pliku ).
  Nie wszyscy się włączają transfer.fsck, ale GitHub tak: każde wypychanie zostanie przerwane w przypadku źle sformułowanego obiektu lub przerwanego łącza. Chociaż ... istnieje powód, dla którego domyślnie nie jest aktywowany .
• plik pdf może zawierać dowolne dane binarne, które można zmienić w celu wygenerowania kolidującego SHA-1, w przeciwieństwie do sfałszowanego kodu źródłowego.
  Rzeczywisty problem z tworzeniem dwóch repozytoriów Git z tym samym hasłem zatwierdzania głowy i inną zawartością. I nawet wtedy atak pozostaje zawiły .
• Linus dodaje :

  Cały sens SCM polega na tym, że nie chodzi o jednorazowe wydarzenie, ale o ciągłą historię. Zasadniczo oznacza to również, że udany atak musi działać z czasem, a nie być wykrywalny.
  Jeśli możesz oszukać SCM jeden raz, wstaw kod i zostanie on wykryty w przyszłym tygodniu, tak naprawdę nie zrobiłeś nic przydatnego. Spaliłeś się tylko.

Joey Hess wypróbowuje te pliki pdf w repozytorium Git i znalazł :

Obejmuje to dwa pliki o tym samym SHA i rozmiarze, które uzyskują różne obiekty BLOB dzięki sposobowi, w jaki git dodaje nagłówek do zawartości.

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

Podczas gdy dołączanie identycznych danych do tych kolidujących plików generuje inne kolizje, wcześniejsze dane nie.

Zatem głównym wektorem ataku (fałszowanie zatwierdzenia) byłoby :

• Wygeneruj zwykły obiekt zatwierdzenia;
• użyj całego obiektu zatwierdzenia + NUL jako wybranego prefiksu oraz
• użyj ataku kolizyjnego z identycznym prefiksem, aby wygenerować kolidujące dobre / złe obiekty.
• ... i to jest bezużyteczne, ponieważ dobre i złe obiekty zatwierdzania nadal wskazują na to samo drzewo!

Dodatkowo możesz już wykryć kryptoanalityczne ataki zderzeniowe przeciwko SHA-1 obecnemu w każdym pliku z cr-marcstevens/sha1collisiondetection

Dodanie podobnego czeku w samym Gicie wiązałoby się z pewnymi kosztami obliczeniowymi .

Podczas zmiany skrótu Linux komentuje :

Rozmiar skrótu i ​​wybór algorytmu skrótu to kwestie niezależne.
To, co prawdopodobnie zrobisz, to przełączenie na 256-bitowy skrót, użyj go wewnętrznie i w natywnej bazie danych git, a następnie domyślnie wyświetlaj skrót jako 40-znakowy ciąg szesnastkowy (coś w rodzaju tego, jak już skróciliśmy rzeczy w wiele sytuacji).
W ten sposób narzędzia wokół git nawet nie zobaczą zmiany, chyba że zostaną przekazane jakiś specjalny --full-hashargument „ ” (lub „ --abbrev=64” lub cokolwiek innego - domyślnie jest to skrót 40).

Mimo to plan przejścia (z SHA1 na inną funkcję skrótu) byłby nadal złożony , ale aktywnie badany. Kampania jest w toku :
convert-to-object_id

Aktualizacja 20 marca: GitHub szczegółowo opisuje możliwy atak i jego ochronę :

Nazwom SHA-1 można przypisać zaufanie za pomocą różnych mechanizmów. Na przykład Git pozwala na kryptograficzne podpisanie zatwierdzenia lub znacznika. W ten sposób podpisuje tylko sam obiekt zatwierdzenia lub znacznika, który z kolei wskazuje na inne obiekty zawierające rzeczywiste dane pliku przy użyciu ich nazw SHA-1. Kolizja w tych obiektach może doprowadzić do podpisu, który wydaje się prawidłowy, ale który wskazuje na inne dane niż zamierzony przez osobę podpisującą. W takim ataku sygnatariusz widzi tylko połowę kolizji, a ofiara widzi drugą połowę.

Ochrona:

Ostatni atak wykorzystuje specjalne techniki w celu wykorzystania słabości algorytmu SHA-1, które znajdują kolizję w znacznie krótszym czasie. Techniki te pozostawiają w bajtach wzorzec, który można wykryć podczas obliczania SHA-1 każdej połowy kolidującej pary.

GitHub.com wykonuje teraz to wykrywanie dla każdego obliczanego SHA-1 i przerywa operację, jeśli istnieją dowody, że obiekt stanowi połowę kolidującej pary. Uniemożliwia to atakującym korzystanie z GitHub w celu przekonania projektu do zaakceptowania „niewinnej” połowy ich kolizji, a także uniemożliwia hostowanie złośliwej połowy.

Zobacz „ sha1collisiondetection” autorstwa Marc Stevensa

Ponownie, wraz z dodaniem przez Git 2.16 struktury Q1 2018 reprezentującej algorytm mieszania, rozpoczęto wdrażanie przejścia na nowy skrót.
Jak wspomniano powyżej, nowym obsługiwanym hashem będzie SHA-256 .

Myślę, że kryptografowie świętowaliby.

Cytat z artykułu w Wikipedii na temat SHA-1 :

W lutym 2005 r. Ogłoszono atak Xiaoyun Wanga, Yiqun Lisa Yin i Hongbo Yu. Ataki mogą znajdować kolizje w pełnej wersji SHA-1, wymagające mniej niż 2 ^ 69 operacji. (Wyszukiwanie metodą brutalnej siły wymagałoby 2 ^ 80 operacji).

Istnieje kilka różnych modeli ataku dla skrótów, takich jak SHA-1, ale najczęściej omawianym jest wyszukiwanie kolizji, w tym narzędzie HashClash Marca Stevensa .

„Począwszy od 2012 r., Najbardziej skuteczny atak przeciwko SHA-1 jest uważany za atak Marc'a Stevensa [34], którego szacunkowy koszt 2,77 mln USD przełamuje pojedynczą wartość skrótu poprzez wynajem mocy procesora z serwerów w chmurze”.

Jak zauważyli ludzie, możesz wymusić kolizję skrótu z git, ale nie spowoduje to zastąpienia istniejących obiektów w innym repozytorium. Wyobrażam sobie, że nawet git push -f --no-thinnie nadpisze istniejących obiektów, ale nie jestem w 100% pewien.

Powiedział, że jeśli włamać się do zdalnego repozytorium, a następnie można dokonać fałszywe obiekt starszy tam , ewentualnie osadzania kodu włamał się do projektu open source na github lub podobnym. Jeśli byłeś ostrożny, być może mógłbyś wprowadzić zhakowaną wersję, którą pobrali nowi użytkownicy.

Podejrzewam jednak, że wiele rzeczy, które mogliby zrobić programiści projektu, mogą albo ujawnić, albo przypadkowo zniszczyć hack o wartości wielu milionów dolarów. W szczególności jest to dużo pieniędzy, jeśli jakiś programista, którego nie zhakowałeś, kiedykolwiek uruchomił wspomniane wyżej git push --no-thinpo zmodyfikowaniu plików, czasem nawet bez --no-thinzależności.