Predicting and controlling NetHack's randomness

NetHack, being a single-player game of imperfect knowledge, incorporates a large element of randomness. Random numbers control how much damage that minotaur will deal you, what the identity of each purple-red potion is, whether dipping into that fountain will net you a wish, etc. To generate random numbers, NetHack employs a pseudorandom number generator. Wikipedia says:

A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's [seed].

Because NetHack uses a PRNG, providing identical input to two separate games, sharing the same seed and PRNG algorithm, will lead to the same results in each game. This should not be surprising as this is a property fundamental to PRNGs. The input must be identical for both games, otherwise the games will diverge; on the same turn, casting a spell in game A will do a different amount of damage than simple melee in game B. Since the two actions use a different amount of random numbers, it would be annoying (but not difficult) to reconcile the two games.

NetHack uses the current time (specifically the number of seconds since midnight, January 1st, 1970) as the seed for its PRNG. Thus, two games started in the same second will have the same seed. You can verify this by typing "nethack" into two separate terminals, then quickly hitting enter in each. Once you select the same characters, you should be greeted with the same map and stats. If not, your clock may have ticked between starting the two games, so just try again. If you play both games identically you'll see that you obtain the same results in both games. You can, of course, diverge once you experience very unfavorable results in one game, such as death.

That's a lot of work just to fool the game. If you're going to those lengths, you're better off playing in the immortal "explore mode", or changing the code so that it's easier to win. These are some of the reasons that "public server ascensions" are more highly valued than local ascensions. You can't change the code on the server, or play in god mode, so everyone knows that your server ascensions are legitimate.

However, public NetHack servers still use PRNGs, so there still exist some serious exploit vectors. On the nethack.alt.org public server, I abused the PRNG for demonstrative purposes (though never for actual ascensions). On the WowDeath account, I killed myself by kicking wands of wishing on the first level — three times in one day.

Though NetHack uses the current time for its seed, it's very easy to change that to be, say, an option to NetHack. You can tell NetHack to start a game in advance, fooling it into thinking it's 11:00:00. If that game doesn't work out so well (perhaps you got a lame starting inventory), you can try again, using a seed 11:00:01. Repeat until you find a great starting haul, then start a game on the server at that exact time. I went one step further, generating thousands of starting levels until a wand of wishing was created as part of the initial level. paxed, one of the admins of nethack.alt.org, patched nethack to use a truly random seed so that this specific exploit can no longer be used on that server.

The trickiest part, which was the only point of failure, was in starting a game on the server at some exact second. Due to clock skew, the server could think it is several seconds (or even minutes) earlier or later than your clock does. The server doesn't broadcast what it thinks the current time is, either. One way to actually figure out the current time is through the random seed! Start a game on the server, noting the current time on your clock. Then generate NetHack games for that time, that time plus a second, that time minus a second, plus two seconds, and so on until you get the same starting map and stats. The offset you used is the number seconds between your machine and the server, so you can use it to know exactly when to start a server game. It's still not as exact as I would like, since you only get resolution of a second.

That method actually describes a distinct avenue of exploitation. Since you now have a server game and a local game with the same seed, you can play the local game (remembering to mirror the input to the server game as well) until you get to some point at which you want to diverge. It's actually more powerful than even that, because you can modify your local nethack to display object identities instead of appearances, or not require exploration for the map. You will appear to have x-ray vision or prescience to the audience of your server game.

This was actually how I was introduced to practical methods of exploiting nethack's PRNG. A nethacker named switch told me to start up a game and wait. He then said "See that gold in the upper right corner of the room? It has 70 gold pieces in it." That was viciously consternating. What he had done is what I described in the previous paragraph. He found my game's seed then looked at the pile of gold before I did: prescience.

nethack.alt.org has patched the initial seed calculation, but as nethacker Adeon has demonstrated, it's still feasible to figure out the game's seed by observing random effects. Being able to observe random effects without advancing the game's state is very helpful in sussing out the game's seed, since monsters moving, level messages, and many more per-turn effects use an unknowable amount of random numbers. By using something similar to the artifact naming exploit, you can observe the effects of a knowable amount of random numbers. Adeon has code that will do exactly this for server games. Once you have the seed, you're in control of the random number generator. You can trash as many random numbers as you want by using the same actions you used to figure out the seed. This will let you make every fountain quaff produce a wish by throwing out every random number that wouldn't produce a wish.

The fix for this would be to re-seed the PRNG every n (say, 100) random numbers. That way, well before you have a chance figure out the current seed, a new one takes its place. Re-seeding must use true random numbers. If not, the re-seeding is useless; pseudorandom seeds fall victim to the same exploits. [Update March 3rd: paxed has patched this fix into nethack.alt.org as well]

You might wonder why we use PRNGs at all; why not use a truly random source for every number? Unfortunately, a computer's pool of truly random numbers is very limited; it has to build up by measuring minute temperature changes or internal timing variations. NetHack, especially being played by fifty people on a public server, would keep that pool empty and harm the game's playability.

This type of exploit could affect many single-player games like NetHack, but I don't think there would be value in doing this for other games, since one of the preconditions is that server play is more highly valued than local play. Commercial games use closed-source servers anyway. The real applicability of these techniques is in cryptanalysis. Use truly random numbers for your keys!