Well, I guess I'm not quitting my day job to become a cryptographer any time soon.
As was instantly ascertained on reddit, the key algorithm in my "Hacker Challenge" is RSA. I was hoping that it would take at least an hour to crack the private key, but alas, I had severely underestimated the time that modern elliptic-curve and number field sieve integer factorizers would take. It factored in under a second, which means the key would have to be many orders of magnitude larger to offer any kind of security.
So within an hour a factorization of n was posted to reddit by c0dep0et. Even so, LoneStar309 pointed out an embarassing implementation mistake which significantly weakened it (given a valid key, you could generate several other valid encodings of the same key); I patched this, as I mentioned in my update. And then teraflop demonstrated posession of a working keygen a couple hours later.
I wanted the key generator challenge to be possible, and it definitely wasn't trivial, but it was still far easier than I had hoped. Still, I couldn't be happier with the result, and I would like to thank my fellow programming.redditors for a great discussion.
For those who haven't studied how RSA works in sufficient detail to go from a factored n to a key generator, go take a moment to read up on Wikipedia. Basically the public and private keys, e and d, are multiplicative inverses mod φ(n) where φ(n) is Euler's totient function. In the case of n=pq where p and q are prime, φ(n) = (p - 1)(q - 1). So you use the extended euclidean algorithm to find e from d and φ(n). If you're using GMP (I am), you can just call mpz_invert to do that.
Once you've recovered e from d, you just RSA-encrypt the message m = 12345678 + check_mod*N where N is the key number of your choosing and 12345678 is a "nothing up my sleeve" number I chose for validating a decryption. The ciphertext is thus me (mod n), calculated using exponentiation by squaring, mod n at each step (which is what expmod does in bn.h), and then you do the reverse of decode to turn the number into a string.
The code I used for generating RSA private key pairs is rsa_genpriv.c and for generating license keys is rsa_genlic.c. These require libgmp; the job is just too big for poor little bn.h.
(All my code here is MIT-licensed, by the way, so feel free to steal it for your own purposes. By all means, use it instead of some silly easy-to-duplicate hashing scheme for your application...)
So, will RSA-based license schemes work? Not with such a short key length. Can we just make the key length longer? Well, that depends. Your ciphertext is always going to be a number between 2 and n, if n is 512 bits then so is your ciphertext. 1024 bits is probably the smallest reasonably secure size you'd want to use for RSA, which is 205 characters in the A-Y,1-9 code I'm using. So if your users are pasting keys out of an email, that's probably fine, but if they're typing it in by hand off of a CD case, forget it.
Also, this scheme, though cryptographically weak, has some points in its favor. If a theoretical cracker disassembles the code, he absolutely must understand RSA at some level, extract n, and factor it in order to create a key generator. I probably wouldn't have the patience to do it if the least bit of obfuscation were used in conjunction. It's totally self-contained (so you don't have to link in libcrypto or libopenssl or libgmp), so it's pretty much a drop-in replacement for whatever hashing scheme that most software tends to use.
And, though the backbone of the challenge was quickly broken, only one person demonstrated a keygen. I guess one is all it takes.
Can we do better? Yes, I think we can do much better. RSA's security derives from the difficulty of the integer factorization problem. There are two other commonly used classes of asymmetric key cryptosystems based on harder problems: discrete logarithm and elliptic curve discrete logarithm. Each provides more "strengh" per bit of key than the last.
james_block brings up some good points along these lines. It may not be possible to create a software license scheme with both short license codes and enough security to withstand a large, coordinated effort to break it. But it's far better to use a license key scheme that could be broken with a large effort than one that will definitely be broken with a small effort, when the former is an easy drop-in replacement for the latter. Truly uncrackable (in the cryptographic sense) security will require longer keys and users who paste keys out of emails.
So here is challenge #2. I've used another common algorithm which is no longer encumbered by a patent. The ciphertext is still slightly less than 125 bits. It is not impossible to crack by any means, but it is much harder (in terms of CPU time necessary) than the previous one. And there's always the possibility that I screwed something up and left a big back door in it, which is a good reason for proposing the challenge in the first place.
The code:
keydecode2.cpp - challenge #2 decoder
bn.h - quick and dirty bignums (updated from
last time)
I plan on issuing one further challenge next week, and there's a good chance that this one will be broken before then if it receives the same level of attention as the first one did.
Here is the reddit thread for part 2.
Update: The solution to part 2 has been posted.