Kees Cook, bývalý hlavní systémový administrátor kernel.org a vedoucí týmu Ubuntu Security, demonstroval možnost vytvoření commitu, jehož zkrácený identifikátor se shoduje s commitem, který byl dříve přidán do jádra Linux. Experiment byl proveden jako důkaz vhodnosti přechodu na 16 znakové zkrácené identifikátory commitů v jádře Linux, o čemž se již dříve diskutovalo v mailing listu vývojářů jádra, ale nebylo to schváleno Linusem Torvaldsem.
Zkrácené identifikátory commitů se vytvářejí ponecháním prvních 12 znaků z hash SHA-1 (48 bitů z 160 bitů). Vzhledem k tomu, že počet objektů v jádře, které jsou identifikovány pomocí hash SHA-1, překročil 13 milionů, stalo se vznikání kolizí při použití 12-znakových prefixů otázkou času. Jako příklad byly uvedeny již přidané objekty do jádra, které se kříží podle svých 11-znakových identifikátorů. Dále bylo zmíněno, že křížení 12-znakových identifikátorů již bylo zaznamenáno v říjnu, ale před odesláním patch byl odhalen utilitou checkpatch.
Zkrácené identifikátory se používají při publikaci krátkých odkazů na commits a také se uvádějí při odesílání změn v tagu „Fixes”, jako odkaz na commit, kde byla odstraněna problém v odeslaném patchi (například „Fixes: e21d2170f366”). Vznikající kolize, kdy jsou s jedním zkráceným identifikátorem spojena různá změny, mohou vést k porušení funkcionality nástrojů pro analýzu a kontrolu změn, které zohledňují obsah tagů „Fixes”. Například, tyto tagy jsou zohledňovány v handleru check_fixes, aplikovaném ve větvi linux-next, jakož i v skriptech pro analýzu oprav zranitelností a sledování životního cyklu patchů.
Linus Torvalds byl skeptický k návrhu na zvýšení minimální velikosti zkrácených identifikátorů, protože ve skutečnosti je počet commitů v repozitáři výrazně nižší než počet objektů (přibližně 1/8). Je pravděpodobné, že pokud k náhodným kolizím dojde, bude to mezi commitem a objektem jiného typu (například blobem nebo větví). Podle jeho názoru jsou zkrácené identifikátory zkrácené právě proto, aby byly přehledné, čitelné a snadno citovatelné, a pro zvýšení jejich velikosti zatím neexistují objektivní předpoklady.
Jeden z vývojářů navrhl, aby se zmenšení velikosti dosáhlo zvýšením počtu významných bitů pomocí nového formátu založeného na kódování Base36 (znaky 0-9a-z) místo hexadecimálních číslic. Podle Linuse by taková změna vytvořila více problémů, než by vyřešila. Například by bylo nutné přidat podporu nového formátu do stávajících utilit a zavést identifikátor formátu k rozlišení mezi starým a novým formátem.
Aby demonstroval, že problém se zkrácenými identifikátory není pouze teoretický a jeho řešení by se nemělo odkládat, Kees Cook vytvořil změnu v dokumentaci jádra, jejíž zkrácený identifikátor (1da177e4c3f4) se shodoval s identifikátorem commitu pro vytvoření větve jádra 2.6.12-rc2. Kolizi se podařilo nalézt za 6 hodin výpočtů na systému s GPU NVIDIA GeForce RTX 3080.
Nalezení bylo provedeno pomocí nástroje lucky-commit — do textu cílového patchi byly přidávány náhodné mezery, dokud 12-znakový prefix SHA-1 neodpovídal již existujícím prefixům commitů v jádře. Podle názoru Keesa představují problém nejen náhodné kolize, ale především možnost manipulace se zkrácenými identifikátory za účelem zneužití, například pro obcházení určitých kontrol.
Zdroj: opennet.ru
