a1k0n

I can't believe I won.

I can't believe I won decisively at all.

I've never won any programming contest before (although I did place in 3rd in the Mario AI contest but there were only about 10 entrants). Whenever I badly lose at an ICFP contest I'm always anxious to see the post mortems of the people who did better than I did, and I imagine a lot of people are curious as to how I won, exactly. So here's my post-mortem.

Code

Before we get into it, note that all of my code is on github here. The commit logs might be a mildly entertaining read.

Phase 1: denial

The first thing I did was attempt to ignore this contest as long as possible, because month-long programming contests get me into a lot of trouble at work and at home. The contest was the Tron light cycle game. I've played variants of this game ever since I got one of these when I was in 1st grade or so. The most fun variant was my uncle's copy of Snafu for the Intellivision which we played at my Grandma's house all day long. I've long wondered how to write a bot for it, because the AI on these usually isn't very smart.

Phase 2: space-filling

But I finally gave in on the 9th, downloaded a starter pack, and attempted to make a simple semi-decent wall-hugging bot. I quickly discovered a simple useful heuristic: the best rule for efficiently filling space is to always choose the move that removes the least number of edges from the graph. In other words, go towards the space with the most walls for neighbors. But! Avoid cut vertices (AKA articulation points), and if you have to enter a cut vertex, then always choose the largest space left over. At this stage I wasn't actually calculating articulation points; I just checked the 3x3 neighborhood of the square and made a lookup table of neighbor configurations that might be articulation points based on the 3x3 neighborhood. This is what the potential_articulation function does in my code, and artictbl.h is the lookup table.

I was, however, computing the connected components of the map. This is a simple two-pass O(NM) algorithm for N squares in the map and M different components. For each non-wall square in the map, traversed in raster order, merge it with the component above it (if there is no wall above) and do the same to its left (if there is no wall to the left). If it connects two components, renumber based on the lowest index, maintaining an equivalence lookup table on the side (equivalence lookups are O(M) but really just linear scans of a tiny vector). Then scan again and fixup the equivalences. This is what the Components structure is for; it has this algorithm and simple sometimes-O(1), sometimes-O(NM) update functions based on potential_articulation above.

Phase 3: minimax

I left it at that for the rest of the week and then Friday the 12th I was inspired by various posts on the official contest forum to implement minimax with alpha-beta pruning, which would let it look several moves ahead before deciding what to do. The problem with this approach is that you have to have some way of estimating who is going to win and by how much, given any possible configuration of walls and players. If the players are separated by a wall, then the one with the most open squares, for the most part, wins. If they aren't separated, then we need to somehow guess who will be able to wall in whom into a smaller space. To do that, I did what everyone else in the contest who had read the forums was doing at this point: I used the so-called Voronoi heuristic.

The "Voronoi heuristic" works like this: for each spot on the map, find whether player 1 can reach it before player 2 does or vice versa. This creates a Voronoi diagram with just two points which sort of winds around all the obstacles. The best way to explain it is to show what it looks like during a game:

The light red area are all squares the red player can reach before the blue player can. Similarly for the light blue squares. If they're white, they're equidistant. The heuristic value I used initially, and many other contestants used, was to add up the number of squares on each side and subtract.

Once the red player cuts the blue one off, they are no longer in the same connected component and then gameplay evaluation switches to "endgame" or "survival" mode, where you just try to outlast your opponent. After this point, the minimax value was 1000*(size of player 1's connected component - size of player 2's connected component). The factor of 1000 was just to reward certainty in an endgame vs. heuristic positional value. Note that this was only used to predict an endgame situation. After the bot actually reached the endgame, it simply used the greedy wall-following heuristic described above, and it performed admirably for doing no searching at all.

evaluation heuristic tweaking

I next noticed that my bot would make some fairly random moves in the early game, effectively cluttering its own space. So I took a cue from my flood filling heuristic and added a territory bonus for the number of open neighbors each square in the territory had (effectively counting each "edge" twice). This led to automatic wall-hugging behavior when all else was equal.

After fixing a lot of bugs, and finally realizing that when time runs out on a minimax search, you have to throw away the ply you're in the middle of searching and use the best move from the previous ply, I had an extremely average bot. Due to the arbitrariness of the ranking up until the last week in the contest, it briefly hit the #1 spot and then settled to a random spot on the first page. It was pretty hard to tell whether it was any good, but I was losing some games, so I figured it must not be.

endgame tweaking

The next realization was that my bot was doing a lot of stupid things in the endgame. So the next improvement was to do an iteratively-deepened search in the endgame. I exhaustively tried all possible moves, and at the bottom of the search tree, ran my greedy heuristic to completion. Whichever move sequence "primed" the greedy evaluator the best wins. This works great on the smallish official contest maps. It works terribly on very large random maps currently in rotation on dhartmei's server, but I didn't realize that until after the contest.

data mining

I was out of ideas for a while and spent some time optimizing (I used Dijkstra's to do the Voronoi computation and I sped it up by using what I call a radix priority queue which is just a vector of stacks... see dijkstra). But it had been bothering me that my edge count/node count Voronoi heuristic was pretty arbitrary, and wondered if I could do any kind of inference to discover better ones.

Well, hundreds of thousands of games had been played on the contest server by this point, and they are extremely easy to download (the contest site's game viewer does an AJAX request to get some simple-to-parse data for the game), so I figured I'd try to do some data mining. I wrote a quick perl hack to grab games from the site and output them in a format that Tron bots recognize. Then I copied-and-pasted my code wholesale into examine.cc and marked it up so it would read in a game back-to-front, find the point at which the players enter separate components, guess what the optimal number of moves they could have made from that point forward, and then use the existing territory evaluation code on every turn before that and dump out some statistics. The goal was to discover a model that would predict, given these territory statistics, what the difference in squares will eventually be in the endgame.

I started with an extremely simple linear model (and never really changed it afterwards): the predicted difference in endgame moves is K₁ (N₁ - N₂) + K₂ (E₁ - E₂) where N_i is the number of nodes in player i's territory and E_i is the number of edges (double-counted actually).

Now, this model is pretty far from absolutely great, and only a little predictive. This is what the raw data looks like after analyzing 11691 of the games the top-100 players (at the time) had played:

That's the difference of nodes/edges on the x-axis and the difference of endgame moves on the y-axis. So both nodes and edges by the Voronoi metric are, of course, correlated. I did a linear regression to find approximate values for K₁ (currently 0.055) and K₂ (0.194) and multiplied through by 1000 to keep everything integers.

This definitely improved play in my own testing (I kept 14 different versions of my bot throughout the contest so I could compare them. Interestingly, no bot ever totally shut out a previous bot on all maps in my tests; every bot has a weakness). Once I had that, I was doing very well in the leaderboard rankings.

applied graph theory

Next I noticed dmj's "mostly useless" idea on the official contest forums: Pretend the game is played on a checkerboard. Each player can only move from red to black and vice versa. Therefore, if a given space has a lot more "red" squares than "black" squares, the surplus "red" squares will necessarily be wasted. I switched out all my space counting code to count up red and black spaces, and found a tighter upper bound on the amount of space an ideal bot could fill. This let my endgame code stop searching when it had found a solution matching the upper bound, and gave slightly more realistic territory evaluations.

I had already started to think about what came to be called "chamber trees", as pointed out by iouri in the same thread: find all the articulation points on the map and construct a graph of connected spaces. I implemented the standard O(N) algorithm for finding articulation points (calc_articulations, taken from this presentation [pdf]). I messed around with this idea but nothing came to fruition until just before the deadline.

At around this point, I got extremely sick and spent all day Wednesday in bed. That day, dhartmei's server showed up, which was a huge blessing. I ran my bot on there in the background all Thursday long, and it did very well on there too, which was a very reassuring thing. But it was still losing a lot of games.

So finally, after failing to get to sleep Thursday night thanks to coughing and being unable to breathe through my nose, I was struck by an idea at around 3am. This, it turns out, was probably the contest-winning idea, though I'm not so sure that nobody else implemented it. Anyway, take a look at this game (a1k0n_ v. ecv257):

(The little circles are the articulation points found by the algorithm above.) By the so-called Voronoi heuristic, blue has a lot more space than red does. But red is ultimately going to win this game, because the only space that blue controls that matters here is the space that borders red. Blue can choose to cut off that space and fill in the two chambers on the right, or it can choose to move into the left chamber and take its claim on what I call the "battlefront": the border between blue space and red space.

I had long ago come to the realization that a better evaluation heuristic will always beat deeper minimax searches, because a deep minimax search using a flawed evaluation heuristic is self-deluded about what its opponent is actually going to do, and will occasionally favor moves that lose to moves that win, simply because it can't tell the difference. Anything you can do to make your evaluation function smarter will result in improved play in the long run.

In this case, I decided to make my evaluation function aware of the above condition: if the player is not in the chamber containing the "battlefront", then make the choice I outlined above. More formally, the new heuristic value is the same as the old one, but N_i and E_i are counted differently. First, find all cut vertices assuming the opponent's territory by the Voronoi metric is disconnected. Start a depth-first search in the player's "chamber", count N_i and E_i within the chamber, and list all the neighboring cut vertices but do not traverse them (_explore_space). Now, explore space recursively for each adjacent cut vertex. If child j's space is not a battlefront, then our potential value is the sum of the current chamber size and child j's value. Otherwise, it is a bottlefront, and we ignore the current chamber's size but add only the number of steps it takes to enter the child chamber (I don't have a good formal reason for this, it just seemed intuitively right). After computing this potential value for each child, we return the maximum of them as the current chamber's value.

Therefore the new code will handle the mutual exclusion of battlefront chambers and other chambers, and force it to choose to either ignore the upper left chamber or ignore the two chambers on the right.

The idea was extremely roughly-formed when I implemented it (see max_articulated_space), but it did improve play markedly after throwing it together (again, it didn't shut out the previous version of my bot totally but it won 12-1 IIRC).

I also had the idea of negatively counting the space we ignore on a battlefront, as we are effectively handing that space to our opponent. Never got a chance to try it, though. Might be a nice improvement.

So that was it. I submitted that Friday around noon, and was subsequently afraid to touch it. (My wife and son and I left for Wisconsin Dells right afterwards, where I couldn't help but check rankings on my cellphone and keep up on the forums the whole time, which didn't go over well) The bot is still running on dhartmei's server, and still loses many games as a result of miscounting the opponent's space in the endgame, since my endgame evaluation wasn't very good. But it was good enough for the contest.

I got a BlackBerry 8350i from ebay to use with a Boost Mobile prepaid plan. Boost (as prepaid plans are in general) is much, much cheaper than the alternatives when you don't talk on the phone a lot. And (slow) unlimited wireless internet is only 35 cents a day which works out to a little over $10/month.

But anyway, my used BlackBerry turned out to have a broken USB port. It was mounted entirely with cold solder joints and fell right off like it wasn't even soldered on when I first tried to charge it up.

Most people would avail themselves of the return policy, but I'm not most people.

I needed to get updated firmware to get SMS and GPS to work, so I soldered some wires on, clipped them to a USB cable, and that worked flawlessly, to my surprise.

That let me charge it up, too. So then I had a phone with a full charge, upgraded firmware, working everything, except it does me no good just sitting on my desk tethered to a bunch of flimsy wires. I clipped off all the wires and ordered a replacement USB port as well as a cradle charger, and all was well until the battery died. Which it pretty much did the next day.

So last night I came up with this:







Two nails driven through a block of wood connected to USB +5V and ground. Works like a charm.

Because I am lazy and easily sidetracked, the promised update to the "Hacker challenge" (part 1, part 2) is now over seven months late. So I might as well post the solution to part 2, which was solved by three individuals on reddit (bobdole, c0dep0et, and xahtep).

Part 2 used DSA, which was fairly obvious; as before I made no effort to hide it. Instead of decrypting to a particular value, it verifies a message signature hash of 12345678 with various "random per-message values" or nonces.

The parameters for the algorithm were encoded in 32-bit chunks. The nice thing about DSA is that you can use huge p and y values (see Wikipedia for the terminology) without making the license key any bigger; unfortunately that doesn't buy you a lot, because the underlying group order is only q, so that's how big the search space theoretically is -- it doesn't increase security, it just makes it marginally slower to factor.

So I chose p, y, and g to be on the order of 384 bits, but q and x are only on the order of 64 bits. In fact p is just a 64-bit number shifted left 320 bits and then incremented.

The security of DSA derives from the difficulty of determining x from y = g^x mod p, which is known as the discrete logarithm problem, which is harder than factoring primes.

So after you reconstruct the parameters from the hexadecimal encoding you find:

p = 12026070341127085754893097835098576041235013569186796331
441953314639277634647572425804266039236571162321832835547137
g = 54659936461116297034410364232325768273521088000551606899
39983550682370032756410525809260221877924847568552733696072
y = 27434965696578515868290246727046666462183462061939529180
41150093730722092239431092724025892380242699544101134561292


You can plug these numbers into a discrete log solver and find x (it will also deduce q as the subgroup size after a few seconds). This takes about three hours on my MacBook Pro, IIRC.

Once you have x the challenge collapses into reimplementing DSA (with a small twist: s is inverted in the generator, not in the validator; I can't see any reason this would affect security and it makes the validator simpler):

let H = 12345678 (the supposed message hash)

choose a nonce k

compute r = (g^k mod p) mod q

compute k^-1 (mod q) using the modular multiplicative inverse (mpz_invert with GMP)

compute s = (k^-1(H + x r)) mod q

let w = s^-1 (mod q)

combine (r,w) into K = r q + w

convert K into a base32-ish key string

I think this scheme is actually pretty good, as it's non-trivial to solve, but it's still crackable with the newest discrete log solver methods. It did confound some dedicated redditors for a couple days, at least, with all the details laid bare.

The obvious next step is to move on to elliptic curve cryptography, and that is the reason this post is so late. When I started writing the first hacker challenge I was completely ignorant of ECC. Immediately after writing the previous post, I bought a book on the subject, and while I understand the basics now I still don't understand it well enough to write a toy implementation suitable for a "Hacker Challenge". So I will leave that for another day, or perhaps for another person.

Source code for the DSA private key generator and license generator:

keydecode2.cpp - the challenge code from the last post (for reference)

bn.h - quick and dirty bignum template

dl_genpriv.c - discrete log private/public key pair generator

dsa_genlic.c - license generator (key parameters hardcoded)

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 m^e (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.

I like to reverse-engineer things, and I like number theory. These hobbies happen to intersect in the art of reverse-engineering software license keys.

I won't lie: I've cracked programs. I've created key generators for programs. But I also never distribute them. I do it for the challenge, not for the program.

But from a warez d00d perspective, it is infinitely preferable if you can create a key generator instead of cracking, because then you can typically get further software updates, and things are just easier for everyone.

It is sometimes shockingly easy to create a key generator. Often a program that checks a license key is structured like this:

  licensestr = get_license_key_modal_dialog()
  validlicensestr = make_valid_license(licensestr);
  if(licensestr == validlicensestr) { ... }

So now all I have to do is extract your make_valid_license code, feed it random garbage, and I have a key generator for your program. One time I just replaced the call to strcmp() with puts() in a program and turned it into its own key generator.

Other key generators cycle through a hash of some sort (the hash is sometimes srand() / rand()) and ensure some check digits, or whatever. Any way you slice it, it's security through obscurity: you're giving the end user the code, and if end user can read and understand that code, they can break it.

It doesn't have to be this way. I have created a self-contained license key decoder, and I'm distributing the source code to it. In my next post, I will reveal all the details and how to create keys for it. For now, I want to see whether anyone can break it without having the "official" key generator. If so, there's a flaw in my reasoning. It uses a well-known, public-domain algorithm; that's all I'm going to say for now.

The code is here:

keydecode.cpp - key decoder

bn.h - quick and dirty bignums

(The web host I'm using has the wrong MIME types on .cpp and .h, so they're .txts - sorry)

I would like to open up a discussion on reddit. Undoubtedly many people there will recognize the algorithm and maybe poke holes in what I'm doing.

Update: "maybe poke holes in what I'm doing". Ha. More like drive a cement mixer through it in minutes. I was pleasantly surprised to find that this reached #1 on the programming subreddit. LoneStar309 found a gaping hole which I patched, and tharkban also found a bug in the final if statement, also fixed. It's fair game to make keys that way for the challenge I proposed, I suppose, but I wanted to see whether the idea would work, not necessarily my poor implementation of it. Turns out: no, it won't, and unsurprisingly it's been done before. Part 2 coming later.

Update 2: Hacker challenge part 2 has been posted.