UUID-Kollisionen [geschlossen]

33

Hat irgendjemand die Wahrscheinlichkeit von UUID-Kollisionen untersucht, insbesondere mit (zufälligen) UUIDs der Version 4? UUIDs generieren?

Meine Mitarbeiter betrachten das Testen auf UUID-Kollisionen als reine Zeitverschwendung, aber ich habe immer Code eingegeben, um eine doppelte Schlüsselausnahme aus der Datenbank abzufangen und es mit einer neuen UUID erneut zu versuchen. Dies wird das Problem jedoch nicht lösen, wenn die UUID von einem anderen Prozess stammt und auf ein reales Objekt verweist.

Paul Tomblin
quelle
4
Die Frage wurde bereits auf Stack Overflow beantwortet: stackoverflow.com/questions/3038023/… , wie die grundlegende Google-Suche zeigt: google.com/search?q=uuid+collision
Arseni Mourzenko
3
Bei dieser Frage geht es um die spezifischen Algorithmen, die in SQL * Server verwendet werden. Dies ist definitiv KEINE Version 4 (zufällig). Ich frage speziell nach Version 4.
Paul Tomblin
Wollen Sie damit sagen, dass die Implementierung der NEWID()Funktion durch SQL Server nicht zufällig ist? Wenn ja, haben Sie Quellen, um eine solche Behauptung zu stützen? Die Ausgabe sieht für mich eindeutig nach v4-UUIDs aus. NEWSEQUENTIALID()ist entschieden nicht völlig zufällig, aber das ist sein Zweck : UUIDs zu generieren, die gut funktionieren (so wie UUIDs zumindest können) als Indexschlüssel.
ein Lebenslauf am
1
Ich gehe von der Antwort auf die verknüpfte Frage aus, die besagt, dass NEWID () einige Bits der MAC-Adresse enthält, was es zu einer V1- oder V2-UUID macht, nicht zu einer V4.
Paul Tomblin
2
Diese Frage scheint nicht zum Thema zu gehören, da es sich um etwas handelt, über das bereits im Internet, in Büchern und insbesondere bei StackOverflow

Antworten:

18

Wikipedia hat einige Details:

http://en.wikipedia.org/wiki/Universally_unique_identifier

http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates

Die Wahrscheinlichkeit gilt jedoch nur, wenn die Bits vollkommen zufällig sind. Der RFC http://tools.ietf.org/html/rfc4122#page-14, der in der anderen Antwort verlinkt ist, definiert dies jedoch für Version 4:

"4.4. [...] Die Version 4-UUID dient zum Generieren von UUIDs aus wirklich zufälligen oder Pseudozufallszahlen. [...] Setzen Sie alle anderen Bits auf zufällig (oder pseudozufällig) ausgewählte Werte."

Dies ermöglicht so ziemlich alles vom xkcd-Zufallsgenerator http://xkcd.com/221/ bis zu einem Hardwaregerät, das Quantenrauschen verwendet. Die Sicherheitsaspekte im RFC:

"6. Verteilte Anwendungen, die UUIDs auf verschiedenen Hosts generieren, müssen bereit sein, sich bei allen Hosts auf die Zufallszahlenquelle zu verlassen. Wenn dies nicht möglich ist, sollte die Namespace-Variante verwendet werden."

Ich las das wie folgt: Du bist auf dich allein gestellt. Sie sind für Ihren Zufallsgenerator in Ihrer eigenen Anwendung verantwortlich, aber dies und alles andere basiert auf Vertrauen. Wenn Sie Ihrer eigenen Fähigkeit, den Zufallsgenerator Ihrer Wahl richtig zu verstehen und zu verwenden, nicht vertrauen, ist es in der Tat eine gute Idee, nach Kollisionen zu suchen. Wenn Sie dem Programmierer der anderen Prozesse nicht vertrauen, prüfen Sie, ob Kollisionen vorliegen, oder verwenden Sie eine andere UUID-Version.

Sichern
quelle
11

Sie sollten auf jeden Fall feststellen, ob eine Kollision auftritt, und Ihre Anwendung sollte in diesem Fall eine Ausnahme auslösen. Wenn beispielsweise die UUID als Primärschlüssel in der Datenbank verwendet wird, sollte die Datenbank beim Einfügen einer kollidierenden ID einen Fehler auslösen.

Ich würde jedoch glauben, dass das Schreiben von Code zum Generieren einer neuen UUID im Falle einer Kollision und das erneute Versuchen, eine Zeitverschwendung zu sein. Die Wahrscheinlichkeit, dass eine Kollision auftritt, ist so gering, dass das Auslösen einer Ausnahme eine durchaus vernünftige Möglichkeit darstellt, mit ihr umzugehen.

Denken Sie daran, es ist nicht nur eine Verschwendung Ihrer eigenen Zeit, den Code zu schreiben, sondern es macht den Code auch komplexer, was es für die nächste Person schwieriger macht zu lesen, fast ohne Gewinn.

Pete
quelle
2
Ihre UUID ist nur so gut wie Ihr Zufallsgenerator. Bei einem sehr ( sehr ) schlechten Fall treten Kollisionen nicht nur auf, sondern sind unvermeidlich. Das heißt, vielleicht wäre es in der Tat übertrieben, zur Generationszeit nach Duplikaten zu suchen, aber zu erwarten, dass die Situation eintreten könnte, ist meiner Meinung nach nicht so viel zu verlangen. In einigen Bereichen (z. B. im Gesundheitswesen) ist es meines Erachtens erforderlich, Code zu haben, der solche Situationen abfängt (z. B. als Kollisionserkennung in der Datenbank). Sie wären überrascht, wie viel Zeit ich mit dem Debuggen von Situationen verbracht habe, die niemals vorkommen.
Newtopian
1
Ich glaube, ich habe mich nicht klar ausgedrückt. Ich habe die Antwort aktualisiert, um sie expliziter zu gestalten.
Pete
7

Das ist eine sehr gute Frage. Ich glaube nicht, dass es in der Eile angemessen berücksichtigt wurde, UUIDs überall zu verwenden. Ich habe keine solide Forschung gefunden.

Ein Vorschlag: Gehen Sie hier sehr vorsichtig vor und kennen Sie Ihre Kryptographie gut. Wenn Sie eine 128-Bit-UUID verwenden, gibt der Geburtstagseffekt an, dass eine Kollision wahrscheinlich ist, nachdem Sie ungefähr 2 ^ 64 Schlüssel generiert haben , vorausgesetzt, Sie haben 128 Bit Entropie in jedem Schlüssel .

Es ist tatsächlich ziemlich schwierig sicherzustellen, dass dies der Fall ist. Echte Zufälligkeit kann aus (a) radioaktivem Zerfall (b) zufälligem Hintergrundrauschen erzeugt werden, das häufig kontaminiert ist, sofern Sie nicht vorsichtig sind. (C) geeignet ausgewähltes elektronisches Rauschen, z. (Ich habe mit dem letzten gespielt, und es funktioniert wie ein Zauber, Übrigens).

Ich würde Aussagen wie "Ich habe dies seit einem Jahr nicht mehr gesehen" nicht vertrauen, es sei denn, der Benutzer hat etwas erzeugt, das sich 2 ^ 64 (dh ungefähr 10 ^ 19) Schlüsseln nähert, und sie alle gegeneinander überprüft, a nicht-triviale Übung.

Das Problem ist das hier. Angenommen, Sie haben nur 100 Entropiebits, wenn Sie Ihre Schlüssel mit allen anderen Schlüsseln vergleichen, die alle anderen in einem gemeinsamen Schlüsselraum generieren. Sie werden Kollisionen in ca. 2 ^ 50 sehen, dh. ungefähr 10 ^ 15 Schlüssel. Ihre Chancen, eine Kollision zu sehen, wenn Sie Ihre Datenbank mit nur 1000 Milliarden Schlüsseln bevölkert haben, sind weiterhin vernachlässigbar. Und wenn Sie dies nicht überprüfen, werden Sie später unerwartete Fehler erhalten, die sich in Ihre Datenbank mit der Größe von Peta-Zeilen einschleichen. Das könnte hart beißen.

Die Tatsache, dass es mehrere Ansätze zur Generierung solcher UUIDs gibt, dürfte für einen Moment Anlass zur Sorge geben. Wenn Sie feststellen, dass nur wenige Generatoren 'wirklich zufällige' Prozesse mit ausreichender Entropie für eine UUID des Typs 4 verwenden, sollten Sie sich übermäßig Sorgen machen, es sei denn, Sie haben den Entropieinhalt des Generators sorgfältig untersucht. (Die meisten Leute werden dies nicht tun oder wissen gar nicht, wie es geht; Sie könnten mit der DieHarder Suite beginnen). Verwechseln Sie die Erzeugung von Pseudozufallszahlen NICHT mit der Erzeugung echter Zufallszahlen.

Es ist wichtig, dass Sie erkennen, dass die Entropie, die Sie eingeben, die Entropie ist, die Sie haben. Wenn Sie den Schlüssel einfach durch Anwenden einer kryptografischen Funktion stören, ändert sich die Entropie nicht. Es ist möglicherweise nicht intuitiv ersichtlich, dass der Entropieinhalt der folgenden zwei Zeichenfolgen entspricht, wenn mein gesamter Raum die Ziffern 0 und 1 enthält, sofern dies die einzigen beiden Optionen sind: "Dies ist eine wirklich sehr komplexe Zeichenfolge. 293290729382832 * ! @@ # & ^% $$) ,. m} "und" Und JETZT FÜR ETWAS VOLLSTÄNDIG ANDERSES ". Es gibt nur noch zwei Möglichkeiten.

Zufälligkeit ist schwierig in Ordnung zu bringen, und einfach zu glauben, dass "Experten darauf geachtet haben, ist es daher in Ordnung" möglicherweise nicht ausreicht. Erfahrene Kryptografen (und es gibt nur wenige, die wirklich kompetent sind) geben als erste zu, dass sie oft falsch liegen. Wir vertrauten Heartbleed, DigiNotar, etc.

Ich denke, Paul Tomblin ist angemessen vorsichtig. Mein 2c.

user199506
quelle
6

Wenn Sie einen "Zufallszahlengenerator" verwenden und nicht wissen, wie zufällig dieser Generator ist, ist die Kollisionswahrscheinlichkeit tatsächlich unbekannt. Wenn die Zufallszahlengeneratoren in irgendeiner Weise korrelieren, kann sich die Wahrscheinlichkeit einer Kollision dramatisch erhöhen - möglicherweise viele, viele Größenordnungen oder Größenordnungen.

Selbst wenn Sie eine sehr geringe Kollisionswahrscheinlichkeit haben, haben Sie ein grundsätzliches Problem: Die Wahrscheinlichkeit ist NICHT 0. Dies bedeutet, dass eine Kollision letztendlich auftreten WIRD, sie wird nur sehr selten auftreten.

Je häufiger Sie die UUIDs generieren und verwenden, desto eher ist eine Kollision zu erwarten. (1 pro Jahr zu generieren bedeutet eine längere Wartezeit als eine Million pro Sekunde zu generieren, alle anderen Dinge sind gleich).

Wenn diese Wahrscheinlichkeit endlich und unbekannt ist und Sie viele UUIDs verwenden, müssen Sie die Folgen einer Kollision berücksichtigen. Wenn es nicht akzeptabel ist, eine Ausnahme auszulösen und eine Geschäftsanwendung zu beenden, tun Sie es nicht! (Beispiele aus dem Kopf: "Es ist in Ordnung, den Webserver während des Aktualisierens eines Bibliothekseincheckvorgangs herunterzufahren. Es kommt nicht oft vor." "Diese Entscheidungen können karrierebeschränkende Maßnahmen sein.)

Abhängig von Ihrer Anwendung kann der Fall jedoch noch schlimmer sein. Wenn Sie auf das Vorhandensein einer UUID prüfen (dh eine Suche durchführen) und dann eine neue UUID erstellen, falls diese noch nicht vorhanden ist - was häufig genug ist -, stellen Sie möglicherweise fest, dass Sie Datensätze verknüpfen oder Beziehungen herstellen , wenn Sie tatsächlich zwei Dinge über eine UUID anschließen, die nicht angeschlossen werden sollten. Dies ist etwas, bei dem das Auslösen einer Ausnahme nichts löst und irgendwo ein unauffindbares Durcheinander entsteht. Dies führt zu Informationslecks und kann sehr peinlich sein. (Beispiel: Melden Sie sich bei Ihrer Bank an und stellen Sie fest, dass Sie den Saldo eines anderen Kontos sehen können! Schlecht!)

Zusammenfassung: Sie müssen die Art und Weise, wie Ihre UUIDs verwendet werden, und die Folgen einer Kollision berücksichtigen. Dies legt fest, ob Sie darauf achten sollten, Kollisionen zu erkennen und zu vermeiden, im Falle einer Kollision einfache Maßnahmen zu ergreifen oder nichts zu unternehmen. Eine einfache, einheitliche Lösung für alle Fälle ist unter bestimmten Umständen wahrscheinlich ungeeignet.

schnell_nun
quelle
2
"Die Wahrscheinlichkeit (der Kollision) ist NICHT 0" Jede Sequenz mit endlicher Länge hat diese Eigenschaft. Sogar mit einer perfekt zufälligen v4-UUID wird die nächste, die Sie generieren, garantiert eine Kollision sein , sobald Sie 2 ^ 122 eindeutige UUIDs (128 Bits minus 4 Bits Version minus 2 reservierte Bits) generiert haben . Höchstwahrscheinlich würden Sie früher auf eine Kollision stoßen. Die größere Frage ist , ob eine Kollision nach so etwas wie 5e36 Wiederholungen ein Problem, und das kann nicht beantwortet werden , im allgemeinen (obwohl es offensichtlich möglich ist , in jedem Einzelfall zu beantworten), wie Sie in der Zusammenfassung sagen.
ein Lebenslauf am
Na sicher. Dies war eine Aussage des Offensichtlichen (aber immer noch zu wiederholen). Das Problem ist, wie stark die Korrelation zu den Zufallszahlengeneratoren ist. Dies kann die Kollisionswahrscheinlichkeit erheblich erhöhen (2 ^ groß), aber wie viel wissen Sie erst, wenn Sie viel graben, recherchieren oder rechnen. Unter der Annahme, dass die Kollisionswahrscheinlichkeit erheblich schlechter ist als der beste Wert, ist dies wahrscheinlich vernünftig. Danach ... müssen Sie die Konsequenzen abwägen.
quick_now
0

Es gibt zwei Probleme:

  1. Qualität der verwendeten Zufallszahlengeneratoren.

  2. Anzahl der UUIDs, die generiert werden können.

Eine "zufällige" UUID hat 122 zufällige Bits. Unter der Annahme einer perfekten Zufälligkeit können Sie die erste Kollision bei etwa 2 ^ 61 generierten UUIDs erwarten (das ist die Quadratwurzel von 2 ^ 122). Wenn jeder auf dieser Erde eine UUID pro Sekunde erzeugen würde, wären das 10.000.000.000 * 365 * 24 * 60 * 60 = 315360000000000000 UUIDs pro Jahr, was ziemlich nahe an 2 ^ 58 liegt. Das heißt, nach ein paar Jahren würden Sie die ersten Kollisionen bekommen. Wenn sich Ihre Anwendung diesen Zahlen nicht annähert, können Sie ziemlich sicher sein, dass Sie keine Kollision bekommen, wenn Ihr Zufallsgenerator von guter Qualität ist.

Apropos Zufallszahlengenerator: Wenn Sie die Standard-C-Bibliotheksgeneratoren (direkt, indirekt oder ähnliche Generatoren) verwenden und diese wahrscheinlich mit der Zeit aussäen, sind Sie skrewed. Diese können nicht genug Entropie nutzen, um Kollisionen zu vermeiden. Wenn Sie jedoch unter Linux arbeiten, lesen Sie einfach 16 Byte Daten aus /dev/urandom: Dies basiert auf einem Entropie-Pool, der vom Kernel bewegt wird und Zugriff auf einige echte Zufallsereignisse hat. Es sei denn, Sie generieren normalerweise UUIDs, die sich wirklich sehr früh in der Startsequenz befinden, /dev/urandomsollten sich wie eine echte Zufallsquelle verhalten.

cmaster
quelle
-1

Ich habe es einmal mit einem recht einfachen (Brute Force) Programm getestet, das 10 Millionen UUIDs generiert hat, und ich habe keine Kollision erlebt.

Der UUID-RFC besagt, dass es sich bei der UUID nicht nur um eine Reihe von (Pseudo-) Zufallszahlen handelt.

xea
quelle
1
Version 4, nach der ich frage, ist so ziemlich ein Haufen von Zufallszahlen, mit Ausnahme der 6 Bits, die in allen genau gleich sind.
Paul Tomblin
8
10 Millionen sind noch nicht einmal ein Tropfen auf den heißen Stein. Es besteht nur eine 1: 3E30-Chance auf eine Kollision. Wenn Sie einen gefunden hätten, hätte ich Ihnen geraten, in jeder Lotterie, die Sie können, ein Ticket zu kaufen!
Ross Patterson
@ RossPatterson, ich habe mich speziell gefragt, ob Sie mehrere hundert Computer haben, die den exakt gleichen pseudozufälligen Algorithmus auf derselben Hardware verwenden, wodurch sich die Kollisionswahrscheinlichkeit dramatisch erhöht. Ich vermute es würde.
Paul Tomblin
1
@Paul - Ich hätte nur gedacht, wenn der anfängliche Aussaatprozess nicht genügend Entropie aufweist - zum Beispiel, wenn der Samen erst ab der Tageszeit erzeugt wird und alle Ihre Maschinen sehr nahe am selben Zeitpunkt gestartet sind. Ich bezweifle sehr, dass das Seeding so schwach ist - es ist sogar möglich, dass Hardware-Seriennummern verwendet werden, die natürlich für jede Maschine einzigartig wären.
Steve314
1
Leider kann die Aussaat sehr schwach sein. Linux-Systeme lieben es, PRNG aus sehr zufälligen Quellen (Gerätetreiberaktivität usw. ) zu extrahieren. In anderen Umgebungen ist es jedoch Standard, den aktuellen Zeitstempel zu verwenden, was ein Problem sein kann, wenn genügend Maschinen zeitnah synchronisiert sind.
Ross Patterson