Cryptographic protocols, again
tc...@lsa.umich.edu
that backgammon websites cheat with the dice. The responses I received
revealed that many people don't understand what I mean by cryptographic
protocols, so I thought I would give a brief explanation. The idea is
taken from the "Mental Poker" article that I mentioned previously.
The website and I agree on some publicly known cryptographic algorithm.
To roll the dice, I secretly choose a key, and encrypt thirty-six phrases:
"one one," "one two," "one three," etc. With a good algorithm, this
produces thirty-six random-looking strings of the same length. I send
these thirty-six strings to the website in some random order chosen by me,
without of course revealing my secret key. The website picks one of the
strings and sends it back to me. Upon receiving the chosen string, I
publicly reveal my secret key, and the thirty-six strings are publicly
decrypted (to prove that I really did encrypt all thirty-six dice rolls).
The (decrypted) chosen string is the dice roll.
It is hard for the website to cheat with the dice under such conditions.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Michael Petch
4a340800$0$507$b45e...@senator-bedfellow.mit.edu, "tc...@lsa.umich.edu"
<tc...@lsa.umich.edu> wrote:
> publicly reveal my secret key, and the thirty-six strings are publicly
> decrypted (to prove that I really did encrypt all thirty-six dice rolls).
> The (decrypted) chosen string is the dice roll.
>
> It is hard for the website to cheat with the dice under such conditions.
It appears the basic solution your trying to resolve is that of a 3rd party
server manipulation of the rolls. Server picks from a random set of strings
that it has no knowledge about, and is only decipherable when the originator
publicizes a key.
You could use simple PKI on each roll (I am not suggesting this as an ideal
mechanism - its costly in resources, but servers as an example). Generate a
public private keypair. Encrypt the 36 strings with your own private key AND
your public key. Send the 36 encrypted strings out, have the server pick
from a random set of strings it has no knowledge about and then send that
choice out to all the clients (And all 36 encrypted strings) and then reveal
your private key. Your private key will the allow for your self encrypted
message to be unencrypted by everyone else. Start over with a new
public/private key pair and do again.
Cryptographically this would be sound, server would need inordinate amount
of time/resources to break the private key by itself.
The problem. Lets say you have someone like "Murat" who believes that the
GnuDung cheats (And has professed it for eons), yet has all the source code
at his fingertips and can't pin point anything. How do you convince them
that a cryptographic technique is sound, or can't be easily broken by a
server.
Its trying to convince the layman that this works. How would you go about
proving to Murat that the mathematics (which he likely won't comprehend)
actually work.
I use Murat as an example because he represents the people that likely will
never understand the math and will still draw their own na�ve conclusions
even though reality says otherwise.
SSL works in a browser. Ask a normal user how it works (besides a little
icon appearing) and they likely don't have the faintest idea. Ask them why
they trust it, and they'll likely tell you they have to trust the software
(or not) that it "just" works.
Michael Petch
On 14/06/09 4:09 AM, in article C65A287B.1D679%mpe...@capp-sysware.com,
"Michael Petch" <mpe...@capp-sysware.com> wrote:
> You could use simple PKI on each roll (I am not suggesting this as an ideal
> mechanism - its costly in resources, but servers as an example).
I will point out that with PKI it would be easier to generate a single
private/public keypair, each user publishes his public key to the server
automagically. User then encrypts all the strings with his opponents public
key and his own private key, randomizes their order and sends them all to
the server. Server picks one of the 36 randomly and sends its choice and all
the strings to the opponent.
With games where there are more than 2 players the originator would have to
generate separate sets of encrypted strings for each target opponent. Server
would then have to forward the right set to each opponent along with the
random choice the server makes.
Because of the way PKI works, each user will be able to decrypt the sequence
with their own private key and the senders public key. No key regenration
would be needed.
Entire idea is for the server not to know ahead of time what data it is
actually randomizing.
tc...@lsa.umich.edu
Michael Petch <mpe...@capp-sysware.com> wrote:
>The problem. Lets say you have someone like "Murat" who believes that the
>GnuDung cheats (And has professed it for eons), yet has all the source code
>at his fingertips and can't pin point anything. How do you convince them
>that a cryptographic technique is sound, or can't be easily broken by a
>server.
First of all, as I have been at pains to emphasize before, the goal of the
cryptographic protocol is *not* to convince *everybody* that the website is
not cheating with the dice. That's an impossible task. I could bring my
own precision dice to a face-to-face game and *still* complain that my
opponent was cheating by manipulating my dice telekinetically.
The world is not solely composed of suckers and paranoids. There are people
in between. Without any cryptographic protocols in place, a perfectly
reasonable person can wonder whether the website is cheating. While most
websites are honest, my feeling (based not on experience, mind you, because
I've never played backgammon on any such site, but just on gut feeling) is
that there probably *are* sites out there that cheat. Whenever there is
money at stake, some people cheat. Cheating occasionally with the dice is
particularly tempting because it's hard to prove, and there will always be
plenty of people around who will believe that the website is not cheating.
With cryptographic protocols in place, only the people far on the paranoid
end of the spectrum will still think that the website is manipulating the
dice.
The second point to make is that some degree of reassurance about the
algorithm can be given by choosing an algorithm that has been public for
a long time and survived numerous concerted attempts at breaking it. For
further reassurance, the server could support a whole range of such public
algorithms and allow the user to choose one. The user would then have to
believe that the server was somehow capable of breaking *all* those public
algorithms and not just one.
At the risk of sounding like a broken record, I will emphasize once again
that of course, there is nothing one can do to convince extremely paranoid
people that a website is not cheating with the dice. The measures I've
suggested, however, make cheating very difficult, in contrast to the current
situation where cheating is easy.
Michael Petch
On 14/06/09 6:08 PM, in article
4a359101$0$502$b45e...@senator-bedfellow.mit.edu, "tc...@lsa.umich.edu"
<tc...@lsa.umich.edu> wrote:
> The second point to make is that some degree of reassurance about the
> algorithm can be given by choosing an algorithm that has been public for
> a long time and survived numerous concerted attempts at breaking it.
Exactly why I picked standard PKI. You could use an AES or DSA keys -
algorithms that are well known and have been validated mathematically and
are difficult to break and are widely used.
We really don't disagree.
My point really is - no matter how far you go, there will always be nay
sayers.
Now of course generally speaking with mental poker type problems you may
wish to do away with the server and make dice generation peer to peer. Each
side could theoretically exchange components of a random roll using a
cryptographic algorithm (Can't use PKI here of course) whereby at the end of
the exchange(s) both players can decode the complete roll with their
respective keys. A little easier said than done, but such algorithms are
documented to varying degrees.
tc...@lsa.umich.edu
Michael Petch <mpe...@capp-sysware.com> wrote:
>We really don't disagree.
>
>My point really is - no matter how far you go, there will always be nay
>sayers.
Although we don't really disagree, I find it puzzling that you would even
mention this obvious fact, as if it were relevant. Mentioning it makes it
sound like you think this fact is relevant.
>Now of course generally speaking with mental poker type problems you may
>wish to do away with the server and make dice generation peer to peer.
For example, as in the protocol I posted at the start of this thread.
Michael Petch
On 15/06/09 7:41 AM, in article
4a364f7e$0$515$b45e...@senator-bedfellow.mit.edu, "tc...@lsa.umich.edu"
<tc...@lsa.umich.edu> wrote:
> In article <C65B0780.1D6A6%mpe...@capp-sysware.com>,
> Michael Petch <mpe...@capp-sysware.com> wrote:
>> We really don't disagree.
>>
>> My point really is - no matter how far you go, there will always be nay
>> sayers.
>
> Although we don't really disagree, I find it puzzling that you would even
> mention this obvious fact, as if it were relevant. Mentioning it makes it
> sound like you think this fact is relevant.
I believe it is relevant. We will agree to disagree ;-)
>
>> Now of course generally speaking with mental poker type problems you may
>> wish to do away with the server and make dice generation peer to peer.
>
> For example, as in the protocol I posted at the start of this thread.
I said the case of PEER TO PEER. In this thread you described a non peer to
peer implementation requiring a 3rd party server (That server does the
randomization independent of the 2 clients).
Please quote the passage from THIS thread where you described a mechanism
involving NO server where two peers interact directly, where the clients
securely generate shared data that can be used to provide random rolls that
have not been tampered with (by either peer).
Some Backgammon servers are Peer to Peer based as well. The server is used
for matchmaking only (Allowing a company to reduce resources like CPU power,
bandwidth etc)). The game logic is maintained on the client including
randomization and all game state is managed entirely between the peers.
I bring it up, not because there is no solution (I know of one in use), but
because it is a form of the mental poker problem that you did not bring up
"in this thread".
tc...@lsa.umich.edu
Michael Petch <mpe...@capp-sysware.com> wrote:
>I said the case of PEER TO PEER. In this thread you described a non peer to
>peer implementation requiring a 3rd party server (That server does the
>randomization independent of the 2 clients).
Simply replace "website" with "opponent" in my original post.
Michael Petch
On 15/06/09 5:55 PM, in article
4a36df7d$0$500$b45e...@senator-bedfellow.mit.edu, "tc...@lsa.umich.edu"
<tc...@lsa.umich.edu> wrote:
> In article <C65C0A42.1D734%mpe...@capp-sysware.com>,
> Michael Petch <mpe...@capp-sysware.com> wrote:
>> I said the case of PEER TO PEER. In this thread you described a non peer to
>> peer implementation requiring a 3rd party server (That server does the
>> randomization independent of the 2 clients).
>
> Simply replace "website" with "opponent" in my original post.
Then your algorithm as stated is pretty much useless for P2P. Because you
don't address (even remotely) the requirement that either client can't
manipulate the random roll. If the opponent is the server and he generates
the roll how do you know he didn't use a Debugger and change the memory
location with the random number prior to it being encrypted (this is easy,
and in fact on msn gaming zone exactly how I defeated their dice years ago).
I state for the record, that what you proposed Is NOT valid where the
"server" is the opponent. There is an entire layer that is missing to handle
the actual randomization and make sure that it can't be manipulated by
either peer without it being detectable.
Your algorithm is very valid for the server environment because in that case
the selection can't be manipulated by the peers (Player A and B), and of
course since the server doesn't know what it has actually selected (you have
hidden that with encrypted entries) you can't manipulate it there either.
tc...@lsa.umich.edu
Michael Petch <mpe...@capp-sysware.com> wrote:
>Then your algorithm as stated is pretty much useless for P2P. Because you
>don't address (even remotely) the requirement that either client can't
>manipulate the random roll. If the opponent is the server and he generates
>the roll how do you know he didn't use a Debugger and change the memory
>location with the random number prior to it being encrypted (this is easy,
>and in fact on msn gaming zone exactly how I defeated their dice years ago).
I confess that I don't understand your objection. When you talk about
"generating a roll" and "encrypting a random number," what parts of my
protocol are you referring to?
To repeat my protocol, I encrypt thirty-six suitable plaintext strings and
send them to my opponent in an order chosen by me. My opponent chooses one
of those strings and sends it back to me. Then I reveal my secret key and
everything is decrypted. The chosen string is the roll (either my roll or my
opponent's roll; the protocol can be used either way around).
In this scenario, there isn't much my opponent can do to cheat. He has to
send me back one of the thirty-six things I sent or I won't accept it. I
suppose he might afterwards claim that he chose a different string from the
one he sent me, but I'm assuming that's not your objection.
For me to cheat, I would have to come up with a different secret key from
the real one, that successfully decrypts all the ciphertexts, but decrypts
(say) the encryption of "one two" into "three six" and vice versa. For most
crypt algorithms out there, this isn't feasible. For example, in RSA, I
can't lie about what the factors of pq are.
I can't see what part of this protocol you are referring to you when you
talk about changing memory locations with random numbers, or encrypting
random numbers.
Michael Petch
On 15/06/09 6:31 PM, in article
4a36e7c4$0$494$b45e...@senator-bedfellow.mit.edu, "tc...@lsa.umich.edu"
<tc...@lsa.umich.edu> wrote:
> To repeat my protocol, I encrypt thirty-six suitable plaintext strings and
> send them to my opponent in an order chosen by me. My opponent chooses one
> of those strings and sends it back to me. Then I reveal my secret key and
> everything is decrypted. The chosen string is the roll (either my roll or my
> opponent's roll; the protocol can be used either way around).
Actually I confess, that the answer to the solution lies in something I
thought you ommitted originally (However I suggested in my PKI
implementation). It was an oversight in how I read you original post.
Buried in your post was one word I missed "Random" order. Without that I
believed you were sending ORDERED packets.
Since I didn't see the word "random" there originally that was where my
point of contention was. I thought you were sending ordered data to the
Opponent/Server where they randomly select.
Anyway, with everyone on the same page - I can say that this method works,
and is actually one that has already been implemented. I have personally
used a similar technique on a P2P product I had developed (Was why I was
leaning towards the PKI and hashing). Because that solution was one I was
familiar with.
Well now I can put an end to my responses to this thread. I am not in
disagreement :) on your actual implementation.
tc...@lsa.umich.edu
Michael Petch <mpe...@capp-sysware.com> wrote:
>Well now I can put an end to my responses to this thread. I am not in
>disagreement :) on your actual implementation.
Glad to see we finally agree on this point!
By the way, while looking back through this thread, I noticed that my comment
about the "irrelevance" of your point about diehard skeptics came across as
rude. I apologize for that; it was a product of my frustration that this
same (non-)objection seemed to keep coming up over and over again.
Also, thank you very much for your very helpful pointers on the bug-gnubg list.
Michael Petch
On 15/06/09 7:59 PM, in article
4a36fc7d$0$509$b45e...@senator-bedfellow.mit.edu, "tc...@lsa.umich.edu"
<tc...@lsa.umich.edu> wrote:
> In article <C65C49D3.1D74C%mpe...@capp-sysware.com>,
> Michael Petch <mpe...@capp-sysware.com> wrote:
>> Well now I can put an end to my responses to this thread. I am not in
>> disagreement :) on your actual implementation.
>
> Glad to see we finally agree on this point!
>
> By the way, while looking back through this thread, I noticed that my comment
> about the "irrelevance" of your point about diehard skeptics came across as
> rude. I apologize for that; it was a product of my frustration that this
> same (non-)objection seemed to keep coming up over and over again.
>
> Also, thank you very much for your very helpful pointers on the bug-gnubg
> list.
No problem. If I thought it was overly rude I would have given up on the
thread long ago.
Your ideas have merit. I was just trying to understand your proposal... Was
my fault to have missed one key point in the original post. Missing it
wasn't intentional, but caused a pile of unnecessary messages. I could
understand why you thought I was being intentionally anal the whole time!
MaxM
(I'm no expert at all in cryptograph).
To me, playing for money online requires something that guarantees the
randmoness/non-manipulation of
the dice/cards. Also, I would feel more comfortable if the method
would not involve a third party (you will
never be sure the third party is not corrupted/biased).
I came up with something like this (imagine for a second bg is played
with a single dice, extension is trivial):
1- Before the game:
1.1- Each player generates (whichever manner) on his side a long
(10000) sequence of numbers in the range 1-6
1.2- Each player encrypts its entire sequence with a key and sends
it to the opponent.
2- During the game:
2.1- At each turn, each player pops a number from its sequence and
sends it to the other player.
2.2- The player on roll sums (modulo 6, +1) the 2 numbers to obtain
the value of the dice (player not on roll does the same, to verify).
3- At the end of the game/match:
3.1- Each player communicates its own key, so that each player can
decrypt the entire other player's sequence and check that it matches
the communicated numbers.
I'm not sure if, once we have used most of the numbers in the
sequence, the key could become easy to crack (disclosing the rest of
the sequence), that may depend on the chosen algortihm. Possible
solution: if the sequence is 10000 numbers, generate a new one as soon
as you've eaten up 50% of it (or whichever percentage is considered as
safe from a cryptographic point of view), eventually encrypt it with a
different key.
The thing I like most of this is that the sequences are "available"
before the match: it's like having the list of rolls locked in a chest
before the match, but being allowed to open it only at the end of the
match. This should avoid ad-hoc dice manipulations, i.e. giving a
large double in a race to the player that is below in the score, to
make the match more excting or to favor the underdog.
MaX.
Piranha
Regardless of method, whether it is practical or causes heavy load on
the server, the question is, HOW do you want to do it on the players
end?
1) Automatically?
The software picks a random number out of a random sequence of
encrypted data, without either of the players has to click a button or
something? It is sent to the opponent or the server and returned
automatically?
What´s the point?
Even with open source software like GNU, people still believe it
cheats on the dice, simply because 99.9% of the players don´t have the
slightest clue of programming and out of the ones who have a clue,
there still is a good percentage who refuse to even look at the
source, because they know for a fact it cheats, they don´t have to
verify it.
If the software is not open source, how many people do you think would
trust the word of the programmer, that he has implemented this
properly?
Even if it was all implemented correct, even if was perfectly secure
and there was no way that a programmer could have done anything at all
to manipulate it, how do you make this transparent to a player who has
no idea about programming, nor encrypting?
Any bet, even among professional programmers you would convince only a
tiny fraction of players.
2) Manually?
Players gets a sequence of encrypted data on the screen and have to
pick from the list?
First of all that would cause big protest among those who don´t
believe in cheat, as this would be a completely unneccessary,
uncomfortable and time consuming procedure.
And still it wouldn´t convince anyone, even if you reveal the
decrypted data at the end of the match, players without knowledge in
encrypting/decrypting cannot tell afterwards, whether or not the
decrypted data matches the encrypted data.
I would even bet, this would extend the problem, as players will
frequently come up with statements like "I am sure I did not click on
that string, the server must have altered my choice".
I once played a testmatch over MSN Messenger with a friend who
believes in rigged dice and I was trying to convince him there is no
cheat.
The setup was:
Both of us used our own BG-Software, I played against my Snowie, he
played against his, both set to 3-ply precise, both set dicerolls to
manual.
I´ve used my precision dice and rolled them on my real board.
I´ve typed all rolls into messenger chat, and we both put them into
Snowie as the actual rolls, without either of us knew the position or
score of the other.
We both did our move (or waited for Snowie to move) before I would
roll again.
I´ve even used different colored dice and included the color of each
die, so in case the roll was an initial roll for either of us, we used
red for Snowie and green for ours.
It was time consuming and uncomfortable, but we did it anyway, just
out of curiosity about the outcome.
Snowie won both matches, I don´t really recall the scores, something
like 7:4 against me and 7:2 against him.
Now you might say, I had an opportunity to cheat on my game, basically
I wouldn´t have needed to play against Snowie myself, I just did,
because I was curious to see whether or not I could do better than
him, but from start we never considered the outcome of my match valid
for anything.
But for my friend, latest from 3rd or 4th roll on it was clear, I
couldn´t know his position (there was no webcam involved), I couldn´t
even know whos turn it was, or what roll would fit into his current
position. Even if I had tried to bring up some weird sequence, I wouldn
´t have known whom (if anyone) I give an advantage.
My friend found a LOT of similarities between his match and his
"normal" matches against his robot, unbelievable jokers, big doubles
in races etc., but due our setup he could be sure, there was no way
his Snowie could have cheated on the dice, so he had to admit, Snowie
was either lucky or skillful, but no cheat.
However, up to today he still believes in rigged dice, within his own
robot as well as on almost all online servers.
Regardless whether some sites or robots cheat or not, regardless what
kind of perfectly secure thing you would implement to disable
cheating, 99% of those who currently believe in cheat will keep
believing in rigged dice, no matter what.
Some servers used to have certified dice generators, paying a lot of
money to an independent company to certify the randomness of their
dice, but the effect on the amount of complaints about rigged dice was
near zero.
In other words, the effect of implementing anything is never worth the
efford, and that´s why most servers don´t bother anymore, whether or
not a handful of professional programmers could be convinced about
fair dice is meaningless.
Last but not least:
IF a server doesn´t cheat on the dice, and the effect of implementing
perfect proof for that is near zero, they won´t spend a lot of money
and manpower to implement it.
IF a server does cheat, they won´t have any intention of implementing
anything.
In the end it´s a matter of trust, and it will remain that way.
tc...@lsa.umich.edu
1. I agree that cryptographic protocols might not make a significant
difference. It could be that most people are either suckers or paranoids,
and that the "in-between" region of people whose level of trust would
increase by means of such protocols is too small. However, I don't think
that you have any more *a priori* insight into the size of this population
than I do. It's an empirical question, and that size cannot be estimated
accurately by armchair theorizing---only by experimental observation. Thus
I think the experiment is worth doing.
2. Even if the in-between population is small, cryptographic protocols could
reduce the number of websites that actually cheat. To my mind, that would be
a win, even if the percentages of people who *believe* that there is (or is
not) cheating remains constant.
3. Certainly there should not be a single "one-size-fits-all" user interface.
People who don't care shouldn't be forced to care. But for people who do
care, it should be possible to do what they want to do.
4. It's true that the general level of education right now means that almost
nobody will understand what's going on with a cryptographic protocol. My
attitude, however, is to be optimistic with educational issues. Otherwise
you remained mired in ignorance and stay there, with no possibility of
raising the level. In the specific case of cryptographic protocols, there
already exists some level of familiarity among the general public, because
of electronic banking. In fact, the online banking case serves as a good
comparison. I claim that it's more secure to have our online credit card
transactions protected cryptographically than not. True, most people don't
understand what's going on. But there are a few watchdogs out there whose
job it is to make sure that the software and the cryptography out there is
good. I have to trust the watchdogs, but that is easier to do than to trust
people who have a financial incentive to cheat me out of my money. If your
attitude were to prevail, we wouldn't have any crypt out there at all.
Piranha
If my attitude were to prevail, we wouldn´t have credit cards in the
first place, at least not in the current form.
I would replace pin codes by a simple automated phone call, where the
owner of the card has to confirm a payment.
Doesn´t make much differencer for either side, instead of typing his
pin, the user has to press a button on his phone, and instead of heavy
encryption, credit card numbers could be submitted in plain text,
while a computerized phonecall initiated from the company to the user
leaves no options for 3rd parties.
But that´s another story, I´m no banker and I´m sure there are several
things I´m overlooking here, so don´t take this one too serious.
However, for backgammon and proof of random dice, I believe the
solution is far easier, in fact I´m currently implementing such a
thing into my own server project and it doesn´t require any kind of
encryption while it is perfectly transparent and easy, so about anyone
can understand it.
I guess we can agree, if the dice are generated in advance, nobody can
suspect a manipulation, simply because at the time of number
generation the server doesn´t know who will get the roll or what
position he will have on his board at that time.
So what I´m doing is:
- Generate at server boot 10,000 numbers in advance and store them in
an array.
- Use these numbers for any kind of need, no matter which function on
the server needs one or more random number(s), picks the first number
from the array and deletes it after use, while an independent thread
keeps filling up at the bottom end.
Only problem left is, how to make this transparent to the user.
My solution is simple: Publish them in advance.
All it takes is two tables, one that lists the numbers waiting for use
and another that adds to each number the function it was used for, a
few minutes after it has been used.
If that´s for example on a website that requires refreshing by the
users, from about a dozen matches in progress on, maybe in different
rooms, maybe even several different games, like Poker and BG
simultanous, there won´t be any problem publishing numbers in advance.
From about 100 simultanous matches on even update in realtime wouldn´t
be a problem, the numbers would scroll up just too fast to predict
anything, and you have a perfect secure and transparent proof for
random dice without any need for encryption and without any option to
manipulate anything for anyone.
tc...@lsa.umich.edu
This could work, but there are potential implementation issues. Depending on
how you publish the numbers in advance, someone could potentially write a bot
that instantly analyzes the numbers and uses them to get an advantage. If my
bot knows what my opponent is going to roll then obviously it can advise me
how to play my checkers. Even if the bot only knows that my opponent's roll
is one of 25 different possibilities, I get an advantage.
And of course if the roll is not published until after I make the move then
I can always suspect that it was not *generated* until after I made my move.
Piranha
> In article <afb94834-1b1c-4e9f-bb4d-7aaca9d8f...@j12g2000vbl.googlegroups.com>,
That´s why I said, you need a given amount of games in progress
simultanous, before this could be done (at least the publishing part).
We can discuss how many that would be, I would guess, if all functions
that require random numbers combined require about 100 numbers per
second there is no prediction possible anymore.
IF you would try to have a robot in between, that tries to predict
what roll you will get, and suggests what to move based on the
prediction, by the time you have seen the prediction the roll you
actually get will already be a different one.
In a list of only 6 possible numbers, the same number appears on
average every 6 rows, the same combination appears every 18 (or 36 for
doubles) rows so even a robot wouldn´t be able to tell, where in the
list you currently are, if the use of a number is published lets say 5
mins (or 30.000 numbers) later.
Last but not least, this would require a pretty sophisticated piece of
robot, one that can read numbers from an HTML page and positions from
a client software, as well as analyse positions in realtime.
The teams of Snowie and GNU will certainly not write such an add on,
meaning you´d have to write the whole thing from scratch by yourself.
Compared to the minimal chance that someone might get a minimal
advantage out of it, I highly doubt anyone would invest the time to
write such a robot.
Even if someone writes such a thing, I would guess, by the time he is
done, the servers reputation for fair dice would be stable enough to
cancel the publishing part.
If nothing else, all the server would have to do is slightly alter the
use, i.e. skip every 3rd number in the list upon use and your robot
would predict nonsense right away.
Michael Petch
On 19/06/09 12:42 PM, in article
afb94834-1b1c-4e9f...@j12g2000vbl.googlegroups.com, "Piranha"
<eu_pi...@gmx.net> wrote:
> Only problem left is, how to make this transparent to the user.
> My solution is simple: Publish them in advance.
> All it takes is two tables, one that lists the numbers waiting for use
> and another that adds to each number the function it was used for, a
> few minutes after it has been used.
There are subtle problems with this. See an algorithm like Tim or I would
use doesn't allow for the server, its owners, or an opponent the ability to
manipulate the dice.
Lets say I have a predefined array of numbers like you suggest on the
server, and all the stats are available. Requests come from a variety of
tables. How do we know someone on the server isn't play games with the order
the requests are being processed.
Lets say I have a fixed set of numbers. And I have incoming requests. Lets
say I run the server and I have a friend who needs a 4 to come off the bar.
If the server is busy I can in theory queue up my friends request and wait
for the right moment and say "Oh there's the client request", lets give him
the 4 that's next in the random queue. When I say "the right moment", I
could hold off my friends request (You can't prove this isn't happening from
a player perspective) and let other requests in first. Then when needed you
add your friend into the queue when the next "4" is available. On a server
with lots of traffic this wouldn't take any time at all.
Since we as players can't see what's on the server or how things arrive (You
could easily change the order of the requests that came in and players would
never be able to prove it).
You need a mechanism where there this type of subtle manipulation by the
server can't take place. A solution as Tim proposes doesn't make this easy
unless you try to determine the keys via some method (brute force etc). The
time required to brute force would likely be so large that the delays in a
game would be huge (days, months, years depending on the encryption
algorithm and key size).
The downside is increased processor requirements (on the clients) to deal
with key generation and encryption. This doesn't cost the server anything.
However the server will need to proxy all the extra data between clients and
that will drive up server bandwidth usage (and potential extra bandwidth
costs), and cause potential delays in forwarding the packets.
Peer to Peer implementations where the server is used for matchmaking (And
for helping the clients punch through NAT and firewalls using techniques
like UDP hole punching) keep the traffic to the server to a minimum, and the
data is transmitted directly between the peers. Cost of extra bandwidth
becomes an issue for the users (not the server), and given most ISP plans -
the amount of extra data for each user is probably negligible and would
never be noticed.
Piranha
Michael,
as always, of course you are right, but besides the fact that NAT
traversal isn´t always possible (I can tell, I´m sitting behind such a
NAT where any attempt of hole punching has failed so far), there is
the "normal" user.
Try to explain to a "normal" user that your encrypted data exchange is
perfectly secure, any bet, most players will keep asking about
possibilities to crack the code and at some point you will have to
admit, it may be highly unlikely, yet not impossible.
The result is the same as with dice generating itself.
Users keep asking how random computer generated dice are compared to
real dice, anyone can easily find on the web 100s of articles about
weak or strong random generators, where about all these articles at
some point mention, it is NOT absolute random, it is "pseudo" random,
nearly random, but not truly.
The "normal" user doesn´t realize, real dice (at least the non
precision ones) are far less random than computer generated dice, the
"normal" user doesn´t realize that "pseudo" random means only the need
for a seed and the result may be only a tiny difference in
distribution, something like one more 4 in first 10 million rolls and
one less in next 10 million, the "normal" user concludes, the dice are
rigged and they automatically follow up, it is all manipulated.
Either way, I guess neither of us will silence the suspicions, somehow
any efford to increase security makes users believe the existing
system must be junk, therefore, while a new system is not in place
yet, everybody is convinced everything is manipulated everywhere.
If there is nobody at the server end willing to manipulate anything,
no corrupt programmer helping his friends, there is no need for
encrypted dicerolls.
If someone wants to manipulate something at the server end, there are
100 ways to do that and encrypted data won´t stop them.
If suspicions go as deep as the programming level, there is nothing
anyone could do to prevent cheating, let alone silence rumors, a
programmer has any option to retrieve any encryption key before you
even start playing, a programmer has any option to either let your
opponent roll dice on will or know in advance what the next roll will
be.
At programming level, it´s a matter of trust, above that increased
security on dicerolls isn´t necessary.
I believe an easy and transparent system will give the users much more
than any highly sophisticated encryption, perfect security doesn´t
exist either way.
tc...@lsa.umich.edu
Piranha <eu_pi...@gmx.net> wrote:
>The "normal" user doesn�t realize, real dice (at least the non
>precision ones) are far less random than computer generated dice, the
>"normal" user doesn�t realize that "pseudo" random means only the need
>for a seed and the result may be only a tiny difference in
>distribution, something like one more 4 in first 10 million rolls and
>one less in next 10 million, the "normal" user concludes, the dice are
>rigged and they automatically follow up, it is all manipulated.
There's one additional point I'd like to make regarding a cryptographic
protocol versus computer-generate dice, which is the role of human psychology.
Users don't trust the pseudorandom number generator because they feel it
is *not under their control*. They like manual dice because they have a
much stronger sense of being in control. It doesn't matter so much that
the manual dice are not really random.
It's like driving. Many people prefer to drive long distances instead of
taking an airplane because they feel that they're in control behind the
wheel. They will feel safer, even if objectively speaking their risk of
injury and death is much greater.
In the cryptographic protocol I mentioned, users get a sense of control by
choosing their own password, and choosing a scrambled order to send to the
server or the opponent. I think this will make a big psychological
difference. It's true that they don't get to choose their own algorithm,
so that may make them somewhat uneasy. But I think that it's easier for
people to trust that a well-tested piece of technology is sound than it
is for them to trust that dice *generated by someone else* are sound. Most
people trust the mechanical performance of their cars, especially after
they've driven them for a while.
Michael Petch
On 19/06/09 5:56 PM, in article
1882069d-6f1c-4696...@t11g2000vbc.googlegroups.com, "Piranha"
<eu_pi...@gmx.net> wrote:
> Michael,
> as always, of course you are right, but besides the fact that NAT
> traversal isn�t always possible (I can tell, I�m sitting behind such a
> NAT where any attempt of hole punching has failed so far), there is
> the "normal" user.
Very fair. I have learned about 75-80% of the traffic I see works with hole
punching. If hole punching doesn't succeed then one can fall back to the
server approach. If you can drop server based traffic to 75-80% it can help.
As for the 20-25% , it happens.
> Try to explain to a "normal" user that your encrypted data exchange is
> perfectly secure, any bet, most players will keep asking about
> possibilities to crack the code and at some point you will have to
> admit, it may be highly unlikely, yet not impossible.
This of course is fair observation. I mentioned this to Tim before. There
will be the naysayers who are totally paranoid that you'll never convince.
> The result is the same as with dice generating itself.
> Users keep asking how random computer generated dice are compared to
> real dice, anyone can easily find on the web 100s of articles about
> weak or strong random generators, where about all these articles at
> some point mention, it is NOT absolute random, it is "pseudo" random,
> nearly random, but not truly.
[snip]
> The "normal" user doesn�t realize, real dice (at least the non
> precision ones) are far less random than computer generated dice, the
> "normal" user doesn�t realize that "pseudo" random means only the need
> for a seed and the result may be only a tiny difference in
> distribution, something like one more 4 in first 10 million rolls and
> one less in next 10 million, the "normal" user concludes, the dice are
> rigged and they automatically follow up, it is all manipulated.
>
One of the advantages to an approach like Tim though is the ability for the
developer to put some control into the users hand. For instance one could
define a "paranoid interface" where PlayerA that generates all 36 of the
encrypt rolls can choose to reshuffle all the random entries again. PlayerA
has a choice of how to randomize the first leg.
The "Paranoid" interface would allow the recipient of the sequence of 36
encrypted (and pre randomized entries) to pick the encrypted entry they wish
to use for a roll (if thy wish to always pick the first one in the list that
is their choice). There really is no requirement for the recipient to have
his computer make the choice for him... The user would be given it. Once the
users choice is made the encrypted response is sent back.
Once the complete exchange is done then the "Paranoid" interface displays
all the encrypted entries to both users, and the chosen encrypted string.
Showing all the encrypted strings shows either player that the strings are
as they were when they started, that all the rolls are represented). If the
encrypted strings hve been tampered with it will be detectable when
unencrypted.
What all does this give the paranoid player. It gives them a chance to be a
master of their own fate. Of course there will still be the naysayers,
however the naysayers had a choice, both in pre randomizing (shuffling) and
then the other player given the choice to manually choose.
The Non-Paranoid interface would simply be one where no choices are given.
Data is auotmagically randomized. The other user if they are not paranoid
would allow the computer to pick the random string arbitrarily - that it
wants for the roll. However in non paranoid mode the unecrypted data should
be validated to make sure it wasn't tampered with, and notify the users.
> At programming level, it�s a matter of trust, above that increased
> security on dicerolls isn�t necessary.
> I believe an easy and transparent system will give the users much more
> than any highly sophisticated encryption, perfect security doesn�t
> exist either way.
Problem is your server side implementation may not be transparent and can be
manipulated. Most people who don't care about the server may not have been
able to point out my concern.
I disagree. If you give the choices to an end user to decided their own
fate, and make it cryptographically sound that people who understand the
math - even better. Most people may not understand the math but if they are
given control on both sides then its much harder for them to say it was
rigged.
For those who understand the math/premise, they don't need to be worried
about any potential manipulation on a server they have no control of. The
advantage to Tim's method is that the server or the opponent can be totally
untrustworthy and it will still work.
Peter Schneider
<tc...@lsa.umich.edu> wrote
> To roll the dice, I secretly choose a key, and encrypt thirty-six
> phrases:
> "one one," "one two," "one three," etc. With a good algorithm, this
> produces thirty-six random-looking strings of the same length. I send
> these thirty-six strings to the website in some random order chosen by
> me,
> without of course revealing my secret key. The website picks one of the
> strings and sends it back to me. Upon receiving the chosen string, I
> publicly reveal my secret key, and the thirty-six strings are publicly
> decrypted (to prove that I really did encrypt all thirty-six dice rolls).
> The (decrypted) chosen string is the dice roll.
>
> It is hard for the website to cheat with the dice under such conditions.
Let me raise a few objections -- "For it is a strange thing, but apparently
true, that those who speak speak rather for the pleasure of speaking
against than for the pleasure of speaking with, and the reason for that is
perhaps this, that in agreement the voice can not be raised perhaps quite
so high as it can in disagreement." (Beckett, Watt). Something I was
longing to say here for the longest time :-).
The most obvious first:
** If you use binary client software
** from somewhere (the usual case, right?), all the
** effort is futile and you can
** let the server roll directly for you right away.
** The level of safety is exactly equivalent.
The next thing that comes to mind is that another indirection of encryption
would be needed in order to protect a potential victim from an alliance
between a malicious server and a malicious opponent; as discussed in
another branch of this thread the safer way is to play peer to peer.
When playing peer to peer a cheater must exploit a weakness in the victim's
software. There may be more weaknesses than one thinks, even in rock solid
open source software.
-- The cryptography may be weak, cf.
http://www.us-cert.gov/cas/techalerts/TA08-137A.html.
-- The shuffling may be bad: Complete predictability is not required; the
detection of an anomaly is sufficient to make somebody a victim. Michael
discussed bad prng some time ago, I believe. And the SSL bug mentioned
above was actually a [p]rng bug.
-- The victim's software may lack some of the tests required in order to
check that the opponent doesn't cheat (the victim doesn't decrypt and check
all of the unused strings, for example, like a protocol conformant first
prototype might). A malicious client or server may test for that and
exploit it.
It's worth mentioning that many of the requirements for correctness are
well outside of the control of the client or server software proper, think
of libssl or /dev/random. They rely on properly maintained systems. (Yes,
the software could re-implement much of that but the result would likely be
even worse.)
The potential benefits for a cheating client of a victim's broken prng are
certainly smaller than if rolls are generated directly by a malicious
server though, and it's true that a *server* (or peer) cannot cheat when
the client is shuffling, encrypting and checking properly.
--
The bottomline may be: A good idea when used peer to peer with open source
software using the latest updates for the system and software proper.
Best,
Peter aka the juggler
Michael Petch
On 22/06/09 7:16 AM, in article 7a9efeF...@mid.individual.net, "Peter
Schneider" <schneiderp...@gmx.net> wrote:
>
> The next thing that comes to mind is that another indirection of encryption
> would be needed in order to protect a potential victim from an alliance
> between a malicious server and a malicious opponent; as discussed in
> another branch of this thread the safer way is to play peer to peer.
>
Of course the scenario that comes to mind (if a 3rd party server actually
rolled the dice) would be one like:
ClientA and MaliciousServer are working together and ClientB is a normal
user/client. If you have the MaliciousServer pick the dice, the one thing
you can't prove (with the current algorithm) is that ClientA didn't send to
the server a copy of the key used to encrypt the 36 sets of strings. If the
server did receive the key from Client A - Client B would never know this.
The Server could decrypt the 36 strings look at the unencrypted strings then
make a choice knowing which string is which.
This is why the choice should be given to ClientB (The user picks). So even
if it passes through the server, the server has no control over the choice
ClientB will make.
> -- The shuffling may be bad: Complete predictability is not required; the
> detection of an anomaly is sufficient to make somebody a victim. Michael
> discussed bad prng some time ago, I believe. And the SSL bug mentioned
> above was actually a [p]rng bug.
Even with good random numbers, you can still botch the shuffling in card
games. For example a lot of people who use Knuth Shuffle often implement the
shuffle incorrectly (Array looping being off by one) and end up with less
than ideal shuffles.
> -- The victim's software may lack some of the tests required in order to
> check that the opponent doesn't cheat (the victim doesn't decrypt and check
> all of the unused strings, for example, like a protocol conformant first
> prototype might). A malicious client or server may test for that and
> exploit it.
>
I discussed a paranoid interface in a previous post that would show all of
the data to the users (encrypted and unencrypted). However the entire
interface to the user could be faked if ClientB was given special malicious
version of the software.
One mechanism to help prevent this would be to have a TRUSTED and
accountable third party (organization) build the source code into binaries
and digitally sign them. The other method would be to make the client source
code available so that it can be built by a user directly. This would allow
people to inspect the code, build it and then use it. You *could* use a more
restrictive license than the GPL that doesn't allow for redistribution or
reuse of the code without violating the license and copyrights.
If a user can have a way to validate the client then tampering by the
software manufacturer becomes that much more difficult.
>
> The bottomline may be: A good idea when used peer to peer with open source
> software using the latest updates for the system and software proper.
>
My observation and idea above is similar in nature.
I think trust in the actual client software and what it is actually showing
(and doing) with the user is the key problem to overcome. "Does the client
software represent to the user what it is actually happening". "Does it have
implementation weaknesses that can be exploited". Those are good questions.
Michael Petch
There are many ways to achieve a certain goal. Another method one could
consider is this (This should work via an untrusted server in the middle or
peer to peer):
When it is time to roll:
ClientA generates a fixed number (128bits, 256 or whatever is needed) of
random bits.
ClientA generates a random Passkey to encrypt the random data
ClientA Encrypts the data and Sends the packet to client B
Simultaneously this occurs:
ClientB generates a fixed number (128bits, 256 or whatever is needed) of
random bits (Same number of bits are generated by both clients).
ClientB generates a random Passkey to encrypt the random data
ClientB Encrypts the data and Sends the packet to client A
Each client waits for the encrypted data from the other. When a client
receives the encrypted data from the other end, it then turns around and
send the other side the passkey needed to decrypt the encrypted packet it
just sent to the other client. The decryption process checks for tampering
to ensure that the received encrypted data packet is valid.
Client A and B now have 2 sets of bits. A set they generated and a set that
was generated from the other client. The 2 sets of bits Are XOR'ed by both
clients independently (Both clients should arrive at the same combined
value). The combined Value is then converted into a roll by each client.
Each client in essence generates the same dice roll from combined data
generated by by both sides.
If it is Client A's roll then Client A's player makes its move and send the
resulting position to Client B. Client B then validates the move by making
sure that the move is legal given the roll it computed. If a side properly
checks the move made by the opposing Player and compare it with the dice
roll it computed then one can determine whether there was any manipulation
by either side and notify the users.
If either Client generates a non random number (lets say one client hacked
the value before encryption) then when it is XOR'ed with the opposing
players value - it should still be random. If both clients have hacked
software and both are manipulating the values being sent then the resulting
roll may not be known but may not be completely random. If both clients are
compromised, that is there problem.
If a server is used to transport (proxy) the data between clients then it is
possible for collusion to occur between the server and one of the clients.
Since data from the other client is needed to produce a final random
sequence - its not possible for the server to know the final roll either -
until both passkeys are passed between the clients. So even though the
server sees the data and can attempt to manipulate it - it will either be
detectable by the clients or the unencrypted result is known too late for
the server to manipulate anything.
This all assumes that a functioning client can properly detect (without
bugs) that a move is legal or illegal based on a given roll.
Michael Petch
based on a Pseudo RNG. As Peter suggested using a source such as /dev/random
on modern Unix systems or the corresponding Microsoft crypto API on windows
should suffice. As well as any external hardware based random number
generator that is available and accessible to the client should work. One
could give the ability for the Players to enter their own random bits
manually (They could retrieve them from random sources that may not be
available directly to their computer).