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?

Latimore

If you only use 16 base-64 characters then that's 96 bits. You can expect to have a collision (read: non-unique serial numbers) if you generate 281474976710656 serial numbers (that's 2^36 keys - the birthday paradox 50% bound) – Lovering

Why does the input have to be sequential numbers? – Shovelboard

@ThomasM.DuBuisson If they sell 2^36 licenses for $2 each, that's the GDP of New Zealand. I think they're safe for a little while. – Shovelboard

@NickJohnson Yeah, that was my point ;-). Still, if they wanted to be safer they could use BlowFish (or just 3DES) in CNT mode to produce 64-bit values (11 base-64 characters) that are mathematically certain to be unique for a count of 2^64. – Lovering

@NickJ, the input is the devices serial number, which are generated sequentially when the devices are manufactured. These serial numbers are stored in a database, so both the customer hardware and any key generator that I create for the office will have access to the seed. – Latimore

@ThomasM.DuBuisson Right, though the same is true for any other algorithm with sufficiently long block size, like SHA1. RLH Gotcha. – Shovelboard

@NickJohnson There is no certainty that the initial X bits of a SHA1 of any two values in the range 0-2^64 won't overlap. I picked two block ciphers with 64 bit blocks as examples specifically for this reason. I'm not aware of any work that can reuse larger blocksize ciphers (or hashes) to produce non-conflicting results of a length smaller than their blocksize, but it's an interesting question. – Lovering

@ThomasM.DuBuisson That's true, but mostly irrelevant - though there's no firm guarantees of no collision, they're so unlikely with a sufficiently large space (and a sufficiently small proportion in use) that it doesn't matter. – Shovelboard

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.

Anergy

This is a possible solution, however, I am a bit curious if there is a simpler solution that a full SHA-1 hash implementation. If this is about as simple as it is going to get and still meet my requirements, I can accept this answer. I will, however, have to write my own SHA-1 implementation. – Latimore

This is a good answer. I'd point out that the choice of the hash function isn't all that important, as long as it's reasonably cryptographically secure. – Edrisedrock

@RLH: I don't think you need to write the SHA-1 implementation, there are loads of ready-made implementations in C available under permissive open source licenses. – Anergy

@Patrick87: sure, I just wrote SHA-1 because it's relatively simple, widespread (=lots of free implementations) and widely recognised as secure. Still, I edited my answer to clarify that any secure hashing algorithm will do. – Anergy

What about using the reference implementation in RFC3174? It's portable C. – Aesculapian

@Ranieri: that's exactly what I just found; I was a bit dubious about the license (since there's no particular reference to the license for the sample code), but since it says that it's "to provide convenient open source access [...] to [...] SHA-1" I'd say that it could be ok. Still, using Google Code Search I found several BSD-licensed implementations that could also be fine. – Anergy

I'd recommend using an HMAC, not just bare SHA1. Also, 'secret salt' is an oxymoron - if it's secret, it's a key. And it's safe to truncate a cryptographically secure hash insofar as the security will be proportional to the length of the resulting hash, not weaker. – Shovelboard

@NickJohnson: you're right on the first two points (I used the term "salt" because that's how you usually call that kind of thing, but it is sure that here it's more a key), but I'm uncertain about the last point, and in case of doubt I prefer to stick with the algorithm "as is", in too many cases trying to do clever tricks with cryptography has resulted in losing a lot of security. – Anergy

@MatteoItalia I agree in general, but one fundamental property of cryptographic hashes is that they're well-distributed. If a given subset of the hash could be broken faster than brute-force, the hash itself would be broken. For an example of this in practice, see RFC 4226 - HOTP. – Shovelboard

@NickJohnson: hmm, you have a point, I'll add this to my answer. – Anergy

@MatteoItalia Great! Your statement about HMAC isn't quite accurate, though - it doesn't add extra cryptographic properties, instead it prevents certain attacks against naive ways of concatenating a key and value in a hash function. See section 6 of RFC2104 for details (and section 5 for a description of the security of truncating it, something I only just noticed). – Shovelboard

@NickJohnson: my knowledge of HMAC is quite lacking, I didn't understand correctly how you meant to use it. I hope now I understood, I'll correct the answer. – Anergy

@NickJohnson: hehe, I was reading that paragraph right now. :) I surely don't mind, thank you for your edit! – Anergy

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.

Diapause

Answer 3

You can use an Xorshift random number generator to generate a unique 64-bit key, and then encode that key using whatever scheme you want. If you use base-64, the key is 11 characters long. If you use hex encoding, the key would be 16 characters long.

The Xorshift RNG is basically just a bit mixer, and there are versions that have a guaranteed period of 2^64, meaning that it's guaranteed to generate a unique value for every input.

The other option is to use a linear feedback shift register, which also will generate a unique number for each different input.

Eft

Using a non-cryptographically-secure PRNG to generate keys is a bad idea, and will allow an attacker who can observe several keys to generate his own. It's also not clear from your answer how you'd verify a generated key. – Shovelboard