Cross-Plattform tauglicher GUID Generator

hustbaer

Tachyon schrieb:

EDIT: Nein, boost::random_device unterstützt Windows leider nicht. Das Ding kompiliert nur unter BSD oder Linux, wegen
#if defined(__linux__) || defined (__FreeBSD__)
in random_device.cpp . Eine Windows-Variante gibts nicht.

Shit.
Obwohl es recht einfach zu implementieren wäre.
CryptGenRandom() is ja nu wirklich keine Hexerei.
Vielleicht sollte ich nen Patch einschicken...

pumuckl

Tachyon schrieb:

Wegen vorangegangen Vorschlägen:
Einfach nur Pseudorandomnummern zu erzeugen, reicht leider nicht. Irgendwoher muss ein Seed kommen, und dafür benutzt man üblicherweise die Systemzeit. Auf dem System, auf dem die Anwendungen laufen soll, wird die Zeit auf allen Plattformen synchronisiert, wodurch eine recht hohe Wahrscheinlichkeit besteht, dass man gleiche Zufallssequenzen auf verschiedenen Clustern produziert. Das darf aber nicht passieren.

Eine synchronisierte Systemzeit macht nur dann Probleme, wenn die Seeds alle zur gleichen Zeit genommen werden. Falls dem so ist hast du immernoch auf jedem Cluster irgendwo eine Kommunikationsschicht, die das Quatschen mit den anderen Rechnern übernimmt. Die Schicht ist eh schon Plattformabhängig, daher kannst du von ihr aus der Mac-Adresse oder IP-Adresse oder was auch immer eine plattformunabhängige Zahl generieren lassen, die von Cluster zu Cluster verschieden ist. Modifiziere die genommene Systemzeit in geeigneter Weise damit und du hast unterschiedliche Seeds, oder seh ich das falsch?

Tachyon

pumuckl schrieb:

...seh ich das falsch?

Ja, aus meiner Sicht ist das Netzwerk plattformunabhängig, weil ich boost.asio benutze. Darüber gibt es aber keine Möglichkeit, an die MAC-Adresse heranzukommen. An IPs schon eher, aber die sind im System nicht eindeutig.

Tachyon

Keros schrieb:

Hat mit dem Thema schon was zu tun. Wenn das erzeugen von echten Zufallszahlen trivial währe (was ich behaupte das es nicht ist) hätte Tachyon das Problem nicht.

Aus informationstechnischer Sicht echte Zufallszahlen zu erzeugen, ist eigentlich kein großes Problem mehr. Die meisten Betriebssysteme bieten Funktionen dafür an, sofern die unterliegende Plattform ausreichend Informationen liefert.
Das Problem ist, an diese Informationen heranzukommen. Außerdem kann sich die Repräsentation der Zufallszahlen sich von System zu System sehr stark unterscheiden.

Dravere

@Tachyon,
Kannst du nicht immer neue Seeds setzen, jedesmal wenn eine GUID erzeugt werden muss? Die GUID werden wohl kaum zur gleichen Zeit erzeugt. Zusätzlich könntest du std::clock aus <ctime> nehmen. Die Programmlaufzeit sollte sich wohl schon unterscheiden.
Oder erzeugst du die GUIDs gleich beim Start des Programmes? Dann würde die Systemzeit allerdings reichen, da du wohl kaum alle Programme zur gleichen Zeit starten kannst

Grüssli

Tachyon

Dravere schrieb:

@Tachyon,
Kannst du nicht immer neue Seeds setzen, jedesmal wenn eine GUID erzeugt werden muss? Die GUID werden wohl kaum zur gleichen Zeit erzeugt. Zusätzlich könntest du std::clock aus <ctime> nehmen. Die Programmlaufzeit sollte sich wohl schon unterscheiden.
Oder erzeugst du die GUIDs gleich beim Start des Programmes? Dann würde die Systemzeit allerdings reichen, da du wohl kaum alle Programme zur gleichen Zeit starten kannst

Grüssli

Leider ist das nicht so einfach. Es gibt etwa 40 synchronisierte Cluster, auf denen das Programm mehr oder weniger parallel gestartet wird. Außerdem kann es sein, dass das Programm auf einem Cluster mehrere Male gestartet wird.
In einer Monte-Carlo-Simulation habe ich herausbekommen, dass der clock + Zeitstempel auf einem Cluster sich immer mal wieder mit denen auf einem anderen Cluster überdeckt. Das ist also leider nicht ausreichend.
Ich bin jetzt dazu übergegangen, den Seed aus einem SHA1-Hash zu erzeugen, den ich mit diversen Dingen füttere, die mir auf den Systemen zur Verfügung stehen.
Drunter:

`

clock()

time()

/dev/urandom (falls vorhanden, ansonten den uninitialiserten Buffer in den ich normalerweise gelesen haette)

den Hostnamen

die Host IP (falls vorhanden)

`

Das scheint bis jetzt zu funktionieren. Ich muss das mal ein paar Tage laufen lassen.

hustbaer

Ich persönlich würde für Windows noch zusätzlich CryptGenRandom() statt /dev/urandom verwenden. Der Aufwand ist ja nicht gross (#ifdef WINDOWS + ein paar Zeilen Code).

Oder aber gleich wie du es schon angedacht hast die GUID Generatoren vom OS kapseln. Könnte man auch mixen, also das was du jetzt machst als Fallback verwenden falls du für das spezielle OS keinen GUID Generator kennst, und ansonsten eben die OS Funktionen verwenden.

Tachyon

hustbaer schrieb:

Ich persönlich würde für Windows noch zusätzlich CryptGenRandom() statt /dev/urandom verwenden. Der Aufwand ist ja nicht gross (#ifdef WINDOWS + ein paar Zeilen Code).

Oder aber gleich wie du es schon angedacht hast die GUID Generatoren vom OS kapseln. Könnte man auch mixen, also das was du jetzt machst als Fallback verwenden falls du für das spezielle OS keinen GUID Generator kennst, und ansonsten eben die OS Funktionen verwenden.

Also ich habe jetzt ein Funktionsmuster fertig gebastelt. Das Ding generiert einen SHA1-Hash (der Algo ist nach dem Pseudocode von Wikipedia implementiert) aus dem oben aufgezählten Input (also auf Windows ohne echte Zufallszahlen).
Mit dem Hash (oder "Digest", wie die das immer nennen) wird dann boost::mt19937 als Engine geseeded. Damit wird dann eine UUID.v4 nach RFC 4122 (danke nochmal @Dravere) generiert.
Bei meinen jetzigen Versuchen konnte ich keine Kollisionen feststellen. Ich werde morgen mal einen Intensivtest dafür fahren.

hustbaer

@Tachyon:
Kollisionen bei Tests zu finden wird schwierig werden, selbst bei relativ "schwachen" Verfahren.
Ich denke mir bloss auf Windows CryptGenRandom zusätzlich zu verwenden ist ja nicht sehr schwer, und kann eigentlich nur eine Verbesserung bringen.

Tachyon

Hast ja recht. Ich frickel das noch rein.