3 ms·

Predicting and controlling NetHack's randomness

48 points by jwilliams 18y ago

jwilliams 18y ago
As an aside, the source code for Nethack is full of some amazing tidbits - moon phase calculations, code to guess plurals....
- henning 18y ago
  If you want code to pluralize a noun, have a look at activesupport/lib/active_support/inflector.rb in the Rails source code. It might make an interesting code kata because you have to decide on a way to represent some declarative knowledge in whatever language you decide to code in, like the fact that the plural of "rice" is "rice".
  - gamache 18y ago
    But does it compile on an Amiga?
swombat 18y ago
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. Surely there's a more practical solution right here: Seed based on a variable that's a component of the actions of all the users of the server in the last 24 hours. Then, in order to correctly guess the new seed, the hacker would have to be the only person the server for the whole day. Obviously, alter "24 hours" to be whatever period is long enough to ensure that there will be more than one user on active the server during that period. That would still not make it leakproof, but would render it considerably harder to hack the PRNG. For many practical situations, making something uncrackable is not necessary. It is enough to make cracking it an insanely difficult proposition. Until we find ourselves faced with science-fiction-like super-intelligences (such as this one: http://en.wikipedia.org/wiki/A_Fire_Upon_the_Deep http://en.wikipedia.org/wiki/A_Fire_Upon_the_Deep ) willing to use infinite intellectual resources to break into the system, making something really, really hard to crack is enough.
- ido 18y ago
  You say that now, but you'll be sorry when the martian invaders cheat on the nethack public server!
- ph0rque 18y ago
  Base the randomness on the internet! That should make it hard enough to crack...
- streety 18y ago
  "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." To me the article reads as though this is more than just an issue with poor seeding. If you can figure out the initial seed by observing events then the PRNG itself needs to be replaced. The article suggests reseeding the PRNG after x random numbers have been generated and to me that sounds like a fairly good solution. It has certainly be the basis of other PRNGs: http://en.wikipedia.org/wiki/Fortuna_(PRNG) http://en.wikipedia.org/wiki/Fortuna_(PRNG)
  - swombat 18y ago
    That is only valid if the new seed is reasonably random and unguessable. Hence the idea of basing that new seed on server activity.
    - streety 18y ago
      Absolutely. However often you reseed the generator you need it to be unguessable. Server activity would be a good source of entropy with the caveat, as you point out, that you need to be sure that there is more activity on the server than just the person receiving the random number. If server activity is the only source you use though you're vulnerable to some attacks. If an attacker can force your server to reboot or can utilise all available connections, locking anyone else out, then they could control all the server activity you're relying on. The solution is simply to use multiple sources. Server activity plus any other sources of entropy you have available on the server.
lacker 18y ago
The problem with seeds based on time in seconds is you only have a few dozen possible seeds, or a few thousand if you don't know when the game started. Make the seed based on more things, like milliseconds, process id, and hostname of the computer. The second problem is you can't use just any random number generator, you need a crypto-safe one. For example, the "Mersenne Twister" random number generator used by python's random() is fast but it is not crypto-safe. If you can observe a sequence of 1000 or so random numbers, that's enough to predict all the future ones. But there are better random number generators like stream ciphers that you can use if predicting the PRNG is a problem.
blasdel 18y ago
This is a pretty epic exploit, killing yourself on DL1 by kicking Wands of Wishing is a great way to show off. I've been playing for a decade, but I only started ascending this year. Just a couple days ago I had a most pointless death -- "Killed by invisible Famine, while helpless (with the Amulet)" -- http://alt.org/nethack/userdata/blasdelf/dumplog/1235254709.nh343.txt http://alt.org/nethack/userdata/blasdelf/dumplog/1235254709.... Nethack is ultimately an object lesson in humility and patience. Past about 1000 turns, all deaths can be avoided without too much trouble, and when you die there's a sinking feeling of "this is totally my fault". You always know exactly what you did wrong, and what you should have done to avoid it. The RNG exists to reward bravery with death.

48 points by jwilliams 18y ago

As an aside, the source code for Nethack is full of some amazing tidbits - moon phase calculations, code to guess plurals....

henning 18y ago
If you want code to pluralize a noun, have a look at activesupport/lib/active_support/inflector.rb in the Rails source code. It might make an interesting code kata because you have to decide on a way to represent some declarative knowledge in whatever language you decide to code in, like the fact that the plural of "rice" is "rice".
- gamache 18y ago
  But does it compile on an Amiga?

swombat 18y ago

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. Surely there's a more practical solution right here: Seed based on a variable that's a component of the actions of all the users of the server in the last 24 hours. Then, in order to correctly guess the new seed, the hacker would have to be the only person the server for the whole day. Obviously, alter "24 hours" to be whatever period is long enough to ensure that there will be more than one user on active the server during that period. That would still not make it leakproof, but would render it considerably harder to hack the PRNG. For many practical situations, making something uncrackable is not necessary. It is enough to make cracking it an insanely difficult proposition. Until we find ourselves faced with science-fiction-like super-intelligences (such as this one: http://en.wikipedia.org/wiki/A_Fire_Upon_the_Deep http://en.wikipedia.org/wiki/A_Fire_Upon_the_Deep ) willing to use infinite intellectual resources to break into the system, making something really, really hard to crack is enough.

ido 18y ago
You say that now, but you'll be sorry when the martian invaders cheat on the nethack public server!
ph0rque 18y ago
Base the randomness on the internet! That should make it hard enough to crack...
streety 18y ago
"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." To me the article reads as though this is more than just an issue with poor seeding. If you can figure out the initial seed by observing events then the PRNG itself needs to be replaced. The article suggests reseeding the PRNG after x random numbers have been generated and to me that sounds like a fairly good solution. It has certainly be the basis of other PRNGs: http://en.wikipedia.org/wiki/Fortuna_(PRNG) http://en.wikipedia.org/wiki/Fortuna_(PRNG)
- swombat 18y ago
  That is only valid if the new seed is reasonably random and unguessable. Hence the idea of basing that new seed on server activity.
  - streety 18y ago
    Absolutely. However often you reseed the generator you need it to be unguessable. Server activity would be a good source of entropy with the caveat, as you point out, that you need to be sure that there is more activity on the server than just the person receiving the random number. If server activity is the only source you use though you're vulnerable to some attacks. If an attacker can force your server to reboot or can utilise all available connections, locking anyone else out, then they could control all the server activity you're relying on. The solution is simply to use multiple sources. Server activity plus any other sources of entropy you have available on the server.

lacker 18y ago

The problem with seeds based on time in seconds is you only have a few dozen possible seeds, or a few thousand if you don't know when the game started. Make the seed based on more things, like milliseconds, process id, and hostname of the computer. The second problem is you can't use just any random number generator, you need a crypto-safe one. For example, the "Mersenne Twister" random number generator used by python's random() is fast but it is not crypto-safe. If you can observe a sequence of 1000 or so random numbers, that's enough to predict all the future ones. But there are better random number generators like stream ciphers that you can use if predicting the PRNG is a problem.

blasdel 18y ago

This is a pretty epic exploit, killing yourself on DL1 by kicking Wands of Wishing is a great way to show off. I've been playing for a decade, but I only started ascending this year. Just a couple days ago I had a most pointless death -- "Killed by invisible Famine, while helpless (with the Amulet)" -- http://alt.org/nethack/userdata/blasdelf/dumplog/1235254709.nh343.txt http://alt.org/nethack/userdata/blasdelf/dumplog/1235254709.... Nethack is ultimately an object lesson in humility and patience. Past about 1000 turns, all deaths can be avoided without too much trouble, and when you die there's a sinking feeling of "this is totally my fault". You always know exactly what you did wrong, and what you should have done to avoid it. The RNG exists to reward bravery with death.