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