Generating unique, hard-to-guess "coupon" codes

Question 1

The code needs to be unguessable, because the only verification you can perform before giving the user their reward is to check whether the code they entered exists in your list of "issued" codes.

That means the number of all possible codes in that format is much larger than the number of codes you want to issue,. Depending on how easy it is to simply try codes (think of a script trying repeatedly), then you might need all possible codes to outnumber issued codes by a factor of a million or a billion or more. This sounds high, but is possible in relatively short strings.
It also means that the codes that you use must be chosen as randomly as possible within all possible codes. This is necessary to avoid users figuring out that most valid codes start with "AAA" for example. More sophisticated users might spot that your "random" codes use a hackable random number generator (Ruby's default rand() is fast and statistically good for random data, but is hackable in this way, so don't use it).

The starting point for such a secure code would be the output from a cryptographic PRNG. Ruby has the securerandom library, which you can use to get a raw code like this:

require 'securerandom'
SecureRandom.hex
# => "78c231af76a14ef9952406add6da5d42"

This code is long enough to cover any realistic number of vouchers (millions each for everyone on the planet), without any meaningful chance of repetition or being easy to guess. However, it is a bit awkward to type from a physical copy.

Once you know how to generate a random, practically unguessable code, your next problem is understanding user experience and deciding how much you can realistically compromise security in the name of usability. You need to bear in mind the value to the end user, and therefore how hard someone might try to get a valid code. I cannot answer that for you, but can make some general points about usability:

Avoid ambiguous characters. In print, it is sometimes difficult to see the difference between 1, I and l for example. We often understand what it is supposed to be from context, but a randomised string of characters does not have this context. It would be a bad user experience to have to try several variations of a code by testing 0 vs O, 5 vs S etc.
Use either lower case or upper case letters but not both. Case sensitivity will not be understood or followed by some %age of your users.
Accept variations when matching codes. Allow spaces and dashes. Perhaps even allow 0 and O to mean the same thing. This is best done by processing the input text so it is in the right case, strip separator characters etc.
In print, separate the code into a few small parts, it will be easier for the user to find their place in the string and type a few characters at once.
Don't make the code too long. I would suggest 12 characters, in 3 groups of 4.
Here's an interesting one - you may want to scan the code for possible rude words, or avoid the characters that would generate them. If your code contained only the characters K, U, F, C, then there would be a high chance of offending a user. This isn't usually a concern because users do not see most computer secure codes, but these ones will be in print!

Putting that all together, this is how I might generate a usable code:

# Random, unguessable number as a base20 string
#  .rjust(12, '0') covers for unlikely, but possible small numbers
#  .reverse ensures we don't use first character (which may not take all values)
raw = SecureRandom.random_number( 2**80 ).to_s( 20 ).rjust(12, '0').reverse
# e.g. "3ecg4f2f3d2ei0236gi"


# Convert Ruby base 20 to better characters for user experience
long_code = raw.tr( '0123456789abcdefghij', '234679QWERTYUPADFGHX' )
# e.g. "6AUF7D4D6P4AH246QFH"


# Format the code for printing
short_code = long_code[0..3] + '-' + long_code[4..7] + '-' + long_code[8..11]
# e.g. "6AUF-7D4D-6P4A"

There are 20**12 valid codes in this format, which means you can issue a billion of your own codes, and there would be one in four million chance of a user simply guessing a correct one. In cryptography circles that would be very bad (this code is insecure against a fast local attack), but for a web form offering free burritos to registered users, and where you would notice a someone trying four million times with a script, it is ok.

Question 2

Recently I wrote coupon-code gem that does exactly the same thing. The algorithm borrowed from Algorithm::CouponCode CPAN module.

A coupon code should not only be unique, but also easy to read and type while it still is secure. Neil's explanation and solution is great. This gem provides a convenient way to do it and a bonus validation feature.

>> require 'coupon_code'
>> code = CouponCode.generate
=> "1K7Q-CTFM-LMTC"
>> CouponCode.validate(code)
=> "1K7Q-CTFM-LMTC"
>> CouponCode.validate('1K7Q-CTFM-LMTO') # Invalid code
=> nil

Question 3

The key to create unguessable coupon codes is a large space of possible codes with only a small fraction of them being actually valid. Let's take for example 8 characters long alphanumeric strings:

alphanumeric = 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ - 63 characters

In this case there are 63^8 = 248155780267521 possible codes. It means that if you issue a billion codes the probability of guessing a code will be 10^9/63^8 = 0.000004... - 4 in a million.

However, it doesn't prevent one from running a script that keeps trying until it figures out a valid code. In order to block such a brute force attack you'll need to count attempts per user and ban over some limit.

If you're looking for a library that enables full customization of the output coupon codes (length, charset, prefix, suffix and pattern) take a look at voucher-code-generator-js - a library written in JavaScript. Example usage:

voucher_codes.generate({
    length: 8,
    count: 1000,
});

It will generate 1000 random unique codes, each 8 characters long.

Another example:

voucher_codes.generate({
    pattern: "###-###-###",
    count: 1000,
});

It will generate 1000 random unique codes following given pattern.

The source code is relatively simple. I bet you can easily rewrite it to any other language if JS is not your favorite one ;)

If you need a comprehensive solution for voucher codes management (including brute force attacks prevention) you may be interested in Voucherify.

Question 4

Go with something like:

class Coupon < ActiveRecord::Base
  before_save generate_token

  validates_uniqueness_of :token

  def generate_token
    self.token = "#{current_user.id}#{SecureRandom.urlsafe_base64(3)}"
  end

end

EDIT: Here is a better answer

Question 5

You can e.g. use a random number and check if it was not generated before, by storing all valid codes in a database.

Question 6

Draw random numbers using a proven generator (http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators).

Assume you deliver 333 coupons per day and these are valid for 30 days. So you have to store 10000 numbers and ensure that a forger cannot find one by chance.

If your numbers have 10 significant digits (~32 bits, ~8 hex digits), the probability of such an event is one over a million. Of course you can use more.

Question 7

I had a similar use case where I had to generate a unique/non-repeating code for every object created on the system(in this question, it is a coupon). I had the following requirements:

I wanted the length of the code to be as short as possible.
What I realized is that the length of the code will eventually be atleast as long as the number of digits that determine the count of the number of possible objects. For eg. if you generate 9999 coupons, the code will essentially have to be atleast 4 digits long.
Should not be sequential / easily guessable.

I explored several methods to generate keys including ones which are timestamp based and found that most methods generate long codes. So, I decided to employ my own logic as follows.

I create a db table where I create only one record, which maintains the count of number of objects created so far in the system.
I then prefix and suffix this number with one character each randomly selected from [a-zA-Z0-9]. This step ensures that even though the numbers are sequential, it is not possible to guess the code unless the prefix and suffix are guessed. Based on [a-zA-Z0-9] charset, there would be 3782 (62*61) possibilities for a code. The above charset works for me, but you are free to use a charset of your choice. Some suggestions are found on the best answer for this thread.
Every time a new object is created the object count is increased by one in the db.

In this approach the number of characters of the code will be determined by:

number of characters of ( count of objects in the system so far ) + 2

So, when you start out number of characters will be 3, when you reach 10 objects it will be 4, when you reach 100 objects it will be 5, for 1000 it will be 6 and so on. This way the system will scale on its own depending on the usage.

This approach worked out better than the case where a code is generated first and then checking if the code is already existing in the db. In that case you keep generating codes till you find a code that is not already generated.

Question 8

Get an epoch timestamp and base encode it.. as long as you save a record of it somewhere you can compare if it's valid when it's used.

If you need it to be enterable by hand you can always .string() it down to first 8 or so characters.