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?

Wilfredowilfrid

Why do you need the sequential value? Do you have get back to it? If yes, use a crypto function to encrypt your secquential number with a secret key and encode the cipher with the alphabet ou your choice. – Tarbox

It's been a long time since I asked this question. I rejected this approach a very long time ago. In the many years since I now generate a random number of the desired bits using a cryptographically strong random number generator, store the number in a database with a unique key constraint, and expire the number after a period of time (usually 24 hours). I've never seen a collision and if I did I'd simply retry. Simple effective solution. – Wilfredowilfrid

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

Constituent

Common English words wouldn't be good for a tinyurl-like site. You are more describing a password generator IMO. – Peaceable

@Peaceable 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? – Constituent

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.

Populate

Answer 3

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.

Indisposed

Answer 4

At the time of this writing, this question's title is:

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

To that, I should note that it's not possible in general to create a random value that's also unique, at least if each random value is generated independently of any other. In addition, there are many things you should ask yourself if you want to generate unique identifiers (which come from my section on unique random identifiers):

1. Can the application easily check identifiers for uniqueness within the desired scope and range (e.g., check whether a file or database record with that identifier already exists)?
2. Can the application tolerate the risk of generating the same identifier for different resources?
3. Do identifiers have to be hard to guess, be simply "random-looking", or be neither?
4. Do identifiers have to be typed in or otherwise relayed by end users?
5. Is the resource an identifier identifies available to anyone who knows that identifier (even without being logged in or authorized in some way)?
6. Do identifiers have to be memorable?

In your case, you have several conflicting goals: You want identifiers that are—

• unique,
• easy to type by end users (including small), and
• hard to guess (including random).

Important points you don't mention in the question include:

• How will the key be used?
• Are other users allowed to access the resource identified by the key, whenever they know the key? If not, then additional access control or a longer key length will be necessary.
• Can your application tolerate the risk of duplicate keys? If so, then the keys can be completely randomly generated (such as by a cryptographic RNG). If not, then your goal will be harder to achieve, especially for keys intended for security purposes.

Note that I don't go into the issue of formatting a unique value into a "user-friendly key". There are many ways to do so, and they all come down to mapping unique values one-to-one with "user-friendly keys" — if the input value was unique, the "user-friendly key" will likewise be unique.

Sacking

Answer 5

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.

Sheath

Answer 6

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.

Chuipek

Answer 7

The Crypt::Skip32 algorithm looks promising to generate unique, small, random-looking and user-friendly identifiers. The procedure can be done as follows:

1. Create a database sequence to generate sequential integers (4 bytes);
2. Get the next integer of the sequence;
3. Encrypt the integer using the Crypt::Skip32 algorithm. The result is also 4 bytes in size;
4. Convert the resulting 4 bytes to an encoding of your preference. Hexadecimal yields 8 characters, while Base32 yields 7 characters.

This cipher can be handy for scrambling small (32-bit) values when you would like to obscure them while keeping the encrypted output size small (also only 32 bits).

One example where Crypt::Skip32 has been useful: You have numeric database record ids which increment sequentially. You would like to use them in URLs, but you don't want to make it obvious how many X's you have in the database by putting the ids directly in the URLs.

You can use Crypt::Skip32 to scramble ids and put the resulting 32-bit value in URLs (perhaps as 8 hex digits or some other shorter encoding). When a user requests a URL, you can unscramble the id to retrieve the object from the database.

Warning: A 32-bit value can only go a little over 4 billion (American). Plan ahead if what you need to encrypt might eventually go over this limit.

References

• https://github.com/gitpan/Crypt-Skip32

Dispread