Truncating hash output for a unique ID

Question

This seems like a common question, but my knowledge on hashing is very limited, so I'm looking for a more ELI5-type answer. I would appreciate if someone could help me with my questions

Some context: I'm working on a requirement to generate a human-friendly 12-character long ID (for customer payment receipts) that will use the symbol set A-Z 0-9 without O, I, Z, and U. That gives me 32 symbols which means 5 bits per symbol and hence the ID would be 60 bits. The requirement is that these IDs should be unique, but will be stored in a database so I can look up in the database and regenerate another one if one already exists. It would be great if the IDs were inherently unique (so looking in to the database would not be followed by regenerating a new ID)

My question is

If I choose to create get a SHA-256 of either a UUID, or some value obtained by concatenating the private IP address of the host, the timestamp, and the thread id handling an ID generation request, then get its SHA-256 hash, and use its 60 bits

1. Would I get the maximum benefit from using the first 60, or last 60 (or middle?) to preserve maximum uniqueness? Would I get greater benefit if I used the first 12 characters of the hexadecimal number of the SHA value?
2. I read here that for n-bit values, the birthday bound is 2^(n/2). So that does mean, if I do the above processing, I could expect collisions after 2^(30) generations with 50% probability?

The requirements are not flexible (else I would obviously go with a UUID).

Thanks!

Answer 1

There is no known property of the first/last/middle/whatev 60 bits of a SHA-256 output that would make them more/less "randomish" than the last/whatev/middle/first 60 bits. In other words, you could take the first 60 bits, and that will be as fine as you can get.

With such a random generation, you can indeed expect the first collisions to appear after one billion or so (2³⁰) IDs have been accumulated. Even if you get your first collision at that point, collisions will still remain a rare event. With 60-bit IDs, when you have, say, 2³⁵ of them (that's more than thirty billions), then only one in 2²⁵ of new IDs will collide with an existing one (so this would still happen less than once in 30 millions of cases). If you have a database and can tolerate the occasional but quite rare collision, then random generation of the 60-bit ID is the way to go.

(Or, said otherwise, if you get collisions often, then this means that you have already gathered a huge number of IDs, and your central database must be of biblical proportions.)

If you want more uniqueness than that, then you need some sort of central ID generator. For instance, there is a central server that can be interrogated, and returns the next value of a counter. The server always increases the counter value after being interrogated, so it never returns twice the same value. The server won't run out of 60-bit integers before a long time, because, let's face it, 2⁶⁰ is still huge.

Now comes the hard part, which is the one you did not talk about: must the IDs be unpredictable ? This is not an easy question; it depends on what you do with them and, basically, everything in your system. If you need unpredictable IDs, then a central counter will not work, because everybody can obtain an ID value and predict the next one with 100% accuracy. The usual solution, in that case, would be to still have a counter, but to encrypt the successive values with a block cipher whose block size is identical to that of the ID. Here you would need a block cipher with 60-bit blocks -- this can be built out of a block cipher with slightly larger blocks, e.g. 3DES (64-bit blocks). This makes sense, though, only in the context of a central ID generator.

If you must allow ID generation from several "client" machines without having them talk together or with some central system, then you will have to rely on randomness and tolerate the few occasional collisions (that will be quite rare for a long time). If you need unpredictability, then use a cryptographically secure PRNG. Depending on your operating system and programming framework, this may be called /dev/urandom (Linux/Solaris/*BSD systems), CryptGenRandom() (Windows C/C++), java.security.SecureRandom (Java), System.Security.Cryptography.RNGCryptoServiceProvider (.NET)... Is is possible that the inherent UUID generation system of your local programming environment relies on a cryptographically secure PRNG (so hashing an UUID with SHA-256 would then be fine, even for unpredictability), but why take risks ? Just use a strong PRNG directly.