Is there a standard way to generate ID numbers one after the other such that:
- You can guarantee, or almost guarantee, that you avoid collisions. (By "almost guarantee", I mean for example if you generated completely random 24-digit numbers, and you "only" generated 1 million of them, then even with the birthday paradox, the odds of a collision would be small.)
- You want the ID numbers to be short, not unwieldy - specifically, you don't want to rely on the length of the ID number (and picking random values) to avoid collisions, as described in the previous bullet point. You have to do it some other way.
- You don't want to avoid collisions each time you generate a new value by looking at all the pre-existing values to see if it's already been used. This would only be a log(n) lookup each time on a sorted list, but suppose I want to avoid this anyway.
- You don't want the ID number to reveal any information about when it was generated, or how many ID numbers were generated in between ID number X and ID number Y. Without this condition, the problem is trivial; you could just use the clock time (plus some random value that's large enough to avoid collisions between numbers generated in the same clock time value), or you could just use sequential integers (except now an attacker knows that if someone generated ID value 5000 on March 1st and ID value 6000 on April 1st, there were 1000 other values generated in between then).
I tried to find a trivial answer, but none of the ones I tried seemed to work. You could just take the SHA-256 hash of the numbers 1, 2, 3, etc. (plus some secret key), but this has the same problem as just picking random numbers from the available space -- if you're relying on the length of the hash (e.g. SHA-256) to avoid collisions, the resulting ID numbers are long and unwieldy, and if you make the hash shorter, you increase the chance of collisions.
Or you could generate new IDs by incrementing each time by a random value between 1 and n, instead of always incrementing by 1. The problem is that depending on what the attacker can do, they could figure out what n is -- if they have the ability to generate two IDs in sequence, and do it repeatedly, they could figure out n, or if they have the ability to check which IDs are valid, they could check every number in some small range, to see how densely packed the valid IDs are, and figure out n from that.
The only sort-of solution I could find is as follows: First, do some prep work in advance. For however many ID values you expect to generate (say, 1 million), take all the integers from 1 to 1 million, and in order, start computing the hash of each integer plus a secret key. Truncate the hash to whatever value you think is short enough. But, with a short enough truncation, you expect to see collisions. So each time you generate a new truncated hash for a given integer, check it against previously generated values, and if there's a collision, add that integer to a list L of integers where the hash of that integer collides with that of a smaller integer. (So in fact if your plan is to generate 1 million IDs, during his prep work you'll have to go a little bit last 1 million integers, to make up for the ones that you skipped.)
Then, at run time when you generate your IDs, you just start with an integer counter. Each time you generate a new ID, you increment the integer and check if it's on your list L, and if it is, you skip and to go the next integer. (This does involve a "log n lookup", apparently breaking one of my stated rules, but what I really wanted to do was avoid having to check each new ID value against every value generated so far; checking L should be much faster.) And you can fine-tune this for tradeoffs (the longer you make the truncated hashes, the shorter L will be and hence the shorter the check will be each time you generate a new ID; but longer ID values might not be desirable).
But this feels like a hack. Is there a standard way? If not, can you think of a better way?
