How to generate a verification code/number?

Question

I'm working on an application where users have to make a call and type a verification number with the keypad of their phone.

I would like to be able to detect if the number they type is correct or not. The phone system does not have access to a list of valid numbers, but instead it will validate the number against an algorithm (like a credit card number).

Here are some of the requirements :

• It must be difficult to type a valid random code
• It must be difficult to have a valid code if I make a typo (tranposition of digits, wrong digit)
• I must have a reasonnable number of possible combinations (let's say 1M)
• The code must be as short as possible, to avoid errors from the user

Given these requirements, how would you generate such a number ?

EDIT :

@Haaked : The code has to be numerical, because the user type it with it's phone.

@matt b : On the first step, the code is displayed on a Web page, the second step is to call and type in the code. I don't know the user's phone number.

Folowup : I've found several algorithms to check the validity of numbers (See this intersting Google Code project : checkDigits).

Answer 1

You want to segment your code. Part of it should be a 16-bit CRC of the rest of the code.

If all you want is a verification number then just use a sequence number (assuming you have a single point of generation). That way you know you are not getting duplicates.

Then you prefix the sequence with a CRC-16 of that sequence number AND some private key. You can use anything for the private key, as long as you keep it private. Make it something big, at least a GUID, but it could be the text to War and Peace from project Gutenberg. Just needs to be secret and constant. Having a private key prevents people from being able to forge a key, but using a 16 bit CR makes it easier to break.

To validate you just split the number into its two parts, and then take a CRC-16 of the sequence number and the private key.

If you want to obscure the sequential portion more, then split the CRC in two parts. Put 3 digits at the front and 2 at the back of the sequence (zero pad so the length of the CRC is consistent).

This method allows you to start with smaller keys too. The first 10 keys will be 6 digits.

Answer 2

When you are creating the verification code, do you have access to the caller's phone number?

If so I would use the caller's phone number and run it through some sort of hashing function so that you can guarantee that the verification code you gave to the caller in step 1 is the same one that they are entering in step 2 (to make sure they aren't using a friend's validation code or they simply made a very lucky guess).

About the hashing, I'm not sure if it's possible to take a 10 digit number and come out with a hash result that would be < 10 digits (I guess you'd have to live with a certain amount of collision) but I think this would help ensure the user is who they say they are.

Of course this won't work if the phone number used in step 1 is different than the one they are calling from in step 2.

Answer 3

• I must have a reasonnable number of possible combinations (let's say 1M)
• The code must be as short as possible, to avoid errors from the user

Well, if you want it to have at least one million combinations, then you need at least six digits. Is that short enough?