Kees Cook, tidligere hovedsystemadministrator for kernel.org og leder af Ubuntu Security Team, demonstrerede muligheden for at skabe et commit, hvis forkortede identificer svarer til et commit, der tidligere er tilføjet til Linux-kernen. Eksperimentet blev udført som en bekræftelse på rimeligheden af overgangen til 16-tegns forkortede commit-ID'er i Linux-kernen, som tidligere er blevet diskuteret på mailinglisten for kerneludviklere, men ikke godkendt af Linus Torvalds.
Forkortede commit-ID'er dannes ved at tage de første 12 tegn af SHA-1 hash (48 bit ud af 160 bit). Da antallet af objekter i kernen, der identificeres via SHA-1 hash, har oversteget 13 millioner, er det kun et spørgsmål om tid, før der opstår kollisioner ved brug af den 12-tegns præfiks. Som eksempel vises allerede tilføjede objekter i kernen, der krydser hinanden i deres 11-tegns identificeringer. Desuden nævnes det, at krydsninger af 12-tegns identificeringer allerede blev registreret i oktober, men at der blev opdaget problemer med checkpatch-værktøjet, inden patchen blev sendt.
Forkortede identificeringer anvendes ved offentliggørelse af korte links til commits, og de angives også ved indsendelse af ændringer i tagget "Fixes" som et link til det commit, hvor problemet er løst i den indsendte patch (for eksempel "Fixes: e21d2170f366"). Opståen af kollisioner, hvor flere forskellige ændringer er knyttet til én forkortet identificering, kan føre til funktionsforstyrrelser i værktøjer til at analysere og kontrollere ændringer, der tager højde for indholdet af "Fixes"-taggene. For eksempel tages disse tags i betragtning i check_fixes-handleren anvendt i linux-next, samt i analyse-scripts til rettelse af sårbarheder og sporing af patch-livscyklussen.
Linus Torvalds var skeptisk over for forslaget om at øge den minimale størrelse af de forkortede identifikatorer, da antallet af commits i repositoryet faktisk er betydeligt mindre end antallet af objekter (omtrent 1/8). Sandsynligvis, hvis tilfældige overlappinger opstår, vil de være mellem et commit og et objekt af en anden type (for eksempel en blob eller en gren). Ifølge ham er forkortede identifikatorer netop forkortede for at være visuelt tiltalende, læsbare og let citerbare, og der er endnu ikke objektive forudsætninger for at øge deres størrelse.
En af udviklerne foreslog at opnå en reduktion af størrelsen ved at øge antallet af signifikante bits ved at bruge et nyt format baseret på Base36-kodning (tegnene 0-9a-z) i stedet for hexadecimale cifre. Ifølge Linus vil en sådan ændring skabe flere problemer, end den løser. For eksempel vil det kræve at tilføje understøttelse af det nye format i eksisterende værktøjer og introducere et format-id for at skelne mellem det gamle og det nye format.
For at demonstrere, at problemet med forkortede identifikatorer ikke er hypotetisk, og at løsningen ikke bør udsættes, dannede Kees Cook et ændringsforslag til kernen dokumentationen, hvis forkortede identifikator (1da177e4c3f4) stemte overens med identifikatoren for commit, der skabte kernen 2.6.12-rc2. Kollisionen blev fundet efter 6 timers beregning på et system med GPU NVIDIA GeForce RTX 3080.
Opgaven blev udført ved hjælp af værktøjet lucky-commit — der blev tilføjet tilfældige mellemrum til teksten i det målrettede patch, indtil den 12-tegnede SHA-1-præfiks matchede med de allerede eksisterende præfikser af commits i kernen. Ifølge Kees udgør ikke så meget tilfældige overlappinger et problem, som muligheden for manipulation med de forkortede identifikatorer til skadelige formål, for eksempel for at omgå visse kontroller.
Kilde: opennet.ru
