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

Кейс Кук (Kees Cook), бившият главен системен администратор на kernel.org и лидер на Ubuntu Security Team, демонстрира възможността за създаване на комит, чийто съкратен идентификатор съвпада с комит, преди това добавен в ядрото на 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 или клон). Според него съкратените идентификатори са именно съкратени, за да бъдат ясни, четими и лесни за цитиранe, и засега няма объективни предпоставки за увеличаване на техния размер.

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

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

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

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