Security of a self-decrypting block-cipher?

Question

If I have a block-cipher like for example AES, a plaintext $x$, we use different function to encrypt and decrypt : $\text{encrypt}(x) = y$ , $\text{decrypt}(y)=x$. Now, if we build a function with a permutation $P(x)$ with $P(P(x))=x:$ $F(x)=\text{decrypt}(P(\text{encrypt}(x))$ , we have $F(F(x))=x$, a function that encrypts and decrypts.

Does this reduce the security or allow new attack on the cipher? I know stream cipher already encrypts and decrypts using the same function but what about a block-cipher ?

Answer 1

As I understand, your question is about using an involutive function $F$ as a block cipher. This function is constructed as $F(x) = D(P(E(x)))$, for some (let's assume secure) block cipher represented by $(E, D)$. I will assume the encryption and decryption keys are equal such that the same holds for $F$. Below is a generic attack that only uses the involutive property of $F$, there might be additional problems (depending on $E$ and $D$).

It is typically required that block ciphers are secure against chosen-plaintext attacks. In the example it is trivial to obtain $x$ given $y = F(x)$ and an encryption oracle. We just ask the oracle to encrypt $y$. In other words, an encryption oracle is equivalent to a decryption oracle. Practically speaking, the attacker just needs to get his victim to encrypt something that he already encrypted earlier. Do not underestimate this attack; it is often easier to trick the victim into encrypting something than you might suspect.

Note that many block ciphers do use involutions in their structure. This could be useful, for example, to reduce the size of the implementation.

What about stream ciphers? In a stream cipher, the state of the cipher constantly changes. This effectively means that the function $F$ is variable, so you'd need a much stronger oracle (which can somehow rewind the state).

Answer 2

For some modes of operation you can easily show that an involution would be insecure:

• OFB would be most clearly insecure, since the keystream just repeats the nonce/IV and its corresponding encrypted block.
• CFB would likewise be insecure, since zero blocks encrypt just like with OFB. This is of more limited advantage to an attacker, but far from secure.
• CBC mode again has problems with zero blocks, since the following block's ciphertext can be decrypted simply by XORing it with the ciphertext of the block two back.

Similarly, CBC-MAC, including some of its variants, would be broken, because adding two blocks of zeros anywhere in the message would not alter its authentication tag.

---

Now for the handwavy part.

With CTR mode you are going to have worse bounds on the amount of ciphertext you can encrypt. Normally CTR mode is secure up to roughly $2^{b/2}$ blocks, because at that point you would expect outputs to collide with a PRF but not with a PRP. Equivalently, at that point you expect ciphertext blocks to collide, which tells you that the message blocks differ.

With an involution you have the additional case that the output may collide with another input block, which tells you the corresponding output. That has an equal chance of happening, doubling the chance that one of these cases happens and thus about halving the amount of data you can encrypt. (Or reducing it by a factor of $\sqrt{2}$, but close enough.)

However, beyond that I think CTR mode would remain secure, as long as the attacker cannot control the nonce.

---

AEAD modes are more complicated to analyze, especially when they use the same key for encryption and authentication. GCM is probably secure, since its security comes down to that of CTR both for encryption and authentication. Others like CCM might not be, due to the use of CBC-MAC.