Co by się właściwie stało, gdybym miał kolizję hash podczas korzystania z git?

Np. Udaje mi się zatwierdzić dwa pliki z tą samą sumą kontrolną sha1, czy git to zauważy lub uszkodzi jeden z plików?

Czy można ulepszyć git, aby z tym żyć, czy też musiałbym zmienić na nowy algorytm mieszania?

(Proszę nie odwracać tego pytania, omawiając, jak mało prawdopodobne jest to - dziękuję)

Zbieranie atomów na 10 księżycach

Skrót SHA-1 to ciąg 40 znaków szesnastkowych ... czyli 4 bity na znak pomnożone przez 40 ... 160 bitów. Teraz wiemy, że 10 bitów to w przybliżeniu 1000 (dokładnie 1024), co oznacza, że ​​istnieje 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 różnych skrótów SHA-1 ... 10 ⁴⁸ .

Co to jest odpowiednik? Cóż, Księżyc składa się z około 10 ⁴⁷ atomów. Więc jeśli mamy 10 księżyców ... i losowo wybierzesz jeden atom na jednym z tych księżyców ... a potem idź dalej i wybierz ponownie losowy atom na nich ... wtedy prawdopodobieństwo, że wybierzesz ten sam atom dwa razy , to prawdopodobieństwo, że dwa podane zatwierdzenia git będą miały ten sam skrót SHA-1.

Rozwijając to, możemy zadać pytanie ...

Ile zatwierdzeń potrzebujesz w repozytorium, zanim zaczniesz martwić się o kolizje?

Dotyczy to tak zwanych „ataków urodzinowych”, co z kolei odnosi się do „Paradoksu urodzinowego” lub „Problemu urodzinowego”, który mówi, że kiedy wybierasz losowo z danego zestawu, potrzebujesz zaskakująco niewielu typów, zanim będzie bardziej prawdopodobne wybrać coś dwa razy. Ale „zaskakująco mało” jest tutaj bardzo względnym terminem.

Wikipedia ma tabelę prawdopodobieństwa kolizji Paradoksu urodzinowego . Nie ma wpisu dla 40-znakowego skrótu. Ale interpolacja wpisów dla 32 i 48 znaków daje nam wynik w zakresie 5 * 10 ²² git commits z prawdopodobieństwem 0,1% kolizji. To pięćdziesiąt miliardów miliardów różnych zobowiązań, czyli pięćdziesiąt Zettacommitów , zanim osiągniesz nawet 0,1% szansy na kolizję.

Suma bajtów samych skrótów dla tych zatwierdzeń oznaczałaby więcej danych niż wszystkie dane wygenerowane na Ziemi przez rok, co oznacza, że ​​musiałbyś generować kod szybciej niż YouTube przesyła strumieniowo wideo. Powodzenia z tym. :RE

Chodzi o to, że jeśli ktoś celowo nie powoduje kolizji, prawdopodobieństwo przypadkowego zdarzenia jest tak oszałamiająco małe, że można zignorować ten problem

„Ale gdy kolizja nie występuje, to co rzeczywiście się dzieje?”

Ok, przypuśćmy, że zdarzy się nieprawdopodobne, lub przypuśćmy, że komuś udało się dostosować celową kolizję hash SHA-1 . Co się wtedy stanie?

W takim przypadku jest doskonała odpowiedź, gdy ktoś na niej eksperymentował . Cytuję z tej odpowiedzi:

1. Jeśli obiekt BLOB już istnieje z tym samym hashem, nie otrzymasz żadnych ostrzeżeń. Wygląda na to, że wszystko jest w porządku, ale kiedy naciskasz, ktoś klonuje lub cofasz, 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 wypchnąć lub ktoś nie sklonuje repozytorium. Wtedy zobaczysz, że repozytorium jest uszkodzone.
3. Jeśli obiekt zatwierdzenia już istnieje i tworzysz obiekt blob z tym samym hashem: tak samo jak # 2 - uszkodzony
4. Jeśli obiekt BLOB już istnieje i utworzysz obiekt zatwierdzenia z tym samym skrótem, aktualizacja „ref” zakończy się niepowodzeniem.
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, aktualizacja „ref” nie powiedzie się.
7. Jeśli obiekt drzewa już istnieje i utworzysz obiekt drzewa z tym samym hashem, wszystko będzie wyglądać dobrze. Ale kiedy zatwierdzisz, całe repozytorium odniesie 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ć dobrze. Ale kiedy zatwierdzisz, 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.

Jak się wydaje, niektóre przypadki nie są dobre. Szczególnie przypadki nr 2 i 3 powodują bałagan w repozytorium. Wydaje się jednak, że błąd pozostaje w tym repozytorium, a atak / dziwaczne nieprawdopodobieństwo nie rozprzestrzenia się do innych repozytoriów.

Wydaje się również, że kwestia celowych kolizji jest uznawana za realne zagrożenie, dlatego np. GitHub podejmuje działania, aby temu zapobiec .

Jeśli dwa pliki mają tę samą sumę skrótu w git, potraktuje te pliki jako identyczne. W absolutnie mało prawdopodobnym przypadku, gdy tak się stanie, zawsze możesz cofnąć się o jedno zatwierdzenie i zmienić coś w pliku, aby już nie kolidowały ...

Zobacz post Linusa Torvaldsa w wątku „Zaczynasz myśleć o sha-256?” na liście mailingowej git .

Naprawdę nie można odpowiedzieć na to pytanie właściwym „ale” bez wyjaśnienia, dlaczego nie stanowi to problemu. Nie da się tego zrobić bez naprawdę dobrego uchwycenia tego, czym naprawdę jest haszysz. Jest to bardziej skomplikowane niż proste przypadki, na które mógłbyś zostać narażony w programie CS.

Istnieje tutaj podstawowe nieporozumienie dotyczące teorii informacji. Jeśli zredukujesz dużą ilość informacji do mniejszych poprzez odrzucenie pewnej ilości (np. Hash), może wystąpić kolizja bezpośrednio związana z długością danych. Im krótsze dane, tym MNIEJ prawdopodobne. Teraz zdecydowana większość kolizji będzie bełkotem, co znacznie zwiększa prawdopodobieństwo ich wystąpienia (nigdy nie sprawdziłbyś bełkotu ... nawet obraz binarny jest nieco ustrukturyzowany). W końcu szanse są nikłe. Aby odpowiedzieć na twoje pytanie, tak, git potraktuje je jako takie same, zmiana algorytmu haszującego nie pomoże, zajmie jakieś „drugie sprawdzenie”, ale ostatecznie będziesz potrzebować tyle danych „dodatkowego sprawdzenia” ponieważ długość danych jest w 100% pewna ... pamiętaj, że będzie to 99,99999 .... do naprawdę długiej liczby cyfr ... pewnie za pomocą prostego czeku, jak opisałeś. SHA-x to skróty o dużej mocy kryptograficznej, co oznacza, że ​​celowe utworzenie dwóch zestawów danych źródłowych, które są BARDZO PODOBNE i mają ten sam skrót, zazwyczaj nie jest trudne. Jeden bit zmiany w danych powinien spowodować utworzenie więcej niż jednego (najlepiej jak najwięcej) bitów zmiany w danych wyjściowych skrótu, co również oznacza, że ​​bardzo trudne (ale nie całkiem niemożliwe) jest powrót od skrótu do pełnego zestawu zderzeń, a tym samym wyciągnie oryginalną wiadomość z tego zestawu kolizji - wszystkie oprócz kilku będą bełkotem, a tych, których nie ma, wciąż jest ogromna liczba do przeszukania, jeśli długość wiadomości jest znacząca. Wadą skrótu kryptograficznego jest to, że wolno je oblicza ... ogólnie.

Więc co to wszystko oznacza dla Gita? Niewiele. Hashy są wykonywane tak rzadko (w stosunku do wszystkiego innego), że ich koszt obliczeniowy jest ogólnie niewielki w przypadku operacji. Szanse na zderzenie z parą kolizji są tak niskie, że nie jest to realistyczna szansa na wystąpienie i nie zostanie wykryte natychmiast (tj. Twój kod najprawdopodobniej nagle przestałby się budować), co pozwala użytkownikowi naprawić problem (wykonać kopię zapasową wersji, i dokonaj zmiany ponownie, a prawie na pewno otrzymasz inny hash ze względu na zmianę czasu, który również zasila hash w git). Jest bardziej prawdopodobne, że będzie to dla ciebie prawdziwy problem, jeśli przechowujesz dowolne pliki binarne w git, co nie jest tym, czym jest jego podstawowy model użycia. Jeśli chcesz to zrobić ... prawdopodobnie lepiej będzie, jeśli skorzystasz z tradycyjnej bazy danych.

Nie ma nic złego w myśleniu o tym - to dobre pytanie, które wielu ludzi po prostu uważa za „tak mało prawdopodobne, że nie warto o tym myśleć” - ale to naprawdę trochę bardziej skomplikowane. Jeśli tak się stanie, powinno być bardzo łatwe do wykrycia, nie będzie to ciche uszkodzenie w normalnym przepływie pracy.

Czy można ulepszyć git, aby z tym żyć, czy też musiałbym zmienić na nowy algorytm mieszania?

Kolizje są możliwe w przypadku dowolnego algorytmu wyznaczania wartości skrótu, więc zmiana funkcji skrótu nie wyklucza problemu, a jedynie zmniejsza prawdopodobieństwo jego wystąpienia. Więc powinieneś wybrać naprawdę dobrą funkcję skrótu (SHA-1 już jest, ale prosiłeś, aby nie mówić :)

Możesz zobaczyć dobre studium w „ Jak Git poradziłby sobie z kolizją SHA-1 na obiekcie blob? ”.

Ponieważ kolizja SHA1 jest teraz możliwa (o czym odnoszę się w tej odpowiedzi w shattered.io ), wiedz, że Git 2.13 (Q2 2017) poprawi / złagodzi obecną sytuację dzięki wariantowi „wykrywania próby stworzenia kolizji” implementacji SHA-1 autorzy: Marc Stevens (CWI) i Dan Shumow (Microsoft) .

Zobacz zatwierdzenie f5f5e7f , zatwierdzenie 8325e43 , zatwierdzenie c0c2006 , zatwierdzenie 45a574e , zatwierdzenie 28dc98e (16 marca 2017) autorstwa Jeffa Kinga ( peff) .
^{(Scalone przez Junio ​​C Hamano - gitster- w zobowiązaniu 48b3693 , 24 marca 2017 r.)}

Makefile: ustaw DC_SHA1jako domyślne

Kiedyś domyślnie używaliśmy implementacji SHA1 z biblioteki OpenSSL.
Ponieważ staramy się uważać na ataki kolizyjne po ostatnim ogłoszeniu „shattered”, zmień ustawienie domyślne, aby zachęcić ludzi do korzystania z implementacji DC_SHA1.
Ci, którzy chcą użyć implementacji z OpenSSL, mogą wprost o to poprosić, OPENSSL_SHA1=YesPleaseuruchamiając " make".

W rzeczywistości nie mamy kolizji obiektu Git, więc najlepsze, co możemy zrobić, to uruchomić jeden z zniszczonych plików PDF za pomocą testu-sha1. Powinno to uruchomić kontrolę kolizji i zginąć.

Czy można ulepszyć Git, aby z tym żyć, czy też musiałbym zmienić na nowy algorytm mieszania?

Aktualizacja z grudnia 2017 r. Za pomocą Git 2.16 (I kw. 2018 r.): Trwają prace nad obsługą alternatywnego SHA: zobacz „ Dlaczego Git nie używa nowocześniejszego SHA? ”.

Będziesz mógł użyć innego algorytmu mieszania: SHA1 nie jest już jedynym algorytmem Git.

Git 2.18 (Q2 2018) dokumentuje ten proces.

Zobacz zatwierdzenie 5988eb6 , zobowiązanie 45fa195 (26 marca 2018) autorstwa Ævara Arnfjörð Bjarmason ( avar) .
^{(Scalone przez Junio ​​C Hamano - gitster- w zatwierdzeniu d877975 , 11 kwietnia 2018)}

doc hash-function-transition: wyjaśnij, co oznacza SHAttered

Spróbuj wyjaśnić, co w praktyce oznacza atak SHAttered dla Git.
W poprzedniej wersji tekstu nie było żadnej wzmianki o tym, że Git już posiada środki łagodzące dla tego konkretnego ataku, co według naukowców SHAttered pozwoli wykryć kryptoanalityczne ataki kolizyjne.

Być może pomyliłem się w niektórych niuansach, ale o ile wiem, ten nowy tekst dokładnie podsumowuje obecną sytuację z SHA-1 w git. To znaczy, że git tak naprawdę nie używa już SHA-1, używa Hardened-SHA-1 (tak się składa, że ​​produkują te same wyniki 99,99999999999 ...% czasu).

Tak więc poprzedni tekst był błędny, twierdząc, że:

[...] W wyniku [SHAttered], SHA-1 nie może być już uważane za bezpieczne kryptograficznie [...]

To nie o to chodzi. Mamy środki zaradcze przeciwko SHAttered, jednak uważamy, że rozsądne jest podjęcie działań w kierunku NewHashpojawienia się przyszłych luk w SHA-1 lub Hardened-SHA-1.

Tak więc nowa dokumentacja brzmi teraz:

Git v2.13.0, a później został domyślnie przeniesiony do wzmocnionej implementacji SHA-1, która nie jest podatna na atak SHAttered.

Tak więc Git w efekcie już migrował do nowego skrótu, który nie jest SHA-1 i nie ma wspólnych luk w zabezpieczeniach, jego nowa funkcja skrótu po prostu tworzy dokładnie takie same dane wyjściowe dla wszystkich znanych danych wejściowych, z wyjątkiem dwóch plików PDF opublikowanych przez SHAttered badaczy, a nowa implementacja (napisana przez tych badaczy) twierdzi, że wykrywa przyszłe kryptoanalityczne ataki kolizyjne.

Niezależnie od tego, rozważne jest przejście od dowolnego wariantu SHA-1 do nowego skrótu. Nie ma gwarancji, że przyszłe ataki na SHA-1 nie zostaną opublikowane w przyszłości, a ataki te mogą nie mieć wykonalnych środków zaradczych.

Gdyby SHA-1 i jego warianty były naprawdę zepsute, funkcja skrótu Gita nie mogłaby być już uważana za bezpieczną kryptograficznie. Miałoby to wpływ na przekazywanie wartości skrótu, ponieważ nie mogliśmy ufać, że dana wartość skrótu reprezentuje znaną dobrą wersję treści, zgodnie z zamierzeniami głośnika.

Uwaga: ten sam dokument (Q3 2018, Git 2.19) wyraźnie odwołuje się do „nowego skrótu” jako SHA-256 : zobacz „ Dlaczego Git nie używa nowocześniejszego SHA? ”.

Google twierdzi teraz, że kolizja SHA-1 jest możliwa pod pewnymi warunkami wstępnymi: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Ponieważ git używa SHA-1 do sprawdzania integralności plików, oznacza to, że integralność plików w git jest zagrożona.

IMO, git zdecydowanie powinien użyć lepszego algorytmu haszującego, ponieważ teraz możliwa jest celowa kolizja.

Kolizja haszyszu jest tak mało prawdopodobna, że ​​jest po prostu oszałamiająca! Naukowcy na całym świecie bardzo się starają, aby to osiągnąć, ale jeszcze im się to nie udało. Jednak w przypadku niektórych algorytmów, takich jak MD5, odniosły sukces.

Jakie są szanse?

SHA-256 ma 2 ^ 256 możliwych skrótów. To około 10 ^ 78 . Lub mówiąc bardziej obrazowo, szanse na kolizję są bliskie

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 000

Szansa na wygranie loterii wynosi około 1:14 mln . Szansa na kolizję z SHA-256 jest jak wygrana w loterii przez 11 kolejnych dni !

Wyjaśnienie matematyczne: 14000000 ^ 11 ~ 2 ^ 256

Ponadto wszechświat ma około 10 ^ 80 atomów. To tylko 100 razy więcej niż jest kombinacji SHA-256.

Udana kolizja MD5

Nawet w przypadku MD5 szanse są niewielkie. Chociaż matematykom udało się stworzyć kolizję:

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

ma taką samą MD5 jak

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

Nie oznacza to, że MD5 jest mniej bezpieczny teraz, gdy jego algorytm został złamany. Możesz celowo tworzyć kolizje MD5, ale szansa na przypadkową kolizję MD5 wciąż wynosi 2 ^ 128, czyli wciąż dużo.

Wniosek

Nie musisz się martwić o kolizje. Algorytmy haszujące to drugi najbezpieczniejszy sposób sprawdzania identyczności plików. Jedynym bezpieczniejszym sposobem jest porównanie binarne.

Cóż, myślę, że teraz wiemy, co się stanie - należy się spodziewać, że repozytorium zostanie uszkodzone ( źródło ).

Niedawno znalazłem post z 29.04.2013 w grupie dyskusyjnej BSD pod adresem

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

gdzie plakat głosi:

Raz wpadłem na kolizję hash, używając git rebase.

Niestety, nie przedstawia żadnego dowodu na swoje roszczenie. Ale może chciałbyś spróbować się z nim skontaktować i zapytać o ten rzekomy incydent.

Ale na bardziej ogólnym poziomie, z powodu ataku urodzinowego, szansa na zderzenie z hashem SHA-1 wynosi 1 w pow (2, 80).

Brzmi to dużo i na pewno znacznie więcej niż całkowita liczba wersji poszczególnych plików obecnych we wszystkich repozytoriach Git na świecie razem wzięta.

Jednak dotyczy to tylko wersji, które faktycznie pozostają w historii wersji.

Jeśli deweloper w dużym stopniu polega na ponownym bazowaniu, za każdym razem, gdy rebase jest uruchamiany dla gałęzi, wszystkie zatwierdzenia we wszystkich wersjach tej gałęzi (lub zmienionej części gałęzi) otrzymują nowe skróty. To samo dotyczy każdego pliku modyfikowanego przez „git filter-branch”. Dlatego „rebase” i „filter-branch” mogą być dużymi mnożnikami liczby haszów generowanych w czasie, mimo że nie wszystkie z nich są w rzeczywistości zachowywane: Często po zmianie bazy (szczególnie w celu „oczyszczenia” gałęzi ), oryginalna gałąź jest wyrzucana.

Ale jeśli kolizja nastąpi podczas rozgałęzienia rebase lub filtru, nadal może mieć niekorzystne skutki.

Inną rzeczą byłoby oszacowanie całkowitej liczby zahaszowanych obiektów w repozytoriach git i sprawdzenie, jak daleko są one od pow (2, 80).

Powiedzmy, że mamy około 8 miliardów ludzi, a wszyscy z nich korzystaliby z gita i przechowowaliby swoje wersje w 100 repozytoriach git na osobę. Załóżmy dalej, że przeciętne repozytorium ma 100 zatwierdzeń i 10 plików, a tylko jeden z tych plików zmienia się na zatwierdzenie.

Dla każdej wersji mamy co najmniej skrót dla obiektu drzewa i samego obiektu zatwierdzenia. Razem ze zmienionym plikiem mamy 3 skróty na wersję, a zatem 300 skrótów na repozytorium.

Dla 100 repozytoriów 8 miliardów ludzi daje to pow (2, 47), który wciąż jest daleki od pow (2, 80).

Nie obejmuje to jednak rzekomego efektu mnożenia wspomnianego powyżej, ponieważ nie jestem pewien, jak uwzględnić go w tym oszacowaniu. Może mogłoby to znacznie zwiększyć szanse na kolizję. Zwłaszcza jeśli bardzo duże repozytoria, które mają długą historię zatwierdzeń (jak jądro Linuksa), są ponownie bazowane przez wiele osób w celu wprowadzenia drobnych zmian, które jednak tworzą różne skróty dla wszystkich zatwierdzonych zmian.