16

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

Gilles 'SO- stop being evil'
  • 50,912
  • 13
  • 120
  • 179
Dave
  • 261
  • 1
  • 2
  • 6
  • That's pretty open-ended. What sorts of properties do you want the numbers to have? And what it the salt about and where would it be saved? – nealmcb Mar 07 '11 at 06:13
  • I'm not clear about this, if you're asking for a cryptographically secure random number generator - even with certain additional constraints - then that's easy, just tell us which platform/language you're on. If you're asking for something else - then it's not clear, and why would you ask on ITsec? – AviD Mar 07 '11 at 07:07
  • javascript is primarily a client side language, so everyone will see ur algorithm. (there is ssjs, but who uses it??). Its also SLOW in compare to compiled programs. whatever you do, the best would be to: *1 generate these keys and save them to a database. *2 write a php/java form to read in user imputed key and see if its in the database. This allows for pretty much anything. One way to generate the keys is then to make a random number and get a sha1 or md5 of it (can do more then once to make it true random) – Sigtran Mar 07 '11 at 09:52
  • If you generate and check the keys with JavaScript someone is going to figure it out and abuse it. – WalterJ89 Mar 28 '11 at 10:00
  • What kind of application is it? php? if PHP, You might want to look at http://www.phplicengine.com to get an idea. –  Nov 19 '14 at 19:59
  • Here is an article I find very informative regarding generating secure license keys: [How to Generate License Keys Securely](http://www.softactivate.com/softactivate/GenerateLicenseKeys.aspx) It's about using elliptic curve cryptography to generate license keys. The generated keys can be as small as 20 characters and still secure. –  Nov 25 '11 at 09:40

3 Answers3

26

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

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • thank you for your answer. I'm trying to understand the cryptographically secure solution. By giving the generator a private key and the checker a public key, the checker could make sure that the messages it gets actually come from the generator. But what would be the content of these messages? Could you please explain what you mean by payload and signature of the payload or give a very simple example? Thx in advance. – Dave Mar 07 '11 at 14:19
  • You want several serial numbers, I think. The "payload" is whatever makes them distinct from each other. Say, it is a counter. Or it could be a customer identifier. – Thomas Pornin Mar 07 '11 at 15:53
  • The payload could also be customer name that the software is licensed to. Many software packages require entering both a serial number and a name, which then verifies that the two match. – David Phillips Jan 03 '12 at 23:23
6

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 ...
Community
  • 1
0xC0000022L
  • 1,604
  • 2
  • 15
  • 20
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):

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.

Misha
  • 2,699
  • 2
  • 19
  • 17