License key / Serial number generator and checker

Question

I need a serial number generator and accompanying checker. I would like to be able to set a salt (and maybe a length). The generator should only produce serial numbers that pass the test of the checker. Those numbers should only account for a small fraction of all the possible numbers of the given length.

The algorithm needn't be cryptographically secure. Rather, it should be very easy to implement (in javascript) and it should be very fast.

To clarify: If you buy commercial software, it is sometimes protected with a serial number/a key. If you type it in, the software verifies it algorithmically (by checking whether it fulfills certain properties), rather than looking up a huge database. I'm also pretty sure that the keys were all generated algorithmically rather than by hand. And only a small fraction of all the possible keys of a given length are actually valid so it's hard to guess keys.

Salt: I don't know whether salt is the right word, but the algorithm should have at least one parameter, whose choice alters the generated keys (so that multiple people can use the same algorithm and needn't fear collisions).

Answer 1

If there is no real need for security, then here is a very fast serial number generator, with a checker:

• User a counter. Initialize it at 0. When you want a new serial number, increment your counter by 1000; the new counter value is the serial number. The checker works like this: a serial number is valid if it ends with three zeros. Only one of every 1000 numbers will be accepted by the checker.

If this solution does not please you, then you do have a need for security, and this calls for cryptography.

The cryptographically secure solution is to have signed serial numbers: the serial number is the encoding of some payload (e.g. a counter of all serial numbers that you have generated) and a signature over the payload. The generator has a private key, which it uses to compute the signatures; the checker only knows the corresponding public key. The trouble with this setup is not really about verification time, even in Javascript; rather, it is the size of the signature which is a problem. I assume that the serial number will be, at some point, typed by a user. The minimal theoretical size for a cryptographically secure signature is about 80 bits (since signatures can be verified with only the public key, an attacker could try all possible bit sequences, and we usually require a security level of at least 2⁸⁰). However, the smallest signatures among the "assumed to be secure schemes" are closer to 160 bits (with BLS, which uses a pairing, which is kind of complex to implement) or 320 bits (with DSA or ECDSA). There is some work on signature systems with shorter signatures (Quartz, or McEliece-Niederreiter) but there is quite some controversy on their security.

Even with both uppercase letters and digits (36 possible characters, and there you have both 'I' and '1', and also 'O' and '0'), a 160-bit signature will use 31 characters. Along with the payload, you will end up with serial numbers of length 35 or so, which is probably too much for an average user to type in (but not by a large margin; an 80-bit signature would fit nicely).

If you do not use a signature scheme, then you must be aware that a reasonably determined attacker will be able, through some disassembly, to circumvent the checker, or even to learn enough to be able to produce his own serial numbers (which the checker will happily accept). At that point, you will not get quantified security: you will not be able to say: "my scheme is secure up to a budget of 3.8 billion dollars". Rather, it will go as: "my scheme is secure until a sufficiently witty and bored student comes along, reverse-engineers the checker code, and publishes the result on Facebook".

The classical not-really-secure scheme would look like this:

• Use the counter from the previous scheme (the one with ends with three zeros). Encode it as a 64-bit block. Encrypt that block with some hardcoded symmetric key, using a block cipher. The checker knows the key, and verifies the serial number by decrypting it (with the same hardcoded symmetric key) and looking at the final zeros.

This is not really more secure than the plain counter, but at least the serial numbers will be random-looking. With an alphabet of 34 characters (digits and uppercase letters except 'O' and 'I'), a 64-bit block requires 13 letters, which is probably acceptable (a typical Microsoft serial number has 25 letters). For the 64-bit block cipher, I recommend XTEA, which should be fast and simple enough to implement.

Answer 2

If you want the cryptographically secure method you won't get around an internet connection to verify the serial. This means that such a protection scheme is better suited for subscription based software than it is for traditional shelf software.

With internet connections it's simple (since you use JS, I assume that's the one you want):

1. Someone creates a key, that party has to know the secret
2. Server knows secret and is able to decode the data
3. Client sends the key, which is a binary blob encoded in Base32 (also see this)
4. Server decrypts the key and checks whether it's valid (either just syntactically or also semantically)

Without internet connection you can still use a scheme similar to PGP signing in order to verify that the blob that the user enters was created by you. Encryption won't work the same, because the decryption always requires to know the secret and the big issue here is:

1. you don't trust the user (otherwise you wouldn't need the protection scheme)
2. you give the user the secret, compiled into your binary

Obviously both points contradict each other. On one hand you don't trust the user, on the other hand you have to deploy the secret used for decryption.

All in all I have to conclude that without the internet connection and the server-based validity check that results in the revelation of some knowledge (e.g. content that is useful only for so long) any protection scheme I have seen so far is more or less an arms race between crackers and vendors.

---

Now, if it isn't important to have a cryptographically secure system, I'd still go for any binary data that you can secure by means of a simple CRC or so. What comes to mind would be:

1. Have a monotonically increasing serial number
2. XOR it with your salt value (or any other reversible operation)
3. Take the CRC32 of that value (or Adler32 or whatever) - add more salt here if needed
4. Encode it with Base32 (aids readability etc)
5. Only check that the CRC32 for validity ...

Answer 3

OP wrote "it should be very easy to implement (in javascript) and it should be very fast"

Its not clear whether "in javascript" refers to the generator or the checker or both, or whether it refers to "javascript in the browser", or some other java/ecmascript implementation (e.g. server-side in the web server).

Javascript as an implementation language isn't necessarily a problem, and there are a couple of crypto libraries for javascript (supporting MD5, DES, AES, SHA, PBKDF2, HMAC):

• http://crypto.stanford.edu/sjcl/
• http://code.google.com/p/crypto-js/

Speed shouldn't be too much of a problem either (browser javascript engines are getting quite usable in that respect, once you get past IE6/7).

However, neither of the above support public key crypto (which is required for security if the "checker" is distributed to the untrusted user and thus cannot be allowed access to the key used to create serial numbers) - let alone the specific algorithms suggested by Thomas, above. Google does turn up some hits for public-key implementations in JavaScript (http://www-cs-students.stanford.edu/~tjw/jsbn/, http://ohdave.com/rsa/, http://www.hanewin.net/encrypt/rsa/rsa.htm) but personally I'd be even more nervous about their bug-free-ness than the "bigger" libraries above.

Perhaps more significantly, even with a public key-based approach, if either the generator or the checker are distributed to the untrusted user, then the scheme is not secure. If the generator code is available to the untrusted user then they can generate as many keys as they like, while if the checker is available to the untrusted user then they can simply modify the javascript code to skip the checks. [The same issue arises with native code, of course, but, even with obfuscation, JavaScript is arguably simpler to attack through local modifications.]

Before implementing a security scheme in JavaScript you should also consider the wider trust issues: see http://rdist.root.org/2010/11/29/final-post-on-javascript-crypto/ for a useful summary.