How can I generate a unique, small, random, and user-friendly key?

Question

A few months back I was tasked with implementing a unique and random code for our web application. The code would have to be user friendly and as small as possible, but still be essentially random (so users couldn't easily predict the next code in the sequence).

It ended up generating values that looked something like this:

Af3nT5Xf2

Unfortunately, I was never satisfied with the implementation. Guid's were out of the question, they were simply too big and difficult for users to type in. I was hoping for something more along the lines of 4 or 5 characters/digits, but our particular implementation would generate noticeably patterned sequences if we encoded to less than 9 characters.

Here's what we ended up doing:

We pulled a unique sequential 32bit id from the database. We then inserted it into the center bits of a 64bit RANDOM integer. We created a lookup table of easily typed and recognized characters (A-Z, a-z, 2-9 skipping easily confused characters such as L,l,1,O,0, etc.). Finally, we used that lookup table to base-54 encode the 64-bit integer. The high bits were random, the low bits were random, but the center bits were sequential.

The final result was a code that was much smaller than a guid and looked random, even though it absolutely wasn't.

I was never satisfied with this particular implementation. What would you guys have done?

Answer 1

Here's how I would do it.

I'd obtain a list of common English words with usage frequency and some grammatical information (like is it a noun or a verb?). I think you can look around the intertubes for some copy. Firefox is open-source and it has a spellchecker... so it must be obtainable somehow.

Then I'd run a filter on it so obscure words are removed and that words which are too long are excluded.

Then my generation algorithm would pick 2 words from the list and concatenate them and add a random 3 digits number.

I can also randomize word selection pattern between verb/nouns like

eatCake778
pickBasket524
rideFlyer113 etc..

the case needn't be camel casing, you can randomize that as well. You can also randomize the placement of the number and the verb/noun.

And since that's a lot of randomizing, Jeff's The Danger of Naïveté is a must-read. Also make sure to study dictionary attacks well in advance.

And after I'd implemented it, I'd run a test to make sure that my algorithms should never collide. If the collision rate was high, then I'd play with the parameters (amount of nouns used, amount of verbs used, length of random number, total number of words, different kinds of casings etc.)

Answer 2

In .NET you can use the RNGCryptoServiceProvider method GetBytes() which will "fill an array of bytes with a cryptographically strong sequence of random values" (from ms documentation).

byte[] randomBytes = new byte[4];
RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
rng.GetBytes(randomBytes);

You can increase the lengh of the byte array and pluck out the character values you want to allow.