# Security of a parallelizable block cipher mode

This is the scheme of a parallelizable block cipher mode of operation:

• $IV$ is the initialization vector.
• $BN$ is the zero-based index number of a block in a stream of data.
• $BT$ is the tweak that is used in the encryption process of each block.
• $K$ is the key.
• $PT$ is a plaintext block.
• $CT$ is a ciphertext block.

Encryption and decryption are as follows:

• $BT = IV \boxplus BN$
• $CT = \mathrm{Encrypt}(K, PT \oplus BT)$
• $PT = \mathrm{Decrypt}(K, CT) \oplus BT$

• It is parallelizable.
• It does not suffer from the drawbacks of ECB mode.
• There is no cascading effect as seen in CBC, PCBC, and OFB modes of operation.

Are there any security drawbacks with this scheme?

Update: I've considered the criticism and now $BT = \mathrm{Encrypt}(K, IV \boxplus BN)$. What impact does this have on the security?

• "There is no cascading effect as seen in CBC, PCBC, and OFB modes of operation." This is not always a good thing. Sometimes the cascading effect is a desirable feature. Also, OFB doesn't have this effect, iirc. CFB does, however. Feb 4, 2016 at 0:26
• what happens if you blocks with values that increment sequentially? Feb 4, 2016 at 0:33
• What benefits are you hoping to get from this method that CTR doesn't already provide? Feb 4, 2016 at 0:47
• Maybe a silly question, but what's $\boxplus$? I assume $\oplus$ means bitwise XOR, but I don't really know a standard meaning for $\boxplus$. Feb 4, 2016 at 0:51
• @IlmariKaronen I was wondering the same. I imagine it's more of an arithmetic addition rather than xor or some bitwise operation. Someone correct me on this though, if I'm wrong. Feb 4, 2016 at 0:53

One of the basic security requirements of a block cipher mode of operation is that it is indistinguishable under chosen plaintext attack (IND-CPA). Essentially, this means that, if an attacker chooses two messages $m_A$ and $m_B$ and the defender randomly returns either $\text{Encrypt}(K, m_A)$ or $\text{Encrypt}(K, m_B)$ (with $K$ kept secret from the attacker), the attacker should be unable to determine whether the defender chose $m_A$ or $m_B$.

This scheme is not secure under that definition. Here's how an attacker can win (assume $n$ is the block size).

• The attacker submits $m_A = 0^n \| 0^n$ (two zero blocks) and $m_B = 0^n \| 0^{n-1}\|1$ (a zero block, and a block that is all zeros except the last bit).
• If the defender chooses $m_A$, it will return $E(K, 0^n \oplus BT_0) \| E(K, 0^n \oplus BT_1) = E(K, IV) \| E(K, IV \oplus (0^{n-1} \| 1))$. In other words, the output blocks will be different.
• If the defender chooses $m_B$, it will return $E(K, 0^n \oplus BT_0) \| E(K, (0^{n-1}\|1) \oplus BT_1)$, where $E$ is the block cipher. This simplifies to $E(K, 0^n \oplus IV \oplus 0^n) \| E(K, (0^{n-1}\|1) \oplus IV \oplus (0^{n-1}\|1)) = E(K, IV) \| E(K, IV)$. In other words, the output blocks will be the same.

The attacker can easily distinguish which plaintext the defender chose. This violates IND-CPA, which often leads to vulnerabilities in real-world systems.

Counter mode seems to offer similar benefits without the security problems: parallelizable, random access, etc.

• I've updated the question and the way $BT$ is calculated. Feb 10, 2016 at 7:20
• The problem with counter mode is that it is vulnerable to bit flipping. Block ciphers are not. Feb 10, 2016 at 7:22
• @Melab Bit flipping can easily be guarded against by using a MAC, which you should be anyway. What you want to accomplish could be done with CTR mode and some sort of MAC, or just bundle it in GCM. Feb 10, 2016 at 8:57

In essence it seems to be a sort of mixture of CFB and CTR.

I see a possible issue where encrypting sequential values will show up as repeating patterns in the ciphertext. Consider the following 4 bit example.

$$PT_0 = 1010$$ $$PT_1 = 1011$$ $$PT_2 = 1100$$ $$PT_3 = 1101$$ $$IV = 1110$$ Assuming $PB$ is the plaintext block directly before encryption. $$PB_0 = PT_0 \oplus (IV \boxplus 0) = 1010 \oplus (1110 \boxplus 0) = 0100$$ $$PB_1 = PT_1 \oplus (IV \boxplus 1) = 1011 \oplus (1110 \boxplus 1) = 0100$$ $$PB_2 = PT_2 \oplus (IV \boxplus 2) = 1100 \oplus (1110 \boxplus 2) = 1100$$ $$PB_3 = PT_3 \oplus (IV \boxplus 3) = 1101 \oplus (1110 \boxplus 3) = 1100$$ The $PB$ blocks repeat very often, which means the ciphertext blocks will too. The same would apply to the full 128 bit version. Therefore, this has problems similar to ECB mode.

• I've updated the question and the way $BT$ is calculated. Feb 10, 2016 at 7:20
• @Melab Your update effectively makes BT a pseudorandom stream. It can be XOR'd with the plaintext directly to get the ciphertext, skipping the encryption, to be more efficient. However, if you do that, you've invented CTR mode exactly. Feb 10, 2016 at 8:44

You do not get semantic security; a chosen plaintext attack can (with high probability) distinguish this mode from random.

Consider the case where you are encrypting a two block message $(B, B \oplus 1)$ (for an arbitrary value B). Then, if IV (which I assume is selected randomly) happens to have an lsbit of 0 ($p = 0.5$), then the two ciphertext blocks generated will be identical.

In general, if the blocks that make up the message are related (that is, have small differences), then this mode will, at times, leak that.

Given that we have parallelizable modes that don't have this property (and do have semantic security, assuming a strong block cipher), I don't see any reason to use this mode.

I have seen a proposal (by Richard Schroeppel) of a similar mode; however instead of doing a simple increment of $BT$ between blocks, he did a multiply by 2 (in $GF(2^n)$); that doesn't have the problems with related blocks.

• How about $BT = \mathrm{Encrypt}(K, IV \boxplus BN)$? Feb 9, 2016 at 3:10
• @Melab: so, you're doing 2 Encrypt operations per plaintext block??? Feb 9, 2016 at 13:13
• This is a hypothetical, so sure. Now, what about the security of it? Feb 9, 2016 at 16:37
• I've updated the question and the way $BT$ is calculated. Feb 10, 2016 at 7:20
• Is it still semanitically insecure? Jul 24, 2023 at 18:32