Predicting and controlling NetHack's randomness (2009)

http://taeb-nethack.blogspot.com/2009/03/predicting-and-controlling-nethacks.html

by epsylon • 11 years ago

22 10 11 years ago

taeb-nethack.blogspot.com

dahart• 11 years ago

This bit is clever:

"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."

Reminds me of the oracle exploits the Matasano crypto challenge taught. I'm sure this is a very common type of tactic, I just haven't spent much time practicing exploits, despite my interest.

But correct me if I'm wrong, I would guess that with many attempts, possibly a binary search of time offsets, one can get sub-second timing resolution in the clock skew exploit above, no?

quarktasche• 11 years ago

If you like this kind of thing go read this write-up of predicting hands in online poker due to bad implementations of shuffling and PRNG algorithms! Its quite a fun read.

https://www.cigital.com/papers/download/developer_gambling.p...

tptacek4• 11 years 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.

I'm confused. Why can't they just read from /dev/urandom for all their random numbers?

vinceguidry• 11 years ago

I imagine that would make the server pretty slow in times of heavy load.

tptacek4• 11 years ago

I doubt it. Things exercised far more strenuously than nethack rely on urandom.

wolf550e• 11 years ago

You can use 24 bytes of "true" randomness (16 for key and 8 for nonce) and then get 2^64 16-byte blocks of randomness before re-keying at better than 1Gbps per core using AESNI. How much more do you need?

EDIT: How is what I wrote wrong?

wtbob2• 11 years ago

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.

No, no, no. This is a horrible misconception.

It's easy to generate an effectively infinite stream of random numbers: use a block cipher in CTR mode (i.e., using the seed as the key, encrypt 0, then 1, then 2, then 3 and so on). All you need for this is a single truly-random seed, and from it you'll get 2^128 random numbers—far more than you will ever, ever need.

Now, how do you get that initial random seed? That's where the art comes in, but a basic version would simply hash all those truly-random input events (e.g. those temperature changes or internal timing variations) together. A more complex system, such as Schneier and Ferguson's superb Fortuna, uses a system of 32 pools, where the pools are used to periodically reseed the generator, in a clever fashion which can protect even against generator-state compromise.

And with modern chips, AES-256 in CTR mode is fast, really fast. Fortuna'd be perfectly usable in Nethack.

(As an aside, it'd also be perfectly usable as a replacement for the needlessly-complicated and insufficiently-grounded Linux CSPRNG underlying /dev/random and /dev/urandom).

tptacek4• 11 years ago

For a game, fine, donk around with your own CSPRNG implementation; for real-world apps, please just use /dev/urandom.

The overwhelming majority of RNG disasters in the past decade have come from userland CSPRNGs written by people who were wary of urandom.

wtbob2• 11 years ago

For a game, fine, donk around with your own CSPRNG implementation; for real-world apps, please just use /dev/urandom.

Sure. I just wish that /dev/urandom were well-thought-out rather than accidentally probably-good-enough.

Predicting and controlling NetHack's randomness (2009)

Related Stories