Ideas for designing a Secure, "Low Cost" method for confirming client-side game results

views:

102

answers:

+3 Q:

Ideas for designing a Secure, "Low Cost" method for confirming client-side game results

+3 A:

If the client code calculates the next piece and you can't hide this algorithm very well, then some bored college student will figure this out. As a result, they will be able to generate a massive score and defeat your intentions.

KM 2009-05-26 21:14:38

My thoughts exactly. They'll just make a program that "plays" the board with many different scenarios, and then submit the one producing the highest score.

Lasse V. Karlsen 2009-05-26 21:19:53

Worse than knowing what pieces are coming up, and planning accordingly, since the next piece is a function of time between moves, they can actually choose each piece that they get.

erickson 2009-05-26 21:57:52

So, maybe I'm not being clear. The idea is that the client calculates the next pieces based on the initial seed provided by the server. The server is confirming that the client acted in good faith based on what it posts back.Also, hiding the algorithm is not the point. You seem to be advocating security through obscurity, unless I miss understand.@Lasse: The search space on that is... considerable I think. X moves * N milliseconds per search-tree level where X is one the order of 10 and N is on the order of 10,000.

Kevin Montrose 2009-05-26 22:01:41

@Kevin Montrose, if the server only validates that the returned string contains a valid "game", a person only has to generate a good string of valid moves (generated with their own program) and they will get a great score. If they take your server based seed and can generate the board and next pieces from it they can manipulate the process in any way they want.

KM 2009-05-27 18:50:51

I tend to say that it is impossible to do. Why? You cannot trust the client - I could just analyse and completly rewrite the client side code and return whatever values I like. The only way to protect you from cheating and all kinds of attacks is to perform the logic at the server - the client will just collect user input and display the server output. But this is completly against your design goal to minimize the number of server calls.

Daniel Brückner 2009-05-26 21:20:08

You are correct in that the client can always return whatever it wants, but I think its possible to design a system that enforcing meaningful constraints on what the client can get the server to accept.

Kevin Montrose 2009-05-26 22:22:25

I think only in a very limited way. A simple model: The server sends initialization values fixing the initial layout and the sequence of pieces. The client returns a sequence of moves. Now you can validate that the sequence of moves is valid for the send initial values. But you have no control about what the client did with the initial values. I could take them and perform a search accross all possible moves to find the one with the highest score. Then I just send the best sequence with random but plausible timing values back and get my score.

Daniel Brückner 2009-05-26 22:43:35

Everything besides this simple model - send initial values and get list of moves back - will make it harder to cheat but nothing more. So you can hash the state, mix it with timing information, or whatever, but this will add no security at all - just take a bit longer to unterstand what's going on.

Daniel Brückner 2009-05-26 22:47:54

Part of the idea is to role your timing values back into the RNG, which makes the search space much larger. I freely admit that given sufficient time anything like this can be broken (in this case, best moves chosen dishonestly), but if the time required is large enough I don't think its an issue.

Kevin Montrose 2009-05-26 22:50:15

Feeding the timing back will not increase the search space - it will just change the sequence of pieces. (It becomes obviouse if you imagine that you fix the times for every move - for example one every second - before you start to play. The same applies to feeding back the last move - it will change the sequence of pieces but only in different subspaces.)

Daniel Brückner 2009-05-26 23:25:31

Then you're not guaranteed ideal, if you fix the time interval, as it discards a large number of valid potential game "boards". I'm beginning to think that the attack is going to be roughly equal in complexity to building a program that plays for you, using alpha-beta pruning on unknowns. Which would be acceptable.

Kevin Montrose 2009-05-26 23:28:37

You are right, fixing the times will discard a lot of the search space - I missed this point. But you could still perform a randomized search on this huge search space and perform much better than a human. Using A* search might be a good way to explore the search space.

Daniel Brückner 2009-05-26 23:40:32

Eh, most (possibly all) of the great search algorithms rely on heuristic estimates of distance-to-goal. Having neither the goal nor a reliable heuristic would make this problem trickier than you're making it out to be I suspect.Regardless, can you think of an improvement to the approach that still minimizes callbacks?

Kevin Montrose 2009-05-27 00:34:14

I think you already got the best possible approach. It's indeed much better then I thought when I first read the question. When you got it working, I would like to try cheating...

Daniel Brückner 2009-05-27 15:26:09

ansaurus

tags:

views:

answers:

Ideas for designing a Secure, "Low Cost" method for confirming client-side game results

related questions