3 ms·
Does it need to be for this use-case? As a way of "cutting the deck" that results in an unfeasably-computationally-large variation on the "ordinary" card deck c
by bigiain 13y ago
Does it need to be for this use-case? As a way of "cutting the deck" that results in an unfeasably-computationally-large variation on the "ordinary" card deck cut (which has only 52 possible changes to the allegedly shuffled deck) - doesn't it satisfy that goal?
- tptacek 13y agoI read the article closely enough to come to believe they could have used a CSPRNG but opted instead to use MT19937, considered that the title indicated that the approach was an application of cryptography, and decided to keep my response simple. MT is really, really bad. We don't see it too much in the real world, but it's so easy to attack that we have several attacks on it in our crypto challenges.
- bigiain 13y agoHave 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.
- tlrobinson 13y agoI'm also unsure whether their usage of MT is actually a problem. The small seed size is what seems like a problem to me. They note they're actually reshuffling, not just cutting the deck, but even then there are only 2^32 possible seeds and thus 2^32 possible reshuffles. What's stopping them from pregenerating server seeds that are biased in their favor? Maybe using MT makes that even easier.
- bigiain 13y agoI don't think that works - they have to tell me their server_seed before I tell them my client_seed. That makes the PRNG seed dependent on the SHA256 hash of something out of their control.
- sirclueless 13y agoI think tlrobinson means seed decks, not server_seeds as used in the generation of the MT seed.