Order Independent Ciphers

Question

Is there an encryption approach so that the encryption and decryption order is arbitrary? Similar to using two padlocks in one lock cycle.

That is, if there are two keys (or keypairs) K1, K2 , message M , and cryptogram C obtained as (for example) C=M*K1*K2 (where * means encryption), then message M can be obtained in one of the following ways: 1) M=C*K1*K2 , 2) M=C*K2*K1 (here * stands for decoding).

XOR is obviously a trivial candidate. Are there cryptographically strong examples?

Answer 1

Take any strong block cipher (like AES) and run it in 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 are looking for. Just make sure your K1 and K2 are independent.

In addition, since OFB and CTR are NIST-approved (and widely used) block cipher modes, they will be “cryptographically strong” if you implement them correctly and use a strong basic block cipher.

Answer 2

What you ask for is called a commutative cipher. One application of such ciphers is the Shamir protocol with three passages (which is often explained using padlocks).

It is unclear what you mean by "cryptographically strong." That is, one requirement that is often necessary is that the adversary cannot recognize the message if he recognizes the encryption of the message with K1, then the encryption of the message with K2 and the encryption of the message with K1 and K2. This requirement is obvious in the case of the Shamir protocol with three passes.

It is easy to see that stream ciphers do not satisfy the above requirement. Therefore, it would be wrong to call the stream cipher a “cryptographically strong commutative cipher”. Similarly, it is easy to break, in accordance with the above assumptions, the Rasmus Fabers proposal (which, I think, is the design proposed by Bruce Schneier for something a little different).

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

Answer 3

If the size of the cryptogram is not a problem, you can easily build such a cipher based on any other encryption:

Let the first cipher generate a random bit mask B1 size> = M Encrypt the bitmask using the original cipher and key and pass this encryption along with B1 ^ M

Similarly, the next cipher generates a new random bitmask B2 , encrypts it with its key, and transmits both encrypted bitmasks and B2^(B1^M) . (etc. for N encryptors).

To decrypt, simply decrypt each bitmask in any order and xor them into a disguised message.