Kees Cook, ehemaliger Chief System Administrator von kernel.org und Leiter des Ubuntu Security Teams, hat die Möglichkeit demonstriert, einen Commit mit einer gekürzten Kennung zu erstellen, die mit einem bereits in den Linux-Kernel hinzugefügten Commit übereinstimmt. Dieses Experiment wurde als Nachweis für die Sinnhaftigkeit der Einführung von 16-stelligen gekürzten Commit-Identifikatoren im Linux-Kernel durchgeführt, die zuvor in der Mailingliste der Kernel-Entwickler diskutiert, aber von Linus Torvalds nicht genehmigt wurden.
Gekürzte Commit-Identifikatoren entstehen durch die Verwendung der ersten 12 Zeichen des SHA-1-Hashes (48 Bit aus 160 Bit). Da die Anzahl der im Kernel identifizierten Objekte, die über den SHA-1-Hash identifiziert werden, 13 Millionen überschreitet, ist es nur eine Frage der Zeit, bis Kollisionen bei der Verwendung von 12-stelligen Präfixen auftreten. Beispielsweise werden bereits genutzte Objekte im Kernel gezeigt, die sich durch ihre 11-stelligen Identifikatoren überschneiden. Zudem wird erwähnt, dass bereits im Oktober Kollisionen bei 12-stelligen Identifikatoren festgestellt wurden, bevor der Patch mit dem Tool checkpatch gesendet wurde.
Verkürzte Identifikatoren werden beim Veröffentlichen von Kurzlinks für Commits verwendet und sind auch bei der Übermittlung von Änderungen im Tag „Fixes“ als Verweis auf den Commit angegeben, in dem das Problem, das im eingereichten Patch behoben wurde, festgehalten ist (zum Beispiel „Fixes: e21d2170f366“). Das Auftreten von Kollisionen, bei denen mehrere unterschiedliche Änderungen mit einem einzigen verkürzten Identifikator verknüpft sind, kann dazu führen, dass die Werkzeuge zur Analyse und Überprüfung von Änderungen, die die Inhalte der Tags „Fixes“ berücksichtigen, nicht mehr korrekt funktionieren. Beispielsweise werden diese Tags im Handler check_fixes berücksichtigt, der im Branch linux-next verwendet wird, sowie in den Skripten zur Analyse von Schwachstellenbehebungen und zur Nachverfolgung des Lebenszyklus von Patches.
Linus Torvalds äußerte sich skeptisch zu dem Vorschlag, die minimale Größe der verkürzten Identifikatoren zu erhöhen, da die tatsächliche Anzahl der Commits im Repository deutlich geringer ist als die Anzahl der Objekte (etwa 1/8). Wahrscheinlich werden zufällige Überschneidungen nur zwischen einem Commit und einem Objekt eines anderen Typs (zum Beispiel einem Blob oder einem Branch) auftreten. Seiner Meinung nach sind verkürzte Identifikatoren gerade dafür gedacht, anschaulich, leserlich und leicht zitierbar zu sein, und es gibt derzeit keine objektiven Gründe, ihre Größe zu erhöhen.
Einer der Entwickler schlug vor, die Größe zu reduzieren, indem die Anzahl der signifikanten Bits erhöht wird, wobei ein neues Format auf der Basis von Base36-Codierung (Zeichen 0-9a-z) anstelle von hexadezimalen Ziffern verwendet wird. Linus ist der Meinung, dass eine solche Änderung mehr Probleme schaffen als lösen würde. Zum Beispiel müsste die Unterstützung für das neue Format in bestehende Utilities integriert und ein Formatbezeichner eingeführt werden, um zwischen dem alten und dem neuen Format zu unterscheiden.
Um zu demonstrieren, dass das Problem mit verkürzten IDs nicht nur theoretisch ist und dessen Lösung nicht aufgeschoben werden sollte, hat Case Cook eine Änderung der Kern-Dokumentation formuliert, deren verkürzte ID (1da177e4c3f4) mit der ID des Commits zur Erstellung des Kern-Branches 2.6.12-rc2 übereinstimmte. Die Kollision konnte in 6 Stunden Berechnungen auf einem System mit einer NVIDIA GeForce RTX 3080 gefunden werden.
Die Suche wurde mit dem Werkzeug lucky-commit durchgeführt — im Text des Ziel-Patches wurden zufällige Leerzeichen hinzugefügt, bis der 12-stellige SHA-1-Präfix mit bereits vorhandenen Präfixen der Commits im Kernel übereinstimmte. Laut Case stellt das Problem nicht so sehr zufällige Überschneidungen dar, sondern die Möglichkeit, verkürzte IDs für schädliche Zwecke zu manipulieren, beispielsweise um bestimmte Überprüfungen zu umgehen.
Quelle: opennet.ru
