[Replying back to the list with Elias's permission]
On Sun, Jul 4, 2010 at 11:15 AM, Elias Önal <[email protected]>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). > > Cameron Hutchison wrote: > > On Sun, Jul 4, 2010 at 10:24 AM, Elias Önal <[email protected] > > <mailto:[email protected]>> 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 > > <[email protected] <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>>> wrote: > > > > > > 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 > > <[email protected] <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>> > > > > <mailto:[email protected] > > <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>>>> 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 > > <[email protected] <mailto:[email protected]> > > > <mailto:[email protected] <mailto:[email protected]>> > > > > <mailto:[email protected] > > <mailto:[email protected]> <mailto:[email protected] > > <mailto:[email protected]>>>> > > > wrote: > > > > > 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 > > > > > > > > -- > > > > You received this message because you are subscribed > > to the > > > > "Crypto++ Users" Google Group. > > > > To unsubscribe, send an email to > > > > [email protected] > > <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>> > > > > <mailto:[email protected] > > <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>>>. > > > > More information about Crypto++ and this group is > > available at > > > > http://www.cryptopp.com. > > > > > > > > > > > > -- > > > > You received this message because you are subscribed to the > > > "Crypto++ > > > > Users" Google Group. > > > > To unsubscribe, send an email to > > > > [email protected] > > <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>>. > > > > More information about Crypto++ and this group is available > at > > > > http://www.cryptopp.com. > > > > > > -- > > > You received this message because you are subscribed to the > > > "Crypto++ Users" Google Group. > > > To unsubscribe, send an email to > > > [email protected] > > <mailto:[email protected]> > > > <mailto:[email protected] > > <mailto:[email protected]>>. > > > More information about Crypto++ and this group is available at > > > http://www.cryptopp.com. > > > > > > > > > -- > > > You received this message because you are subscribed to the > > "Crypto++ > > > Users" Google Group. > > > To unsubscribe, send an email to > > > [email protected] > > <mailto:[email protected]>. > > > More information about Crypto++ and this group is available at > > > http://www.cryptopp.com. > > > > -- > > You received this message because you are subscribed to the > > "Crypto++ Users" Google Group. > > To unsubscribe, send an email to > > [email protected] > > <mailto:[email protected]>. > > More information about Crypto++ and this group is available at > > http://www.cryptopp.com. > > > > > > -- > > You received this message because you are subscribed to the "Crypto++ > > Users" Google Group. > > To unsubscribe, send an email to > > [email protected]. > > More information about Crypto++ and this group is available at > > http://www.cryptopp.com. > > -- You received this message because you are subscribed to the "Crypto++ Users" Google Group. To unsubscribe, send an email to [email protected]. More information about Crypto++ and this group is available at http://www.cryptopp.com.
