Колизии в съкратените идентификатори на комитите в ядрото на Linux

Кейс Кук (Kees Cook), бившият главен системен администратор на kernel.org и ръководител на екипа по сигурността на Ubuntu, демонстрира възможността за създаване на комит, чийто съкратен идентификатор съвпада с комита, който вече е добавен в ядрото на Linux. Експериментът е проведен като потвърждение на целесъобразността от преминаване към 16-символни съкратени идентификатори на комити в ядрото на Linux, който беше обсъждан в пощенския списък на разработчиците на ядрото, но не беше одобрен от Линус Торвалдс.

Съкратените идентификатори на комити се генерират, като се оставят първите 12 символа от хеша SHA-1 (48 бита от 160 бита). Тъй като броят на обектите в ядрото, идентифицирани чрез хеша SHA-1, надхвърли 13 милиона, възникването на колизии при използването на 12-символен префикс стана въпрос на време. Като примери са показани вече добавени в ядрото обекти, които се пресичат по своите 11-символни идентификатори. Освен това е споменато, че пресичането на 12-символни идентификатори вече е регистрирано през октомври, но преди изпращането на патча е била установена проблема с утилитата checkpatch.

Съкратените идентификатори се използват при публикуването на кратки връзки към комити, а също така се указват при изпращането на промени в етикета „Fixes“, като се посочва комитът, чиято проблема е решена в изпратения патч (например „Fixes: e21d2170f366“). Възникването на колизии, при които няколко различни промени се свързват с един съкратен идентификатор, може да доведе до нарушения в работата на инструментите за анализ и проверка на промените, вземащи предвид съдържанието на етикетите „Fixes“. Например, тези етикети се вземат предвид в обработчика check_fixes, използван в клона linux-next, както и в скриптовете за анализ на поправки на уязвимости и проследяване на жизнения цикъл на патчовете.

Линус Торвалдс скептично реагира на предложението за увеличаване на минималния размер на съкратените идентификатори, тъй като всъщност броят на комитите в репозитория е значително по-малък от броя на обектите (около 1/8). Най-вероятно, ако случайни съвпадения се появят, те ще бъдат между комит и обект от друг тип (например, blob или branch). Според него съкратените идентификатори са наистина съкратени, за да бъдат видими, четими и лесно цитируеми, и в момента няма обективни предпоставки за увеличаване на техния размер.

Един от разработчиците предложи да се постигне намаляване на размера чрез увеличаване на броя значими битове, използвайки нов формат на базата на кодировка Base36 (символи 0-9a-z) вместо шестнадесетични цифри. Според Линус подобно изменение ще създаде повече проблеми, отколкото ще реши. Например, ще трябва да се добави поддръжка на новия формат в съществуващите утилити и да се въведе идентификатор на формата, за да се различават стария и новия формат.

За да демонстрира, че проблемът със съкратените идентификатори не е абстрактен и решаването му не трябва да се отлага, Кейс Кук формулира изменение на документацията на ядрото, съкратеният идентификатор на което (1da177e4c3f4) съвпада с идентификатора на комита за създаване на клона на ядрото 2.6.12-rc2. Колизията беше подбрана за 6 часа изчисления на система с GPU NVIDIA GeForce RTX 3080.

Подборът е извършен с помощта на инструмента lucky-commit — в текста на целевия патч са добавяни случайни интервали, докато 12-символният префикс SHA-1 не съвпадне с вече съществуващите в ядрото префикси на комитите. Според Кейс проблемът не представляват толкова случайните съвпадения, колкото възможността за манипулация със съкратените идентификатори с вредоносна цел, например, за заобикаляне на проверки.

Източник: opennet.ru