# Are there any secure commutative ciphers?

This answer lists two commutative cipher algorithms - Pohlig-Hellman and SRA. However, they don't appear to be too secure.

My question is, here there any commutative ciphers out there that are secure enough for sensitive data encryption / decryption (money is involved) and at the same time not burdening enough on the computer to be run in real time on less powerful devices (say, a smartphone)?

• Can you use a hybrid scheme, where you apply the commutative cipher to a symmetric key? And how long are your messages? Mar 3, 2013 at 22:09
• RSA suffers from pretty much the same issues, so we apply randomized padding and use it as hybrid encryption. Mar 3, 2013 at 22:11
• This question probably has to be rephrased. Commutativity is, by itself, more of a security vulnerability than a security feature. If you really need this commutativity, you probably have to build an entire protocol around it, to make sure it can't be exploited by an attacker. Just asking for the security of the commutative cipher itself doesn't make much sense. Mar 4, 2013 at 1:59
• @CodesInChaos The application is mental poker - the messages are very short. Mar 4, 2013 at 5:50
• @HenrickHellström - I asked about it in a separate question - crypto.stackexchange.com/q/6575/843 . Mar 4, 2013 at 5:51

For a set of $B$ elements (e.g. $B = 2^n$ for all the "blocks of $n$ bits"), there are $B!$ possible permutations. An ideal block cipher is such that an instance with an unknown key is indistinguishable from a permutation chosen at random, uniformly, in these $B!$ permutations.

Since permutations don't commute in general, a "perfect" commutative block cipher must work over a subset of these $B!$ permutations, where all elements of the subset actually commute with each other, and this makes a commutative block cipher highly distinguishable from a randomly chosen permutation. Namely, suppose that there is a black box which implements either the block cipher $E_K$ (for some unknown key $K$), or a randomly chosen permutation. The attacker can submit plaintexts to encrypt (that's a chosen-plaintext attack scenario), and observe the result; his goal is to determine whether the box really implements $E_K$ for some $K$, or not. He then does the following:

• He selects a key $K'$ randomly, as well as a plaintext block $x$.
• He sends $x$ and $y = E_{K'}(x)$ as plaintexts to encrypt with the box.
• The box returns, respectively, $u$ and $v$.
• The attacker checks whether $E_{K'}(u) = v$. That equation will hold with probability $1$ if the box implements $E_K$, but only $1/B$ (i.e. almost zero) if the box implements a randomly chosen permutation.

In that sense, a commutative block cipher cannot be secure "as a block cipher". Commutative encryption can be secure only as part of a protocol in which the commutative encryption primitive is not used in the same way as, say, AES. What the scenario explained above means is that a deterministic commutative cipher cannot be "IND-CPA secure" (indistinguishable from a random permutation in a chosen-plaintext attack setup). So you need some randomness injected "somewhere", which may be some padding or an other feature of the overall protocol (e.g. encryption is only applied on values chosen randomly and uniformly in a given set, which are then used to derive a "normal" symmetric key, aka hybrid encryption).

Remember the “locked box puzzle” recounted on a “Security Now!” podcast (Episode #33, titled “Symmetric Block Ciphers”, 30 Mar 2006)?

Steve Gibson says:

… Leo and I answer last week's Puzzler/Brain-Teaser which explored the idea of using two private one-time pad "keys," like two padlocks, to securely convey a message between two parties, neither of whom would have the other's key. Then we continue our ongoing tour of fundamental crypto-technology by describing the operation of Symmetric Block Ciphers …

Steve Gibson and Leo Laporte agreed that an eavesdropper seeing ALICE's cipher text before and after encryption could XOR both together and derive her secret key. However, if a complex, commutative cipher which doesn't use simple XORing to encrypt is used then I think the key exchange would be secure and the key exchange would work.

For example: Bob encrypts a message with his key. Alice encrypts Bob's encrypted above message with her key. ALICE sends above encrypted message back to Bob. Bob decrypts Alice's above message with his key. BOB sends above to ALICE. ALICE decrypts above with her key. Alice can now read BOB'S original decrypted cipher text and they didn't need to exchange keys. An eavesdropper attack will not work if the algorithm is not a simple XOR-ing of plain text and key.

This cipher is a commutative, complex algorithm.

Starting with a text file containing one character, an m. The symbol m is hex 6d 01101101. Â is hex c2. 11000010 is 'm' encrypted by bob and then sent to alice. ø is hex d8 11011000 is Alice's encryption of Â which Bob decrypts to £ and sends to Alice. £ is hex a3 10100011 which alice decrypts to m with her key. m is Alice’s decryption result. An eavesdropper sees Â Alice's message before her encryption. the eavesdropper sees ø alice's msg after her encryption. the eavesdropper XORs Â and ø. 11000010 Â 11011000 ø 00011010 the eavesdropper's XOR result = 1a in hex. If an eavesdropper attack worked he would have found E hex 45 01001001 which is first letter of Alice's key.

This seems to be a simpler key exchange than PGP etc. All that's needed is that both parties use the same crypto-program and agree on an authenticator.

I confess to being a hobbyist. If anyone wants the C# program and/or the source code for the cipher (which targets Microsoft Windows), they may have it/them.

Below is example with longer, random keys.

• Plaintext:

this is a test.

• Bob's key:

kZtOfS0kKqcRLjTNPh7OjcJKZZFLjmm5OVm02YlrBQN0zI9SxOD1zJjQcpetUbX

• Bob's ciphertext to Alice:

1IÎ.8Ío#"ëìAùJ'

• Alice's key:

O1yfuV7MpX3n4wtefUhr6YctRaeCcrrzH7LqLNRUQCMVZuL5Mr0Bw3qMeIT92hg

• Alice's ciphertext to Bob:

µRÖ³#ïÓO,fzkÆaå

• Bob decodes Alice's above which = below:

øqqøð<ª>P¸&@<


and sends above back to Alice which Alice decodes, yielding:

this is a test.


To authenticate, simply add agreed upon passwords in plain text inside the message but not part of the message's ciphertext. needed only for last 2 exchanges. E.g.: µRÖ³#ïÓO,fzkÆaå apassword.

• If you XOR the intercepted messages (Bob encrypted message + Bob/Alice encrypted message + Alice encrypted message), you get back the message. The keys are not visible, but the message can easily be read. This is not a real encryption.
– Bgs
Mar 12, 2018 at 17:56

As Thomas Pornin said block cyphers cannot commute, but all stream cyphers would seemingly commute, not merely with themselves, but with different stream cyphers. A commonly used stream cypher is the ChaCha cypher in NaCL by DJB.

Now stream cyphers require care in their usage. In particular, NaCl wants two inputs, a key that must be kept secure, and a random nonce that need not be secure, but must never be reused. It might be tricky to apply this commutativity by making the key material and nonce available at exactly right point in time.

As an aside, one-time pads would usually be produced deterministically using stream cyphers, making the distinction slightly artificial in practice.

• Don't do this. Using stream ciphers in this fashion will appear to work, but it's trivially broken: just XOR all of the transmitted messages together to get the original plaintext. The reason for this is that by encrypting one message and decrypting another, you're reusing the nonce that, as you even point out, "must never be reused". Aug 21, 2018 at 14:12
• You did not read my answer. I'm obviously not encouraging key and nonce reuse. In particular, anonymous networking protocols often do exactly what I describe and yes do exploit the commutativity of stream ciphers. All sane ones prevent the trivial attack you describe, but some mixnet packet formats even have security proofs. Anonymity protocol mostly make the key materials available one at endpoints and at one hop in the middle. Feb 16, 2020 at 4:53
• Can you explain exactly how you'd use stream ciphers in a commutative way without succumbing to that attack? Because as far as I can see, it's unavoidable. Feb 16, 2020 at 5:29
• It's onion encryption. You think onion encryption reuses keys in trivially broken ways? We've layers with different keys so M xor S(k1,n1) xor S(k2,n2) xor S(k3,n3). In practice, you always need commutativity when creating an AEAD-like packet with MACs while preserving lengths because you make routine info body and tails running backwards and forwards. See cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf There exist protocols in which mixes add their own layers too, fairly questionable anonymity, but folks attempt to make the crypto work. Feb 16, 2020 at 18:48
• One may also want to note that stream ciphers are unsuitable for use in Shamir's Three-Pass-Protocol - the prime application for commutative ciphers. Feb 16, 2020 at 19:20