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 <[email protected] > <mailto:[email protected]>> 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 > <[email protected] <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[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]> > <mailto:[email protected] <mailto:[email protected]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[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]>> > > <mailto:[email protected] > <mailto:[email protected]> > <mailto:[email protected] <mailto:[email protected]>>> > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>> > > > <mailto:[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]>>> > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>>>> > > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>>> > > > > <mailto:[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]>>> > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] <mailto:[email protected]>> > <mailto:[email protected] <mailto:[email protected]> > > <mailto:[email protected] <mailto:[email protected]>>>> > > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] <mailto:[email protected]>> > > > <mailto:[email protected] > <mailto:[email protected]> <mailto:[email protected] > <mailto:[email protected]>>> > > <mailto:[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]>>> > > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>>>> > > > > > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>>> > > > > > <mailto:[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]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>>> > > > > > <mailto:[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]>> > > > <mailto:[email protected] > <mailto:[email protected]> > > <mailto:[email protected] > <mailto:[email protected]>>> > > > > > <mailto:[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]>> > > > <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]>> > > > <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]>. > > 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.
