3 ms·
Have you got any links or keywords I can search about MT's vulnerabilities? I wonder if those vulnerabilities are exploitable given the seeding construct they c
by bigiain 13y ago
Have you got any links or keywords I can search about MT's vulnerabilities? I wonder if those vulnerabilities are exploitable given the seeding construct they chose?
seed = SHA256(client_seed + server_seed) % 2 ^ 32
- tptacek 13y agoIt takes a tiny amount of entropy as its input and its internal state is recoverable from its outputs.
- bigiain 13y agoYeah, but it's "internal state" is already known to the attacker here. The whole point of using it is for it's deterministic output given a pre-disclosed seed. It's only using it as a way to enumerate with of 2^32 possible reshufflings we agree to do to the deck before playing - which either of us can check at the conclusion of the game since we both knew up front the initial shuffled deck hash, the two PRNG seeds, and the order the cards came out in the game.
- ryan-c 13y agoAgreed. The only way I can see for either party to cheat would be for the casino precompute a large number of shuffled decks along with the output after all 2^32 possible MT seeds and use shuffles that give the house an additional statistical edge, but I can't see this getting a large enough edge to be worth the trouble.
- bigiain 13y agoSo I went looking myself - it seems a big problem with MT is that it's "easy" to determone the seed from a sample of generated "random" numbers. I don't think that's a problem here, since the "casino" end knows the seed anyway. I _think_ to attack this you would need to do two seemingly difficult things. 1) come up with a seed which generates a sequence from the prng which allows a shuffle to create a favourable-to-you deck - this might be doable given my very quick reading of MT's weaknesses. But then you need to do 2) create a server_seed such that PRNGseed = SHA256(client_seed + server_seed) % 2 ^ 32. I suspect that's "hard". (I don't know if SHA256 is vulnerable to extension attacks the way MD5 is - I don't _thin_ so, but even if it were, some simple "plausibility checks" on the alleged server_seed would protect against that.) I guess there's a problem if the client_seed ad server_seed ever get re-used - but that's a common crypto in-use issure, right? Just don't do that...
- tptacek 13y agoWhy do you care about attacks on SHA? It's a 32 bit seed.
- bigiain 13y agoYeah - in retrospect I was confusing myself there. I still think this works though. Unless there is a way for them to chose a server_seed such that: SHA256(server_seed + client_seed) % 2 ^ 32 = PRNG_seed(favourable to them) without my choice of client_seed messing up their desired PRNG_seed.
- danielweber 13y agoTwo generation of Pokemon games were plagued by people who figured out how to reverse the random number generator, and could make the game do exactly what they want. I think it was a MT generator, but it's been a while since I played with it -- the search space was small enough that a decent desktop could search the space in less than a minute.