Kees Cook, bývalý hlavný systémový administrátor kernel.org a líder Ubuntu Security Team, demonštroval možnosť vytvárania commitu, ktorého skrátený identifikátor sa zhoduje s commitom, ktorý bol predtým pridaný do jadra Linux. Experiment bol vykonaný ako potvrdenie účelnosti prechodu na 16-znakové skrátené identifikátory commitov v jadre Linux, ktoré boli predtým diskutované na zozname diskusie vývojárov jadra, ale neboli schválené Linusom Torvaldsom.
Skrátené identifikátory commitov sa vytvárajú ponechaním prvých 12 znakov od hash SHA-1 (48 bitov z 160 bitov). Keďže počet objektov v jadre identifikovaných cez hash SHA-1 presiahol 13 miliónov, vznik kolízií pri používaní 12-znakového prefixu sa stal otázkou času. Ako príklad sú uvedené už pridelené objekty v jadre, ktoré sa prelínajú vo svojich 11-znakových identifikátoroch. Okrem toho sa spomína, že sa už v októbri zaznamenali kolízie 12-znakových identifikátorov, no pred odoslaním patchu to bolo zistené utilitou checkpatch.
Skrátené identifikátory sa používajú pri publikovaní krátkych odkazov na commity a sú uvádzané pri odosielaní zmien s tagom "Fixes", ako odkaz na commit, problém v ktorom bol vyriešený v zaslanom patche (napríklad "Fixes: e21d2170f366"). Vznik kolízií, pri ktorých súčasne viaceré rôzne zmeny sa viažu na jeden skrátený identifikátor, môžu viesť k narušeniu činnosti nástrojov na analýzu a kontrolu zmien, ktoré zohľadňujú obsah tagov "Fixes". Napríklad, tieto tagy sú zohľadňované v spracovateľovi check_fixes, ktorý sa používa vo vetve linux-next, ako aj v skriptoch na analýzu opráv chýb a sledovanie životného cyklu patchov.
Linus Torvalds skepticky reagoval na návrh zvýšiť minimálnu veľkosť skrátených identifikátorov, pretože v skutočnosti je počet commitov v repozitári výrazne menší ako počet objektov (približne 1/8). Je pravdepodobné, že ak náhodné prekrytia vzniknú, tak budú medzi commitom a objektom iného typu (napríklad blobom alebo vetvou). Podľa jeho názoru sú skrátené identifikátory navrhnuté tak, aby boli prehľadné, čitateľné a ľahko citovateľné, a zatiaľ neexistujú objektívne predpoklady na zvýšenie ich veľkosti.
Jeden z vývojárov navrhol dosiahnuť zmenšenie veľkosti pri zvýšení počtu významných bitov použitím nového formátu založeného na kódovaní Base36 (znaky 0-9a-z) namiesto hexadecimálnych číslic. Podľa Linusa by takéto zmeny vytvorili viac problémov, než by vyriešili. Napríklad by bolo potrebné pridať podporu pre nový formát do existujúcich utilít a zaviesť identifikátor formátu, aby sa rozlíšil starý a nový formát.
Na demonštráciu toho, že problém so skrátenými identifikátormi nie je hypotetický a jeho riešenie sa neoplatí odkladať, Kees Cook vypracoval zmenu dokumentácie jadra, skrátený identifikátor ktorej (1da177e4c3f4) sa zhodoval s identifikátorom commitu na vytvorenie vetvy jadra 2.6.12-rc2. Kolíziu sa podarilo nájsť za 6 hodín výpočtov na systéme s GPU NVIDIA GeForce RTX 3080.
Vyhľadávanie sa vykonalo pomocou nástroja lucky-commit — do textu cieľového patchu sa pridávali náhodné medzery, kým sa 12-znakový prefix SHA-1 nezrovnal s existujúcimi prefixmi commitov v jadre. Podľa názoru Keesa predstavujú problém nie toľko náhodné prekrytia, ako skôr možnosť manipulácie s skrátenými identifikátormi na zlé účely, napríklad na obídenie určitých overení.
Zdroj: opennet.ru
