Generating secure short activation code for offline applications

Question

My application is as follows

• User has a hardware system (with an unique ID) that does not have connectivity but has a keypad for input.
• To make the hardware operational, the user has to go to central authority and get a code (7-8 digits) in exchange for money
• The user enters this code through the keypad and the system is operational for a certain period of time after which the user has to repeat the process.

Requirements

• The code has to be short and numeric (7-8 digits)
• The code should work for a specific hardware only (unique to each user)
• To keep things simple at the beginning, we can assume that every code generated will run the hardware for the same amount of time (as opposed to codes which give the time for which the hardware should run)
• Availability of standard libraries to implement this.

Here's what I've done so far

• I thought of using the ISO 7064 Mod 97,10 formula to generate codes (in the central authority) and the use the same formula on the hardware to see if it is valid. Based on this post. However, this means the same code is not unique to a hardware system. This is just an error detection algorithm.

• I can generate the code using the above formula and use RSA with digital certificate. However, the output will be too long correct? Besides, this means that the central authority has to have access to public keys of all hardware systems.

Answer 1

Let's examine the propositions in the question:

• I thought of using the ISO 7064 Mod 97,10 formula
  That provides no cryptographic protection against determined adversaries. ISO/IEC 7064 merely

  specifies a set of check character systems capable of protecting strings against errors which occur when people copy or type data.

• I can generate the code using the above formula and use RSA with digital certificate. However, the output will be too long correct?
  Yes. RSA signatures are at minimum roughly the width of the public modulus, that is for modern security 2048-bit or $2048\log2/\log10\approx617$ decimal characters. That's way too much to key in.
  

• Besides, this means that the central authority has to have access to public keys of all hardware systems.
  No. Verification of an RSA signature requires the public key of the authority entitled to produce it. Ignoring the size problem, there would be need for a single public/private key pair, with the private key held by the signing authority, and the same public key in all devices. Devices can recognize their serial number in the signed data.

---

While there are signature systems more compact than RSA, all yield a signature at least 10 times above the target "7-8 digits". Thus we can't use public-key cryptography.

The standard option there will be symmetric cryptography, with a secret key in each device. Standard practice is that the device key is derived from a master key known by the issuing authority, and the device's serial number, by some key derivation function (the Smart Card industry does this since the 1980s, under the name diversification). A single master key has to be kept, yet extraction of a device's key does not compromise the others. HMAC-SHA-256 would be a suitable derivation method. $\mathsf{DeviceKey}=\operatorname{HMAC}(\mathsf{MasterKey},\mathsf{SerialNumber})$ will do.

The unlock code can be some kind of Message Authentication Code of an index incremented at each reload and held in permanent memory by the device (and the authority's emission system), and truncated. That could be the decimal expression of $\mathsf{UnlockCode}=\operatorname{HMAC}(\mathsf{DeviceKey},\mathsf{Index})\bmod10^8$.

Normal operation is that the authority gets payment, finds $\mathsf{Index}$ for the $\mathsf{SerialNumber}$ in its database, computes $\mathsf{DeviceKey}$ then $\mathsf{UnlockCode}$, increment the $\mathsf{Index}$ for this device in the database. The device checks what's keyed-in against the $\mathsf{UnlockCode}$, and if there's a match activates and increment its $\mathsf{Index}$ in permanent memory.

Some issues need to be addressed:

• The $\mathsf{MasterKey}$ and the $\mathsf{DeviceKey}$s are sensitive targets, and that might be vulnerable at the authority and manufacturing site. A HSM or Smart Card might help. In particular, a Smart Card good for a limited number of $\mathsf{UnlockCode}$s could be what clerks at the authority really use.
• There should be significant redundancy in $\mathsf{SerialNumber}$ or whatever identifies devices in order to avoid clerical errors at the authority; ISO 7064 might be adequate there.
• There is a risk that an attacker tries codes at random to unlock a device, perhaps automatically. A countermeasure is a delay between entries, perhaps increasing after a number of consecutive errors. It is also possible that there are two codes, a short one with a limit of 3 tries (6 digits will be fine), and a long one (say 12 digits) used as backup (similar to the PIN in a mobile phone SIM, with the PUK as backup).
• The device should have appropriate mitigation for a variety of threats: unauthorized use with bypass of the payment, $\mathsf{DeviceKey}$ extraction, setting $\mathsf{DeviceKey}$ to a known value, setting $\mathsf{Index}$ to earlier value allowing reuse of an earlier code, resetting the aforementioned delay between entries by battery removal or other upset, side channel.. A classical goof is comparing the code keyed-in to $\mathsf{UnlockCode}$ using strcmp or similar library/language feature that leaks the position of the first mismatch by timing, which might be observable without opening the box, e.g. thanks to a LED or the keyboard scan EMI, allowing to find an 8-digit code in about 40 tries rather than 50 millions. Security engineering is not easy!
• Users will loose or temporarily misplace codes, and rather than bother asking for a duplicate, will pay for a new one. The device should thus accept a few codes ahead. And then it's desirable to accept slightly out-of-order codes; that complicates the algorithm, especially for short codes (since all codes in the acceptable window need to be distinct). A simple option if a window of $w$ codes must be accepted is that $\mathsf{UnlockCode}=w(\operatorname{HMAC}(\mathsf{DeviceKey},\mathsf{Index})\bmod\lfloor10^8/w\rfloor)+(\mathsf{Index}\bmod w)$.
• More generally it is possible to encode ancillary information within the code (e.g. reload amount). While we are at that, the length of the code can be variable, perhaps larger by one or two extra digits for high-value codes, for higher security.

Note: I do not see that Format Preserving Encryption really helps here, even when there is ancillary information to convey, since confidentiality of that seems to be more of a nuisance than a useful feature.

Answer 2

Let's get some basic math out of the way. If you have 8 digits your activation/authentication code only can encode a maximum of $8 \cdot log_2(10)$ bits worth of information. (About 26.5) So public key signatures are out of the question. Second, the probability of success is relatively high. ($10^{-8}$ or 1 in 100 million). That is a lot of numbers to type manually, but the chance of success is too high to consider secure unless we relax the assumptions and requirements made.

So here's what I would consider instead:

• We will trust the majority of users to be honest. It's not a big problem if some users "pirate" activation codes. (I'm personally opposed to "DRM" on principal when it's invasive, compromises user security, or prevents expert analysis of compiled code.) Preventing access to secret information and at the same time preventing tampering is hard.
• Instead we will say we'll assume most users don't have the ability to access symmetric keys on their device. Maybe there is a hardware security module. Maybe law and morality discourages "stealing" activation. Maybe people are just willing to pay and play fair.
• Additionally the user won't or can't delete local records, change the system clock, or modify code. Keeping a symmetric key secret won't help if the user hacks the app's binary to replace something like "if activation fails goto X" with a No-OP.

So first you will want to rate limit guesses. Just like online brute force password guessing, you can lock a person out of guessing temporarily if they fail too many activation-code-entries. Offline brute-forcing isn't something that you may be able to prevent. (If a person reads a secret key from memory in their device and brute forces an activation code on a personal computer then they can confirm if a potential activation code and wait until they find one they know is correct before attempting activation.) But it doesn't matter that this is theoretically possible if we accept the assumptions listed.

To prevent double spending you will want to save a list of activation codes the user has already used. We assume the users doesn't meddle with this list. If you have an app the user can uninstall and reinstall without restoring the spent-code-list then they could reuse codes at the expense of losing all their other data. You can still prevent this within the limits of the assumptions made. Instead of deriving a user ID from a hardware ID you can generate a new random user ID after time the app is reinstalled. Since those spent codes are associated with only the old user ID they cannot be reused this way.

Next you have to worry about the probability of guessing any unspent code. Not just one of them. If you do not allow old purchased but unused activation codes to expire, then there is only a finite number of activation codes you can issue to a user. The greater this number the more likely a person can guess a correct activation code.

Option 1: One solution, based on what I read Nintendo does with some of its freemium games, is to set the maximum number of purchases you can make. After the user spends the equivalent amount of money for a normal full game all the freemium pay-to-play features are replaced with permanent unlimited resources. Presumably the reason for this is to preserve consumer's respect and to prevent parents from complaining that their child spent infinity dollars on in game purchases. This has the dual use of showing good will to the customer (someone may spend the maximum up front just to support your product) and keeping the probability of guessing correct activation codes low.

Option 2: Let purchased activation codes expire. So now you validate that activation codes are correct for the user and correct for the current date.

Crypto-Implementation:

For option 1: I would generate the limited number of activation codes ahead of time and make a database relating user IDs to activation codes. When I sell a customer their activation code I mark that code as used so I don't sell them the same one again. This requires, for example, physical access to the device at the sale point to program activation codes, or online registration (which doesn't require internet access to use activation codes later), or you generate random codes prior to sale of the hardware and record them in the server database and onto the device at the same time. You can store hashes (stretched or not) of the activation codes if you want to further obscure activation codes. This does not make codes less guessable because a 8 digit number cannot contain enough entropy to make guessing impractical.

If you don't want to store any data or instead prefer no activation-code programming or registration. you can instead derive an encryption key from the user ID the customer gives you and use format preserving encryption to generate activation codes. The user says "my ID is x and I want to buy activation code n". The server encrypts n using a key derived from x, converts the result to decimal, and gives it to the user. The user inputs the decimal code into their device, their device derives the same key from it's user ID, and checks if it decrypts to the number stored in its activation-counter, and, if the plaintext and activation counters match, unlock some feature and increment the activation-counter. Since format preserving encryption is bijective on whatever set it uses for input/output only one activation code will map to a number in {0, 1, 2, 3, ...}.

For Option 2: I would use the time based one time password algorithm. Your use case is essentially identical with respect to security as is the case for one time passwords. There server and user device need to hold the same secret key and every user needs there own key. That way Alice's one-time-password is not the same as Bob's one-time-password so they cannot share the same activation code. With web based authentication you set the period length in which identical one-time-passwords are computed (from the secret key and the current time) to just a few seconds. Then you check within a window of a few periods to account for clock differences, user input delay, and communication time. You will want to set the period to be much longer because the transfer of user-ID -> store -> activation-code -> code entry on device is effectively a very slow communications channel. Your time period length could half your activation time and your window should be large enough to accommodate a week or more delay between the time of purchase and the time of activation code entry.

Remember with both methods you need to store spent keys client side (or at least a counter for option 1). You also need to trust the user isn't cracking/hacking/pirating also, but even if you could prevent this with some other user access control system someone capable of hacking your app could just disable the need for activation codes by patching the check out of the code binary.

PS I've written this post over several sittings. Let me know if some part seems unclear. For option 1 there is also sibling of TOTP, HOTP. I've been distracted so many times that I can't remember why I didn't include it.

One more thing. For TOTP and HOTP you need to keep a list of spent activation codes but also need to be conscious of repeat codes. You can instead store the code plus the counter value or the code plus the time. If you don't account for this then after you sell an access code there is a one in $10^8$ chance their code will fail despite paying for the same activation code twice.