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
