9
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ A good way to build $P$ would be through the use of an MDS Cauchy matrix with multiplication done in a finite field, a 16x16 8-bit matrix would match a 128-bit block cipher, you could also add an s-box and its inverse on the IO to the matrix $\endgroup$ – Richie Frame Oct 30 '15 at 23:51
  • $\begingroup$ This reciprocal cipher reminds me a lot of the (usually not reciprocal) "single-key Even-Mansour cipher". $\endgroup$ – David Cary Mar 31 '16 at 19:19
5
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ You have shown that such a primitive would not meet the standard security definitions of a block cipher; what you haven't shown is whether there would be any security issues if such a primitive were used where we typically use a block cipher, for example, in CBC mode (with an integrity transform) or in a GCM configuration. $\endgroup$ – poncho Oct 30 '15 at 19:48
  • 1
    $\begingroup$ An involutive function can be easily distinguished from a random permutation (as you point out), so such an $F$ is not a pseudorandom permutation. But $F$ built in the way you describe is indistinguishable from a random involution. And it seems to me that most standard block cipher modes applied to a random involution would give CPA security. $\endgroup$ – Mikero Oct 30 '15 at 19:54
  • $\begingroup$ @otus A chosen-ciphertext attack usually only allows us to decrypt a different message. An oracle which can decrypt any given ciphertext (including the ciphertext under attack) trivially allows breaking any cipher with one oracle query per message. $\endgroup$ – Aleph Oct 31 '15 at 9:37
  • $\begingroup$ @Aleph, yes, but unless you define a mode of operation you don't know if a decryption oracle would break the encryption. Similarly, you don't know if an involution would be secure. I guess I didn't really add anything to poncho and Mikero's comments, so deleted. $\endgroup$ – otus Oct 31 '15 at 10:40
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ GCM is roughly CTR mode integrated with a reasonably independent MAC, so it may very well be secure. $\endgroup$ – K.G. Jul 23 '16 at 9:02
  • $\begingroup$ @K.G. true, it seems likely to be secure. $\endgroup$ – otus Jul 28 '16 at 5:21
  • $\begingroup$ Are you saying collisions are less likely for a PRP in CTR mode than for a PRF in CTR mode? $\endgroup$ – Melab Dec 22 '17 at 12:14
  • $\begingroup$ @Melab, yes, because CTR mode relies on each input to the PRP being different and a PRP will never produce the same value for different inputs. $\endgroup$ – otus Dec 22 '17 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.