Re: Bit on cheating: was: Re: Introductions

[madsdyd@challenge.dk]

On Thu, 11 Dec 2003, Gregor Mückl wrote:

> > the server replay all events when syncing. Only if the states match, the
> > player is allowed online. And obviously, other clients would check from
> > time to time, that the hashed state of the clients matched the server
> > hashes. (This way the server could check the rules, reducing the load on
> > the clients). This is doable, I am sure.
> >
> 
> That sounds like a nice approach for simulations.

Yes, it sure will not work with fps and similar. Requires lax time limits.

> Yes, you can definitvely play some tricks here. But since my focus is on an 
> action game, I am not really aware of too many techniques.

No, action games really are hard. However, you _could_ use a similar
approach: Have the players that interact the most relay information to a
trusted server (btw: I assume a trusted server, otherwise it is near
impossible to fix anything!). Have the server replay the actions, checking 
them against the rules. If a player is caught cheating, punish him. Its OK 
if the check and the punishment is delayed - better late than never.

I know this is not what we really want, but it is a lot better than 
nothing.

> > Other methods, includes what the nethack people does; blessed binaries,
> > with embedded (randomly accessed) digital keys.
> >
> 
> This is an interesting approach. However, I do not understand how they are 
> able to hide the key in their binaries. Given the statistic characteristics 
> of a cryptographic key (quite a lot of keys look like they are an almost 
> perfect stream of random numbers, mostly because how they are generated), you 
> should be able to make it out within the file within minutes. Using strace or 
> gdb on a nethack session might give you quite some extra hints on the 
> location of the key.

Hmm. I have tried to locate more information, and I am now getting 
confused as to whether my memory serves me correctly. I have been told 
about this approach in relation to nethack, but can not find any 
information on their site. Maybe someone was speculating about this 
method, and I misunderstood. Anyway, it goes something like this:

- You trust the server (period).
- The server have a private/public key pair (for signing the network 
  packets). However, the public key is _not_ made public.
- The client needs to know the public keys, the public key is embedded
  in the client code. The client and server can now communicate and be 
  fairly sure that each end is the "expected" part.

A number of problems arise, which you readily identify:

a) A digital key have a very high entropy (or is it low, I can never 
   remember, but you know what I mean, carries a lot of information.). 
   This should make it easy to locate the key in the binary, right?

b) How about the the license? How can you call this game open source?

My understanding is that 
b) is fixed by releasing the source as open source, and provide the 
oppertunity for everyone to build the system, using any keys they want. 
They just can't have the key the master server uses. So, if you make 
changes, you can connect to the officiel master servers, but you can 
create your own games, and invite other players to play, either by 
publizing the key, or create your own blessed binaries.

a) Is fixed by splitting the key into a large number of pieces, and
embedding them all over the binary. Also, including lots of different
keys, although only one set of pieces is used. That ruins the static
analysis. Wrt. the gdb attack, a number of methods can be applied to make
it harder to figure out what is the real key, and what is random noise. 
This however will only work for a while. The solution to that is to 
release new blessed binaries often, and make sure that the methods to 
split the keys/assemble them, are also regularely changed.

There are a number of weak points in this approach. But I have not heard 
of better methods...

> To the key to this approach is to effectively hide the key from prying eyes, 
> within a region, on which the user has the ultimate control. How can you 
> possibly do that?

Well, only with TCPA/Palladium (and similar). And then we may as well bend 
over.

> See above. Some time ago I've started to design some sort of generic 
> metaserver along with a player database, which would essentially become some 
> sort of single-sign-on environment for players.

That sounds interessting - I hope you may get to the point of realizing 
this.

Mads

-- 
Mads Bondo Dydensborg.                               madsdyd@challenge.dk
No rational argument will have a rational effect on a man who does not want
to adopt a rational attitude.
                                - Karl Popper