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

543

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.

Gnurou
źródło
76
Kiedyś łamigłówka, teraz potencjalnie problem .
Toby
11
@Toby To pytanie dotyczyło ataku przed obrazem ; Google pokazał atak kolizji - podobny, ale nieco inny. Możesz przeczytać więcej o różnicy tutaj .
Saheed
@Saheed nie widzę, jaka część to pytanie jest o ataku sprzed obrazu konkretnie postawione pytanie, jak to tylko około o kolizji w repozytorium git, a nie o wykorzystaniu go.
Toby
3
@Toby Oryginalna łamigłówka nie dotyczyła ataku (ani obrazu wstępnego, ani kolizji), ale przypadkowej kolizji, która jest tak nieprawdopodobnie nieprawdopodobna, że ​​nie warto jej brać pod uwagę. Myślę, że to, co Saheed słusznie próbował powiedzieć, to wciąż nie jest faktyczny problem. Masz jednak rację, że atak kolizyjny Google potencjalnie stworzył problem bezpieczeństwa w zależności od sposobu korzystania z Git.
Andrew W. Phillips
Oto druga kolizja, która ma tylko 320 bajtów privacylog.blogspot.com/2019/12/the-second-sha-collision.html
William Entriken

Odpowiedzi:

735

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.

Ruben
źródło
156
Niesamowita odpowiedź - zmniejszenie rozmiaru skrótu, aby zobaczyć, jak naprawdę się zachowuje, to świetny pomysł.
Gnurou,
4
@Gnurou Zgadzam się i głosowałem za odpowiedzią w tym czasie. Czy te przypadki zostały wymienione na liście mailingowej git?
VonC
1
Jak prawdopodobne jest to, że tak się dzieje bez zmniejszonego rozmiaru skrótu?
Mathias Bader,
4
Jakie są plany przejścia na inny algorytm mieszający.
Pete,
9
Musisz przeczytać - wyjaśnienia Linusa
Torvala
238

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ącychautorstwa 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 .

VonC
źródło
25
twist: nadal hasze to samo po dodaniu /* This line added to avoid collision */: D możesz wygrać na loterii dwa razy: P
Janus Troelsen
4
@JanusTroelsen na pewno, ale wciąż jest to loteria, prawda? ;) (jak wspomniano w tej krótkiej notatce o SHA1 )
VonC
6
@VonC w odniesieniu do tej wzmianki : czy wybuch globalnej epidemii wilkołaków - zmiotł całą ludzkość i doprowadził do makabrycznej śmierci wszystkich moich programistów tej samej nocy, mimo że zostały one rozproszone geograficznie - uważany za niepowiązany incydent? Oczywiście zakładając, że stało się to podczas pełni księżyca. Taki scenariusz by wszystko zmienił. Nawet myślenie o tym to szaleństwo! To jest na zupełnie inną skalę prawdopodobieństwa! Oznaczałoby to, że musimy ... przestać używać GIT! TERAZ!!! KAŻDY RUUUUUN !!!!!!!
Daniel Dinnyes
2
Zauważ, że gitbrute nie wymusza określonego SHA1, a jedynie tylko przedrostek (tj. Podsekcję całego SHA1). Wymuszenie całego SHA1 (tj. Z prefiksem pełnej długości klucza) prawdopodobnie potrwa „za długo”.
mb14
2
@JanusTroelsen Następnie dodajesz:/* This line added to avoid collision of the avoid collision line */
smg
42

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.

Mata
źródło
44
Chciałbym zobaczyć źródło liczb z ostatniego zdania ;-)
Joachim Sauer
17
@Jasper: ten link jest dobrą dokumentacją, ale nie zawiera statystyk dotyczących prawdopodobieństwa zaatakowania i zabicia każdego członka drużyny przez wilki w niepowiązanych incydentach tej samej nocy.
Joachim Sauer
5
@Jasper: Cóż, tak jak czytam, tekst dosłownie twierdzi, że prawdopodobieństwo, że 6,5 miliarda członków zespołu zostanie zabitych przez wilki tej samej nocy, jest wyższe niż 50%. Ale mój główny zarzut wobec jego wypowiedzi jest to, że takie zdarzenie może mieć do być zjawiskiem na całym świecie; jest nie do pomyślenia, aby mogło to nastąpić z powodu niepowiązanych zdarzeń. ;)
Keith Robertson,
5
@KeithRobertson jestem całkiem pewny, słupek jest mówić o szansie wszystkich swoich rzeczywistych członków zespołu zjedzone w porównaniu z przypadkiem kolizji hash jeśli wszyscy na świecie nie produkuje szalone ilości kodu, oprócz czasu potrzebnego w tych okolicznościach dostać 50% szansy na kolizję (tj. incydent z wilkami nie obejmował całego świata, a 50% było oddzielone od wilków). Zrozumiałeś jednak, że jeśli takie zdarzenie jest nie do pomyślenia, kolizja z hashem git powinna być. (Oczywiście, jeden jest (prawie) całkowicie oparty na przypadku, a drugi nie, ale nadal.)
Jasper,
23

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:

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 .

VonC
źródło
Kolizja: 1. Próbowano stworzyć kolizję, a nie przypadkową. 2. Z raportu PDF: Całkowity wysiłek obliczeniowy jest równy 2 ^ 63,1 kompresjom SHA-1 i zajął około 6500 lat procesora i 100 lat GPU . 3. Chociaż powinniśmy przejść od wersji MD5 i SHA-1, ogólnie rzecz biorąc, są one w porządku za unikalne zastosowania plików.
zaph
Warto zauważyć, że WebKit sprawdził w kolidujących plikach PDF do testu. Zepsuł
dahlbyk
1
@dahlbyk Warto zwrócić uwagę… w tym, że zauważyłem to w odpowiedzi (link „ git-svnChociaż ma to jakiś problem ”, choć odnosi się do tego, choć pośrednio)
VonC
1
@Mr_and_Mrs_D nie, to jeszcze nie kończy się niepowodzeniem z błędem. Trwa
VonC
1
@Mr_and_Mrs_D ZOBACZ edycję 4 w stackoverflow.com/posts/42450327/revisions : teraz nie działa, przynajmniej po przejściu na GitHub.
VonC
6

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).

Willem Hengeveld
źródło
7
Chodzi o to, że w SHA1 znaleziono usterkę i że był to czas, w którym Git był wprowadzany. Również prawdopodobieństwo jest nieliniowe. To, że grasz na loterii przez pięćdziesiąt lat, nie oznacza, że ​​masz większą szansę na wygraną. Po prostu masz tę samą szansę za każdym razem. Osoba grająca po raz pierwszy nadal może wygrać.
0xC0000022L
Jest to tylko atak polegający na znalezieniu kolizji, co oznacza, że ​​można znaleźć ytaki, że h(x) == h (y) `jest poważnym zagrożeniem dla dowolnych danych, takich jak certyfikaty SSL, jednak nie wpływa to na Git, który byłby podatny na drugi atak przed obrazem, co oznacza, że posiadające wiadomości xmożna zmodyfikować go do wiadomości x'tego h(x) == h(x'). Więc ten atak nie osłabia Gita. Również Git nie wybrał SHA-1 ze względów bezpieczeństwa.
Hauleth
Teraz znaleziono kolizję - po prostu nie taką, która bezpośrednio przeszkadza Gitowi. stackoverflow.com/questions/42433126/…
Willem Hengeveld
2 ^ 69 to około 600 operacji Exa. Osiem lat później superkomputer Nvidii SaturnV zaktualizowany o A100 może wykonać 4.6 ExaOPS, więc może to rozwiązać w ciągu nieco ponad 2 minut lub wykonać atak brutalną siłą w ciągu kilku dni.
qdin
6

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.

Jeff Burdges
źródło