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 48 .
Co to jest odpowiednik? Cóż, Księżyc składa się z około 10 47 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 22 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:
- 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).
- 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.
- Jeśli obiekt zatwierdzenia już istnieje i tworzysz obiekt blob z tym samym hashem: tak samo jak # 2 - uszkodzony
- Jeśli obiekt BLOB już istnieje i utworzysz obiekt zatwierdzenia z tym samym skrótem, aktualizacja „ref” zakończy się niepowodzeniem.
- Jeśli obiekt blob już istnieje i utworzysz obiekt drzewa z tym samym hashem. Nie powiedzie się podczas tworzenia zatwierdzenia.
- Jeśli obiekt drzewa już istnieje i utworzysz obiekt zatwierdzenia z tym samym hashem, aktualizacja „ref” nie powiedzie się.
- 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.
- 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.
- 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 .
I've been informed by the git Gods that the chances of a SHA1 collision is the same as the Earth being sucked up into the black hole created by the CERN accelerator. If this is indeed true, then there's no need for that extra memcmp.
, źródło: lwn.net/Articles/307281