# Cryptographically secure product keys

I am looking for a scheme to generate and validate cryptographically secure product keys. My requirements are:

• Unforgeable. It must be impossible (or at least very hard) for users to forge a product key.
• Short. Users may enter product keys by typing so they must be convenient to enter. 128 bits can be encoded using 26 base-32 characters, which is probably close to the maximum that users will type comfortably.
• Payload. The keys must be able to carry a limited amount of arbitrary information. For example, this might be flags about enabled product features. 32-bits of payload should be sufficient.
• Numerous. There must be a large number of valid (but difficult to guess) product keys for the same payload.
• Unique. The product key generation process must generate distinct product keys for the same payload, when invoked multiple times.

In the following I consider only symmetric key schemes. A public key scheme is not necessary in my case because key generation and validation is done on the server, thus there is no need for public/private keys.

I have considered a number of different schemes, but I have found all of them wanting. The main issue is the shortness of the product key.

The obvious first choice is to create product keys of the form

nonce || timestamp || payload || HMAC(K, nonce || timestamp || payload)


The nonce || timestamp ensures that there are numerous unique product keys. HMAC is a secure MAC thus guaranteeing unforgeability. A payload is included. The only issue here is the length of the product key.

Recall that all this needs to fit in 128 bits. Even if we truncate the HMAC to 80 bits (the recommended minimum), this leaves only 48 bits for the nonce || timestamp || payload component, which is clearly not enough (the payload alone requires 32 bits).

Another choice is to create product keys of the form

AES-ECB(K, nonce || timestamp || magic || payload)


Here we use magic to enforce unforgeability. Clearly this is suboptimal, unless we make magic very long. If magic is short it is quite easy for an attacker to keep guessing product keys and feeding them to the validation server to see which ones pass (let's assume for now that the validation server has no countermeasures such as throttling).

The problem is that the nonce || timestamp part also needs to be very long to avoid problems with the use of ECB mode. Ideally it should be at least 80 bits, but perhaps we could get away with 64 bits. This would leave only 32 bits for magic, which I suspect would make this scheme weak.

I have also considered other alternatives, but I have not arrived at a satisfactory solution. I would love to hear any feedback you may have.

-
Have you considered the option of simply storing assigned product keys on the server securely? –  Thomas Jan 11 '14 at 12:12
Thomas, yes, that is a practical solution. Product keys will be in fact stored on the server after their first use (to avoid reuse). But I would rather not store the keys on the server at generation time if it can be avoided. –  Bill Zissimopoulos Jan 11 '14 at 18:42

Your second solution seems to be quite close to optimal. You perhaps do not need both nonce and timestamp unless timestamp is part of the payload. Anyway, the structure $$N||P,$$ where $N$ is 48-bit nonce and $P$ is a 32-bit payload seems sufficient for your needs, as you are unlikely to generate more than $2^{48}$ product keys. To ensure authentication (unforgeability) you merely add a 48-bit zero string (analogue of your 'magic') and encrypt it with AES: $$KEY = AES_K(N||P||0^{48}).$$ Forgery is unlikely in this scheme unless an attacker makes more than $2^{47}$ attempts (which I also suppose is a fair assumption).

In this scheme you can vary all these parameters if you have a larger payload but expect fewer keys or forgery attempts.

-
Similar to good answer by Ricky, but better, because this points out extraneous redundancy in OP's question, which can be removed and arrived at a practical solution. Extra credit for remembering to advice that the parameters can be varied. –  user4982 Jan 11 '14 at 20:27
Dmitry, I agree. This seems to be the best and most practical solution given the constraints. I will accept it as the answer. –  Bill Zissimopoulos Jan 12 '14 at 0:52

An important point is that you should make sure the fields are all fixed-length,
so that you can recover each of them from the concatenation of all of them.

You can just let magic be an all-zero string. $\:$ (It does not need to be kept secret or chosen randomly.)

The "problems with the use of ECB mode" are not relevant to your proposed scheme.
However, you could do slightly better by using one of these two format-preserving encryption schemes instead of AES. $\:$ (For example, you could let the domain be the set of all length-26 base-32 strings.)

-
Ricky to clarify: yes, all fields would be fixed length and easily extracted. Thanks for providing the links, they look very interesting. –  Bill Zissimopoulos Jan 11 '14 at 8:23
If using AES, it is possible to use NIST SP 800-38G, draft if a format preserving encoding is wanted. (As you say, FPE is not needed here.) –  user4982 Jan 11 '14 at 12:17