Entwicklertools · UUID Generator
Wie viele Zufallsbits hat ein v4 UUID? 122, nicht 128
· Wie es funktioniert
UUID Kryptographie Browser-APIs
Sechs der 128-Bits in einem zufälligen UUID sind durch den Standard festgelegt, so dass 122 für die Zufälligkeit übrig bleibt. Dieser Beitrag zeigt, wie man Kollisionswahrscheinlichkeiten ehrlich einschätzt und warum echte Kollisionen von defekten Generatoren herrühren und nicht von der Mathematik.
Die Frage des Architekten: Werden wir jemals ein Duplikat bekommen? – woher die Sorge kommt und warum die Antwort vom Generator abhängt
Der Architekt fragt: Wenn wir zehn Jahre lang 10 Millionen UUIDs pro Tag generieren, erhalten wir dann jemals ein Duplikat? Die ehrliche Antwort lautet: Mit ziemlicher Sicherheit nicht, wenn der Generator kryptografisch sicher ist; mit ziemlicher Sicherheit ja, wenn der Generator kaputt ist. Die RFC-9562-Mathematik ist fundiert: Ein v4 UUID mit 122 Zufallsbits hat eine Kollisionswahrscheinlichkeit von ungefähr n² / 2 hoch 123, wobei n die Anzahl der generierten Bezeichner ist. Für die meisten realen Systeme ist diese Wahrscheinlichkeit vernachlässigbar. Der Haken daran ist, dass diese Formel davon ausgeht, dass jedes Bit wirklich zufällig ist. Wenn der Generator leckt oder sich wiederholt oder vorhersehbar ausgelöst wurde, ist die Formel falsch und Duplikate sind unvermeidlich. Das 128-Bit-Layout umfasst vier Versionsbits (0100 für v4) und zwei Variantenbits (10 für RFC 9562), die durch den Standard festgelegt und festgelegt sind.
Für welche sechs Bits gesprochen wird – die vier Versionsbits und zwei Variantenbits, und warum sie gesetzt und nicht zufällig sind
Damit bleiben 122 Bits für den Zufall übrig. Die Formulierung wird manchmal als 2 für die Zufallsbits 122 bezeichnet, wodurch eindeutige Werte erzeugt werden. Unter Verwendung der Geburtstagsparadox-Näherung beträgt die Wahrscheinlichkeit mindestens einer Kollision zwischen n zufällig generierten Werten ungefähr n² / 2 hoch 123. Für n = 1 Millionen ist dies (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36, was etwa 10^-25 entspricht. Für n = 10 Milliarden sind es immer noch etwa 10^-16. Diese sind nicht „effektiv Null“; Sie lauten: „Das werden Sie nie beobachten.“ Die Geburtstagsnäherung bietet eine konkrete Möglichkeit, das Risiko zu berechnen: Zählen Sie die UUIDs, die Sie generieren möchten, quadrieren Sie diese Zahl, dividieren Sie durch 2 hoch 123. Wenn der Generator die crypto.getRandomValues des Browsers sind, wird jedes Bit durch die Entropie des Betriebssystems gestützt. Wenn es eine Mathematik ist.
Die Geburtstagsnäherung im Klartext – die Wahrscheinlichkeit mindestens einer Kollision zwischen n Bezeichnern beträgt ungefähr n zum Quadrat dividiert durch 2 zu 123
Für einen UUID, der von einem ungeeigneten oder wiederholten Zustandsgenerator erzeugt wird, bricht das mathematische Modell zusammen, weil seine Unabhängigkeitsannahme falsch ist. Ein fester Test-Seed, ein kopiertes Fixture oder ein Prozess-Snapshot können Werte wiedergeben, obwohl der Text noch das Halbbyte „version-4“ enthält. Hierbei handelt es sich um Implementierungsfehler und nicht um einen Beweis dafür, dass die Berechnung des 122-Felds falsch war. Eine andere alltägliche Quelle ist das Kopieren derselben wörtlichen Kennung in mehrere Vorrichtungen und das spätere Zusammenführen ihrer Daten. Behalten Sie bei der Untersuchung eines Duplikats den Generator, die Seed-Richtlinie, den Prozesslebenszyklus und den Importverlauf bei. Springen Sie nicht von einem wiederholten Wert zu der Behauptung, dass die unabhängige CSPRNG-Ausgabe den UUID-Speicherplatz erschöpft hat.
Ausgearbeitetes Beispiel – Einfügen einer angegebenen Erzeugungsrate und Zeitspanne in die Näherung, wobei jeder Schritt angezeigt wird, damit Sie Ihre eigenen Zahlen ersetzen können
Prozessverzweigung ohne zufällige Neusynchronisierung. Ein Fehler, bei dem Math.random anstelle von crypto.getRandomValues verwendet wurde. Eine Testvorrichtung, die mit demselben UUID in mehreren Reihen handgefertigt wurde und versehentlich in der Produktion verwendet wurde. Eine alte Version einer UUID-Bibliothek, die eine Bereichsbeschränkung oder einen Statusfehler aufwies. Keines dieser Szenarien beinhaltet die Geburtstagsnäherungsmathematik; es handelt sich dabei um fehlerhafte Implementierungen oder Betriebsfehler. Berechnen Sie das Kollisionsrisiko für Ihr System ehrlich: Zählen Sie die Rate der UUID-Erzeugung (pro Sekunde, pro Tag, pro Jahr), projizieren Sie sie auf die Laufzeit des Systems und setzen Sie die Summe in die Geburtstagsformel ein. Wenn Ihr System fünf Jahre lang 100,000 UUIDs pro Tag generiert (insgesamt 182 Millionen), beträgt die Kollisionswahrscheinlichkeit (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, was vernachlässigbar ist.
Woher Duplikate tatsächlich kommen – Math.random-Seeds, geklonte virtuelle Maschinen, gespaltene Prozesse mit kopiertem Status und Kopieren und Einfügen in Vorrichtungen
Wenn Sie ein Jahr lang 10 Millionen pro Sekunde generieren (insgesamt 315 Billionen), beträgt die Wahrscheinlichkeit (3. 15 × 10^14)² / 2^123 ≈ 10^-10, was immer noch verschwindend klein ist. Diese Schätzungen gehen davon aus, dass jedes Bit unabhängig und zufällig ist. Der ToolAcre-Generator verwendet crypto.getRandomValues, wodurch Sie CSPRNG-gestützte Zufälligkeit erhalten. Der Betrieb ist der einzige Teil, dem Sie vertrauen müssen. Verlassen Sie sich niemals auf die Kollisionswahrscheinlichkeit als Vorwand, um ordnungsgemäße Autorisierungsprüfungen zu überspringen. Ein UUID ist kein Passwort, kein Zugriffstoken und kein Geheimnis, selbst wenn es aus 122 Zufallsbits besteht. Die Einzigartigkeit ist der Vorteil; Die Unvorhersehbarkeit ist eine separate (und wichtigere) Eigenschaft, die das Erraten verhindert. Die Geburtstagsmathematik befasst sich mit der Einzigartigkeit; Es befasst sich nicht mit der Lebensdauer (sollte dieser UUID ablaufen?), der Geheimhaltung (muss er vor der Speicherung gehasht werden?) oder der Autorisierung (beweist der Besitz dieses UUID etwas über den Aufrufer?). Der ToolAcre-Generator liefert Ihnen CSPRNG-gestützte UUIDs mit 122 Zufallsbits, was bedeutet, dass die mathematische Einzigartigkeit und die Unvorhersehbarkeit solide sind. Alles andere – Token-Validierung, Ablauf, Zugriffskontrolle – liegt in der Verantwortung Ihrer Anwendung. Die Wahrscheinlichkeitsformel geht davon aus, dass jedes generierte UUID unabhängig von früheren Generationen ist. Wenn Ihr System Bezeichner aus einer einzelnen CSPRNG-Instanz generiert und jeder Aufruf neue Zufälligkeiten vom Betriebssystem bezieht, gilt die Unabhängigkeitsannahme. Wenn Ihr System einen zwischengespeicherten CSPRNG-Status oder einen gesetzten Generator ohne erneutes Betriebssystem-Seeding verwendet, ist die Annahme ungültig. Das Kollisionsrisiko erhöht sich dramatisch, wenn die Entropiequelle erschöpft ist (tritt bei einigen eingebetteten Systemen oder virtuellen Maschinen unter Last auf) oder wenn der Zufallszustand zwischen Prozessen nie zurückgesetzt wird (Prozessverzweigung ohne erneutes Seeding des CSPRNG).
Was dies nicht abdeckt – die Einzigartigkeit von v1 und v7, die auf Zeitstempeln und Taktsequenzen und nicht nur auf Zufälligkeit beruht
Der ToolAcre-Fallback ruft crypto.getRandomValues für jedes Byte-Array auf und enthält keinen PRNG-Status auf Anwendungsebene. Die internen Aspekte der Plattform liegen weiterhin in der Verantwortung des Browsers und des Betriebssystems. Die Simulation von Kollisionen mit realen Generatoren zeigt den Unterschied zwischen Theorie und gebrochener Praxis. Ein mit Math.random erstellter Generator, der mit demselben Startwert beginnt, erzeugt identische Sequenzen; Sie werden die erste UUID-Kollision innerhalb einiger hundert bis einiger tausend generierter Werte sehen, nicht nach 2^60-Werten (der Quadratwurzel von 2^122), wie die Geburtstagsnäherung vorhersagt. Ein Generator, der crypto.getRandomValues aus einer soliden Betriebssystementropie verwendet, erzeugt Kollisionen nur dann, wenn die theoretische Wahrscheinlichkeit unvermeidbar wird (ungefähr 2^60 UUIDs), eine Zahl, die so groß ist, dass Sie sie nie erreichen werden. Ein Generator, der eine schwache oder wiederverwendete Entropiequelle verwendet (häufig in schlecht implementierten UUID-Bibliotheken oder Test-Frameworks), erzeugt irgendwo dazwischen Kollisionen.
Takeaway: Vertrauen Sie der Mathematik, prüfen Sie den Generator – der ToolAcre-Generator verwendet das CSPRNG des Browsers, das ist der Teil, der nicht gefälscht werden darf
Ein Batch-Test kann eine Implementierung abfangen, die eine Konstante zurückgibt oder eine offensichtliche Sequenz wiedergibt, aber ein bestandenes Beispiel kann die zukünftige Einzigartigkeit nicht beweisen. Produktionssysteme sollten immer noch eine Eindeutigkeitsbeschränkung erzwingen, wenn doppelte Bezeichner Daten beschädigen würden. Importe verdienen besondere Aufmerksamkeit, da zwei gültige Quellsysteme möglicherweise bereits denselben Literalbezeichner enthalten und Geräte umgebungsübergreifend kopiert werden können. Die Tests von ToolAcre prüfen, ob ein Stapel von 500 500 unterschiedliche Werte enthält; Das ist eine Regressionsprüfung für diese Implementierung, keine statistische Garantie. Wenn ein Duplikat auftritt, bewahren Sie Beweise auf und überprüfen Sie die Erzeugungs-, Import-, Vorrichtungs- und Speicherpfade, bevor Sie eine Ursache angeben.