Коллизии в сокращённых идентификаторах коммитов в ядре 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). Скорее всего, если случайные пересечения и возникнут, то они будут между коммитом и объектом какого-то другого типа (например, блобом или веткой). По его мнению сокращённые идентификаторы на то и сокращённые, чтобы быть наглядными, читаемыми и легко цитируемыми, и для увеличения их размера пока нет объективных предпосылок.

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

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

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

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