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.
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.
Shortened identifiers are used when publishing short links to commits and are specified when sending changes in the 'Fixes' tag, as a reference to the commit where the issue was resolved in the submitted patch (for example, 'Fixes: e21d2170f366'). The occurrence of collisions where multiple different changes are associated with the same shortened identifier can lead to malfunctions in the tools for analyzing and reviewing changes that consider the content of the 'Fixes' tags. For example, these tags are taken into account by the check_fixes handler used in the linux-next branch, as well as in scripts for vulnerability patch analysis and tracking the lifecycle of patches.
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.
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.
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.
The matching was performed using the lucky-commit tool — random whitespace was added to the text of the target patch until the 12-character SHA-1 prefix matched existing prefixes of commits in the kernel. According to Kees, the issue is not so much random collisions as the potential for manipulation of shortened identifiers for malicious purposes, such as bypassing certain checks.
Source: opennet.ru
