Kees Cook, tidigare huvudsystemadministratör för kernel.org och ledare för Ubuntu Security Team, demonstrerade möjligheten att skapa en commit med en förkortad identifierare som matchar en commit som tidigare lagts till i Linux-kärnan. Experimentet genomfördes för att bekräfta rimligheten av att övergå till 16-teckens förkortade identifierare för commits i Linux-kärnan, som tidigare diskuterats i mailinglistan för kärnans utvecklare, men inte godkänts av Linus Torvalds.
Förkortade identifierare för commits skapas genom att behålla de första 12 tecknen från SHA-1-hashen (48 bitar av 160 bitar). Eftersom antalet objekt i kärnan som identifieras via SHA-1-hashen har överstigit 13 miljoner, har uppkomsten av kollisioner med bruk av 12-teckens prefix blivit en tidsfråga. Som exempel visas redan tillagda objekt i kärnan som överlappar med sina 11-teckens identifierare. Dessutom nämns att kollisioner med 12-teckens identifierare redan har registrerats i oktober, men innan patchen skickades upptäcktes detta av verktyget checkpatch.
Förkortade identifierare används vid publicering av korta länkar till commits samt anges vid inskickande av ändringar i taggen "Fixes" som en referens till den commit där problemet har åtgärdats i den skickade patchen (till exempel "Fixes: e21d2170f366"). Uppkomsten av kollisioner, där flera olika ändringar kopplas till en och samma förkortade identifierare, kan leda till att verktyg för analys och kontroll av ändringar, som tar hänsyn till innehållet i "Fixes"-taggarna, fungerar felaktigt. Till exempel beaktas dessa taggar i hanteraren check_fixes, som används i linux-next-grenen, samt i skripten för analys av sårbarhetsfixar och spårning av patchars livscykel.
Linus Torvalds var skeptisk till förslaget att öka den minimi storlek på förkortade identifierare, eftersom antalet commits i repositoryt faktiskt är avsevärt mindre än antalet objekt (ungefär 1/8). Troligtvis om några slumpmässiga kollisioner skulle inträffa, skulle de vara mellan en commit och objekt av någon annan typ (till exempel en blob eller en gren). Enligt hans åsikt är förkortade identifierare just förkortade för att vara överskådliga, läsbara och lättare att citera, och det finns för närvarande inga objektiva skäl att öka deras storlek.
En av utvecklarna föreslog att uppnå en minskning av storleken genom att öka antalet betydelsefulla bitar, genom att använda ett nytt format baserat på Base36-kodning (tecken 0-9a-z) istället för hexadecimala siffror. Enligt Linus skulle en sådan förändring skapa fler problem än den löser. Till exempel skulle det krävas att lägga till stöd för det nya formatet i befintliga verktyg och införa ett formatidentifierare för att särskilja det gamla och det nya formatet.
För att demonstrera att problemet med förkortade identifierare inte är teoretiskt och att en lösning inte kan skjutas upp, formulerade Kees Cook en ändring av kärnans dokumentation, vars förkortade identifierare (1da177e4c3f4) överensstämde med identifieraren för committen som skapade kärngrenen 2.6.12-rc2. Kollisionen lyckades hitta efter 6 timmars beräkningar på ett system med GPU NVIDIA GeForce RTX 3080.
Hittandet genomfördes med hjälp av verktyget lucky-commit - i texten av den målpatchet lades slumpmässiga mellanslag till tills den 12-tecken långa SHA-1-prefixet överensstämde med redan befintliga prefix i kärnans commits. Enligt Kees är det inte så mycket de slumpmässiga kollisionerna som utgör ett problem, utan möjligheten till manipulation av de förkortade identifierarna för skadliga syften, till exempel för att kringgå vissa kontroller.
Källa: opennet.ru
