Archived

This topic is now archived and is closed to further replies.

Andrew Russell

Co-operative Random Number Generator?

Recommended Posts

OK, I''m probably going to be making some sort of peer to peer game soonish, and I was wondering about a good way of doing a co-operative random number generator. The basic idea being that the two computers will generate random numbers that cannot be tampered with to the benifit of either player. Any ideas? It''s pretty tricky. If you assume both machines are hostile to one another, if your random number is generated by your own machine, then the opponent could be generating favourable random numbers continuiously. If the random number for you is generated remotly, it could be generated to be bad for you. If the generation is shared between machines, then a machine could get the segment from the oponent, and generated their own segment that would still create the desired result for them. One idea is having a "random number list" that is stepped through. However this is not nearly random enough. Perhaps a variation on that theme?
Free Game: Yet Another Falling Block Game

Share this post


Link to post
Share on other sites
However you do it, it will be open to tampering, even if it was just modifed to completely ignore the random generator and always choose the "best" value.

but if you really want to do it, how about (for example)

both machines generate a random 64 bit number

each machine sends that 64 bit number to the other machine

each machine XOR''s the 2 numbers together ( "^" operator in C/C++)

one machine uses the top 32 bits of the result, the other uses the bottom 32 bits, also each machine then knows what the other got so could check the result to try to detect cheating.

Share this post


Link to post
Share on other sites
Perhaps if each machine generated a random number, sent it to the peer, and the peer XORed them together for the final number?

I wrote a littlle program which generates two random numbers and XORs them together - results over 10k tries show that the numbers are about as random as can be expected; 100 possible numbers, all numbers occured between 80 and 123 times, most fall between 90 and 110.

EDIT: Crap, Narcist beat me to it while i was trying out my theories...

Member of the Un-Ban nes8bit Association (UNA) (to join put this in your sig)

We are at war with Iraq. We have always been at war with Iraq. I love Big Brother.
- DakeDesu

[edited by - Valderman on November 14, 2003 9:05:41 AM]

Share this post


Link to post
Share on other sites
> ... some sort of peer to peer game ...
> ... co-operative random number generator.

If the random number generation is not the same across peers, each peer's game simulation will diverge and things start to get out-of-sync; typically, orders from opponents become inconsistent with the your game state. Exchanging game state CRCs at some set frequency can help detecting cheaters as the game evolves. Check Terrano's article.

-cb

[edited by - cbenoi1 on November 14, 2003 10:07:24 AM]

Share this post


Link to post
Share on other sites
why dont you just make your own random number generator and seed both systems with the same value, and every once in a while check that they are producing the same "random" values?

that way you wouldn''t need to worry about the network communications performance so much, as soon as you detect an out-of-sync random number, assume they have cheated, and disconnect the cheater. but they wouldnt actually need to exchange data continuesly to generate the ''random'' values.

Share this post


Link to post
Share on other sites
Something you *could* do would be this:

Assuming it is a 2-player game, have each client generate their their own random number.

Next, send the chosen number to the other person.

Then, have the program randomly pick which of the random numbers to use on the client.

-Greven

Share this post


Link to post
Share on other sites
if you really care about cheating, the only safe thing to do would be to seed them both with the same number and check that they are the same (as aboeing said). the other methods can still be cheated.

Share this post


Link to post
Share on other sites
@AndreTheGiant

Sounds really slow, and wouldn't work in many situations you have peer to peer connections (lan/lan party w/o net access, or, you don't want the things using net access.)

XOR thing, sounds bad - all one would have to do is XOR their desired value by the 1st value, and send that new value off, then when both sides XOR it it would have player 2's original value. You need to have some sort of random number generator, which takes a seed, and doesn't have to be reseeded (hopefully, not a requirement though)
I would check out the mersenne twister, there was a cotd at flipcode awhile ago, or you could just search for it on google. It has a period 2 to the 19937 power, minus 1. It's also fairly fast.

-Michael

Someone mentioned storing calculated positions based on game physics, and checking to make sure the other player was within the bounds - this sounds like the best way to make sure there isn't a cheater.


[edited by - thr33d on November 14, 2003 1:22:21 PM]

Share this post


Link to post
Share on other sites
Lets look at the problems:

You want to have random number generation. Lets assume it''s for a turn based game like Risk (the roll of the dice determines the outcome of battles). This means there are two ways to cheat:

*By modifiying the "random" numbers to ones that are most favorable.

*By knowing the "random" numbers in advance (such as if they are from a list or from a seed known at the beginning of the game) and using the knowledge to make better moves (only attacking when you know the outcome will be in your favor).


Obviously you can''t have any list or a predefined seed, because players can use that to completely override the "random" elements by knowing what they are in advance.

The other option brought up here was to have both players send a value, and have those values combined to form a single random value. However this opens it up again to number tampering. One player can wait until the other player has sent his piece, then figure out what he should send in order to make the outcome he wants (even with a complex algorithm that could not be reversed, a machine could still try random values for X seconds, then send the value which gave the best result).


So here is a new option which allows for a more secure game:

At the beginning both machines select seperate seed values, which will be used with the same random number generator. These values are secret until the end of the game, at which point both players will send their seed value. Each time a random value is required both players send the next value from their seed and it is combined as described above (the complexity of trying to come up with a valid seed number at the end becomes infinitely complex as the number of values sent goes up). This can also be further secured (assume that your random generator was crypto analysed and found to have a flaw such that you could determine a seed that would have given the values you sent) by having each machine generate 10 or 100 (some amount that would be used up in 1 or 2 minutes of play) random values at a time from the seed and cache them. It would then send an MD5 hash of the entire list before any values from the list where sent. Once the list was exhausted both players could check that the values matched the hash (at the moment MD5 cannot be reversed, and there is no easy way to come up with matching values for an MD5 list)

Share this post


Link to post
Share on other sites
I find this topic interesting but unfortunately Im not very knowledgable on the subject.

I do have another suggestion, which is probably wrong again, but at least I''ll have someone explain to me WHY it is a dumb idea...



You could just let the clients generate the random numbers as normal, with the assumption that they wont cheat and make favorable random numbers.

Then in the part of the program that actually uses the random numbers, you could randomly choose which algorithm to use. The randomness for this part is NOT based on any user input so there can be NO tampering with which algorithm is used. So for example, you could have 2 different algorithms like so:


void alg1(int randomNumFromUser) {
if (randomNumFromUser is big) player1 loses life
else if (randomNumFromUser is small) player2 loses life
}

void alg2(int randomNumFromUser) {
if (randomNumFromUser is small) player1 loses life
else if (randomNumFromUser is big) player2 loses life
}


You could have more than two algorithms to choose from, and could obviously use more clever factors than whether the random number is big or not.

Since the users dont know what algorithm you are going to use, there is no benefit for them to send off certain random numbers, and therefore they wont bother.

You have to balence the algorithms out so that the logic of the game is preserved no matter which algorithm is picked. And you have to make sure that the likely hood of each outcome is equally likely, or else players will realize that for example if they submit small random numbers all the time then they have an advantage in the long run.

Please comment on how dumb this idea is

Share this post


Link to post
Share on other sites
AndreTheGiant''s won''t work, as far as I can tell.

Michalson''s on the other hand, seem''s pretty great. I didn''t quite understand it entirly, however. Can you perhaps split it into stages or something for me? (or I''ll talk to you about it later, ta)


Free Game: Yet Another Falling Block Game

Share this post


Link to post
Share on other sites
Why don''t you just have the current "host" machine (the one that generates the random number) change every round? That way, if a devious person was using a hacked client they could only influence the game every nth dice roll (or whatever you''re using the numbers for ).

- Daniel Roth,
Programmer / Web Developer

(www.rothware.com, www.cwu.edu)

Share this post


Link to post
Share on other sites
quote:
Original post by Ramius
Why don''t you just have the current "host" machine (the one that generates the random number) change every round? That way, if a devious person was using a hacked client they could only influence the game every nth dice roll (or whatever you''re using the numbers for ).

Unfortunatly, 50% of the game time would still ruin the game. Also, if they shoved a bot in their, it would be unbeatable.


Oh, and fredizzimo, if you''re reading: that was half an hour later, and was quite difficult to type without spelling errors.




Free Game: Yet Another Falling Block Game

Share this post


Link to post
Share on other sites
You might consider some approach similar to that taken by public key cryptography.

Its been awhile since I studied it, but imagine something like this:

Computer A has a public-key Pa, which is known to all other computers, Computer B has a similar Pb. Additionally, each Pi has a corresponding private key Ci, known only to computer i. Say Alice wants to send a message to Bob. She uses Bobs''s Pb to encrypt the message. When Bob gets it, he uses his private key pair, Cb to decrypt it. If the message is intercepted by Eve, Eve cannot read it because it does not know Cb.

You might be able to use this in a method known as a key-exchange protocol. I''ll try and remember an overview of one called Diffie-Hellman Key Exchange Protocol.

Everyone knows two things, a primitive root R and a prime Q.

Alice chooses a number Xa and sends Bob the value (R^Xa) mod Q. Bob likewise chooses a number Xb and sends Alice (R^Xb) mod Q. Once Alice and Bob have each other''s transmissions they can calculate the following:

Alice: ((R^Xb) mod Q)^Xa mod Q)
Bob: ((R^Xa) mod Q) ^ Xb mod Q)

It turns out that these two values will be the same! Likewise, is Eve is listening in, she will only know (R^Xb) mod Q) and (R^Xa) mod Q). Getting Xa or Xb from this information is a very difficult problem (known as the discrete log problem) and is what the security of this protocol is founded on.

If you have each computer choose Xa and Xb randomly then this may provide you with a solution. However, there are still problems.

1) A program could theoretically be modified decide to use any arbitrary value regardless of what is created via the above calculation. However, because both computers know what SHOULD be happening, you could maybe keep a state on both computers of where the game should be and compare them to make sure they stay in sync.

2) You''ll still have the problem that a maphacker or something simply reading from memory instead of trying to modify it. I''m not sure there is much to be done about this one, especially since even the giants (Blizzard, SOE) haven''t been successful at supressing it.

3) The main drawback: this is significantly slower than just having both machines using the same seed and ensuring the state between the two does not differ. Imagine if every single time your game needed a random number (quite possibly hundreds of times a second), it had to send out a packet and get one as well. While only an implementation would show how much of a problem this is, I imagine it would be large, and the best way around it I can think of at the moment would be to only use such co-decided keys once every few minutes, and use the value that is decided on as a random seed for the time in between.

Hopefully this has/will be of some help, if not, hey, I got to review the stuff typing all this out.

Share this post


Link to post
Share on other sites
quote:
Unfortunatly, 50% of the game time would still ruin the game.


True, though at least it''s a place to start. If elements of your gameplay rely on pure chance (ie. impossible to validate as there''s no pattern to compare against), then I don''t think there is a feasible technical solution for peer-to-peer networking. Short of using an independent third party (eg. server) for the number generation, I believe the best you can do is make your encryption and validation algorithms as elaborate as possible. While a dedicated hacker could of course reverse engineer whatever you employ given enough determination, I''ve noticed that malicious people with way too much time on there hands tend to target only mainstream, large-audience titles. Now if that''s what you''re developing, then good luck , but otherwise I doubt anyone will spend that much effort to break a single game''s anti-cheat code, even for bragging rights. On the other hand, all it takes is one person, so maybe the "frequent update" defense would work best.

- Daniel Roth,
Programmer / Web Developer

(www.rothware.com, www.cwu.edu)

Share this post


Link to post
Share on other sites
Well, it won''t be particularly main stream.

I am wanting to finish multiplayer for YAFBG (see siggy), and add online multiplayer, and then shareware it.


So, each player will know the other player''s state, but when you generate the combination of the block that drops, it needs to be properly random, otherwise it is too open to cheeting. Consider how easy it would be to make a cheating program if the RNG just called rand localy.


Random numbers are not needed very frequently, so speed is not particularly an issue. I don''t really understand how gibson''s method would work, unfortunatly.


Free Game: Yet Another Falling Block Game

Share this post


Link to post
Share on other sites
With the falling blocks game, both hostile generation and lookahead problems I think would be big issues.

Lookahead is probably the worst factor, since a cheater would be able to take advantage of knowing the next few pieces in real time without looking like he''s cheating.

Hostile generation would be easier to see. After all, wouldn''t you get suspicious if your opponent always got the same piece over and over, and you always got the worse mishmash imaginable? Of course, it''s all random, so such a thing could happen during the course of a game. And if only a limited amount of hostile generation was possible, it might not be noticable at all.

So being a paranoid SOB, I''d do the following protocol, which is a variation on hashing and public-key cyphers: Every time one of the clients requires a random number, both clients supply a random number. These numbers are placed in a buffer with a salt, and the whole mess is hashed. This hash can be used to generate a new random number. This prevents a lookahead RNG exploit, because a random number can''t be obtained until both clients supply the initial values. However, this still suffers from a hostile generation exploit, becuase whichever client sends the key second has the opportunity to run through as many hashes as it can before deciding on sufficiently evil initial value to pass back.

To patch that, each of the clients each has a public and private key. I find it''s easiest to think of the keys as functions. So client A has public key F() and private key f() and client B has public key G() and private key g(). These keys have the properties F(f(x)) == f(F(x)) == x && G(g(x)) == g(G(x)) == x. At game start, the clients exchange public keys.

So now, when Client A needs a new random number, it asks Client B for a initial value, and gives client B it''s own initial value. These initial values are salted and hashed. Let''s call the hash H. H is a value that both clients can calculate. However, instead of using H directly, client A uses f(G(H)). Client A then passes f(G(H)) to client B. Client B gets a value X form Client A, and checks to see if g(F(X)) == H. If it does then client A is playing by the rules, if it doesn''t, then either network error or client A is cheating. The key to this is that Client B can''t force Client A to use a bad value because it doesn''t know f(), and Client A can''t fake a good value because it doesn''t know g().

Of course, doing this is all slow as heck, but for a falling block game, random numbers are generated fairly rarely.

gibson gave a (incomplete) description of one method to generate the public and private keys. However, I wouldn''t bother thinking about the nitty gritty and just link against a proven crypto library, and let the library worry about the details.

For the less paranoid, strictly speaking, the initial hash is unnecessary because applying f(G()) is itself a kind of hash. However, that''s to add another roadblock against brute-forcing an inverse for the public key in order to generate the initial values. A good initial hash will only add maybe a couple hundred cycles while exponentially increasing the amount of time needed to generate an inverse. (Milage may vary according to salt and algorithm).

And if you''re feeling really paranoid, you''ll rehash H against another salt, in order to generate the actual random number used. This one isn''t really for protection against hacking, but more in cause you''re worried that application of the keys will cause a skew in the distribution of numbers. Or you could do it as protection against hacking, but you''d have to be doubleplus paranoid if you did that.

Share this post


Link to post
Share on other sites
Something I thought of awhile back for a MUD...

Well, I considered adding a ''fortune teller'' -type skill. Basically, it would return to the user of the skill the general ''luck'' a person they were ''reading'' would have in the near future.

The way I had this planned, a LIST of randomly generated numbers would be generated, long enough for several hours at least. The person''s ''luck'' would be pre-planned and ''readable'' by the fortune tellers.

So, what you might be able to do is generate a list of a short length and pass it to the client from the host. Likewise, after a period of time, you could generate a list on the client and pass it back to the host.

*shrugs* An idea, maybe annoying to impliment though.

-Greven

Share this post


Link to post
Share on other sites
I suggest a syncronized random number generator (ie all clients seeded to the same value). To prevent lookahead, any time a number is generated that is a multiple of X {a fairly small number, maybe depending on connection speed} (or maybe make it every X numbers generated, to limit lookahead to X numbers, or maybe make it some property of a number like if it is prime, or maybe in the middle of every turn during a turn-based game), all clients create a new seed (cpu clock tick # or something like that so it will be different between machines). Then encrypt the new seed with a private/public system, encrypt it, send it to all other clients. After a client has encrypted seeds from all other clients, it sends out the decrypt key for its seed. After a client has decrypt keys for all seeds, it decrypts them, makes a linear string out of them all (sorted by client ID or something global like that, so you end up with like 123456789 etc where 1 = client #1s decrypted seed), hash it, and use it as a seed. I think it would be pretty hard to generate a decrypt key to produce a desired end result seed. You would need to reverse the hash (to know what effect your seed has on the final seed), then reverse the generate a decrypt key to make the random data you send as the fake 'encrypted seed' decrypt to the proper value.

Sounds pretty difficult to undo to me, as long as you use 'proven' encryption and hashing. If you included more data than just the seed from that client in the encrypted packet, it could be made even more difficult to hack. For ex: if you send a seed, a checksum of some global{syncronized between clients} variable, and the player's name, it will be difficult to randomly generate a decrypt key that will make the all fields correct. When other clients see that the name is incorrect, it disconnects that player, or maybe just ignores their part of the string that is hashed, etc. If the verifiable data sent encrypted is longer than the key, hacking may not be possible - you'd need to talk to a security expert for sure though)

In other words, you 'randomly' reseed the generator using an algorithm that prevents manipulation of the seed.

[edited by - extrarius on November 15, 2003 3:17:08 AM]

Share this post


Link to post
Share on other sites
Urk. That would require generating a new public/private key pair every X random numbers. Generating key pairs is hideously expensive. It''s the equivilant of testing the primeness of random 300 digit numbers until you find two that are actually prime. Not only is this processor intensive, but it also creates unpredicatble processing requirements. In general, unpredictable processing requirements is bad for game programming.

If you''re going to generate a new key every request, you might as well make them symmetric keys. Especially since you never take advantage of any of the properties of public key encryption in your algorithm.

Share this post


Link to post
Share on other sites
What I was basically described was a system where you combine the combination method to generate random numbers (both players send half the number) with a trust system that ensures that players did not generated those numbers in response to what the other player sent (in order to change the resulting random value). I''ve thought it out a bit more, and here is a slightly nicer version.

To break it down you need:

*A random number generator. Both clients must be using the same algorithm (same seed will result in same random numbers). It should also be designed for a fairly large range (32bit), in order to prevent another player from trying to guess their opponents seed1 (this attack explained below).

*An MD5 hash function (takes a chunk of binary data, and produces a 16byte hash value)

*A queue template that stores 10 objects (a queue is like a stack, except that it is first in, first out)


At the beginning of the game:

Each player initializes their random number generator with a secret seed (and a secret offset; read attack 1 below). They then fill a queue object with the first 10 numbers their generator produces.

For each random number you need
Each player takes the 10 numbers currently in their queue and generates the MD5 hash of them. They send the top number from the queue and the MD5 hash to the other player, and place a new number from the random generator at the bottom. The players combine the numbers (easy example: Just add them together and mod by the number of possible pieces) to get the piece to drop. As each player recieves data from their opponent they save it. Once they have at least 10 numbers they compare the MD5 hash recieved 9 (or 10, depending on how you look at it) turns ago with the hash of the 10 latest numbers. If they don''t match the other player is cheating.

At the end of the game
Players send their secret seed (and offset values). Both players then use it to generate as many numbers as where used in the game. This allows you to check the final 9 numbers recieved (since the last few moves of the game are likely important), and also adds an extra layer of security ontop of the overlapping MD5 hashs (The overlapping MD5 hashs make it basically impossible to fake without a quantum computer for any reasonable sized set, the revealing of the seed makes it even hard). then you can


1 A possible attack against a random number system is by knowing the generator, you can input the values already produced, and then compare them with the output of all possible seeds (this is must faster if the random number algorithm can be reversed). When enough of the random number sequence is known the attacker (with enough computing power) can find the seed and begin generating the same random values. This was actually used in Atlantic city once (I can''t remember the name, but it''s the game where 7 numbers come up and you guess them, kind of like a really fast lottery). A guy who had the random number generator (a weak one) sat there with a laptop inputing numbers until he found the current seed. With that he could predict exactly what numbers came up. He got caught when he "guessed" all 7 numbers.

How to stop this attack: Add a second parameter to existing 32bit seed; a 16bit offset value. This value (random like the seed) causes the random number generator to generate and discard OFFSET numbers before it starts providing real numbers. This makes the task of guessing the seed beyond any reasonable computing time (unless the generator is really weak).

Share this post


Link to post
Share on other sites
I don''t see how this really can prevent look ahead attacks. With a known RNG algorithm, even if you do a seed-offset scheme, you can still try a definable known prefix attack, which relies on figuring out the internal state at a given point of the opposing RNG. Because the whole algorithm is completely transparent to both clients, it''s still possible to infer the value of the next random number to be generated without knowing either the seed or the offset. If you complicate the RNG algorithm to reduce the vulnerability to the definable known prefix attack, it could make the replay of the generated number stream at the end painfully slow.

And really, 32 bits plus a 16 bit offset isn''t going to give you that much more security over a 32 bit seed. It only helps when the actual seed generation is semi-deterministic (like seeding with system time). If it''s already assumed that the seed generation is fully entropic, adding an offset like that doesn''t grant any additional security.

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
Urk. That would require generating a new public/private key pair every X random numbers. Generating key pairs is hideously expensive. It's the equivilant of testing the primeness of random 300 digit numbers until you find two that are actually prime. Not only is this processor intensive, but it also creates unpredicatble processing requirements. In general, unpredictable processing requirements is bad for game programming.

If you're going to generate a new key every request, you might as well make them symmetric keys. Especially since you never take advantage of any of the properties of public key encryption in your algorithm.

You're right, but for most symetric key systems, there are attacks that can break the first many X (for those that use rounds), and in a crypto book I recently picked up they said there is recently a new kind of attack that might break most of them (still being worked out, but it looked primising), so I don't trust those kinds of encryption algorithms any more =-)
And of course, quantum computers can do prime factorization almost instantly, so they would break prime-based algorithms.

The world just isn't secure anymore =-P

You could use weak keys (32bits wouldn't take too long, would it?), no need for hundreds of bits. Like I said, short keys with long data looks like it would actually be more secure to me since it would be harder to find a key to make a decryption of random data look like you want.

[edited by - extrarius on November 15, 2003 4:32:06 PM]

Share this post


Link to post
Share on other sites
A prefix attack only works when using an incredibly simple random number generator, those that basically use it random number as the seed for the next number (and are thus very poor random number generators). IIRC even the VB random number generator uses a 160bit internal value to generate each "random" 32bit value. Thus there are many possible values to follow any specific value.

If you are really worried about this type of attack then you cycle. Every ten numbers you reseed (using the clock or some other random element). Keep in mind that the new random numbers only start appearing as the queue of previous random numbers are empty, so they will be overlapping and thus being included in the multiple hashes. This limits you to ten numbers to guess the seed before it is reset (and as said above, unless you''re using a stupidly simply [and not very well distributed] generator it should take more then 10 numbers to be able to guess right)

Share this post


Link to post
Share on other sites