1

In a program i am writing, i use session authentication tokens that we give back to a user to have them hand in with their requests.

This is working very well but this question is about the generated token and chance of collision.

Here is the PHP code used to generate a token: bin2hex(random_bytes(32)).

I have been considering for a while on generation of this token, should we do a quick database check that it does exist already.

I fully understand the low chances of this happening, but because it's a possibility should i check anyway? or are the chances so low that the lines of code checking are comedic from the point of view of others that read the commit?

Put another way from an info sec perspective: Is the risk assessment of one user getting into another users session a high enough danger that we should always check for session token collisions?

Necro
  • 125
  • 4
  • 2
    Being that `random_bytes` uses a CSPRNG, I think you can make a compelling argument that the chances of a collision are so infinitesimally small that it's not even worth the CPU time to do the database query to check for a collision. If you did find a collision any time in the next century or so, that would be a strong indication that there is something wrong with the CSPRNG. – mti2935 May 26 '21 at 23:36
  • What @mti2935 said, but `s/century/heat death of this universe and the trillion after it/g` – CBHacking May 27 '21 at 11:24
  • Well said, @CBHacking. After I wrote my comment above, I found myself thinking about the last sentence, and wondering, `what if the so-called 'CSPRNG' is not really a CSPRNG after all?`. IMO, this is much more likely than a true CSPRNG serving two of the same values any time during `s/century/heat death of this universe and the trillion after it/g`. That alone might be a good reason to err on the safe side, and do the (very inexpensive) database check, with a comment in the code next to it, reading `# just in case the 'CSPRNG' is not really a CSPRNG after all`. – mti2935 May 27 '21 at 12:32
  • For persistent tokens, they're probably being put in a DB, and there's probably already an index on that field; it's fine and very cheap to additionally make that indexed value unique. For ephemeral values... I wouldn't go out of my way at all. Unless you're already storing the values in some system that makes it trivial to check for duplicates, it's not worth putting effort into (IMO) – CBHacking May 27 '21 at 18:07

1 Answers1

3

I fully understand the low chances of this happening

With all due respect, I don't think you do :P I would say the chances are indeed comedically low!

The first thing to check is the quality of the random numbers. The PHP docs claim that these are cryptographically secure pseudo-random bytes. Good good.

Next, 32 bytes = 256 bits. IE 2256 possible values, which because it's a cryptographic RNG, we assume will chosen uniformly at random. To understand the probability of naturally-rolling a collision, watch this excellent 5 min video.

Paraphrased:

Say you generate a random number with PHP's random_bytes(32). How long until you expect to see that number come up again naturally?

Imagine that you have a machine packed full of 8 GPUs generating numbers with PHP's CSPRNG as fast as they can. Now imagine that half the people on Earth had their own personal kilo-google's worth of those machines (1000x the number of CPUs that Google is estimated to own). Now imagine a galaxy with 4 billion copies of that Earth. Now imagine 4 billion copies of that galaxy. Let them run for 37x the age of the universe. And you're still missing another factor of 4 billion before you would expect to see a natural collision on a 32-byte random number.

32 bytes seem short, but people tend to have very bad intiutions about what it means for that number to have 2256 possible values.

So put in the uniqueness check if you want, but know that your CPU will rust out and return to the earth long before you expect that line of code to trigger. Seems like a waste of a DB search to me.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • 1
    +1. Great video. I've seen a number of ways that people have tried to illustrate how massively large 2^256 is, but this is one of the best. – mti2935 May 27 '21 at 01:03