After a bit of tinkering, I think I've found a RNG appropriate for use in Crawl. It's a combination of David Jone's JKISS generator with an alternating-step generator (Alternating-Step KISS? Ha!). This generator passes the entire TestU01's BigCrush test battery, while Mersenne Twister fails two linear complexity tests in this battery. I believe that the period of the generator is approximately 2^160. its state is 160-bits. MT's state is approximately 2.5 kilobytes. This should significantly speedup calls to push and pop the generator state.
The cryptographic complexity of attacking the alternating-step generator should be about 2^32, hardly enough to be considered secure. Since the generator output is being combined with an independent RNG with a period of 2^32, it should be infeasible to mount an attack in the context of Crawl (I suspect that the cryptographic complexity is somewhere between 2^32 < n < 2^64...). In contrast, it's possible to learn the state of Mersenne's Twister after observing 624 outputs. I'd love to chat with the player who previously managed to decode the RNG state. In some unscientific benchmarks, its operating speed is 15% worse than Mersenne's Twister (producing 100m 32-bit values took 2.01s using MT, and 2.34s using my generator). It will be significantly faster than our current hardened generator which concatenates eight MT calls before running them through SHA-256. Generator Details: https://gist.github.com/904238 The Alternating Step Generator is built from a 32-bit Galois linear feedback shift register (taps 32,22,2,1), a 32-bit Xorshift generator, and a 64-bit Multiply-with-carry generator (MWC). At each step, the LFSR output is used to advance either the Xorshift generator or the MWC generator. A 32-bit linear-congruential generator (LCG) is advanced at every step. The generator output is formed by adding the states from the LCG, Xorshift and MWC. Since the LFSR can never be set to a zero state, there is a tiny bias toward stepping the MWC generator. In practice, I have no reason to believe that this will have any effect. We should be able to change the particular subgenerators if we see fit. Here are the results from TestU01's BigCrush: https://gist.github.com/904257 Brendan ------------------------------------------------------------------------------ Xperia(TM) PLAY It's a major breakthrough. An authentic gaming smartphone on the nation's most reliable network. And it wants your games. http://p.sf.net/sfu/verizon-sfdev _______________________________________________ Crawl-ref-discuss mailing list Crawl-ref-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/crawl-ref-discuss
