Generating unique tokens in a NodeJS, Crypto Token authentication environment

Question

Using nodejs and crypto, right now, when a user logs in, I generate a random auth token:

var token = crypto.randomBytes(16).toString('hex');

I know it's unlikely, but there is a tiny chance for two tokens to be of the same value.

This means a user could, in theory, authenticate on another account.

Now, I see two obvious methods to get pass this:

• When I generate the token, query the user's database and see if a Token with the same value already exists. If it does, just generate another one. As you can see, this is not perfect since I am adding queries to the database.
• Since every user has a unique username in my database, I could
  generate a random token using the username as a secret generator key. This way, there is no way of two tokens having the same value. Can crypto do that? Is it secure?

How would you do it?

Answer 1

It's too unlikely to worry about it happening by chance. I would not sacrifice performance to lock and check the database for it.

Consider this excerpt from Pro Git about the chance of random collisions between 20-byte SHA-1 sums:

Here’s an example to give you an idea of what it would take to get a SHA-1 collision [by chance]. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (1 million Git objects) and pushing it into one enormous Git repository, it would take 5 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists [for average projects] that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

(SHA-1 collisions can be directly constructed now, so the quote is now less applicable to SHA-1, but it's still valid when considering collisions of random values.)

If you are still worried about that probability, then you can easily use more random bytes instead of 16.

But regarding your second idea: if you hashed the random ID with the username, then that hash could collide, just like the random ID could. You haven't solved anything.

Answer 2

You should always add a UNIQUE constraint to your database column. This will create an implicit index to improve searches for this column and it will make sure that none of two records will ever has the same value. So, in the worst-case scenario you will get a database exception and not a security violation.

Also, depending on how frequently unique tokens are needed to be created, I think it's perfectly fine in most cases to use database lookups during generation. If your column, again, is properly indexed, it will be a pretty fast query. Most databases a very well horizontally scalable, so if your are building a next Facebook it is again an option. Furthermore, you will probably need to do a query to check for E-Mail uniqueness anyway.

Finally, if you are really concerned about performance you could always pre-generate a one-million of unique tokens and store them in the separate database table for quick use. Just setup a routine to periodically check it's usage and insert more records to it as needed. However, as @MacroMan stated in the comments, this could have a security implications if someone will get access to the list of pre-generated tokens, so this practice should be avoided.

• PostgreSQL UNIQUE CONSTRAINT

• MySQL: Unique Constraints