Bitcoin Forum
April 16, 2014, 01:38:55 PM *
News: ♦♦ A bug in OpenSSL, used by Bitcoin-Qt/Bitcoin Core, could allow your bitcoins to be stolen. Immediately updating Bitcoin Core to 0.9.1 is required in some cases, especially if you're using 0.9.0. Download. More info.
The same bug also affected the forum. Changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Beware bitZino shuffling algorithm leaves much to be desired...  (Read 3713 times)
Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
June 30, 2012, 06:38:14 PM
 #1

The supposed "Provably Fair Shuffling Through Cryptography" https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html leaves much to be desired to be called "Provably fair".

These are only a few reasons:

(1) Client_seed is not big enough (32 bits) to assure a fair statistical distribution. The server can try each possibility in advance...

(2) The server knows the shuffled deck (every card) BEFORE the user, so the server can abort the game (showing any strange error message) if the deck is too good for the user.

(3) Last but not least, the site is HTML5 only (no open source client application), so there is no way to know if the client-side javaScript code is actually verifying anything !!!

(4) Where is the "proof" for the "Provably Fair" algorithm?

The only way to implement secure card games on the Internet is by using Mental Poker protocols (crypto newbies, check it on Wikipedia). And it happens that I designed the fastest MP protocol so far... humbly  Smiley


Best regards,
 Sergio.















1397655535
Hero Member
*
Offline Offline

Posts: 1397655535

View Profile Personal Message (Offline)

Ignore
1397655535
Reply with quote  #2

1397655535
Report to moderator
1397655535
Hero Member
*
Offline Offline

Posts: 1397655535

View Profile Personal Message (Offline)

Ignore
1397655535
Reply with quote  #2

1397655535
Report to moderator
1397655535
Hero Member
*
Offline Offline

Posts: 1397655535

View Profile Personal Message (Offline)

Ignore
1397655535
Reply with quote  #2

1397655535
Report to moderator
Pre-order Cloud Mining Power. Cheapest price.
2 Ph/s in stock.
INVEST NOW  >

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1397655535
Hero Member
*
Offline Offline

Posts: 1397655535

View Profile Personal Message (Offline)

Ignore
1397655535
Reply with quote  #2

1397655535
Report to moderator
1397655535
Hero Member
*
Offline Offline

Posts: 1397655535

View Profile Personal Message (Offline)

Ignore
1397655535
Reply with quote  #2

1397655535
Report to moderator
Boussac
Hero Member
*****
Offline Offline

Activity: 1008


e-ducat.fr


View Profile WWW

Ignore
June 30, 2012, 08:38:54 PM
 #2

Bravo for spotting the weakness in their claim of provability.
Can you tell us more about your protocol ?
Is it implemented on a poker site ?

The European Exchange - Casascius Coins, shipped from Paris since 2011: microbitcoin.net - PGP: 77272396
vuce
Sr. Member
****
Offline Offline

Activity: 476


View Profile

Ignore
June 30, 2012, 08:55:55 PM
 #3

Bravo for spotting the weakness in their claim of provability.
Can you tell us more about your protocol ?
Is it implemented on a poker site ?
http://www.dc.uba.ar/inv/tesis/licenciatura/2010/lerner

this is... wow.
libertaad
Sr. Member
****
Offline Offline

Activity: 266



View Profile WWW

Ignore
June 30, 2012, 09:35:42 PM
 #4

The supposed "Provably Fair Shuffling Through Cryptography" https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html leaves much to be desired to be called "Provably fair".

Hi Sergio! I'm the owner and primary developer of bitZino. Thanks for the feedback! I relish the opportunity to defend our approach to shuffling as truly Provably Fair. I firmly believe that the best cryptography is that which is practiced in the open, with honest and open discussion about any possible weaknesses or avenues of attack.

I believe that the blog post you linked to has a pretty good discussion about most of your points, but I'll take the time to individually address all of your critiques:

(1) Client_seed is not big enough (32 bits) to assure a fair statistical distribution. The server can try each possibility in advance...

The client_seed is only used to reshuffle the deck, so it's not necessary to use it to be able to represent the full set of possible decks. In effect, the reshuffling is like cutting the deck, but significantly more robust. Even if the server could analyze all possible deck combinations before each shuffle, it wouldn't help. This is because the Mersenne Twister has the property of having a Uniform Distribution, which means the avenue of attack of "creating a pre-shuffled deck such that all possible re-shuffled decks still favor the house" is impossible.

(2) The server knows the shuffled deck (every card) BEFORE the user, so the server can abort the game (showing any strange error message) if the deck is too good for the user.

Even if there is a server error prior to the deal, the user can still confirm that the server didn't change the pre-shuffled deck - as long as the `Hash(secret)` which is presented to the user doesn't change when the user reloads the page, they will know the server is being honest. I do agree though, that if the `Hash(secret)` changes,  this would be a clear indication that the house is cheating.

(3) Last but not least, the site is HTML5 only (no open source client application), so there is no way to know if the client-side javaScript code is actually verifying anything !!!

The code for the Javascript Hand Verifier is indeed open source! If you view the source for that page, you will see the algorithm implemented in 100 lined of clean, well-commented javascript. If you don't trust the javascript though, you are free to re-implement your own verifier - that's why I created the detailed blog post as well as the reference javascript implementation - I want to be as open about this whole process as possible.

(4) Where is the "proof" for the "Provably Fair" algorithm?

Ok, I admit there is no rigorous mathematical proof to accompany the algorithm - but that's why it's not "Proven" - it's just "Provable".  I do believe a rigorous mathematical proof could accompany this, and prove that it would be NP hard to cheat a user at dealing if this algorithm is followed. You could say it's just in the theory stage right now Smiley


The only way to implement secure card games on the Internet is by using Mental Poker protocols (crypto newbies, check it on Wikipedia). And it happens that I designed the fastest MP protocol so far... humbly  Smiley

A link to the wikipedia Mental Poker page, for the lazy Smiley I'm a big fan of these types of approaches, and the general guiding principal is what drove me to make bitZino provably fair. But, I disagree on your assessment that MP is the only way to have a secure game. MP is great for situations when neither player can know the shuffle of the deck. But in a casino game's use case, it is not a problem for the house to know the shuffle - as long as it doesn't know the shuffle until the moment the game is dealt (again, assuming that `Hash(secret)` doesn't change in the event of an error - which would be a clear indication that the house is cheating).

Thanks again for the critique! I truly do love how the bitcoin community embraces cryptographic approaches to solve real-world problems, and I also love how it's rigorous in its critique of systems that aren't truly secure. Please, bring on any more critiques you have, I'd love to continue the discussion!

Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
June 30, 2012, 10:44:03 PM
 #5

Bravo for spotting the weakness in their claim of provability.
Can you tell us more about your protocol ?
Is it implemented on a poker site ?
http://www.dc.uba.ar/inv/tesis/licenciatura/2010/lerner

this is... wow.

The protocol was improved since the thesis.. performance is 10x faster now. These improvements are described in a US patent ...

My implementation is not ready to go open source, and must be cleaned up. Also there is the patent issue, so I must find a license compatible with the patent. I will publish the code soon.

Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
June 30, 2012, 11:06:24 PM
 #6

Hi Libertaad, nice to meet you!


Even if the server could analyze all possible deck combinations before each shuffle, it wouldn't help. This is because the Mersenne Twister has the property of having a Uniform Distribution, which means the avenue of attack of "creating a pre-shuffled deck such that all possible re-shuffled decks still favor the house" is impossible.


What you say is only partially true: since Mersenne Twister is not a Cryptographically-Strong Pseudorandom number generator (CSPRNG) there is the possibility that the possible pre-images could be computed to maximize some statistical properties of the Mersenne Twister output. The advantage might be subtle, but it could be done, in theory.
My suggestion is to use a client_seed much longer (say 80 bits) and a CSPRNG.


Even if there is a server error prior to the deal, the user can still confirm that the server didn't change the pre-shuffled deck - as long as the `Hash(secret)` which is presented to the user doesn't change when the user reloads the page, they will know the server is being honest. I do agree though, that if the `Hash(secret)` changes,  this would be a clear indication that the house is cheating.

You are right. But you should tell the user not to accept reloads with changing hashes.

The code for the Javascript Hand Verifier is indeed open source!
.. I want to be as open about this whole process as possible.

Great! But the problem is that the user has to manually check the shuffles every time. There should be a way to automate the checks, but in a way the the checking code is not sent by the server, but given by the user. An interfase between the web page and a local application.

Thanks again for the critique!
It was my pleasure.



Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
July 01, 2012, 12:25:59 AM
 #7

There are (possibly) two other problems with your protocol:

1) The origin of the code that choses the client_seed:

I haven´t seen the page, but I doubt the user can provide the random seed manually in an edit box.
If not, then the server-sended client-side javaScript code could choose the number in a predictable way, and the user has no way to find it.

A "fake" webpage could be sent with a probability of 1/10, so the user chances of finding it while reviewing the source code is low.

2) The way the client_seed random is chosen:

Again, I haven´t seen the source code of the webpage where the client_seed is chosen. (I haven´t played in your site) but I guess it has some javaScript code that calls Math.random(), which is not cryptographically secure and so it´s predictable.

How do you compute the client_seed ? You should use a CSPRNG, such as the one provided by SJCL namespace sjcl.random (I haven´t tested it myself)

Could you post the source code of the webpage where the client_seed is chosen ?

Best regards,
 Sergio.
libertaad
Sr. Member
****
Offline Offline

Activity: 266



View Profile WWW

Ignore
July 01, 2012, 06:24:30 AM
 #8

Hi Libertaad, nice to meet you!

Nice to meet you too!

What you say is only partially true: since Mersenne Twister is not a Cryptographically-Strong Pseudorandom number generator (CSPRNG) there is the possibility that the possible pre-images could be computed to maximize some statistical properties of the Mersenne Twister output. The advantage might be subtle, but it could be done, in theory.
My suggestion is to use a client_seed much longer (say 80 bits) and a CSPRNG.

A key reason that we went with Mersenne Twister for the reshuffle phase was because we place a lot of value on the reference implementation. We wanted an accessible reference implementation, that any of our end users could run. This meant it had to be in javascript. We didn't want to just have this awesome provably fair shuffling algorithm, but make it basically impossible for any of our end-users to truly verify anything.

We also didn't want to re-implement any PRNG's in javascript, because this would defeat the goal of having a simple reference implementation. Our reference implementation is less than 100 lines of code, but it does rely on an existing Mersenne Twister implementation.

Great! But the problem is that the user has to manually check the shuffles every time. There should be a way to automate the checks, but in a way the the checking code is not sent by the server, but given by the user. An interfase between the web page and a local application.

I believe that a great way for a savvy user to do this on their own would be through a greasemonkey script. This is possible since bitZino is an HTML5 app. Since greasemonkey scripts are in javascript, the user could even use our reference implementation if they desired Cheesy

There are (possibly) two other problems with your protocol:

1) The origin of the code that choses the client_seed:

I haven´t seen the page, but I doubt the user can provide the random seed manually in an edit box.
If not, then the server-sended client-side javaScript code could choose the number in a predictable way, and the user has no way to find it.

A "fake" webpage could be sent with a probability of 1/10, so the user chances of finding it while reviewing the source code is low.

bitZino actually does allow you to edit the client_seed if you so desire (you can see the interface for yourself if you'd like with a play money table at https://bitzino.com/blackjack). While it would be possible for us to send down fake javascript on occasion to generate client_seeds that favored us, we would be guaranteed to eventually be caught if we did this.

This avenue of attack could also be stopped in its tracks by the user running a greasemonkey script which always submitted their own client_seed. In this way, the user would never be depending on the javascript on the page to generate the seed for them.

2) The way the client_seed random is chosen:

Again, I haven´t seen the source code of the webpage where the client_seed is chosen. (I haven´t played in your site) but I guess it has some javaScript code that calls Math.random(), which is not cryptographically secure and so it´s predictable.

How do you compute the client_seed ? You should use a CSPRNG, such as the one provided by SJCL namespace sjcl.random (I haven´t tested it myself)

Could you post the source code of the webpage where the client_seed is chosen ?

We are indeed using Math.random() to generate the seed.

The source code, if you're curious (it creates a 24 character base-62 string):

Code:
function setRandomClientSeed() {
  var a = [];
  for(var i = 0; i < 24; i++) {
    var val = Math.floor(Math.random() * 62);
    val += 48;
    if (val > 57) { val += 7; }
    if (val > 90) { val += 6; }
    a.push(val);
  }
  $('#client_seed_input').val(String.fromCharCode.apply(null, a));
}

Once again though, the user could utilize a greasemonkey script to create their own seed, and therefore not rely on the page javascript for security at all.

We did think about making this whole algorithm greasemonkey script from the beginning - which would have satisfied all of your issues regarding the server sending down tainted JS. The reason we chose not to do this primarily as a greasemonkey script was once again about accessibility. We wanted 100% of our users to be able to verify their hands if they chose to. I still may make a greasemonkey verifier, but I think it would actually be better if the greasemonkey verifier came from the community, rather than from us.

Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
July 02, 2012, 01:11:21 PM
 #9

I've not researched the subject myself, but reading other peoples research it's clearly stated that Math.Random can be predicted with high accuracy: it is seeded with the system time each time a new page or new tab is open.

From http://ifsec.blogspot.com.ar/2012/05/cross-domain-mathrandom-prediction.html:

"In Firefox, each page will have its own PRNG while in IE 8 and below each tab will have its own PRNG and the PRNG will *not* be reseeded if the page in the tab changes, even though the new page might be in another domain."

In Windows, Firefox javaScript engine calls QueryPerformanceCounter(), which provides some a few more bits of entropy (see http://mxr.mozilla.org/seamonkey/source/js/src/jsmath.c#366)

So in IE8 a single javaScript method that is executed before the user starts playing can detect the current seed before the page https://bitzino.com/blackjack loads and afterwards, the client_seed is completely useless as an entropy source. The user will never notice the fact the seed is known by the sever.

But the simplest attack in IE8 is to take some Random() values and solve the modular equations to obtain the seed. Since the PRNG (in Firefox and IE8) is a simple linear Congruential Generator (LCG) [ (state*a+b)%(2^48) ] the seed can be recovered by only knowing only two outputs !! No hidden code has to be sent to the user. Only the first two games would be "fair".
The client script itself is providing enough information for the server to cheat the user in the following games!


So, either you allow the user to supply the random via a greasemonkey script or fairness will never be guaranteed.

On the contrary, claiming fairness by using Math.Random() can be taken by the user as a a sign of hidden malicious intentions.

Best regards,
 Sergio.
libertaad
Sr. Member
****
Offline Offline

Activity: 266



View Profile WWW

Ignore
July 02, 2012, 10:40:47 PM
 #10

I've not researched the subject myself, but reading other peoples research it's clearly stated that Math.Random can be predicted with high accuracy: it is seeded with the system time each time a new page or new tab is open.

...

So, either you allow the user to supply the random via a greasemonkey script or fairness will never be guaranteed.

Fortunately, due to the nature if bitZino being a webapp, this already is possible! Any user is free to create a greasemonkey script which modifies the client_seed using their own randomness source. Additionally, users are free to manually enter a client_seed before every hand.

Also, as an additional measure, because the initial_shuffle is provided directly to the user after every hand, any suspicious user could easily to entropy analysis on all the hands they've played and prove whether or not the server is serving up truly random initial_shuffles.

Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
July 02, 2012, 11:15:15 PM
 #11

libertaad: I know you´re doing your best effort to prove the game is fair, but using math.Random() you are proving nothing. I would be the same as skipping the client_seed stuff and telling the users to trust you because you´re good person or had no complains in the past. Either you provide a secure system or your efforts are worthless. If you want to convince your users there are plenty of companies that audit the PRNGs like iTech Labs. , eCOGRA, etc.

It seems that with little additional effort (providing client-side user programmed scripts to choose the client_seed) you could still take advantage of current developed system and secure it.

best regards, Sergio

                                                                                                                                                                                                                                                                                                                                                                                                                                                               

libertaad
Sr. Member
****
Offline Offline

Activity: 266



View Profile WWW

Ignore
July 03, 2012, 02:02:44 AM
 #12

libertaad: I know you´re doing your best effort to prove the game is fair, but using math.Random() you are proving nothing. I would be the same as skipping the client_seed stuff and telling the users to trust you because you´re good person or had no complains in the past. Either you provide a secure system or your efforts are worthless. If you want to convince your users there are plenty of companies that audit the PRNGs like iTech Labs. , eCOGRA, etc.

It seems that with little additional effort (providing client-side user programmed scripts to choose the client_seed) you could still take advantage of current developed system and secure it.

best regards, Sergio

                                                                                                                                                                                                                                                                                                                                                                                                                                                               



Thanks for the feedback, Sergio. I really do appreciate it!

I believe you're right that a greasemonkey client-side script which used a CSPRNG to generate the client_seed would drastically improve the quality of the overall system, especially for users with insecure browsers. There are some talks in other threads about members of the community building this on their own, which I've offered to support. I think would be the absolute best: having a 3rd party script which verifies all hands, and stores a history of every hand played would be ideal. Before that script is built, I still hold that this system is vastly superior to most other online casinos.

rapeghost
Sr. Member
****
Offline Offline

Activity: 263


STOP THE INSANITY. LETS END HUMANITY


View Profile WWW

Ignore
August 14, 2012, 08:02:52 AM
 #13

this was an extremely interesting read. thank you

When you live in my house you'll follow my rules, boy. Now, butter that bacon!
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!