Ensuring client IDs are unique

Question

I'm writing a node.js application that involves handling clients based on their ID without any real way of confirming that the ID a client says it has is its actual ID. That is, it's possible for a client to tell the server it has an ID of foo even though it was assigned an ID of bar, thus being able to send and receive information from the server as though it was the existing client foo. This is obviously a significant security risk, so I want to ensure it's more or less effectively impossible to guess another client's ID.

I have a clients object, with keys corresponding to the ID of each client. I'm using the crypto library for PRNG and hashing; hashFct returns a SHA256 digest of the input. The following code is run when a client sends its initial creation request.

//Generate random string, hash, and truncate to 8 characters
rand = crypto.randomBytes(32).toString("base64");
id = hashFct(rand).substr(0, 8);

//Loop until unique
for(var i = 0; !!clients[id]; i++) {
    rand = crypto.randomBytes(32).toString("base64");
    id = hashFct(rand).substr(0, 8);
}

...

clients[id] = {
    id: id,
    ...
}

The idea behind the "loop until unique" section is to check if the clients object already has a value in it with the pseudo-random id as a key, and to regenerate the ID and try again until it's unique. Then the ID is put into the clients object as a new client, and the code moves on.

Is there anything glaringly stupid about this approach that I'm overlooking? Is there a better way to ensure an ID is unique, or perhaps a better way of generating the IDs?

Answer 1

rand = crypto.randomBytes(32).toString("base64");
id = hashFct(rand).substr(0, 8);

If those random bytes are random, passing them through a hash function adds nothing. If they are only somewhat random, hash + truncation is better than just truncation. However, crypto.randomBytes are from a strong RNG, so you can use them as is.

The problem is that 8 bytes is not always unique. You solve it by looping until you get one that is unique. However an attacker could do the inverse: guess until it hits a real ID.

The probablity of guessing a particular ID is \$2^{-b}\$, where b is the number of bits in the random number. If you have n users in your database the probability is n times as high. With \$n = 2^m\$, the attacker needs only about \$2^{b-m}\$ guesses to hit some ID.

If your ID's are 8 bytes:

2^64 bit IDs (8 bytes)
2^20 users   (~1 million)
//
2^44 guesses (~17 million million)

However, if your IDs are 8 characters in base64:

2^48 bit IDs (8 base64 characters)
2^20 users   (~1 million)
//
2^28 guesses (~268 million)

Depending on your application and the number of users it is possible that both, the latter or neither is insecure.

---

My recommendation (echoing well known advice) is to use the 32-byte random string directly as an ID (converted to base64 if needed). That gives such a small chance of collisions that you can do away with the loop as well. (It's likelier e.g. that the CPU fails to loop due to cosmic rays than that you see a collision.)