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

Question

My Rails app needs to generate electronic coupons for users. Each coupon given should have a unique coupon code that can be redeemed on our system.

For example a coupon for a free burrito. User A receives a coupon for a free burrito and then User B receives a coupon for a free burrito. The 2 coupons should have unique coupon codes.

What is the best way to generate a code like this that is not easily forged? I don't want users to have a high success rate of typing in random numbers and redeeming other peoples coupons.

I guess thinking about it like a gift card with a unique number on the back is what I am looking for.

Loreanloredana

Is the code for machine use (in e.g. URLs) or supposed to be typed in by hand from a print out, or something in-between (something you expect a user to successfully cut & paste, and not find it difficult to do)? – Humanity

@NeilSlater typed in by hand from a print out. – Loreanloredana

Eric Lippert shows how to do this using a multiplicative inverse. See A practical use of multiplicative inverses. Once you've generated the inverse, you can then encode it using Base 64 or Base 36, or whatever you like.. – Chukar

Answer 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.

Humanity

your raw_string has a maximum of 19 characters. What's when the random_number method returns i.e. 2? – Downtoearth

@wuarmin: It won't (because it is so unlikely), but in general you are right to be concerned, and there are better ways to do this generation so that you have exact randomness you want plus some string padding with any leading zeros (which would become trailing 2s in the example). – Humanity

@wuarmin: I hacked it to still work even when the RNG gives you an unfeasibly small starting number. There are nicer Ruby-ish ways to do this now though – Humanity

I understand, thanks 👍 for the fix. Another point: why are you translating abcde with TYUAP and not with ACDEF? Why are you skipping i.e. C? – Downtoearth

@Downtoearth I deliberately chose a set of target printable letters that are hard to mistake for each other when reading them back from the page. I dropped "C" because I also have "F" and "U", and don't want to randomly offend one in 10,000 people. The specific list is not too important, you could make it different. The specific mapping doesn't matter at all- there's no benefit for preserving letters, it's random anyway. – Humanity

one last question: You write, that if you issue a billion of your own codes, there would be a 4 in a million chance to guess one, but 1**9/20**12 results to 2.44*10**-7. – Downtoearth

@Downtoearth I woite "1 in 4 million" (not 4 in a million as you quote) and 2.44*10**-7 is roughly 1/4000000. – Humanity

thank you for your hints. One last question: Why did you choose 2**80? Why not choose an even larger number to be on the safe side? What would you choose, if you want to generate a 16-digit code? – Downtoearth

@Downtoearth Actually now I think that I would choose exactly the right number. But if you go larger for simplicity of not having to calculate that, there are diminishing returns for "even larger" when your big number is already e.g. 100x the target space. What you are trying to avoid is an exploitable bias towards some subset of the numbers, which might happen if you generate something that is 2.5 times the space, then some numbers will repeat twice, some three times, putting a 60/40 bias on expected codes. – Humanity

@Nail Slater, ok, thanks for your input. What do you think of the following solution to generate raw for a resulting 16-digit code? SecureRandom.random_number(20**15..20**16).to_s(20).reverse – Downtoearth

@Downtoearth It might address dealing with "small" numbers. I cannot realistically review your decisions and make suggestions in comments though. There are much cleaner ways to generate codes than in my example - most of the answer is about the theory. If you want something more robust, I suggest as a new question – Humanity

All right. I have posted a new question. #78220949 – Downtoearth

Answer 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

Vancouver

Answer 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.

Tinsley

Answer 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

Vindicable

Answer 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.

Nicole

Wouldnt that use a lot of time once the database got big? – Loreanloredana

@Deekor: You will need to store the code to store which codes were already used. If you use large random numbers collisions will be quite rare. – Nicole

In this case "rare" is not good enough. Randomness is not intuitive: collision might occur in ten years but also after 10 draws, a typical attribute of (pseudo-)random functions. Databases generally are very good in finding duplicates. I'd argue that the code for unique keys in any RDBMS is optimized in such a way that an average application developer has not a chance. Store them in a table column protected with a unique index. – Gloze

Answer 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.

Infringement

Answer 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.

Graphitize

Answer 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.

Dorettadorette