Score:2

How secure is this modified RSA (SRA / Mental Poker) algorithm?

pf flag

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?

kodlu avatar
sa flag
Nice question. Clarify one thing please. You say "modified". How exactly was it modified compared to the RSA authors' paper?
fgrieu avatar
ng flag
The [standard reference](https://people.csail.mit.edu/rivest/pubs/SRA81.pdf) 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)$.
Justice Almanzar avatar
pf flag
@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.
Justice Almanzar avatar
pf flag
@fgrieu thank you for the corrections/suggestions! I edited my post accordingly
Maarten Bodewes avatar
in flag
In the paper the modulus is prime or composite. In your question the modulus is prime **and** composite :)
Score:0
ng flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.