Commutative ciphers in Crypto++

[Cameron Hutchison]

Hi crypto++ users,

I'm looking for a commutative cipher to use to implement a card game
protocol (any type of card game, not just the 52/54 standard deck
games).

My research has led me to the Massey-Omura cryptosystem, but I cannot
find any implementations of it. I have read of references to elliptic
curve variations on M-O but most of what I read goes over my head. I
don't have the math background to understand the actual implementation
and theory behind these cryptosystems. So I'm not sure if what I've
read is saying that ECC is commutative or not, but my experiments with
the ECC systems in crypto++ leads me to believe it is not.

Are there any commutative ciphers in crypto++ (besides XOR)? Symmetric
key would be simplest, but I can also work with asymmetric key
algorithms.

Thanks

[Vadym Fedyukovych]

El Gamal?

> --
> You received this message because you are subscribed to the "Crypto++ Users" Google Group.
> To unsubscribe, send an email to cryptopp-user...@googlegroups.com.
> More information about Crypto++ and this group is available at http://www.cryptopp.com.

[Elias]

Don't forget about man-in-the-middle - You'd have to use signatures at
least! So better use asymmetric crypto in the first place ;)

[Cameron Hutchison]

[I sent this directly to Elias by accident - gmail newbie here. Here it is again for the list]

I don't think man-in-the-middle is going to be a problem.  My goal here is to make sure information is not revealed to the participants (of which there are two, but the protocol could probably be extended to more easily enough) before both players agree to it.

Anyway, if the man-in-the-middle does become an issue, the game can be played over a SSL/TLS link so I dont have to invent a new identity scheme for the game (i.e. make it possible to set up comms with existing certs - I hate the proliferation of different incompatible certs for different systems that I'm not going to add to it).

None of that matters though, unless I find an appropriate cipher for the game itself. :-)

Cheers

[Elias Önal]

I don't get the problem. It's a server based game right? So just use
some hybrid encryption? I don't get why you'd want to play with a
commutative system system, you probably could do it with AES in OFB
(Streamcipher, thus using XOR) mode, but I don't get the advantage. What
are you trying to hide from the participants? Can't you simply stop
sending that data to them? You want both to have the data, but make them
only able to read it if both agree? Just encrypt it twice using AES OFB
and give each one a key. In order to get the plaintext they have to
apply both keys (thus exchange keys), though the order in which they're
applied doesn't matter. That's what you want to archive using a
commutative system?

Elias

Cameron Hutchison wrote:
> [I sent this directly to Elias by accident - gmail newbie here. Here
> it is again for the list]
>
> I don't think man-in-the-middle is going to be a problem. My goal
> here is to make sure information is not revealed to the participants
> (of which there are two, but the protocol could probably be extended
> to more easily enough) before both players agree to it.
>
> Anyway, if the man-in-the-middle does become an issue, the game can be
> played over a SSL/TLS link so I dont have to invent a new identity
> scheme for the game (i.e. make it possible to set up comms with
> existing certs - I hate the proliferation of different incompatible
> certs for different systems that I'm not going to add to it).
>
> None of that matters though, unless I find an appropriate cipher for
> the game itself. :-)
>
> Cheers
>
> On Sun, Jul 4, 2010 at 9:32 AM, Elias <elias...@googlemail.com
> <mailto:elias...@googlemail.com>> wrote:
>
> Don't forget about man-in-the-middle - You'd have to use signatures at
> least! So better use asymmetric crypto in the first place ;)
>
> On Jul 1, 6:48 am, Cameron Hutchison <camh.c...@gmail.com

> <mailto:cryptopp-user...@googlegroups.com>.

[Cameron Hutchison]

No, it is not a server-based game. There are only two participants. I am trying to implement a peer-to-peer system that does not need a trusted third party.

At the end of the initialisation protocol, each player is left with a list of tokens (cards) that are encrypted by both players (technically they don't need to keep their own cards encrypted with their own keys but it helps to think of a single list of shared tokens than each player having a list of the same tokens but encrypted by the other player).

Anyway, after initialisation, player A can choose to reveal a token to player B by sending them the key that they used to encrypt that token. And vice versa.

To do this, I'm looking for a commutative cipher where each token is multiply-encrypted with multiple keys. Each token is encrypted with a different key. From previous research, a stream-based cipher (XOR) will leave the initialisation phase vulnerable to key discovery. That is how I've ended finding Massey-Omura (for which I cannot find an implementation), and now looking for something similar that is implemented in crypto++.

[Elias Önal]

No idea where you got that information, but I can assure you AES never
reveals the key. It doesn't even allow reconstruction of the key when
used in ECB mode - though ECB allows attacks against the ciphertext.
What you've read was probably about RC4 or something similar. Just use
an IV and AES OFB-mode, that works for your purpose and is secure! I
don't get why you want the other player to have the encrypted data in
advance though. Instead of sending the key to decrypt the data you could
simply send the data the moment player1 reveals some data to player2.

Elias

Cameron Hutchison wrote:
> No, it is not a server-based game. There are only two participants. I
> am trying to implement a peer-to-peer system that does not need a
> trusted third party.
>
> At the end of the initialisation protocol, each player is left with a
> list of tokens (cards) that are encrypted by both players (technically
> they don't need to keep their own cards encrypted with their own keys
> but it helps to think of a single list of shared tokens than each
> player having a list of the same tokens but encrypted by the other
> player).
>
> Anyway, after initialisation, player A can choose to reveal a token to
> player B by sending them the key that they used to encrypt that token.
> And vice versa.
>
> To do this, I'm looking for a commutative cipher where each token is
> multiply-encrypted with multiple keys. Each token is encrypted with a
> different key. From previous research, a stream-based cipher (XOR)
> will leave the initialisation phase vulnerable to key discovery. That
> is how I've ended finding Massey-Omura (for which I cannot find an
> implementation), and now looking for something similar that is
> implemented in crypto++.
>

> > <mailto:elias...@googlemail.com

> <mailto:elias...@googlemail.com>>> wrote:
> >
> > Don't forget about man-in-the-middle - You'd have to use
> signatures at
> > least! So better use asymmetric crypto in the first place ;)
> >
> > On Jul 1, 6:48 am, Cameron Hutchison <camh.c...@gmail.com
> <mailto:camh.c...@gmail.com>

> > <mailto:camh.c...@gmail.com <mailto:camh.c...@gmail.com>>>

> > <mailto:cryptopp-user...@googlegroups.com

[Cameron Hutchison]

On Sun, Jul 4, 2010 at 10:24 AM, Elias Önal <elias...@googlemail.com> wrote:

No idea where you got that information, but I can assure you AES never
reveals the key. It doesn't even allow reconstruction of the key when
used in ECB mode - though ECB allows attacks against the ciphertext.
What you've read was probably about RC4 or something similar. Just use
an IV and AES OFB-mode, that works for your purpose and is secure!

http://stackoverflow.com/questions/2104982/is-there-a-secure-cryptographic-algorithm-where-encryption-and-decryption-can-be/2105369

In the selected answer of that SO question: "On the other hand, the solutions based on RSA or stream cipher can be broken under this assumption."
 

I
don't get why you want the other player to have the encrypted data in
advance though. Instead of sending the key to decrypt the data you could
simply send the data the moment player1 reveals some data to player2.

Because player1 could cheat then and send tokens that were not in the original list (deck).

At the start of the game, both players must submit their list of tokens to each other in such a way that the contents are not revealed until the game rules say to do so. As the game progresses, the tokens are revealed to the specific players as the required by the rules.

If you want some more details of what I'm trying to do, see this old sci.crypt post of mine: http://groups.google.com/group/sci.crypt/browse_thread/thread/eb2512e31e6bb3fc/9e1e9a0cae9fab2f

I am "George Hewitson" in that thread (an old sci.crypt alias I used to use).

Cheers
 

Cameron Hutchison wrote:
> No, it is not a server-based game. There are only two participants. I
> am trying to implement a peer-to-peer system that does not need a
> trusted third party.
>
> At the end of the initialisation protocol, each player is left with a
> list of tokens (cards) that are encrypted by both players (technically
> they don't need to keep their own cards encrypted with their own keys
> but it helps to think of a single list of shared tokens than each
> player having a list of the same tokens but encrypted by the other
> player).
>
> Anyway, after initialisation, player A can choose to reveal a token to
> player B by sending them the key that they used to encrypt that token.
> And vice versa.
>
> To do this, I'm looking for a commutative cipher where each token is
> multiply-encrypted with multiple keys. Each token is encrypted with a
> different key. From previous research, a stream-based cipher (XOR)
> will leave the initialisation phase vulnerable to key discovery. That
> is how I've ended finding Massey-Omura (for which I cannot find an
> implementation), and now looking for something similar that is
> implemented in crypto++.
>

> On Sun, Jul 4, 2010 at 9:55 AM, Elias Önal <elias...@googlemail.com

[Cameron Hutchison]

[Replying back to the list with Elias's permission]

On Sun, Jul 4, 2010 at 11:15 AM, Elias Önal <elias...@googlemail.com> wrote:

> Two known cryptosystems that satisfy
>> E(key1, E(key2, Message)) = E(key2, E(key1, Message))
> are the Massey Omura crytosystem and Shamir's three-pass protocol. One
> reason to prefer these two schemes is the following property: an
> attacker with access to the ciphertexts E(key1, Message), E(key2,
> Message) and E(key1, E(key2, Message)) can not find the message. On

> the other hand, the solutions based on RSA or stream cipher can be
> broken under this assumption.

I think you got him wrong! It doesn't allow the reconstruction of the
key, but the keystream. Of course this is possible when using XOR, but I
don't see the problem in your case - You'd use a new IV for each game
anyway.

Yes, I got it wrong about the key(s) being exposed. I can't see how XOR can work in my case though, in the same way as the problem was expressed by the stackoverflow respondent. That is, reconstructing the keystream also makes my protocol vulnerable to information leakage.

Prior to starting the game, each player as the knowledge of what cards are in their deck and nothing of what is in their opponent's deck. At the end of the initialisation phase, each player has their own deck, shuffled, and with each card independently encrypted by each player, where each card is somehow tagged so that each player knows which key to use to decrypt the card.

To do the initialisation, player1 blinds his cards by encrypting them all with the same key and sends them to player2. Player2 shuffles the list, tags each card with a random ID (or nonce), generates one new key for each card and encrypts each card. They keep the ID with the corresponding encryption key. Player2 sends the cards back to player1 who then removes the blinding factor. This is where the commutative encryption is needed. Player1 then encrypts each card in the same way as player2 did and sends the list back to player2. Each player now has a deck of the same cards, each card encrypted by each player. (now do this over again the other way for player2's deck).

At this point, neither player can expose any cards without the other player's agreement (which comes in the form of them sending the key to decrypt the card). Neither player knows the order of their cards in the shuffled deck.

So since each card is independently encrypted by each player, I'm not sure how I would use a stream cipher with a single IV per game. At various points of the game, the rules will dictate that player2 allow player1 to see card X from their deck. Player2 will do this by sending their key for card X to player1.

One big issue to consider is that player2 can retain the original blind list of cards sent from player1. These are all singly encrypted with the same key. If any part of the protocol or encryption algorithm allows player2 to discover this key or keystream, the will be able to view the entire contents of player1's deck and even know the order of cards coming.
 

I have an other idea that might work for you and is pretty simple. I
will describe it from the view of player 1. Player1 receives a random
nonce from player2. Player1 then concatenates his choice for his card to
the nonce, adds another nonce on his own(a different one for each card)
and hashes it. Then he sends the hash to player2. Player2 can't get any
information from the hash until player1 reveals the card and the nonce
he chose for that card. At that moment player2 is able to verify player1
had the same card at the beginning by concatenating the three values and
hashing them. Using any secure cryptographic hash guarantees that
player1 can't cheat as well since he can't "forge" random hashes. I
would suggest sha256. Since the card-id is probably really short you
should choose the nonce reasonable long. (Defeats rainbowtables)

I can't see how this can support shuffling the deck such that player1 cannot look at the cards he has coming up.

The basic requirement is that at any point in time, any card can be revealed to one or both players (according to the game rules as agreed by each player). But prior to that a player must not know what a card is.

Anyway, I think I've got it all figured out, but I need a commutative cipher similar to Massey-Omura for which I can easily find an implementation. Hence my question on this crypto++ list as to whether it has such a cipher (and whether ECC can somehow be used in this way).

 

[Elias Önal]

I think the system as you've described has another problem. After
player2 shuffled the cards player1 can't decrypt them anymore without
knowing the original position. So player2 would have to keep a remapping
table which is only shared with player1 once both agree on disclosing
one card. If player1 knows the mapping table - he'd know all the cards.
Concerning the streamcipher you don't have to worry. You can't
reconstruct other parts of the keystream from single disclosured parts -
not for modern streamciphers. Just make sure to change the IV with each
game.

Concerning the problem of player1 getting "E(key1, Message) XOR E(key1,
E(key2, Message)) = key2" (he probably could brute force the positions
eventhough they're shuffled) player2 could refuse to share E(key1,
E(key2, Message)) with player1, but give him a hash of every card in
E(key1, E(key2, Message)).

Cameron Hutchison wrote:
> [Replying back to the list with Elias's permission]
>
>

> > On Sun, Jul 4, 2010 at 10:24 AM, Elias �nal

> > > On Sun, Jul 4, 2010 at 9:55 AM, Elias �nal

> > <mailto:camh.c...@gmail.com <mailto:camh.c...@gmail.com>>>>>

[Cameron Hutchison]

On Sun, Jul 4, 2010 at 12:22 PM, Elias Önal <elias...@googlemail.com> wrote:

I think the system as you've described has another problem. After
player2 shuffled the cards player1 can't decrypt them anymore without
knowing the original position.

With a commutative cipher, this doesn't matter. When player1 sends the original list to player2, all the cards are encrypted with the same blinding key. The cards sent back from player2 are all encrypted with a single "blinding" key generated by player1 and a unique key for each card. So player 1 does not need to know how the cards were reordered, they can still remove their blinding key.
 

So player2 would have to keep a remapping
table which is only shared with player1 once both agree on disclosing
one card. If player1 knows the mapping table - he'd know all the cards.

I don't think that's a problem. Player1 sends the original blind list in any order. Player 2 shuffles the list and then tags each card. That tag stays with the card so that player2 knows which key they used to encrypt the card. The list that player2 sends back to player1 has those tags on it. Player1 maintains the tags. They remove the blinding key and encrypt with a unique key for each card, recording the tag and key.
 

Concerning the streamcipher you don't have to worry. You can't
reconstruct other parts of the keystream from single disclosured parts -
not for modern streamciphers. Just make sure to change the IV with each
game.

Maybe I'm being dense here, but I don't see how to use a stream cipher. One cannot reorder a stream and still decrypt it can they? If all the cards are encrypted in a particular order, would they not need to be decrypted again in the same order? I'll get my books back out and explore this idea.

Anyway, this is all getting rather off-track. I have a protocol that I believe works (it's been rattling around in my head for over 10 years). I'm just looking for an implementation of a cypher similar to Massey-Omura and wondering if crypto++ has one.

I'm currently writing up a description of the protocol. I'll post it soon which may give greater clarity to what I'm trying to do.

Cheers

Concerning the problem of player1 getting "E(key1, Message) XOR  E(key1,
E(key2, Message)) = key2" (he probably could brute force the positions
eventhough they're shuffled) player2 could refuse to share E(key1,
E(key2, Message)) with player1, but give him a hash of every card in
E(key1, E(key2, Message)).

Cameron Hutchison wrote:
> [Replying back to the list with Elias's permission]
>
>

> On Sun, Jul 4, 2010 at 11:15 AM, Elias Önal <elias...@googlemail.com

>     > On Sun, Jul 4, 2010 at 10:24 AM, Elias Önal
>     <elias...@googlemail.com <mailto:elias...@googlemail.com>

>     >     > On Sun, Jul 4, 2010 at 9:55 AM, Elias Önal

[Elias Önal]

They could be decrypted in a different order, you just need to know the
area of the streamcipher you used. A streamcipher is basically a
cryptographic PRNG. You can tell it to generate 2 megabytes of
randomness and it will do. Since you'd never disclosure the key, but
only parts of the keystream it wouldn't really be a streamcipher -
rather a one time pad. One time pads are commutative as well.

Cameron Hutchison wrote:

> > On Sun, Jul 4, 2010 at 11:15 AM, Elias �nal

> > > On Sun, Jul 4, 2010 at 10:24 AM, Elias �nal

> > > > On Sun, Jul 4, 2010 at 9:55 AM, Elias �nal

[Vadym Fedyukovych]

On Sun, Jul 04, 2010 at 10:38:49AM +1000, Cameron Hutchison wrote:
> ...

> If you want some more details of what I'm trying to do, see this old
> sci.crypt post of mine:
> http://groups.google.com/group/sci.crypt/browse_thread/thread/eb2512e31e6bb3fc/9e1e9a0cae9fab2f
>
> I am "George Hewitson" in that thread (an old sci.crypt alias I used to
> use).

No wonder ElGamal was suggested already (by Shai Halevi)

[Cameron Hutchison]

Elias, thanks for the time you have taken to respond to my query.

Unfortunately, XOR will not work for this protocol. Using a stream cipher as a PRNG to generate a one time pad still uses XOR as the cipher used to encrypt the plaintext.

I can't use XOR for the reasons referenced previously. It would allow recovery of (part of) the keystream which would then allow player2 to see all of player1's cards. You'll have to take this on faith until I get around to publishing the protocol I'm working on. This is why I'm looking for an implementation of a non-XOR commutative cipher.

Cheers

On Sun, Jul 4, 2010 at 12:55 PM, Elias Önal <elias...@googlemail.com> wrote:

They could be decrypted in a different order, you just need to know the
area of the streamcipher you used. A streamcipher is basically a
cryptographic PRNG. You can tell it to generate 2 megabytes of
randomness and it will do. Since you'd never disclosure the key, but
only parts of the keystream it wouldn't really be a streamcipher -
rather a one time pad. One time pads are commutative as well.

Cameron Hutchison wrote:
>
>
> On Sun, Jul 4, 2010 at 12:22 PM, Elias Önal <elias...@googlemail.com

> <mailto:elias...@googlemail.com>> wrote:
>

>     > On Sun, Jul 4, 2010 at 11:15 AM, Elias Önal
>     <elias...@googlemail.com <mailto:elias...@googlemail.com>

>     >     > On Sun, Jul 4, 2010 at 10:24 AM, Elias Önal

>     >     >     > On Sun, Jul 4, 2010 at 9:55 AM, Elias Önal