How are software license keys generated?

Question

License keys are the defacto-standard as an anti-piracy measure. To be honest, this strikes me as (in)Security Through Obscurity, although I really have no idea how license keys are generated. What is a good (secure) example of license key generation? What cryptographic primitive (if any) are they using? Is it a message digest? If so, what data would they be hashing? What methods do developers employ to make it difficult for crackers to build their own key generators? How are key generators made?

Answer 1

I've not got any experience with what people actually do to generate CD keys, but (assuming you're not wanting to go down the road of online activation) here are a few ways one could make a key:

• Require that the number be divisible by (say) 17. Trivial to guess, if you have access to many keys, but the majority of potential strings will be invalid. Similar would be requiring that the checksum of the key match a known value.

• Require that the first half of the key, when concatenated with a known value, hashes down to the second half of the key. Better, but the program still contains all the information needed to generate keys as well as to validate them.

• Generate keys by encrypting (with a private key) a known value + nonce. This can be verified by decrypting using the corresponding public key and verifying the known value. The program now has enough information to verify the key without being able to generate keys.

These are still all open to attack: the program is still there and can be patched to bypass the check. Cleverer might be to encrypt part of the program using the known value from my third method, rather than storing the value in the program. That way you'd have to find a copy of the key before you could decrypt the program, but it's still vulnerable to being copied once decrypted and to having one person take their legit copy and use it to enable everyone else to access the software.

Answer 2

CD-Keys aren't much of a security for any non-networked stuff, so technically they don't need to be securely generated. If you're on .net, you can almost go with Guid.NewGuid().

Their main use nowadays is for the Multiplayer component, where a server can verify the CD Key. For that, it's unimportant how securely it was generated as it boils down to "Lookup whatever is passed in and check if someone else is already using it".

That being said, you may want to use an algorhithm to achieve two goals:

• Have a checksum of some sort. That allows your Installer to display "Key doesn't seem valid" message, solely to detect typos (Adding such a check in the installer actually means that writing a Key Generator is trivial as the hacker has all the code he needs. Not having the check and solely relying on server-side validation disables that check, at the risk of annoying your legal customers who don't understand why the server doesn't accept their CD Key as they aren't aware of the typo)
• Work with a limited subset of characters. Trying to type in a CD Key and guessing "Is this an 8 or a B? a 1 or an I? a Q or an O or a 0?" - by using a subset of non-ambigous chars/digits you eliminate that confusion.

That being said, you still want a large distribution and some randomness to avoid a pirate simply guessing a valid key (that's valid in your database but still in a box on a store shelf) and screwing over a legitimate customer who happens to buy that box.

Answer 3

For old-school CD keys, it was just a matter of making up an algorithm for which CD keys (which could be any string) are easy to generate and easy to verify, but the ratio of valid-CD-keys to invalid-CD-keys is so small that randomly guessing CD keys is unlikely to get you a valid one.

INCORRECT WAY TO DO IT:

Starcraft and Half-life both used the same checksum, where the 13th digit verified the first 12. Thus, you could enter anything for the first 12 digits, and guess the 13th (there's only 10 possibilities), leading to the infamous 1234-56789-1234

The algorithm for verifying is public, and looks something like this:

x = 3;
for(int i = 0; i < 12; i++)
{
    x += (2 * x) ^ digit[i];
}
lastDigit = x % 10;

CORRECT WAY TO DO IT

Windows XP takes quite a bit of information, encrypts it, and puts the letter/number encoding on a sticker. This allowed MS to both verify your key and obtain the product-type (Home, Professional, etc.) at the same time. Additionally, it requires online activation.
The full algorithm is rather complex, but outlined nicely in this (completely legal!) paper, published in Germany.

Of course, no matter what you do, unless you are offering an online service (like World of Warcraft), any type of copy protection is just a stall: unfortunately, if it's any game worth value, someone will break (or at least circumvent) the CD-key algorithm, and all other copyright protections.

REAL CORRECT WAY TO DO IT:

For online-services, life is a bit simpler, since even with the binary file you need to authenticate with their servers to make any use of it (eg. have a WoW account). The CD-key algorithm for World of Warcraft - used, for instance, when buying playtime cards - probably looks something like this:

1. Generate a very large cryptographically-secure random number.
2. Store it in our database and print it on the card.
   
   Then, when someone enters a playtime-card number, check if it's in the database, and if it is, associate that number with the current user so it can never be used again.

For online services, there is no reason not to use the above scheme; using anything else can lead to problems.