Case Kees Cook, former chief system administrator of kernel.org and leader of the Ubuntu Security Team, demonstrated the possibility of creating a commit whose shortened identifier matches a commit previously added to the Linux kernel. The experiment was conducted as proof of the feasibility of transitioning to 16-character shortened commit identifiers in the Linux kernel, which had previously been discussed in the kernel developers' mailing list but not approved by Linus Torvalds.
Shortened commit identifiers are formed by truncating the first 12 characters of the SHA-1 hash (48 bits from 160 bits). As the number of objects in the kernel identified by the SHA-1 hash has exceeded 13 million, the occurrence of collisions when using a 12-character prefix has become a matter of time. For example, previously added kernel objects intersecting by their 11-character identifiers are shown. Furthermore, it is mentioned that the intersection of 12-character identifiers was already recorded in October, but the checkpatch utility revealed issues before the patch was sent.
Shortened identifiers are used when publishing short links to commits, as well as specified when sending changes in the 'Fixes' tag, as a reference to the commit where the problem was resolved in the submitted patch (e.g., 'Fixes: e21d2170f366'). The occurrence of collisions, where multiple different changes are linked to one shortened identifier, can lead to malfunctions in tools for analyzing and verifying changes, taking into account the contents of 'Fixes' tags. For example, these tags are considered in the check_fixes handler used in the linux-next branch, as well as in scripts for analyzing vulnerabilities and tracking the lifecycle of patches.
Linus Torvalds był sceptycznie nastawiony do propozycji zwiększenia minimalnego rozmiaru skróconych identyfikatorów, ponieważ w rzeczywistości liczba commitów w repozytorium jest znacznie mniejsza niż liczba obiektów (około 1/8). Prawdopodobnie, jeśli przypadkowe kolizje się pojawią, będą miały miejsce pomiędzy commitem a obiektem innego typu (na przykład, blobem lub gałęzią). Jego zdaniem skrócone identyfikatory są takie, aby były czytelne, przejrzyste i łatwe do cytowania, a na razie nie ma obiektywnych przesłanek do ich zwiększenia.
Jeden z deweloperów zaproponował osiągnięcie mniejszego rozmiaru poprzez zwiększenie liczby znaczących bitów, używając nowego formatu opartego na kodowaniu Base36 (znaki 0-9a-z) zamiast szesnastkowych cyfr. Według Linusa taka zmiana stworzy więcej problemów, niż rozwiąże. Na przykład konieczne będzie dodanie wsparcia dla nowego formatu w istniejących narzędziach oraz wprowadzenie identyfikatora formatu, aby odróżnić stary od nowego formatu.
Aby pokazać, że problem ze skróconymi identyfikatorami nie jest teoretyczny i jego rozwiązanie nie powinno być odkładane, Kees Cook stworzył zmianę w dokumentacji jądra, której skrócony identyfikator (1da177e4c3f4) zbiega się z identyfikatorem commitu, który stworzył gałąź jądra 2.6.12-rc2. Kolizję udało się znaleźć w ciągu 6 godzin obliczeń na systemie z GPU NVIDIA GeForce RTX 3080.
Poszukiwania były prowadzone z użyciem narzędzia lucky-commit — do tekstu docelowej łatki dodawane były przypadkowe spacje, aż 12-znakowy prefiks SHA-1 zbiegł się z już istniejącymi w jądrze prefiksami commitów. Według Keesa problemem są nie tyle przypadkowe kolizje, co możliwość manipulacji skróconymi identyfikatorami w celach złośliwych, na przykład w celu ominięcia jakichś weryfikacji.
Źródło: opennet.ru
