views:

750

answers:

5

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?

+2  A: 

In C#, I have used the 'System.IO.Path.GetRandomFileName() : String' method... but I was generating salt for debug file names. This method returns stuff that looks like your first example, except with a random '.xyz' file extension too.

If you're in .NET and just want a simpler (but not 'nicer' looking) solution, I would say this is it... you could remove the random file extension if you like.

Anthony Mastrean
+3  A: 

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.

jasonlaflair
+6  A: 

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.)

chakrit
Common English words wouldn't be good for a tinyurl-like site. You are more describing a password generator IMO.
dfrankow
@dfrankow From the question "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" ... what do I miss?
chakrit
A: 

If by user friendly, you mean that a user could type the answer in then I think you would want to look in a different direction. I've seen and done implementations for initial random passwords that pick random words and numbers as an easier and less error prone string.

If though you're looking for a way to encode a random code in the URL string which is an issue I've dealt with for awhile then I what I have done is use 64-bit encoded GUIDs.

Joseph Kingry
A: 

You could load your list of words as chakrit suggested into a data table or xml file with a unique sequential key. When getting your random word, use a random number generator to determine what words to fetch by their key. If you concatenate 2 of them, I don't think you need to include the numbers in the string unless "true randomness" is part of the goal.

JasonS