Create a set of "coupon codes" based on an algorithm; no need to store the codes

Question

I have a situation where we print out runs of "discount cards" where a unique code is printed on the card that the user can redeem on an online store for the discount.

We create so many of these cards, with so few of them actually being used, that I'd like to use some form of way to identify a valid code using an method rather than storing each individual code in a database. We create say 5,000 of these codes at a time. Probably about 5 times a year.

Ideally I'd like to be able to something like:

$coupons->generate(5000, 'unique_salt', 'prefix_');

Which would generate 5,000 "random" codes like:

prefix-23-3424-4324-3344 or
prefix-4H-34RE-22K3-PE3W

The unique salt and prefix_ would be saved to the database. These codes would then be able to be verified by using the prefix_ to lookup the salt and identify the code as valid or not.

I have a form of this working by using a number as the salt, to find numbers divisible by the salt, and then reorder the digits so that it appears random. With long enough codes, it will take some work to figure out the pattern. But I'd like to think there's a better way... as there's only so many numbers that yield large amounts of codes that are divisible by the salt.

(For example, a salt of 2 would yield 5,000 codes between 1 and 10,000 (and would be easy to see a pattern)... but a salt of 14000 would yield zero codes between 1 and 10,000)

The other advantage to this is I can generate coupons as needed (such as when we give individuals a discount on a one by one basis), and be able to track what coupons are used when, etc based on the prefix_... and potentially see how/when cards are passed out, what yields the best return.

Am I just spinning my wheels when I should just be storing each code in the database? (Or just having fun?) :)

Answer 1

what are you looking for is called Partial Key Verification like the serial numbers on software CDs :)

Have a look at:

http://47hats.com/2007/07/implementing-a-partial-serial-number-verification-system/

http://www.codeproject.com/KB/security/cdkeys.aspx

http://www.brandonstaggs.com/2007/07/26/implementing-a-partial-serial-number-verification-system-in-delphi/

Cheers

Answer 2

You can do this using an HMAC and an appropriate encoding scheme. First, generate a secret key for the HMAC, and make sure you keep it confidential. To generate each token, do the following:

1. Generate a serial number, either at random or sequentially - all that's important is that it's unique.
2. Compute the HMAC (I suggest HMAC-SHA1) of the serial number with the secret key. This will give you a hash value (160 bits in the case of HMAC-SHA1).
3. Concatenate the serial number with part of the hash value. This is your coupon code. The number of bits of the hash value you use determines how hard it is to create a valid code by brute-force - using n bits means your attackers will have to try (on average) 2^(n-1) codes to find a valid one. Which bits you use from the hash does not matter.

To verify the code:

1. Check that the serial number is not already in your database as redeemed previously.
2. Compute the HMAC for the serial number as described above.
3. Compare the relevant bits of the HMAC to those in the rest of the code.
4. Add the serial number to your database to register it as used.