A new attempt at a social cheating solution

by Aardappel_ on 09/23/2006 08:11, 57 messages, last message: 09/27/2006 16:35, 16758 views, last view: 05/05/2024 19:48

Since taking the masterserver down, I have been thinking of new ways to combat cheating in a social rather than technological way. You have all seen my previous ideas on this topic, and I have a new, even simpler system that allows players to establish identity and trust, and admin servers accordingly, all without any central authority:

http://strlen.com/rants/trusted_communities.html

(scroll down, the new system is under "Decentralized trust").

See if you can poke any holes in this one. It is not a silver bullet, but it will bring us much closer to be able to play without cheaters. It works hand in hand with the existing mastermode (it extends it).

If all goes well we will implement this one.

   Board Index   

#38: ..

by pushplay on 09/25/2006 00:13

I've been thinking this over in the back of my head. The problem with this system is how often do you see the same players? Maybe I just have a poor memory but I got the feeling I was almost always playing with new people.

I think the system is stronger with community maintained lists of trusted and untrusted people. For instance someone could keep a list of community contributors so I could have Gilt in the trusted list without recognizing him online. This can be as simple as a manual copy and paste operation as long as the file format allows it and Sauer can deal with potentially contradicting data.

reply to this message

#39: Next candidate..

by eihrul on 09/25/2006 01:54

Found a public domain implementation of elliptic curve cryptography that seems simple enough:

http://www.george-barwood.pwp.blueyonder.co.uk/hp/v8/pegwit.htm

If it can be cleaned up/shrunk down enough and the algorithm isn't too dated, it seems like a good choice.

re: pushplay
If we can manage to make public key crypto work (read: I can find a simple enough implementation), then all you would have to do is include a list of public keys to make that work.

Of course, if we have to go with some hash-based solution like Eivets suggested above, that sadly would not be possible...

reply to this message

#40: Re: Next candidate..

by pushplay on 09/25/2006 02:11, refers to #39

Yeah, I've been assuming some kind of public key crypto.

reply to this message

#41: Re: ..

by marcpullen on 09/25/2006 04:35, refers to #29

The hackers will be on the same server cheating against each other. Honest players go to another server and take it over.

You could go a step further and make it so the owner of the actual physical server can be a moderator and watch the votes like a judge, players being the jury. The players vote and the moderator makes the final decision.

Could also do something like ebay, where other players vote for a player and some master server, or even just the server they are on tracks if they suck or not. So you can see if they cheat or are just jerks. That would be harder to do since tracking things requires some kind of controlled ID (ip, username, etc).

reply to this message

#42: ..

by StillPeter on 09/25/2006 08:15

Um, okay, who actually read the whole page that was linked to in the original post?

reply to this message

#43: Re: Next candidate..

by StillPeter on 09/25/2006 08:24, refers to #39

Plain old GPG? (http://www.gnupg.org/)

You could set it up for the user using a bash script in Linux and a bat file in windows and whatever Macs use for that OS set. That way it would be sauerbraten asking for a password on first run.

Even has a trust system build in, not that you have to use it, could be useful?

reply to this message

#44: Re: Next candidate..

by eihrul on 09/25/2006 08:46, refers to #39

Okay, I've got a port of Pigwet in about 600 lines of code. That may be reasonable, although Aard may think it's too much. We'll have to see. ;)

reply to this message

#45: Re: Next candidate..

by eihrul on 09/25/2006 08:48, refers to #44

Er Pegwit, but same diff.

reply to this message

#46: Re: Viva la wikipedia!

by SleepwalkR on 09/25/2006 18:48, refers to #19

eihrul, what about the Diffie-Hellman Key Exchange + that protocol you found? You can use DH to securely exchange the key for symmetric encryption.

Lookie: http://en.wikipedia.org/wiki/Diffie_hellman

Not sure if there is an implementation available that you can use, but the DH exchange itself is pretty simple. I think the problem is generating primes that are big enough not to be easily cracked.

reply to this message

#47: Re: Viva la wikipedia!

by Eivets on 09/25/2006 20:25, refers to #46

Diffie-Hellmann does not improve anything here. If you use your private key to encrypt a challenge and the other one uses your public key to decrypt and see, if the result is correct, this is enough. The only thing which is not good is, that when you first learn the public key of someone, the server could fake it, which is a man-in-the-middle attack.

That means, that the owner of the server could impersonate people, but only in front of others, which learned the public key of that person on their own server. Other people can still find out, that this is not the one he claims to be.

Anyway, Diffie-Hellmann is also vulnerable to man-in-the-middle attacks. So it does not improve things at all.

reply to this message

#48: Re: Next candidate..

by Eivets on 09/25/2006 20:28, refers to #45

pegwit seems to be okay. SHA-1 is known to be broken, but I don't think, the script kiddies will use sophisticated crypoanalysis with a lot of computing power to break it!

The only caveat might be the export regulations...

reply to this message

#49: Re: Viva la wikipedia!

by eihrul on 09/26/2006 00:02, refers to #47

Well, Pigwet's GF(2^M^N) fields also seem to be vulnerable as well. Unfortunately, I can't find any more concise implementations of ECC than that. :(

All the GF(2^P) implementations don't seem to be made with stand-aloneness in mind.

reply to this message

#50: Re: Viva la wikipedia!

by Eivets on 09/26/2006 18:03, refers to #49

Rethinking the whole thing:
People do not want a central signing instance for public keys. In that case, if you meet a person first time on a compromised server, there is no way that the owner of that server cannot impersonate that person in front of you.
That's true for both public key and an md5 based approach like I proposed above. So I would repropose the md5 approach: You have the same safety, there are no export regulation problems, there are MD5 implementations in less than 300 lines and the rest is easy to implement

reply to this message

#51: Yippee.

by eihrul on 09/27/2006 01:20

I managed to implement secure elliptic cryptography from scratch based on the NIST recommended elliptic curves, since Pegwit's algorithm was broken back around the year 2000. All it took was a few sleepless nights wrapping my head around the crap trying to figure out how this whole cryptography thing works, and one government standards document later... ;)

I also used Tiger for hashing instead of SHA-1 since it seemed to be more secure and easier to implement.

Total size: 650 lines of code. Tada! Stuff is in CVS now for the curious, minus the trust code to actually use it yet.

So, short of Aard not liking it, or serious export restriction problems on this, or my code just being really really buggy, we'll have public key cryptography to work with for certain.

reply to this message

#52: Re: Viva la wikipedia!

by eihrul on 09/27/2006 01:33, refers to #50

Actually, there are compelling reasons to use public key crypto over hashing.

Sending the key the first time around is vulnerable in either system, correct. A simple man-in-the-middle lets them impersonate you by sending out their own key from the compromised server instead of yours.

BUT, how the theft affects you, the victim, in the two systems is very different:

1) Hashing

You need a globally unique id, distinct from your secret relative ids you assign to people. This global id would have to be used so anyone on a server you're connecting to knows what hash to send you in the first place, and you back to them. If someone impersonates you with your global id, and gets any trust relationships at all from someone else, now the relative ids other people assigned to your global id no longer match.

You will be accused of hacking your own identity. You can not solve this short of asking every single person who has the wrong relative ids to clear those entries out and retrust you, or generating an entirely new identity for yourself and losing all your trust.

And if someone was impersonating your friend, using his global id, then you have a tough choice to make if you want to mark that global id as untrustworthy now, thus ruining your friend's identity.

2) Public key crypto

Your public key IS your global id. To do a man in the middle, an impersonator MUST generate a new public key and new private key, and send them in place of yours on the initial trust setup with somebody.

However, the thief will have a problem: your public key will no longer match his on any uncompromised server, and so you will simply show up as a different user. Regardless of what he does with his impersonated public key, it does you no harm whatsoever, since people only legitimately know you by your public id. In other words, the thief can't do any damage of consequence.

There are also advantages in being able to easily distribute lists of trusted individuals like Pushplay mentioned, etc.

reply to this message

#53: Re: Viva la wikipedia!

by Eivets on 09/27/2006 08:49, refers to #52

The idea of using the public keys as the idea is really good and indeed makes an improvement as you describe.

And since the code is in cvs it is already exported, now... ;-)

reply to this message

#54: Re: Viva la wikipedia!

by Eivets on 09/27/2006 08:50, refers to #53

... as the id ...

reply to this message

#55: SIMPLE AND EFFECTIVE

by rock.n.rol on 09/27/2006 14:52

hi @all developers of this awesome game (Aardappel, eihrul and all others) !

First of all i wanna say, u really made a very good job !
This game is outstanding, its simplicity and gameplay is brilliant, and the coop edit mode is the most ingenious game mode i ve ever seen ! Also the graphics: It becomes better and better with every release, awesome !

I m a hardcore-player "since the first hour" (pong), hehe, and i really have played A LOT of different games in my life, believe me, but this one beats everything ! congratulations for that ! I really dont like other first-person-shooters anymore, it seems i am totally addicted to sauer now...

And thats the problem: Since the masterserver is down, it has become kind of dead and i really hope, u will find a solution for the cheater/kickbot/hacker issue, in this forum i always read about "solutions" like "decentralized trust" and other coder-stuff (i m just a player, not a programmer), but it sounds very complicated to me, the best in this game is its simplicity, it was a pleasure to run the game, join a crowded server and start fragging, lol.

I wanna say: when it becomes too complicated, it could be that the players wont like it anymore, not to mention the hackers and script-kiddies, who surely will find a way to hack it again, there is no code which cant be hacked, and what happens next ?

I mean, it was pure fun to join a server and to see what happens there, if there were cheaters or not, and taking the masterserver offline surely gives them even more motivation to try hacking again. I m sure there is NOTHING u can do against bad folks,
they WILL appear, and the more complex the code is, the more it will be a challenge for them to manipulate it and the harder they will try...

I really believe in your skills and hope u will find a SIMPLE and EFFECTIVE solution, like u always did !

rock.n.rol (desperate player)

reply to this message

#56: Re: SIMPLE AND EFFECTIVE

by rpointon on 09/27/2006 15:27, refers to #55

From what I understand it will be simple and effective, plus it may encourage a better sense of community since it basically maintains a list of friends...

> ...there is no code which can't be hacked...
Hacking doesn't matter - the script kiddies will be blocked at the server and thus worst case is DoS.

- aka baby rabbit (who will kick butt of rock.n.rol one day)

reply to this message

#57: Re: SIMPLE AND EFFECTIVE

by rock.n.rol on 09/27/2006 16:35, refers to #56

;)

reply to this message

   Board Index