Generate a random code that can be validated later

Question

I need to generate a verification code and send it to a customer, so that the customer can then provide the code later and I validate it. I want to be able to do this without storing the verification codes in a database, i.e., the codes should be self-containted.

How can I generate the code and prevent the customer from just guessing what a valid code is? Obviously, I can't completely rule out a lucky guess, but I want the probability of such an event to be reasonably small, while keeping the code length small. A code may contain digits and letters.

For example, a very basic verification code would be like this: randomly generate the number 1122. Now, compute the verification code 11226 ( 1122 and append its checksum 6=1+1+2+2). So, if the customer sends back 11226 back I would be able to validate it, but of course this is too easy to tamper with. Is there a method to generate such codes?

EDIT: The problem is that the system which sends the verification code and the system where the verification code is validated are separated, no information is shared between these two systems. There is no way that even the randomly generated number (1122 in the example) is known to the validation system. Let me give you another example: in my country, there is a thing called "Orange Wednesday". You can get 2 movie tickets for the price of one if you have a code received by SMS (you send a SMS and receive a code by SMS if you are Orange customer). However, this code is not tied to anything (phone number or similar): I can give the code to someone else and it is still valid. I would need this kind of verification code.

Answer 1

What you are looking for can be implemented using Message Authentication Codes (MAC):

The key observations to make are:

1. The secret key (which only you know) is required to generate and validate MAC codes.
2. The MAC code produced is tinkering-proof, i.e. an attacker is not able to tell what impact a given modification to the (message, MAC) tuple may have.
3. No information needs to be stored outside of the message flow, except for the secret key.

In your scenario, you can use any arbitrary message since your only requirement is to verify that the input you receive from a customer was originally generated by you. You can do this by

• settling for some kind of pattern, e.g. generate only codes that start with 012345679xxxxxxx, or simply take the date encoded as "dd.mm.yyyy hh:mm:ss" for your 'arbitrary message'.
• use random numbers that are long enough and store which codes have actually been generated by you. However, you seemed to be looking for a solution that does not depend on databases.