How can I generate unique, non-sequential serial keys without 3rd party software?

Question

I'm working on a project that involves writing low-level C software for a hardware implementation. We are wanting to implement a new feature for our devices that our users can unlock when they purchase an associated license key.

The desired implementation steps are simple. The user calls us up, they request the feature and sends us a payment. Next, we email them a product key which they input into their hardware to unlock the feature.

Our hardware is not connected to the internet. Therefore, an algorithm must be implemented in such a way that these keys can be generated from both the server and from within the device. Seeds for the keys can be derived from the hardware serial number, which is available in both locations.

I need a simple algorithm that can take sequential numbers and generate unique, non-sequential keys of 16-20 alphanumeric characters.

UPDATE

SHA-1 looks to be the best way to go. However, what I am seeing from sample output of SHA-1 keys is that they are pretty long (40 chars). Would I obtain sufficient results if I took the 40 char key and, say, truncated all but the last 16 characters?

Answer 1

You could just concatenate the serial number of the device, the feature name/code and some secret salt and hash the result with SHA1 (or another secure hashing algorithm). The device compares the given hash to the hash generated for each feature, and if it finds a match it enables the feature.

By the way, to keep the character count down I'd suggest to use base64 as encoding after the hashing pass.

SHA-1 looks to be the best way to go. However, what I am seeing from sample output of SHA-1 keys is that they are pretty long (40 chars). Would I obtain sufficient results if I took the 40 char result and, say, truncated all but the last 16 characters?

Generally it's not a good idea to truncate hashes, they are designed to exploit all the length of the output to provide good security and resistance to collisions. Still, you could cut down the character count using base64 instead of hexadecimal characters, it would go from 40 characters to 27.

Hex:    a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
Base64: qUqP5cyxm6YcTAhz05Hph5gvu9M

---edit---

Actually, @Nick Johnson claims with convincing arguments that hashes can be truncated without big security implications (obviously increasing chances of collisions of two times for each bit you are dropping).

You should also use an HMAC instead of naively prepending or appending the key to the hash. Per Wikipedia:

The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with MAC = H(key ∥ message). However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC. The alternative, appending the key using MAC = H(message ∥ key), suffers from the problem that an attacker who can find a collision in the (unkeyed) hash function has a collision in the MAC. Using MAC = H(key ∥ message ∥ key) is better, however various security papers have suggested vulnerabilities with this approach, even when two different keys are used.

For more details on the security implications of both this and length truncation, see sections 5 and 6 of RFC2104.

Answer 2

One option is to use a hash as Matteo describes.

Another is to use a block cipher (e.g. AES). Just pick a random nonce and invoke the cipher in counter mode using your serial numbers as the counter.

Of course, this will make the keys invertible, which may or may not be a desirable property.