10
$\begingroup$

I'm trying to design a promo code system for a server app I'm designing. Basically, I generate a promo code for a certain item and give the code out to someone, who then types it into the server.

Currently, the generator I wrote gives out a 20-character alphanumeric code, but the codes are too easy to manipulate. To fix this issue, I'd like to implement some sort of symmetric encryption (so that the generator app can make the code, but the server can also read it) to keep users from figuring out how codes are generated.

Is there a symmetric encryption algorithm I can use that will return 20 alphanumeric characters?

If possible, I'd like to find an algorithm that can easily be implemented into Java code.

$\endgroup$
  • $\begingroup$ Just encode the output into alphanumeric. This should just be post processing on the output. $\endgroup$ – Yehuda Lindell Sep 10 '15 at 4:33
  • $\begingroup$ @YehudaLindell that will not work with a standard block cipher size, which will require truncation, and therefore not be decryptable (if that is a requirement), but yes Base32 encoding on 100 bits of data gives a 20 byte string $\endgroup$ – Richie Frame Sep 10 '15 at 4:45
  • 1
    $\begingroup$ @CodesInChaos Offline generation capability and limited space. Plus, I need an algorithm I can give to trusted people without granting them DB access. $\endgroup$ – Kaz Wolfe Sep 10 '15 at 9:16
  • 1
    $\begingroup$ Cryptography is not the right tool. @CodesInChaos is correct, you should store promo codes in your database. Promo codes are normally individual, single use (otherwise people will use the same code 1000 times, or you must store per-account who has used a particular promo code in your database, which is none more efficient than keeping track of valid codes). Storing valid codes has the advantage that as long as guessing one correctly is unfeasible (surely the case with 20 digits) you can just as well use random numbers as "generation algorithm". $\endgroup$ – Damon Sep 10 '15 at 21:00
  • 1
    $\begingroup$ Limited space shouldn't be a concern for most use cases of promo codes - I mean, when doing estimates for what data storage tech you'd need, a useful rule of thumb is to treat all dataset sizes between one and a million as practically equal, as a million entries is not much data at all. Quite likely a list of all the codes you'll need will take no more than a megabyte, and any distribution channel that you would use for delivering an algorithm to offsite trusted people can also handle an algorithm that says "take the next item from this attached 100000 row subset of pregenerated codes". $\endgroup$ – Peteris Sep 10 '15 at 22:27
14
$\begingroup$

Both of the other answers tackle the question of encryption in a particular format, but I would argue that neither of them is necessarily a good fit for your use case. You want to be able to generate 20 character codes that a server will be able to verify. A symmetric MAC is sufficient for this use case, if you don't need the codes to contain any secret information.

For example, use the format ID||HMAC(key, ID), with ID an arbitrary unique number for each code. You can choose the ID size and then truncate the HMAC to match your length requirements. E.g. 32-bit ID and 168 left bits of HMAC-SHA256. Then encode in the format you want.

IDs can be generated randomly or using a counter or it can include encoded information. The server would store the association between an ID number and whatever the promo code is for etc. An attacker cannot modify a promo code without knowing the MAC key, except by chance with probability $2^{-l}$, where $l$ is the MAC length in bits. You can go as low as $l = 64$ securely. (Perhaps even lower if you make an online guessing attack sufficiently difficult/slow.)

$\endgroup$
  • $\begingroup$ This is what I thought initially. But in the comments on the question he said that he needs to be able to decrypt to find what the code is to be "used for". $\endgroup$ – Yehuda Lindell Sep 10 '15 at 6:25
  • $\begingroup$ @YehudaLindell, yeah, that's why I explained how to do it in the last paragraph. If Insecure Security doesn't think it is sufficient, they can of course ignore this answer, but I think in most cases it would be. $\endgroup$ – otus Sep 10 '15 at 6:28
  • $\begingroup$ @otus: The reason I don't want to store codes in a server is so we can generate them on the fly and not have to rely on updating a database somewhere. $\endgroup$ – Kaz Wolfe Sep 10 '15 at 6:40
  • 4
    $\begingroup$ @InsecureSecurity, even in that case, if what they are for is not secret, you can encode that information in the (public) ID. $\endgroup$ – otus Sep 10 '15 at 6:41
  • 3
    $\begingroup$ @InsecureSecurity How do you track when a code has been used? Store it in the database? $\endgroup$ – mikeazo Sep 10 '15 at 15:32
7
$\begingroup$

What you are asking is a straight application for Format Preserving Encryption, which builds ciphers which input and output are in a constrained format (generically: common to input and output, hence preserved). The FPE field has many articles with proven techniques; and proposed standards, including BPS and SP800-38G Draft.

Specifically, it looks like you want a cipher on the space of 20-characters alphanumeric codes, perhaps with some restriction or special rule in consideration of the operator entering the value into the server; if you restrict to uppercase and digits, and assimilate 0125 to OIZS, you are left with $26+10-4=32=2^5$ symbols, and your message space has a nice $100$-bit size. Among many simple techniques to build a cipher on this space, you could use a Feistel construction with AES as the round function. Adapting an earlier answer:

The AES block cipher is used with a fixed secret key

parameters:
    B = 50                        // half the number of bits per block
    N = 8                         // number of rounds (could be lowered)

enciphering plaintext block P, assumed to be 2*B bits
    L = P>>B                      // extract left  B bits
    R = P & ((1<<B)-1)            // extract right B bits
    for I from 1 to N             // round loop
      encipher ((I<<B) | R) with AES, keep the B right bits H
      L = L ^ H
      exchange R and L
    C = (R<<B) | L                // append the halves, with R on the left
    output ciphertext block C

deciphering ciphertext block C, assumed to be 2*B bits
    L = C>>B                      // extract left  B bits
    R = C & ((1<<B)-1)            // extract right B bits
    for I from N downto 1         // round loop
      encipher ((I<<B)|R) with AES, keep the B right bits H
      L = L ^ H
      exchange R and L
    P = (R<<B) | L                // append the halves, with R on the left
    output plaintext block P

Notice that after deciphering the enciphered alphanumeric code, you need to check enough of the recovered plaintext (perhaps, the last 10 symbols out of 20 must be A) so that a wrong ciphertext (resulting in an essentially random plaintext) will fail the check with high confidence.

$\endgroup$
  • $\begingroup$ This will of course also work but I think it's overkill regarding what is needed (at least as I understand it). $\endgroup$ – Yehuda Lindell Sep 10 '15 at 5:36
  • $\begingroup$ @Yehuda Lindell: I agree 8 rounds are way overkill. For the rest, I got (after fixing my numbers) exactly the same technique as you do, a minute later, and less concidely. $\endgroup$ – fgrieu Sep 10 '15 at 5:46
  • $\begingroup$ This looks very interesting. Are there any java examples for this that you know of? $\endgroup$ – Kaz Wolfe Sep 10 '15 at 5:55
  • $\begingroup$ @fgrieu: Okay, question with the answer you linked. Is it really necessary to split the string into two separate strings for encryption? $\endgroup$ – Kaz Wolfe Sep 10 '15 at 6:05
  • $\begingroup$ @fgrieu Thanks for all your help. I'll try writing the code tonight. $\endgroup$ – Kaz Wolfe Sep 10 '15 at 6:14
2
$\begingroup$

Based on the clarifications in the comments, what you are looking for is a block cipher over 100 bits. This will enable you to Base32 encode into a 20 byte string, and to decrypt as well. Note that encrypting directly with a block cipher is in general not secure. However, I assume that with promo codes you will always encrypt a unique plaintext. If this assumption is correct, then using a block cipher (pseudorandom permutation) is secure.

In order to achieve this, you just need to build a Feistel structure, where in each round you use AES truncated to 50 bits. Note that the input to each round is 50 bits as well, so you must pad this to 128. First, you have to pad the round number (0,1,2,3) and then the rest can just be zeroes (it need not be reversible). I stress that the round number must be included! This will give you an invertible pseudorandom permutation, by the famed Luby-Rackoff theorem. For 100 bits, you would need 12 rounds of Feistel (this is the current recommendation).

$\endgroup$
  • 3
    $\begingroup$ I you have a simple quantitative argument to decide the number of rounds of a balanced Feistel cipher with $2b$-bit width and (assumed) perfectly random round function, that makes it practically as safe as can be, I want it! Perhaps I should make a question about that. $\endgroup$ – fgrieu Sep 10 '15 at 5:41
  • 1
    $\begingroup$ It's an open research question. The number of rounds needed is based on attacks on Feistel ciphers by Patarin and others. We have upper bounds on attacks and no lower bounds (to the best of my knowledge). So, we don't actually have a good answer to this. (These upper bounds show that you need many more than 4...) $\endgroup$ – Yehuda Lindell Sep 10 '15 at 12:50
  • $\begingroup$ I'm not sure that 4 rounds is enough; for a 100-bit block width, you only get a $2^{25}$ level of security, which is uncomfortably low. The scheme would probably be safer with 8 rounds. (There are more modern results than Luby-Rackoff which show better security with more than 4 rounds, as you probably already know.) $\endgroup$ – D.W. Sep 11 '15 at 6:51
  • $\begingroup$ Actually, yes; you are probably right. $\endgroup$ – Yehuda Lindell Sep 12 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.