Algorithm for Gift Card Codes

Question

I recently posted this question about codes for a gift-card-like voucher that users can redeem online. I wanted to find the best tradeoff between large keyspace, low guessability, and human readability. Now that I'm into implementation I realize I've got another problem altogether, more of an algorithmic challenge.

Let's assume I adopt some code format - say 10 characters from A to Z for simplicity, and I start generating vouchers. What is the correct algorithm to do this?!

My first approach is to number all possible codes from 0 to 308,915,776, then start generating random numbers in that range. This obviously has a big problem though - I have to check my random number against all previously generated voucher codes and if it collides with an existing one I'll have to discard the code and try another. As the system accumulates more data it will slow down. At the extreme when there is only one code left it will be nearly impossible for the system to guess it correctly.

I could pre-generate all codes and shuffle them, then consume them in order. But this means I have to store many codes, and in fact my keyspace is bigger than the one i described, so we're talking about a very large amount of data. So that's also not too desirable.

So this leaves me with using the codes sequentially. I do not want guessable voucher codes though. The user who buys voucher "AAAAAAAAAY" should not have a good chance of getting another valid code if they type in "AAAAAAAAAZ".

I can shuffle my alphabet and my positions so that instead of

'ABCDEFGHIJKLMNOPQRSTUVWXYZ' i use

'LYFZTGKBNDRAPWEOXQHVJSUMIC'

and so that instead of positions

9 8 7 6 5 4 3 2 1 0 the positions are

1 8 0 7 5 4 3 9 2 6

Using this logic, given the code

LNWHDTECMA

the next code would be

LNEHDTECMA

This is definitely way less guessable. But they're still only one character off from each other, and given just two of these vouchers you would know which position is incrementing, and you would have a 90% chance of getting the next code in 24 guesses or less.

My "escape hatch" is to ditch all this and go with GUIDs. They have more characters than I wanted my users to have to type in, and contain similar characters like I/1 and O/0, but they magically make all of the above headaches go away. Still, I'm having fun thinking about this, maybe you are too. I'd love to hear some alternate suggestions. What have you got?

Thanks!

Answer 1

Hi again, I answered the other question too :P

The best way is to generate one alphanumeric character at a time, randomly, until you have 8 of them. This will then be your voucher.

Ideally the best way would be to choose a sequence long enough so that you can safely assume if there will be any duplicates. Do note that, perhaps counter-intuitively, this happens more often than you think because of the Birthday problem.

For example, with 8 characters you have 1785793904896 possible combinations, but if you generate only 1,573,415 vouchers you will have a 50% chance to have a duplicate.

So, it all depends on how many you want to generate, and the maximum length of the code you're comfortable with. If you are generating many and you want to keep it short, you should save the ones you previously generated, and check against the database for duplicates.

Answer 2

Some random number generators have an interesting property: Used right they do not generate duplicate numbers in a long time. They produce something called a full cycle. Use one of the algorithms described there, seed it, and you will have many unique numbers,

Add a smart way to map digits to characters and you got your codes.

Answer 3

The likelihood of two randomly generated code colliding is basically the same as a user guessing a valid code - and you cannot prevent users from guessing. So you must have a key space so much larger than the number of actually used codes that random collisions are extremely unlikely as well (though, thanks to the birthday paradox, probably not unlikely enough to ignore them completely, at least if you want your codes to be reasonably short), and checking against existing codes and re-generating in case of a collision is a perfectly viable strategy.

Answer 4

I think the best way to go is that suggested by Andreas. But my answer is about an interesting related discussion.

You want to generate a sequence of numbers that together form a permutation of S = {1, ..., MAX}. One way to do this is to take the elements of a cyclic group over S. For example, the numbers R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p} form a cyclic group over {1, ..., p-1}, provided p is a prime and x is coprime to p. So if you choose MAX as a prime number you do use this sequence.

You want a "tough-to-crack" sequence. A generator for the sufficiently-tough-to-crack sequence is called a pseudorandom generator (ofcourse you probably don't need that tough-to-crack). An example is the last digit of elements in R above, provided p is kept secret (am I correct?). But the answer by Andreas already uses a source of (pseudo-) random numbers, so cannot be called a pseudorandom generator.

If you are interested in pseudorandom generators, they are discussed in detail in volume 2 of Knuth's well-known book.

Answer 5

Here is a though:

• ID = each voucher has an unique (auto-incremented?) ID
• CHECKSUM = apply N iterations of the Verhoeff or Luhn algorithm on the ID
• VOUCHER = base convert the generated CHECKSUM from base 10 to base 36

See also this related SO question: Ideas to create a small (<10 digits), not (very) secure “hash”.

---

One simple way to make this method more secure is to use a non auto-incremented ID value, one option might be to use ID as the last 6 or 7 digits of a UNIX timestamp and calculate the checksum.

Answer 6

I would say to use a "perfect hash" - http://en.wikipedia.org/wiki/Perfect_hash_function combined with a 4-digit random number...

So just increment your voucher code each time, then hash it, add a 4 digit random number and I would also add a check digit to the end (as Alix Axel suggested).

This would be very secure with no clashes - for example if someone worked out your hashing algorithm, they would also have to guess the 4-digit code at the end...

Answer 7

Programming Pearls has several examples of algorithms to generate sets of random numbers, you should read it if you're interested in this kind of problem.

The book shows that if you generate m random numbers with value less than n, the simple approach of generating numbers and throwing out duplicates will generate no more than 2m random numbers if m < n / 2. Here it is, in C++:

void gensets(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    while (S.size() < m) {
        int t = bigrand() % n;
        S.insert(t);
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

Obviously, if you're worried about people guessing values, you will want m to be much less than n / 2.

There's even a set-based algorithm to generate m random numbers less than n with each value being equally likely, no duplicates, and a guarantee not to generate more than m random numbers:

void genfloyd(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    for (int j = n-m; j < n; j++) {
        int t = bigrand() % (j+1);
        if (S.find(t) == S.end())
            S.insert(t); // t not in S
        else
            S.insert(j); // t in S
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

The order of the numbers isn't random, though, so this is probably not a good choice for you.

Answer 8

Use an N-bit serial number R, combined with an M-bit hash H of the concatenated pair (R, S) where S is some secret "salt" S which you do NOT publish. Then encode the pair (R,H) alphanumerically in any reversible way you like. If you like algorithms like MD5* or SHA, but the bit count is too high, then just take the M least significant bits of a standard hash algorithm.

You can verify easily: decode the alphanumeric encoding so you can see R and H. Then compute H' = hash(R+S) and verify that H = H'.

edit: R can be an incrementing serial number or random or whatever, just make sure you use each value not more than once.

*before someone says "MD5 is broken", let me remind you that the known weaknesses for MD5 are collision attacks, and not preimage attacks. Also, by using an unpublished, secret salt value, you deny an attacker the ability to test your security mechanism, unless he/she can guess the salt value. If you feel paranoid, pick two salt values Sprefix and Ssuffix, and calculate the hash of the concatenated triple (Sprefix,R,Ssuffix).

Answer 9

This is a summary of the best bits of all the other answers. :)

You need to generate gift card numbers that are:

• unique
• unguessable

Random numbers are unguessable but not necessarily unique. The numbers produced by various algorithms are unique but guessable (the algorithm can be reverse-engineered). I don't know of a single algorithm that gives both properties, and because of the need to defy reverse engineering, it falls in the domain of cryptography. Non-experts, of course, shouldn't try to design cryptosystems.

Fortunately you don't have to get both properties from the same algorithm. Your gift card codes can consist of two parts: a part that is unique (generated using a linear congruential generator, perhaps, or modulo arithmetic, or even just an integer that you increment each time) and a part that is unguessable (just random numbers).