Konfliktid lühendatud identifikaatorite komiteedes Linuxi tuumas

Kees Cook, endine kernel.org'i peamine süsteemiadministraator ja Ubuntu Security Team'i juht, demonstreeris võimalust luua töötlus, mille lühendatud identifikaator kattub varasemalt Linuxi tuumas lisatud töötlusega. Eksperiment viidi läbi tõendina 16-märgiste töötluse lühendatud identifikaatorite kasutuselevõtu mõistlikkusele Linuxi tuumas, mis oli varem arutelul tuuma arendajate postitusloendis, kuid ei olnud Linus Torvaldsi poolt heaks kiidetud.

Lühendatud identifikaatorid luuakse SHA-1 räsist esimesed 12 märki (48 bitti 160 bitist) eemaldades. Kuna tuumas SHA-1 räsiga identifitseeritavate objektide arv on ületanud 13 miljonit, on 12-märgiste prefikside kasutamisel kokkulangemise tõenäosus muutunud ajaküsimuseks. Näiteks on tuumas juba lisatud objekte, mille 11-märgised identifikaatorid kattuvad. Samuti mainitakse, et 12-märgiste identifikaatorite kattumist on juba registreeritud oktoobris, kuid enne patši saatmist tuvastas utiliit checkpatch probleemid.

Lühendatud identifikaatoreid kasutatakse lühikeste linkide avaldamiseks töötlustele ja need on näidatud ka muudatuste saatmisel 'Fixes' sildiga, viidates töötlusele, mille probleem on saadetud patšis lahendatud (näiteks 'Fixes: e21d2170f366'). Kokkupuuded, kus mitu erinevat muudatust on seotud ühe lühendatud identifikaatoriga, võivad rikkuda tööriistu, mis analüüsivad ja kontrollivad muudatusi, arvestades 'Fixes' siltide sisu. Näiteks arvestatakse neid silte check_fixes töötlejas, mida rakendatakse linux-next harus, samuti haavatavuste parandamise ja patšide eluiga jälgivate analüüsi skriptides.

Linus Torvalds suhtus skepsisega ettepanekusse suurendada lühikeste identifikaatorite minimaalset suurust, kuna tegelikult on commit'ide arv hoidlas märgatavalt väiksem kui objektide arv (umbes 1/8). Tõenäoliselt, kui juhuslikud kattumised tekivad, siis need toimuvad commit'i ja mõne teise objekti vahel (näiteks blob'i või haru vahel). Tema arvates on lühikesed identifikaatorid lühikesed just selleks, et olla arusaadavad, loetavad ja hõlpsasti tsiteeritavad, ning nende suuruse suurendamiseks pole praegu objektiivseid põhjuseid.

Üks arendajatest pakkus välja, et saab vähendada suurust, suurendades märgatavate bittide arvu, kasutades uut formaati, mis põhineb Base36 kodeeringul (märgid 0-9a-z) asemele kuuekohalistele numbritele. Linuse arvates toob selline muudatus rohkem probleeme kui lahendusi. Näiteks tuleb uue formaadi toetuse lisamiseks olemasolevatesse utiliitidesse ja luua formaadi identifikaator, et eristada vana ja uut formaati.

Käesoleva probleemi demonstreerimiseks, et lühikeste identifikaatorite probleem ei ole teoreetiline ja seda ei tohi edasi lükata, koostas Kees Cook muutuse tuumadokumentatsioonis, mille lühikese identifikaatori (1da177e4c3f4) kokku langes tuuma haru loomise commit'iga 2.6.12-rc2. Kattuvuse leidmiseks kulus 6 tundi arvutuskäiku NVIDIA GeForce RTX 3080 GPU süsteemis.

Leidmine viidi läbi lucky-commit tööriista abil — sihitud plaastri tekstile lisati juhuslikke tühikuid, kuni 12- tähine SHA-1 eelvorming kattus tuumas juba olemasolevate commit'ide eelvormingutega. Kees arvates on probleemiks mitte niivõrd juhuslikud kattumised, kuivõrd lühikeste identifikaatorite kuritarvitamise võimalus kahjulikes eesmärkides, näiteks mõne kontrolli ületamiseks.

Allikas: opennet.ru