Forum index VCMI Project - Heroes 3: WoG recreated
Forum of the project aiming to recreate best turn-based strategy ever!

FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  StatisticsStatistics
RegisterRegister  Log inLog in  AlbumAlbum  DownloadDownload

Previous topic :: Next topic
Multiplayer security level: Paranoid
Author Message
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2013-05-08, 16:33   Multiplayer security level: Paranoid

I've recently read about Secure multi-party computation. It's an interesting tool in cryptography that basically tries to make trust not necessary in multi-party communication. One does not have to reveal his secrets to tell something (and nothing more) the other person. One can say something useful actually, like in millionaires' problem. It's even been implemented already: http://www.cs.huji.ac.il/project/Fairplay/ .

The point is that, in theory, one could securely compute things that are currently computed on VCMI's server, that is game mechanics. It's totally crazy and even non-obvious. I think one would have to use symmetrically encrypted full gamestate (key is f.e. xor of each client's partial key) and securely decrypt it, process events, encrypt and return calculated packages and send encrypted GS for further processing.

I don't suggest it's a good idea. I even think it isn't. But if anyone says he wants more security, tell them the truth: it's possible!
_________________
:)
 
     
i30817

Joined: 11 Feb 2013
Posts: 36
Posted: 2013-05-13, 16:13   

Of course it is. I don't really see how you could use it in gamestate here though. A player is a player, why exactly would you anomize any move from a player so that others didn't know about it? What's the usecase?
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2013-05-13, 17:12   

I primarily restrict access to gamestate. Here is how:
1) all players read map & generate random password
2) [secure computation]:
input: keys from players, read map
output: initialized, encrypted map (symmetric key: xor of players' keys), for all players; turn token info
3) player makes move, processing [secure computation]:
input: keys from players, encrypted gamestate from players, move from current player
do: decrypt, update gamestate, encrypt
output: new encrypted gamestate, player-specific info about action results, new turn token info

perform 3 until game ends.

Now nobody can cheat in any constructive way. Nobody knows the true, full state of the game. Nobody knows what others do, unless it affects them.

Once again, full gamestate is input and output of secure computation. It can only be encrypted or decrypted using all the keys, and that's why hiding the input is so important: everyone has encrypted gamestate but only taking all the keys together one can actually use it.
_________________
:)
 
     
Macron1
Guest
Posted: 2013-05-13, 23:16   

Tow dragon wrote:

Now nobody can cheat in any constructive way. Nobody knows the true, full state of the game. Nobody knows what others do, unless it affects them.


In single player game I can in process of gaming move puzzle pieces files to other location temporarily (or before game replace puzzle pieces in LOD by transparent pieces.
This will show me the place for Grail.
In multiplayer this is also possible, I think.
The only solution, I think, is to load all needed puzzles at startup and add them to map information.
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2013-05-13, 23:26   

Yes, there are a few unfortunate corner cases in Heroes III like puzzles. Adding puzzles to gamestate and rendering the puzzle map securely would solve the problem.
_________________
:)
 
     
gotar

Joined: 02 Jul 2012
Posts: 48
Posted: 2013-05-14, 09:33   

Tow dragon wrote:
Yes, there are a few unfortunate corner cases in Heroes III like puzzles. Adding puzzles to gamestate and rendering the puzzle map securely would solve the problem.


Nope, it's not about puzzle images that might not cover graal location on screen, but graal position itself - to be secure, client must not know it at all until discovered (in multiplayer online game).
 
     
i30817

Joined: 11 Feb 2013
Posts: 36
Posted: 2013-05-14, 10:56   

I really don't understand your idea.
The kinds of shared key schemes usually aren't for keeping the data secret from the participants; but to confuse which participant signed, encoded or decoded it. Ex: a polynomial secret key can be used to: take any 4 out of 10 keys and decode the input (this one has secrecy, but only until N participants agree); or to sign a array of bytes without knowing who signed except that it's one of the key of the participants (limited anonymity).

I have no recall of hiding computations from the computer completely except with a trusted server or with fully homomorphic encryption (which is just a 'holy grail' of crypto, of which there is no implementation because it would required special drivers or special hardware; because the input has to be decoded once it needs it hits driver level).

There are MANY ways to to resist tampering though; which i suppose it's what's actually needed?

edit: actually read the wiki link now. I'm not sure how a protocol like that would be used on a H3 game. The main stuff you'd need is to prevent people from
a ) finding the grail by introspection
b ) edit the gamestate with 'illegal' operations in their turn.
c ) secondary stuff would be to find what is in the cities or on the fog-of-war.

These all look like stuff that requires at least one trusted server (to generate keys, decrypt gamestate to check for consistency and update). Even if, for instance the coordinates of the grail could be checked with a homomorphic sum operation, the private key would be needed for decoding the result, so the answer would need to be sent to the server (unless you use this ), which seems to me especially useless.

It just doesn't look like the millionaire problem situation, where two participants each wants to keep a secret. Rather, it looks like a server and a client (player) where the server's secret is the grail location (for instance) and the client doesn't have any pressing need to keep secret it's dig location from the server (input for the 'check for grail' function). Of course, if the server is local too, just introspecting the memory of the server would be enough on that case to fuck everything.
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2013-05-14, 14:09   

I know it's a nonstandard way of using secure multi-party computation and if fact it has little to do with fully homomorphic encryption.

gotar wrote:
Nope, it's not about puzzle images that might not cover graal location on screen, but graal position itself - to be secure, client must not know it at all until discovered (in multiplayer online game).


Not quite. If map has fixed grail position then you're right and IMO it shouldn't be hidden in MP games because it cannot be hidden. When position is randomized, it could never hit the client (unless he digs it out).

i30817 wrote:
a ) finding the grail by introspection

b ) edit the gamestate with 'illegal' operations in their turn.

c ) secondary stuff would be to find what is in the cities or on the fog-of-war.


a) Kind of troublesome, I've answered silmilar problem above.
b) c) Not possible -- it's encrypted *all the time, everywhere*. All processing on it is withing the securely computed function.

i30817 wrote:
It just doesn't look like the millionaire problem situation, where two participants each wants to keep a secret.


Think of client's part of key as the secret. Only the one with all the keys can decrypt gamestate and do anything with it. And who has all the keys? Only securely computed function.
_________________
:)
 
     
cromat 

Joined: 10 Dec 2011
Posts: 8
Location: Wrocław
Posted: 2013-05-21, 00:51   

i30817 wrote:
I have no recall of hiding computations from the computer completely except with a trusted server or with fully homomorphic encryption (which is just a 'holy grail' of crypto, of which there is no implementation because it would required special drivers or special hardware; because the input has to be decoded once it needs it hits driver level).

http://nakedsecurity.soph...n-cryptography/
https://github.com/shaih/HElib
It's not mature enough to be used in VCMI ("it is fairly low-level, and is best through of as "assembly language for HE""), but looks promising:)
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2013-05-21, 14:28   

Does any scheme of fully homomorphic encryption solve the problem of authenticating users sending requests? Standard scenario is 1 client + 1 server, not k clients + 1 server. My scheme of secure computation solves this.
_________________
:)
 
     
i30817

Joined: 11 Feb 2013
Posts: 36
Posted: 2013-05-27, 18:07   

cromat wrote:

http://nakedsecurity.soph...n-cryptography/

It's not mature enough to be used in VCMI ("it is fairly low-level, and is best through of as "assembly language for HE""), but looks promising:)

The grail situation is the other way around!

It's not the client hiding stuff from a third party, but the game mechanics that need to hide something from the client - Therefore, that using HE to send that data to be checked at the client, would be a caching mechanism for something unchanging more than anything. You'd still need the server.
And worse; in HE you don't know the result of the operation too without decrypting it. So it's useless!
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2013-05-27, 22:58   

i30817, yes, of course. HE does not remove the necessity of server. If multi-stage, multi-user, authenticating HE is possible (I have no idea if it is) then we just don't have to trust the server. Therefore one of the players can run it.
_________________
:)
 
     
Display posts from previous:   
Reply to topic
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
Add this topic to your bookmarks
Printable version

Jump to:  

Powered by phpBB modified by Przemo © 2003 phpBB Group
Template Chronicles modified by Nasedo modified by Tow.
© VCMI Team
Page generated in 0.08 second. SQL queries: 12