2
$\begingroup$

I'm making a peer-to-peer game client using an already existing protocol where messages are broadcasted to all people on the network, and messages are already proven to be from a given user. One of the games I want to add is UNO, and I found this paper from the same authors of RSA that describes an algorithm that perfectly suits my needs:

  • Will allow a shared state of a shuffled deck without any of the players knowing the state of the cards.
  • Does not allow duplicates in a deck and is tamper resistant.
  • All players must participate in allowing a player to reveal a card, but only the drawer will end up knowing the value of the drawn card.

Key derivation

  1. All players will agree on a large prime $n$, which will be used as a public modulus.
  2. Each player, $i$, will then generate a secret prime exponent, $e_i$, and it's modular multiplicative inverse under modulo $\phi(n)$, $d_i$. Where $e_i$:

After this, each player now has their own private e, d pair, and all players will know the primes factors of n.

Shuffling

Every game has a known party host who is the authority on certain information about a game, like which users are players, and what order the players are "sitting" in.

Starting from the party host, each player will encrypt each card individually and then shuffle their deck, passing the encrypted & shuffled deck to the next player. Remember that everyone can see all of these messages publicly, so once the cards reach the party host everybody will know the final order of the cards.

Drawing a card

Say player X wants to draw a card, and all players agree that this makes sense. A card is taken from the top of the deck and is passed around to be decrypted, skipping the player that the card is for. Once the card has only player X's encryption left on it, it's given to them and they can now decrypt and see their card.


How many bits of security does this cipher provide in this context? It seems like as a player would have to guess each player's e or d in order to decrypt any card?

$\endgroup$
5
  • $\begingroup$ Nice question. Clarify one thing please. You say "modified". How exactly was it modified compared to the RSA authors' paper? $\endgroup$
    – kodlu
    Aug 28, 2023 at 10:58
  • 1
    $\begingroup$ The standard reference for mental poker is linked by the second author. I find it more readable. If the question is specifically for the 1979 reference linked in the question, please state that. Independently: "modular multiplicative inverse under modulo $n$" is incorrect. Likely, "modular multiplicative inverse modulo $\phi(n)$" is intended (though other options work). And, as pointed in the article, it's possible (and simpler and more efficient on top of that) to agree on a prime $n$, such that $d=e^{-1}\bmod(n-1)$. $\endgroup$
    – fgrieu
    Aug 28, 2023 at 13:12
  • 1
    $\begingroup$ @kodlu I had a really hard time understanding the paper, so I just assumed a few things. I wrote modified because I assumed I didn't do it correctly. $\endgroup$ Aug 28, 2023 at 14:06
  • 1
    $\begingroup$ @fgrieu thank you for the corrections/suggestions! I edited my post accordingly $\endgroup$ Aug 28, 2023 at 14:08
  • 1
    $\begingroup$ In the paper the modulus is prime or composite. In your question the modulus is prime and composite :) $\endgroup$
    – Maarten Bodewes
    Aug 28, 2023 at 15:09

1 Answer 1

1
$\begingroup$

The protocol as in the question, and [SRA1979]/[SRA1981], are insecure as described, but smalls modifications can make it secure.

A serious security issue is that the encryption used is such that for any message $m$ (e.g. the description of a card) and any prime factor $p$ of $n$ (i.e. $p=n$ when $n$ is prime), ciphertext $c=m^e\bmod n$ has the property that the Legendre symbols $\left(\frac m p\right)$ and $\left(\frac c p\right)$ are equal (either $-1$ or $+1$). That is, $c^{(p-1)/2}\bmod p=m^{(p-1)/2}\bmod p$. This allows some level of cheating. For prime $n$, that's much like for a physical deck of cards where the orientation of a card is recognizable by it's back, and the orientation of each individual card is about random, but known. Composite $n$ only makes things worse, since the factors of $n$ are public and the attack can be carried for each.

There is another lesser security issue, related to the Desmedt and Odlyzko attack [DO1985]: the factorization of the $m_i$ representing cards conceivably could be such that we can find some not-all zero tuple of $t_i\in\mathbb Z$ such that $$\prod_{t_i>0}{m_i}^{t_i}\,=\,\prod_{t_i<0}{m_i}^{-t_i}$$ and that would allow to identify the cards with non-zero $t_i$ in this tuple from their ciphertexts $c_i$ (often exactly, perhaps within a few permutations). The probability is low for non-malicious choice of $m_i$, but the ability to subtly alter the $m_i$ (e.g. by inserting invisible characters at the end…) would make it totally practical.

Update: I think [L1979] and [L1981] note the first attack. [C1985] extends it for $n$ with $n-1$ divisible by small odd primes, and gives a variation of the second attack.


I assert without proof that we can make the protocol secure with the following small modifications starting from [SRA1981]:

  1. Choose $n$ a haphazard safe prime of 2048-bit or more, e.g. this or this. That also simplifies the choice of the encryption exponent $e$: we only need $e$ to be odd, large enough ($\lfloor\log_2 n\rfloor$ bit is fine, even 300 bits is enough), otherwise about uniformly random, and secret. We can compute the decryption exponent $d$ as $e^{-1}\bmod(n-1)$, that is also $e^{n-4}\bmod(n-1)$ or $e^{(n-5)/2}\bmod(n-1)$.

  2. Obtain $m_i$ representing card $i$ as $m_i=H(\underline i)^2\bmod n$, where

    • $\underline i$ represents $i$ as byte(s) per some fixed convention (e.g. the byte with value $i$, or the ASCII representation of the text suggested by [SRA1981] for card $i$)
    • $H$ is a cryptographic hash/PRF function with output of size $\lfloor\log_2 n/8\rfloor$ bytes (e.g. $H(M):=\operatorname{SHAKE256}(M,8\lfloor\log_2 (n/8)\rfloor)$ as defined in FIPS 202)
    • we assimilate the bitstring output of $H$ to integer per some convention (e.g. big-endian).
  3. Decryption is slightly modified: we do not obtain the decryption of the card itself, but some $m_i$. Since these are public, we can search which card it is.

Rationale: Precaution 1 makes the Discrete Logarithm Problem modulo $n$ hard, and is recommended in [C1985] to guard against attacks exploiting small factors of $p-1$. That works because precaution 2 is such that the order of $m_i$ is the prime $(p-1)/2$. Further, the hash guards against any variant of the Desmedt and Odlyzko attack, much like in Full Domain Hash [C2000].


Extension: If the number of "cards" is large to the point of making search inconvenient, or there was no agreed-upon description of cards, we can use $m_i=\operatorname{pad}(M_i)$ where $M_i$ is the description of card, and $\operatorname{pad}$ is a reversible pseudo-random encoding like that of ISO/IEC 9796-2 scheme 3 in total recovery mode.


There are many later mental poker protocols requiring less computational work and bandwidth. See [WW2009] for a bibliography, and another one.


[SRA1979]: Adi Shamir, Ronald Rivest, Leonard Adleman; Mental Poker, MIT-LCS-TM-125, January 1979.

[L1979] R. Lipton, How to Cheat at Mental Poker, Technical Report, Computer Science Depertment, Berkeley, CVA, August 1979 (no online source found).

[L1981] R. Lipton, How to Cheat at Mental Poker, in Proceeding of the AMS short course on Cryptology, 1981 (no online source found).

[SRA1981]: Adi Shamir, Ronald Rivest, Leonard Adleman; Mental Poker, in The Mathematical Gardner, 1981.

[C1985]: Don Coppersmith; Cheating at Mental Poker, in proceedings of Crypto 1985 (note: read $a\,\bar a\equiv1\pmod{n-1}$ where there is $a\,\bar a\equiv1\pmod n$).

[DO1985]: Yvo Desmedt and Andrew M. Odlyzko; A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.

[C2000]: Jean-Sébastien Coron; On the Exact Security of Full Domain Hash, in proceedings of Crypto 2000.

[WW2009]: Tzer-jen Wei, Lih-Chung Wang; A Fast Mental Poker Protocol, eprint 2009/439.

$\endgroup$
2
  • $\begingroup$ I appreciate how much detail you went into so muchh. Wow that first security issue sounds so interesting! Are you saying that the Legendre symbols are preserved after a modular exponentiation? And because of that, the first person would be able to mark cards into two groups? $\endgroup$ Sep 3, 2023 at 6:26
  • $\begingroup$ @JusticeAlmanzar: yes, I'm saying the Legendre symbols are preserved after a modular exponentiation to an odd power (as used in SRA). And yes that creates two recognizable groups of card. [C1985] has an extension of that attack. $\endgroup$
    – fgrieu
    Sep 3, 2023 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.