Take the 2-minute tour ×

Is there exist a ciphering approach such that encrypting and decrypting order is arbitrary? Like using two padlocks on the same lock loop.

That is, if there are two keys (or keypairs) K1, K2, message M, and the cryptogram C is obtained as (for example) C=M*K1*K2 (where * denotes ciphering), then the message M can be retrieved in each of the following ways: 1) M=C*K1*K2, 2) M=C*K2*K1 (here * denotes deciphering).

Obviously, XOR is a trivial candidate. Do any cryptographically strong examples exist?

share|improve this question
Stream ciphers have this property. –  GregS Jun 6 '11 at 11:15
@GregS only non-synchronizing stream ciphers based on a commutative combining operation. (there are others!) –  Henno Brandsma Jun 8 '11 at 7:53
add comment

3 Answers

up vote 9 down vote accepted

Take any strong block cipher (e.g. AES) and run it in Output Feedback Mode or Counter Mode.

Since OFB and CTR are essentially just XOR with a cryptographic pseudo-random stream, this will have the property you seek. Just make sure your K1 and K2 are independent.

Also, since OFB and CTR are NIST-approved (and widely-used) block cipher modes, they will be "cryptographically strong" as long as you implement them correctly and use a strong underlying block cipher.

share|improve this answer
add comment

What you ask for is known as a commutative cipher. One application of such ciphers is Shamir's three pass protocol (which is often explained using padlocks).

It is unclear what you mean by "cryptographically strong". I.e. one requirement that is frequently necessary is that an adversary can not learn the message if he learns the encryption of the message with K1, then encryption of the message with K2 and the encryption of the message with both K1 and K2. This requirement is obvious in the case of Shamir's three pass protocol.

It is easy to see that stream ciphers do not satisfy the requirement above. Hence it would misleading to call a stream cipher a "cryptgraphically strong commutative cipher". Equally easy to break under the assumptions above is Rasmus Fabers proposal (which I think is a construction proposed by Bruce Schneier for something a little different).

Strong commutative ciphers can be based for example on modular exponentiation. The Massey-Omura protocol is a great example.

share|improve this answer
OFB and CTR both require a random initialization vector each time you encrypt something. (And so will any stream cipher operating in an "approved" mode, I would wager.) So just because you encrypt something twice with the same key, your adversary cannot learn anything useful because the IVs for each encryption will be different. –  Nemo Jun 8 '11 at 16:22
@Nemo: It is a really trivial exercise usually given in basic crypto classes that instantiating Shamir's three pass protocol with stream ciphers is insecure. Write it down and check yourself. What really matters are the assumptions: the adversary sees the ciphertext after encryption with K1, after encrypting with K2 and then again after decrypting with K1. I.e. one assumes that the message is sent to a different party after each encryption and decryption. –  Accipitridae Jun 10 '11 at 17:50
add comment

If the size of the cryptogram is not an issue, you can easily construct such a cipher based on any other cipher:

Have the first encryptor generate a random bitmask B1 of size >= M. Encrypt the bitmask with the original cipher and key and transmit this encryption together with B1 ^ M.

Similarly, the next encryptor generate a new random bitmask B2, encrypts it with his key and transmits both encrypted bitmasks and B2^(B1^M). (and so on for N encryptors).

To decrypt, just decrypt each of the bitmasks in any order and xor them onto the masked message.

share|improve this answer
add comment

Your Answer


