{"id":121189,"date":"2024-12-31T15:46:00","date_gmt":"2024-12-31T13:46:00","guid":{"rendered":"https:\/\/prohoster.info\/blog\/novosti-interneta\/kollizii-v-sokrashhyonnyh-identifikatorah-kommitov-v-yadre-linux"},"modified":"2024-12-31T15:46:00","modified_gmt":"2024-12-31T13:46:00","slug":"kollizii-v-sokrashhyonnyh-identifikatorah-kommitov-v-yadre-linux","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/news\/kollizii-v-sokrashhyonnyh-identifikatorah-kommitov-v-yadre-linux","title":{"rendered":"Collisions in Shortened Commit Identifiers in the Linux Kernel","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"
Kees Cook, former lead system administrator of kernel.org and leader of the Ubuntu Security Team, demonstrated the possibility of creating a commit whose shortened identifier matches a previously added commit in the Linux kernel. This experiment was conducted to confirm the feasibility of transitioning to 16-character shortened commit identifiers in the Linux kernel, which had been previously discussed in the kernel developers' mailing list but not approved by Linus Torvalds. <\/p>\n
Shortened identifiers are generated by truncating the first 12 characters of the SHA-1 hash (48 bits from 160 bits). Given that the number of objects in the kernel identifiable by SHA-1 hash has exceeded 13 million, the occurrence of collisions using a 12-character prefix was just a matter of time. As an example, previously added kernel objects with overlapping 11-character identifiers are shown. Furthermore, it is noted that intersections of 12-character identifiers had already been recorded in October, but a utility called checkpatch identified issues before the patch was sent. <\/p>\n
Shortened identifiers are used when publishing short links to commits and are also specified when sending changes in the 'Fixes' tag, as a reference to the commit that resolved the issue in the submitted patch (for example, 'Fixes: e21d2170f366'). The occurrence of collisions, where multiple different changes are associated with a single shortened identifier, can lead to the malfunctioning of tools for analyzing and verifying changes that consider the content of 'Fixes' tags. For instance, these tags are taken into account in the check_fixes handler used in the linux-next branch, as well as in vulnerability fixing analysis scripts and patch lifecycle tracking. <\/p>\n
Linus Torvalds reacted skeptically to the proposal to increase the minimum size of shortened identifiers, as the actual number of commits in the repository is significantly less than the number of objects (about 1\/8). Most likely, if random collisions do occur, they will be between a commit and an object of a different type (for example, a blob or branch). In his view, shortened identifiers are meant to be visual, readable, and easily quotable, and there are currently no objective grounds for increasing their size. <\/p>\n
One of the developers suggested achieving a reduction in size while increasing the number of significant bits by using a new format based on Base36 encoding (characters 0-9a-z) instead of hexadecimal digits. According to Linus, such a change would create more problems than it solves. For instance, it would be necessary to add support for the new format in existing utilities and introduce a format identifier to distinguish between the old and new formats. <\/p>\n
To demonstrate that the problem with shortened identifiers is not theoretical and that its resolution should not be delayed, Kees Cook formulated a change to the kernel documentation, the shortened identifier of which (1da177e4c3f4) coincided with the commit identifier for creating the kernel branch 2.6.12-rc2. The collision was managed in 6 hours of computation on a system with an NVIDIA GeForce RTX 3080 GPU. <\/p>\n
The match was executed using the lucky-commit tool \u2014 random spaces were added to the text of the target patch until the 12-character SHA-1 prefix matched the prefixes of commits already existing in the kernel. According to Case, the issue lies not so much in random intersections, but in the potential manipulation of shortened identifiers for malicious purposes, such as bypassing certain checks. \n Source: opennet.ru<\/a> <\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"