Generate truly globally unique id across many clients and servers

Question

Summary

Really globally unique IDs in flash and/or javascript clients. Can I do this with an RNG available in current browsers/flash or must I build a composite ID with server-side randomness?

Details

I need to generate globally unique identifiers for objects. I have multiple server-side "systems" written in java that need to be able to exchange ids; each of these systems also has a set of flex/javascript clients that actually generate the IDs for new objects. I need to guarantee global uniqueness across the set of unrelated systems; for instance I need to be able to merge/sync the databases of two independent systems. I must guarantee that there is never a collision between these ids and that I never need to change the id of an object once created. I need to be able to generate ids in flash and javascript clients without contacting the server for every id. A solution that relies on some server provided seed or system id is fine as long as the server isn't contacted too often. A solution that works completely disconnected is preferable. Similarly a solution that requires no upfront registration of systems is preferable to one that relies on a central authority (like the OUI in a MAC address).

I know the obvious solution is "use a UUID generator," such as UIDUtil in flash. This function specifically disclaims global uniqueness. In general, I'm concerned about relying on a PRNG to guarantee global uniqueness.

Proposed solutions

Rely entirely on a secure random number generator in the client.

Flash 11+ has flash.crypto.generateRandomBytes; Javascript has window.crypto but it's pretty new and not supported in IE. There are solutions like sjcl that use the mouse to add entropy.

I understand that given a perfect RNG the possibility of collision for a 2¹²² random UID is meteorite tiny, but I'm worried that I won't actually get this degree of randomness in a javascript or flash client. I'm further concerned that the typical use case for even a cryptographic RNG is different from mine: for session keys, etc, collisions are acceptable as long as they are unpredictable by an attacker. In my case, collisions are completely unacceptable. Should I really rely on the raw output of a secure RNG for a unique ID?

Generate a composite ID that includes system, session and object IDs.

An obvious implementation would be to create a system UUID at server install time, keep a per-client-login session id (eg in a database), and then send the system and session ids to the client which would keep a per-session counter. The uid would be the triple: system ID, session ID, client counter.

I could imagine directly concatenating these or hashing them with a cryptographic hash. I'm concerned that the hashing itself may potentially introduce collisions, particularly if the input to the hash is about the same size as the output. But the hash would obscure the system id and counters which could leak information.

Instead of generating the system ID at install time, another solution would be to have a central registry that handed out unique system IDs, kind of like what DOI does. This requires more coordination however, but I guess is the only way to really guarantee global uniquness.

Key questions

• Random or composite based?
• Include system ID?
• If system id: generate a random system ID or use a central registry?
• Include timestamp or some other nonce?
• To hash or not to hash?

Answer 1

The simplest answer is to use a server assigned client ID which is incremented for each client, and a value on each client which is incremented for each fragment on that client. The pair of client ID and fragment ID becomes the globally unique ID for that piece of content.

Another simple approach is to generate a set of unique IDs (say 2k at a time) on the server and send them in a batch to each client. When the client runs out of IDs it contacts the server for more.

Client IDs should be stored in a central repository accessible to all the servers.

It may help looking at methods for distributed hashing which is used to uniquely identify and locates fragments within a peer-to-peer environment. This may be overkill considering you have a server which can intervene to assert uniqueness.

To answer your questions you need to determine the benefit that the added complexity of a system ID, nonce or hash would bring.

System ID: A system ID would typically be used to uniquely identify the system within a domain. So if you don't care who the user is, or how many sessions are open, but only want to make sure you know who the device is, then use a system ID. This is usually less useful in a user-centric environment such as JavaScript or Flash, where the user or session may be relevant.

Nonce: A nonce/salt/random seed would be used to obfuscate or otherwise scramble the ID. This is important when you don't want others to be able to guess the original value of the ID. If this is necessary then it may be better to encrypt the ID with a private encryption key, and pass a public decryption key to each consumer who needs to read the ID.

Timestamp: Considering the variability of the client's clock (ie you cannot guarantee it adheres to any time or time zone), a timestamp would need to be treated as a pseudo-random value for this application.

Hash: While hashes are often (ab)used to create unique keys, their real purpose is to map a large (possibly infinite) domain to a smaller, more manageable one. For example, MD5 is typically used to generate a unique ID from a timestamp, random number, and/or nonce data. What is actually happening is that the MD5 function is mapping an infinite range of data into a space of 2^128 possibilities. While this is a massive space, it is not infinite, so logic tells you that there will be (even if only in theory) the same hash assigned to two different fragments. On the other hand perfect hashing attempts to assign a unique identifier to each piece of data, however this is entirely unnecessary if you just assign a unique identifier to each client fragment to start with.

Answer 2

Something quick and dirty and also may not work out for your use case --

Using Java's UUID and coupling that with something like , say clientName. This should solve the multiple client and multiple server issue.

The rationale behind this is that the possibility of getting 2 calls at the same nanosecond are low, refer to the links provided below. Now, by coupling the clientName with the UUID you are ensuring unique IDs across clients and that should leave only handling the use case of the same client calling twice within the same nanosecond.

You could write a java module to generate the IDs and then get Flash to talk to this module. For your reference, you could refer to --
Is unique id generation using UUID really unique?
Getting java and flash to talk to each other