# Composing and Inverting Symmetric Encryption Keys

Using a symmetric encryption algorithm $E$ on a message $M$, users usually send $E(M)$ to the recipient and then the recipient will compute $E^{-1}(E(M))=M$ to retrieve the message. For what symmetric encryption algorithms would it be equally secure to instead send $E^{-1}(M)$ and have the recipient compute $E(E^{-1}(M))=M$?

Suppose we have two symmetric keys $K$ and $L$ to encrypt $M$. We could compute $K(L(M))=M'$. Is there any secure encryption algorithms such that from $K$ and $L$, we can compute a new key $KL$ where $KL(M)=K(L(M))$?

I know XOR has both of the above properties if used on just one block. But my question is: does there exist any secure symmetric algorithms that have both properties and can be used for multiple blocks?

-
Hi, I've replaced the homomorphic-encryption tag with more relevant ones because the rest of your question didn't mention it. If you meant for the encryption to be homomorphic as well, feel free to edit it back in. –  otus Aug 1 at 8:57
A customized version of CTR mode can do what you are looking for. For question 2, it would twice invoke the block cipher with each key and xor the outputs. –  Richie Frame Aug 1 at 9:48

As block ciphers are invertible, and since XOR is too - the main operation on the key stream for many stream ciphers - the resulting encryption/decryption modes of operation are often invertible. For stream ciphers that create a key stream that is XOR'ed with the plaintext, it is even true that $E = E^{-1}$.

Some block cipher modes of operation however require padding. If padding is included in $E$ then then you cannot perform $E^{-1}(M)$, because the padding would likely fail or result in a wrongly sized plaintext.

• ECB mode is invertible, but requires padding
• CBC mode is invertible, but requires padding
• CFB, OFB and CTR modes generate a key stream are therefore invertible, they do not require padding

Any authenticated cipher is of course not invertible as $E$ would include creation of the authentication tag, (and $E^{-1}$ includes the verification of an authentication tag that isn't there).

Usually a (block) cipher has the same security for $E$ as for $E^{-1}$. It would however be advisable to use the cipher as intended, or verify (somehow) that the security conditions hold.

As for the keys, that's an entirely different question. If you have two (possibly identical) encryption functions $E_1$ and $E_2$ then you could create an encryption function $E_3(K_3, M) = E_2(K_2, E_1(K_1, M))$ that uses the $K_3 = K_1 | K_2$ as key. I don't see why you couldn't combine that with the previous approach.

Obviously such a construction is not safe by definition; if $E_2 = E_1^{-1}$ and $K_2 = K_1$ then you would have created the identity function. The identity function is not secure. You should also know about meet-in-the-middle attacks. You may want to study the multiple ways that DES can be - and has been - combined in this regard.

-