Kees Cook, exadministrador del sistema principal de kernel.org y líder del equipo de seguridad de Ubuntu, demostró la posibilidad de crear un commit cuyo identificador breve coincide con un commit previamente añadido al núcleo de Linux. El experimento se realizó como prueba de la viabilidad de cambiar a identificadores de commit abreviados de 16 caracteres en el núcleo de Linux, previamente discutido en la lista de correo de desarrolladores del núcleo, pero no aprobado por Linus Torvalds.
Los identificadores de commit abreviados se forman al dejar los primeros 12 caracteres del hash SHA-1 (48 bits de 160 bits). Dado que el número de objetos en el núcleo, identificados a través del hash SHA-1, ha superado los 13 millones, la ocurrencia de colisiones al utilizar un prefijo de 12 caracteres se ha vuelto cuestión de tiempo. Se muestran, como ejemplo, los objetos ya añadidos al núcleo que se intersectan por sus identificadores de 11 caracteres. Además, se menciona que ya se habían registrado intersecciones de identificadores de 12 caracteres en octubre, pero antes de enviar el parche se detectó con la utilidad checkpatch.
Los identificadores abreviados se utilizan al publicar enlaces cortos a commits, así como se indican al enviar cambios en la etiqueta 'Fixes', como referencia al commit en el que se resolvió el problema en el parche enviado (por ejemplo, 'Fixes: e21d2170f366'). La ocurrencia de colisiones, donde varios cambios diferentes están vinculados a un mismo identificador abreviado, puede llevar a un mal funcionamiento de las herramientas para analizar y verificar cambios, que tienen en cuenta el contenido de las etiquetas 'Fixes'. Por ejemplo, esos tags se toman en cuenta en el controlador check_fixes, utilizado en la rama linux-next, así como en scripts de análisis de correcciones de vulnerabilidades y seguimiento del ciclo de vida de parches.
Linus Torvalds mostró escepticismo ante la propuesta de aumentar el tamaño mínimo de los identificadores abreviados, ya que, de hecho, el número de commits en el repositorio es notablemente menor que el de los objetos (aproximadamente 1/8). Es probable que, si ocurren intersecciones aleatorias, estas sean entre un commit y un objeto de otro tipo (por ejemplo, un blob o una rama). En su opinión, los identificadores abreviados están diseñados para ser visuales, legibles y fácilmente citables, y por ahora no hay razones objetivas para aumentar su tamaño.
Uno de los desarrolladores propuso lograr una reducción del tamaño al aumentar el número de bits significativos, utilizando un nuevo formato basado en la codificación Base36 (símbolos 0-9a-z) en lugar de dígitos hexadecimales. Según Linus, este cambio generaría más problemas de los que resolvería. Por ejemplo, sería necesario añadir soporte para el nuevo formato en las utilidades existentes e introducir un identificador de formato para diferenciar entre el formato antiguo y el nuevo.
Para demostrar que el problema de los identificadores abreviados no es meramente teórico y que su solución no debe posponerse, Kees Cook elaboró un cambio en la documentación del núcleo, cuyo identificador abreviado (1da177e4c3f4) coincidió con el identificador de commit de la creación de la rama del núcleo 2.6.12-rc2. El choque se logró encontrar tras 6 horas de cálculos en un sistema con GPU NVIDIA GeForce RTX 3080.
La búsqueda se realizó utilizando la herramienta lucky-commit, añadiendo espacios aleatorios al texto del parche objetivo hasta que un prefijo SHA-1 de 12 caracteres coincidió con los prefijos de los commits ya presentes en el núcleo. En opinión de Kees, el problema radica no tanto en las intersecciones aleatorias, sino en la posibilidad de manipulación de los identificadores abreviados con fines maliciosos, por ejemplo, para eludir ciertas verificaciones.
Fuente: opennet.ru
