#[1]tpaschalis - software, systems

  [2][profileAvatar.png]

[3]tpaschalis

  software, systems

  [4]Blog [5]About [6]Open-Source [7]Reading [8]Now

Mental Poker in Go

  Standard Disclaimer : Don’t trust me or any random internet person with
  anything related to cryptography and production-grade systems. This is
  just a toy so that I could introduce my SO to some cryptography
  fundamentals with a ‘fun’ example that didn’t involve too much math.
  The Go code is a hacky mess, just to showcase the idea, don’t judge ^^

  So without further ado, let’s get to it.

Intro

  I recently read the [9]‘Mental Poker (1979)’ paper by Shamir, Rivest
  and Adleman (of RSA fame). The acknowledgment section also mentions
  Robert W Floyd (as in the Floyd-Warshall algorithm) as well as Michael
  Rabin (as in the Rabin-Karp search algorithm), so it’s a star-spangled
  effort all in all.

  At just 8 pages, it’s easy for anyone to read and understand. The basic
  question it poses is “Can two potentially dishonest players play a fair
  game of poker without using any cards (eg. via the mail, or via the
  telephone) and without using any mutually trusted intermediate”?

  Before jumping in the paper, I tried to reason for about twenty
  minutes, and decided that no, it wouldn’t be possible. I was smiling at
  the paper’s first part that agreed with my intuition, but then was
  intrigued when they provided such a concise and easy way to achieve it.

  Actually, all it takes is a commutative encryption scheme!

The commutative property

  In mathematics, an operation is commutative if changing the order of
  the operands does not affect the result. Addition and multiplication
  are commutative operations, while subtraction and division are
  noncommutative operations.

  Another two examples of commutative operations would be the symmetry of
  second derivatives for functions satisfying Young’s theorem, ∂xy f =
  ∂yx f or the dot product. On the other hand, the three-dimensional
  cross product is anti-commutative since b × a = −(a × b).

  The authors introduce the concept of a commutative encryption scheme.
  That is, given a key K, we can agree on a pair of encryption and
  decryption functions Ek and Dk. For all messages X, and keys K and J,
  the order which we use to apply the encryption functions should not
  matter;
  that is Ek(Ej(X)) = Ej(Ek(X)).

  We also suppose that this encryption key is strong, meaning that
  a) given a message X and its encrypted version Ek(X), we can never
  infer the key K and
  b) given any messages X and Y, we cannot find any keys J and K such as
  Ej(X) = Ek(Y),
  since any of the above would undermine the integrity of the
  communication and our encryption scheme.

  The authors propose a simple function that utilizes Euler’s totient
  function and fullfills all the above criteria.

The Protocol

  If you haven’t read the paper yet (it takes no more than 5 minutes),
  here’s the protocol steps for our two classic suspects, Bob and Alice.

  1) Bob and Alice agree on the encryption scheme. Each selects their
  key/passphrase, and creates their enryption/decryption function pairs
  Eb/Db and Ea/Da. The keys will remain secret until the end of the game,
  when they will be revealed to verify that no cheating has occured.

  2) It’s Bob’s turn to deal, so he creates a new deck and encrypts all
  of the cards using his encryption function. He then shuffles the deck.

  3) Alice receives the deck, selects five cards at random, and sends
  them back to Bob. These five cards will be Bob’s hand; he can use his
  decryption function to actually see what he has been dealt.

  4) Now Alice encrypts the rest of the deck with her own key, and
  selects five other cards at random for her own hand. Each card in
  Alice’s hand is now doubly-encrypted using Ea(Eb(X)), and she sends the
  hand over to Bob.

  5) Bob decrypts Alice’s hand with his own decryptor, and sends it back
  to her. Alice’s hand is now only encrypted with her own key, and Bob
  has no knowledge of it.

  6) Alice receives her hand, and can use her decryption function to see
  what she has been dealt.

  7) The players can bet on their hand.

  8) Finally, for the showdown, each player reveals their hand, and their
  secret key/passphrase. This way, each player can now check that the
  other was actually dealt the hand that they claimed to have.

The Code

  What feels so great about this process (at least for me) is that the
  physical-world analogy of using padlocks and sending over each card in
  a little box is just as good for understanding what’s up, without
  having to mention anything about mathematics.

  Since we could get a feel of how this works, let’s translate it into
  some hacky Go code! For the commutative encryption scheme, we can use a
  ChaCha20 stream to simply XOR with the key stream. A downside is that
  we have to re-create the Cipher object each time, since it maintains
  state and multiple calls to the XORKeyStream breaks the commutativity.
  Please reach out if you have a better alternative in mind!
package main

import (
       "crypto/sha256"
       "fmt"
       "math/rand"
       "reflect"
       "time"

       "golang.org/x/crypto/chacha20"
       "golang.org/x/crypto/chacha20poly1305"
)

// Do not use anywhere near serious or production-grade systems.
// Commutative scheme idea from https://asecuritysite.com/encryption/go_comm

func main() {
       // Bob and Alice select their passphrace, and get their
       // encoding/decoding functions pairs; Eb/Db and Ea/Da.
       // These will remain secrets until the end of the game, when they will b
e revealed
       // to verify that no cheating has occured.
       passBob := "pass1"
       passAlice := "pass2"
       Eb, Db := getED(passBob)
       Ea, Da := getED(passAlice)

       // Bob creates a new Deck, and encrypts each card using his key. He then
shuffles it.
       deck := buildNewDeck()

       encryptedDeck := make([][]byte, 0)
       for _, card := range deck {
               encryptedDeck = append(encryptedDeck, Eb(card.name()))
       }
       bobRng := rand.New(rand.NewSource(time.Now().Unix()))

       bobRng.Shuffle(
               len(encryptedDeck),
               func(i, j int) {
                       encryptedDeck[i], encryptedDeck[j] = encryptedDeck[j], e
ncryptedDeck[i]
               })

       // Alice receives the deck, and selects five cards at random, and sends
them back to Bob.
       // Τhis will be Bob's hand, and he can laterdecrypt the values to see wh
at he has been dealt.
       aliceRng := rand.New(rand.NewSource(time.Now().Unix()))

       aliceRng.Shuffle(
               len(encryptedDeck),
               func(i, j int) {
                       encryptedDeck[i], encryptedDeck[j] = encryptedDeck[j], e
ncryptedDeck[i]
               })

       bobHand := encryptedDeck[0:5]
       encryptedDeck = encryptedDeck[5:]
       for _, c := range bobHand {
               fmt.Println(string(Db(c)))
       }

       // Now Alice selects five other cards at random, encrypts them with her
key.
       // Each card in Alice's hand is doubly-encrypted now, and she sends them
over to Bob.
       aliceRng.Shuffle(
               len(encryptedDeck),
               func(i, j int) {
                       encryptedDeck[i], encryptedDeck[j] = encryptedDeck[j], e
ncryptedDeck[i]
               })
       aliceHand := encryptedDeck[0:5]
       encryptedDeck = encryptedDeck[5:]
       for i := range aliceHand {
               aliceHand[i] = Ea(aliceHand[i])
       }

       // Bob decrypts Alice's hand with his own decryptor.
       // The hand is now only encrypted with her key, and Bob has no knowledge
of it.
       for i := range aliceHand {
               aliceHand[i] = Db(aliceHand[i])
       }

       // Each player now has a hand, only encrypted with his own key,
       // and thus can decode it to see what was dealt to him, and who has the
better hand.
       realBobHand := make([][]byte, 0)
       realAliceHand := make([][]byte, 0)

       for _, cb := range bobHand {
               realBobHand = append(realBobHand, Db(cb))
       }
       for _, ca := range aliceHand {
               realAliceHand = append(realAliceHand, Da(ca))
       }

       // The two players reveal their secret keys; now each player
       // can check that the other was actually dealt the cards he claimed to h
ave played.
       fmt.Println(realBobHand)
       fmt.Println(realAliceHand)

       // Bob reveals his passphrase, and Alice verifies that she can replicate
the above claim by Bob
       revealedBobPassphrase := passBob
       _, revealedDb := getED(revealedBobPassphrase)
       for i := range bobHand {
               if !reflect.DeepEqual(revealedDb(bobHand[i]), realBobHand[i]) {
                       panic("Bob may have cheated!")
               }
       }

       // Alice reveals her passphrase, and Bob can do the same
       revealedAlicePassphrase := passAlice
       _, revealedDa := getED(revealedAlicePassphrase)

       for i := range aliceHand {
               if !reflect.DeepEqual(revealedDa(aliceHand[i]), realAliceHand[i]
) {
                       panic("Alice may have cheated!")
               }
       }

}

func getED(passphrase string) (func([]byte) []byte, func([]byte) []byte) {

       e := func(src []byte) []byte {
               key := sha256.Sum256([]byte(passphrase))
               nonce := make([]byte, chacha20poly1305.NonceSizeX)

               ecipher, _ := chacha20.NewUnauthenticatedCipher(key[:32], nonce)

               res := make([]byte, len(src))
               ecipher.XORKeyStream(res, src)
               return res
       }

       d := func(src []byte) []byte {
               key := sha256.Sum256([]byte(passphrase))
               nonce := make([]byte, chacha20poly1305.NonceSizeX)

               dcipher, _ := chacha20.NewUnauthenticatedCipher(key[:32], nonce)

               res := make([]byte, len(src))
               dcipher.XORKeyStream(res, src)
               return res
       }

       return d, e
}

type card struct {
       Rank string
       Suit string
}

func buildNewDeck() []card {
       ranks := []string{"Ace", "Two", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Jack", "Queen", "King"}
       suits := []string{"Clubs", "Diamonds", "Hearts", "Spades"}

       var deck []card
       for _, s := range suits {
               for _, r := range ranks {
                       deck = append(deck, card{Rank: r, Suit: s})
               }
       }

       return deck
}

func (c card) name() []byte {
       return []byte(c.Rank + " of " + c.Suit)
}

Outro

  That’s all for today! I don’t claim to know anything about crypto, but
  this has been a fun topic to discuss over beer! Don’t hesitate to reach
  out for any corrections and issues. See you around!
  Written on July 17, 2021

References

  Visible links
  1. https://tpaschalis.github.io/feed.xml
  2. https://tpaschalis.github.io/
  3. https://tpaschalis.github.io/
  4. https://tpaschalis.github.io/
  5. https://tpaschalis.github.io/about
  6. https://tpaschalis.github.io/opensource
  7. https://tpaschalis.github.io/reading
  8. https://tpaschalis.github.io/now
  9. https://people.csail.mit.edu/rivest/pubs/SRA81.pdf

  Hidden links:
 11. https://github.com/tpaschalis
 12. https://www.linkedin.com/in/tsilias/
 13. https://www.twitter.com/tpaschalis_

You are viewing proxied material from 1436.ninja. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.