I’m struggling to see how this works. (Not the sharpest tool in the shed, me).
Cas 
Sorry. I didn’t go into a lot of depth. Let me try again.
1: Inga’s computer makes a list like so.
641253
It is a random ordered list of the possible values for the die she is supposed to roll.
2: She encrypts the list using a key she randomly generates. It is a one-time-use key. After she uses it for encrypting this one die roll, she’ll throw it away and generate a new one the next time she needs to roll.
key: 5791233243234
encrypted list: 114143
3: She sends only the encrypted list to Hans. She keeps the key on her machine.
4: Hans picks a number from 1-6. He sends that number over to Inga.
5: The die roll is now settled. Inga reveals the key to Hans. His PC decrypts the list and confirms that every number that was supposed to be on the die is in the list and appears only once (i.e. she couldn’t just generate a list of all 6’s). Her machine can independently figure out what he rolled just by looking up the value from the list using his choice.
In order to know what the die roll result was, Hans and Inga pick the nth element out of the list Inga generated, where n is the number Hans picked. So, for example, if Hans picks ‘3’, then when the list is revealed to him he sees that the third element in the list was ‘1’ so that’s the result of the die roll. Inga can’t influence which one he picks and he can’t influence what will appear where he picks. And it’s in the best interests of each side to be as random as possible in the generation of the list and the picking. If either side can predict what the other side does then he/she can take advantage of the bias.
Essentially it’s the same thing as a fair coin flip. I’m allowed to flip, but you are allowed to choose heads or tails. Neither of us can cheat the other unless I can change the coins position after you pick. The encrypted list that Hans keeps in this case ensures that Inga can’t change the list ex post facto.
The algorithm works for any size die and even for a coin toss (because a coin is effectively a two sided die). You could even roll multiple dice at once using a single encryption key with Hans making multiple choices (i.e. Inga sends 523164 231564 425631 (encrypted of course) and Hans picks the fourth element from the first group, the second from the second, and the first from the third group before Inga reveals her key). When rolling multiple dice that will result in less key generation, less network traffic, and faster encryption/decryption.
(I hope I can explain this clearly.)
What if:
[]Inga makes a list (or maybe already has one previously calculated)
[]“Encrypts” the list
[]Passes the encrypted form to Hans.
[]Hans picks a number and passes that choice back to Inga…
Now if Inga is very familiar with the encrypted list and the results of the many possible keys. She could keep a list of which keys decrypt to which result sequence. Once she know’s Hans’ choice she could go trough all the possible results and pass the “key” back to Hans that will give her a roll that she wants.
Now you could solve this by letting Hans require that his own key be put in the list as part of the encrypted process so that it will be present in the decrypted form to verify that the list isn’t stale. Now Inga could still brute force an attack on the encrypted list to influence the result but she would need a whole lot of CPU power.
You can complicate the procedure all you want but all you’re really doing is making it computationally undesirable to cheat. And that is the best you can do when you don’t control the system from start to finish.
Also, JohnMunsch, please avoid religious swearing, the content of your post is enough to get people’s attention without offending them.
Ok, it wasn’t that I misunderstood the process, but the application. The way I see it is in terms of computation cycles, bandwidth, latency, and communications.
‘A’ creates a list of ‘n’ numbers. (‘n’ operations)
‘A’ encrypts the list with a key. (‘n’ operations)
‘A’ sends encrypted list to ‘B’ (1 operation + ‘n’ bandwidth + latency)
‘B’ picks a random index from the list (1 operation)
‘B’ sends ‘A’ the random index (1 operation + 1 bandwidth + latency)
‘A’ sends the key to ‘B’ (1 operation + 1 bandwidth + latency)
‘B’ decrypts the entry to find out the roll (1 operation)
A: performs 2n+2 operations, uses n+1 bandwidth, and incurs 2 latency
B: performs 3 operations, uses 1 bandwidth, and incurs 1 latency
This is a total of 2n+5 operations, n+2 bandwidth, and 3 latencies, to calculate one dice roll.
Plain old client server does this:
‘B’ asks ‘A’ for a random number (1 operation, 1 bandwidth, 1 latency)
‘A’ generates a random number (1 operation)
‘A’ sends the number to ‘B’ (1 operation, 1 bandwidth, 1 latency)
That’s 3 operations, 2 bandwidths, and 2 latencies to generate a dice roll that’s every bit as secure.
So keep explaining: I’m lost as to why I’d want to do it the first way…?
Cas
I think the idea is that B doesn’t trust A. And, in fact, A doesn’t trust B. The problem here is coming up with a communications protocol between two parties where they can both agree on a random number without necessarily trusting one another.
Ah, I see, it’s for peer-peer multiplay rather than client-server.
So what’s to stop A sending B whatever key it likes to fudge the dice roll? What’s to stop A creating 6 different keys and cunningly sending B the key that always gives B a ‘1’?
Cas
Yep, that’s exactly the problem! 
If you’re opening your code I expect you have to calculate everything on the server in parallel with the clients and kick any client that deviates from your expected state (note you don’t have to track everything, tracking one variable will do, as long as it’s accurate and noone knows which one you’re tracking).
I get the impression that the peer-to-peer system just isn’t possible yet. It’s a situation that hasn’t to my knowledge been researched much (if at all), and seems to require an unrealistic amount of resources to properly implement.
So what’s to stop A sending B whatever key it likes to fudge the dice roll?
Plenty. See encryption algorithms are designed to be very one-way things. In fact, the public key systems we use every day (e.g. e-commerce over the web) are a perfect example of that. Even though, you, the client has both the public key for a site and an example of an encrypted and decrypted message, you still can’t work backward to figure out what the private key was that was used to encrypt that message.
Trying to work them backwards to generate a key that produces a particular message is nigh on impossible. What you are suggesting is that Inga is clever enough to make a message that can decrypt six different ways with six different keys (which any message does) AND that each of the messages makes sense and is a different valid ordering of the numbers 1-n. Sorry, that’s not going to happen. And even, if by some miracle, she has set a computer to calculating a set of keys + message that gets this result, she blows the whole combo on one die roll.
If she keeps sending the same message more than once then a more sophisticated client can easily detect the cheating. If she doesn’t send the exact same key for the same message then he knows she’s cheating. If she sends the same message and the same key then he’s in a perfect opportunity to cheat by sending a specific return value to choose the roll rather than just randomly select it.
You can complicate the procedure all you want but all you’re really doing is making it computationally undesirable to cheat. And that is the best you can do when you don’t control the system from start to finish.
“A difference which makes no difference, is no difference.”
That does make a difference.
Well bugrit, I’m sticking with client - server as it seems to me to be the only reasonably easy way of making money out of selling a service… mortage to pay etc.
Cas
what goes about preventing cheating in forms of sending false highscores? I have had some ideas about preventing the client from simply decompile the classes and hardcode a score to send to the highscore server, but i’ve always found easy ways to break this.
any ideas? what’s the common thing to do? one of the problems is that the highscore server is customizable to suit all games, not just one (read my game).
You can NEVER trust the client. The only way is that if you have a game server(that you have full control of) that calulates the highscore and send it to the highscore server and configure the highscore server to only accept messages from you game server. Can’t come up with any other ideas.
one of ideas i came up with was that this:
- the client starts a new game
- the client sends some message to the highscore server that he has started a game -> timestamp stored
- client plays for a while and game over
- client sends highscore to server
- the server checks the time elapsed (currentTime-startTime) and checks in some whay that the score is possible to get for the elapsed time.
for instance, say I get 1000 points when playing 5 mins (normal play), then getting 10000000 points in 2 seconds is not possible.
this should work pretty well. as stated before, it’s easy to break. how? start the game, leave it running for a day in the background, send fake score to server -> tada!
i’m lost 
it might work though if i come up with something smart.
my other ideas are similiar to this one.
[quote]The only way is that if you have a game server(that you have full control of) that calulates the highscore and send it to the highscore server and configure the highscore server to only accept messages from you game server
[/quote]
That’s basically the same thing as sending it directly to the hiscore server as far as cheating is concerned. I’d still be able to send bogus scores to the game server.
[quote]for instance, say I get 1000 points when playing 5 mins (normal play), then getting 10000000 points in 2 seconds is not possible
[/quote]
No, but nothing prevents me from sending 2000 points after 10 mins, or 20000 after 100 mins. Or deactivating collision detection or whatever.
Oops sorry, you pointed that out yourself already :-X
Bottomline, you can never prevent cheating if you depend on the client for score calculating. You can complicate things a little at best. The only way is to let the game and scoring happen on the server, not the client and then you’d still not be fully safe.
Greetings,
Erik
maybe a little encrypted native library as the score submitting client that only accepts the full serialized game objects which it validates somehow and from which it subtracts the score which (if validation was ok) it sends to the server.
That might be a little demotivating to hack but of course still not fully safe.
Erik
Maybe I wasn’t clear enough on what I meant. The game server shall contain all game logic and from it create the highscore. The client only sends “move left”, “fire”, etc to the server and the server checks if the fire hits the opponents and register this to the score and sends back a message to the client that he hit the bad guy. Without control of the game logic you can’t trust the highscore.
But if you think of the amount of time you can add on your game on the subject of preventing cheats and the number of possible cheaters in your game I quess that the easiest solution is that you check the highscore yourself every day or so for scores that looks like cheating.
Yes, very true.
My own hiscore server is completely unprotected (don’t tell anyone ;)) but there’s no need to invest time in that yet, as nobody seems to play the game anyway let alone hack it.
First priority is to make the game fun I guess and then if cheating becomes a problem, deal with that then.
Erik
exactly… no need to spend hours and hours on something noone will ever try to do… concentrate on your game and the gameplay… worry about cheaters later… but try to have a little thought that it may come up in the future so that you code your game in a direction that allows you to add anti-cheats.
If anyone comes up with a neat solution to the hiscores problem I’d be especially interested as we’re going to run a Million Points Prize promotion for Alien Flux when it’s launched, and we need to make sure no-one’s cheating because the prize is going to be pretty nice, like an Inspiron or something.
I toyed with the idea of recording the whole game but apart from being detrimental to performance it might also be rather bloody large.
And obviously we can’t run the game on a server.
Cas