"Fixing" PCBC mode?

ManRow

1/23/23, 10:25 AM

In PCBC mode, one encrypts and decrypts via $$ C_i = E(P_i \oplus P_{i-1} \oplus C_{i-1}) \Longleftrightarrow P_i = D(C_i) \oplus P_{i-1} \oplus C_{i-1} $$ (where $P_0 \oplus C_0 = IV$), which has good error propagation in that modifying any $C_i$ would break the decryption of all $P_j$ where $j \ge i$.

However, there is a bug in that swapping $C_i$ and $C_{i+1}$ does not affect the decryption of subsequent plaintexts $P_j$ (for $j > i + 1$). Wikipedia also mentions this, saying

On a message encrypted in PCBC mode, if two adjacent ciphertext blocks are exchanged, this does not affect the decryption of subsequent blocks.[27] For this reason, PCBC is not used in Kerberos v5.

But, what if we instead did the "xor" after encryption? In other words, encrypt/decrypt via $$C_i = E(P_i) \oplus P_{i-1} \oplus C_{i-1} \Longleftrightarrow P_i = D(C_i \oplus P_{i-1} \oplus C_{i-1})$$ (where $P_0 \oplus C_0 = IV$). It seems like this simple change would fix those ciphertext swapping bugs for PCBC, and still preserve its great error propagation properties...

111

0 + 0

encryption

block-cipher

modes-of-operation

malleability

error-propagation

fgrieu

1/23/23, 10:51 AM

I'm ready to bet there remains some alteration of the ciphertext, not needing the key, that does not alter the rest of the ciphertext. A meta-argument is that FPCBC is not used in practice. I suggest the OP finds that attack, and makes a nice self-answer. When self-accepted, they get a (small) reward in rep, and can be upvoted normally.

ManRow

1/23/23, 11:38 AM

Would that be by modifying the IV and first block of ciphertext? The first plaintext block $P_1 = D(C_1 \oplus IV)$, so we can alter both $C_1$ and $IV$ together (just as long as $(C_1 \oplus IV)$ stays the same!) without affecting the decryption of any plaintext...

fgrieu

1/23/23, 2:44 PM

The proposed mode is not CPA-secure. In particular, when we encrypt plaintext comprising the same block repeatedly, the ciphertext is the alternation of two blocks, and that's easily detectable. It is thus inferior to CTR, CBC, OFB, CFB, and PCBC from this elementary standpoint alone. It's plausible it would not even pass a strengthened [penguin test](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_(ECB)) using a larger image with large black and white areas. That does not answer the question about the ciphertext swapping property, but makes it moot.

Score:1

Crypto

ManRow

1/23/23, 11:45 AM

It seems while this scheme fixes the "ciphertext-swapping" problem, it permits modifying the first block of ciphertext $C_1$ and the $IV$ together without affecting the decryption of the message at all.

This is because the first block of plaintext $P_1 = D(C_1 \oplus IV)$, so therefore $C_1$ and $IV$ can be modified "together" without altering $(C_1 \oplus IV)$ and so without affecting the decryption of anything in the message at all...

**Edit: as fgrieu pointed out in the comments, this cipher mode is not even CPA-secure. For example, if we supply plaintext with repeating blocks $P_i = P_{i+1} = \cdots$, then the ciphertext will have $C_j = C_{j+2}$ for all $j > i+1$