{"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\/pl\/blog\/news\/kollizii-v-sokrashhyonnyh-identifikatorah-kommitov-v-yadre-linux","title":{"rendered":"Kolizje w skr\u00f3conych identyfikatorach commit\u00f3w w j\u0105drze Linux","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"
Case Kees Cook, former chief system administrator of kernel.org and leader of the Ubuntu Security Team, demonstrated the possibility of creating a commit whose shortened identifier matches a commit previously added to the Linux kernel. The experiment was conducted as proof of the feasibility of transitioning to 16-character shortened commit identifiers in the Linux kernel, which had previously been discussed in the kernel developers' mailing list but not approved by Linus Torvalds. <\/p>\n
Shortened commit identifiers are formed by truncating the first 12 characters of the SHA-1 hash (48 bits from 160 bits). As the number of objects in the kernel identified by the SHA-1 hash has exceeded 13 million, the occurrence of collisions when using a 12-character prefix has become a matter of time. For example, previously added kernel objects intersecting by their 11-character identifiers are shown. Furthermore, it is mentioned that the intersection of 12-character identifiers was already recorded in October, but the checkpatch utility revealed issues before the patch was sent. <\/p>\n
Skr\u00f3cone identyfikatory s\u0105 stosowane przy publikacji kr\u00f3tkich link\u00f3w do commit\u00f3w, a tak\u017ce s\u0105 podawane przy wysy\u0142aniu zmian w tagu «Fixes» jako link do commitu, w kt\u00f3rym problem zosta\u0142 rozwi\u0105zany w przes\u0142anym patchu (na przyk\u0142ad «Fixes: e21d2170f366»). Pojawienie si\u0119 kolizji, w kt\u00f3rych kilka r\u00f3\u017cnych zmian jest powi\u0105zanych z jednym skr\u00f3conym identyfikatorem, mo\u017ce prowadzi\u0107 do zak\u0142\u00f3ce\u0144 w dzia\u0142aniu narz\u0119dzi do analizy i sprawdzania zmian, kt\u00f3re uwzgl\u0119dniaj\u0105 zawarto\u015b\u0107 tag\u00f3w «Fixes». Na przyk\u0142ad, te tagi s\u0105 brane pod uwag\u0119 w obs\u0142udze check_fixes, stosowanej w ga\u0142\u0119zi linux-next, a tak\u017ce w skryptach analizy poprawek podatno\u015bci i \u015bledzenia cyklu \u017cycia patchy. <\/p>\n
Linus Torvalds by\u0142 sceptycznie nastawiony do propozycji zwi\u0119kszenia minimalnego rozmiaru skr\u00f3conych identyfikator\u00f3w, poniewa\u017c w rzeczywisto\u015bci liczba commit\u00f3w w repozytorium jest znacznie mniejsza ni\u017c liczba obiekt\u00f3w (oko\u0142o 1\/8). Prawdopodobnie, je\u015bli przypadkowe kolizje si\u0119 pojawi\u0105, b\u0119d\u0105 mia\u0142y miejsce pomi\u0119dzy commitem a obiektem innego typu (na przyk\u0142ad, blobem lub ga\u0142\u0119zi\u0105). Jego zdaniem skr\u00f3cone identyfikatory s\u0105 takie, aby by\u0142y czytelne, przejrzyste i \u0142atwe do cytowania, a na razie nie ma obiektywnych przes\u0142anek do ich zwi\u0119kszenia. <\/p>\n
Jeden z deweloper\u00f3w zaproponowa\u0142 osi\u0105gni\u0119cie mniejszego rozmiaru poprzez zwi\u0119kszenie liczby znacz\u0105cych bit\u00f3w, u\u017cywaj\u0105c nowego formatu opartego na kodowaniu Base36 (znaki 0-9a-z) zamiast szesnastkowych cyfr. Wed\u0142ug Linusa taka zmiana stworzy wi\u0119cej problem\u00f3w, ni\u017c rozwi\u0105\u017ce. Na przyk\u0142ad konieczne b\u0119dzie dodanie wsparcia dla nowego formatu w istniej\u0105cych narz\u0119dziach oraz wprowadzenie identyfikatora formatu, aby odr\u00f3\u017cni\u0107 stary od nowego formatu. <\/p>\n
Aby pokaza\u0107, \u017ce problem ze skr\u00f3conymi identyfikatorami nie jest teoretyczny i jego rozwi\u0105zanie nie powinno by\u0107 odk\u0142adane, Kees Cook stworzy\u0142 zmian\u0119 w dokumentacji j\u0105dra, kt\u00f3rej skr\u00f3cony identyfikator (1da177e4c3f4) zbiega si\u0119 z identyfikatorem commitu, kt\u00f3ry stworzy\u0142 ga\u0142\u0105\u017a j\u0105dra 2.6.12-rc2. Kolizj\u0119 uda\u0142o si\u0119 znale\u017a\u0107 w ci\u0105gu 6 godzin oblicze\u0144 na systemie z GPU NVIDIA GeForce RTX 3080. <\/p>\n
Podb\u00f3r zosta\u0142 przeprowadzony z u\u017cyciem narz\u0119dzia lucky-commit — do tekstu docelowego patcha dodawane by\u0142y losowe spacje, a\u017c 12-znakowy prefiks SHA-1 zgadza\u0142 si\u0119 z ju\u017c istniej\u0105cymi w j\u0105drze prefiksami commit\u00f3w. Zdaniem Keysa problemem s\u0105 nie tyle przypadkowe kolizje, co mo\u017cliwo\u015b\u0107 manipulacji skr\u00f3conymi identyfikatorami w celach z\u0142o\u015bliwych, na przyk\u0142ad w celu obej\u015bcia pewnych weryfikacji. \n \u0179r\u00f3d\u0142o: opennet.ru<\/a> <\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"