# 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. – Daffy Feb 4 '16 at 0:26
• what happens if you blocks with values that increment sequentially? – Richie Frame Feb 4 '16 at 0:33
• What benefits are you hoping to get from this method that CTR doesn't already provide? – Daffy Feb 4 '16 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$. – Ilmari Karonen Feb 4 '16 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. – Daffy Feb 4 '16 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. – Melab Feb 10 '16 at 7:20
• The problem with counter mode is that it is vulnerable to bit flipping. Block ciphers are not. – Melab Feb 10 '16 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. – Daffy Feb 10 '16 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. – Melab Feb 10 '16 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. – Daffy Feb 10 '16 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)$? – Melab Feb 9 '16 at 3:10
• @Melab: so, you're doing 2 Encrypt operations per plaintext block??? – poncho Feb 9 '16 at 13:13
• This is a hypothetical, so sure. Now, what about the security of it? – Melab Feb 9 '16 at 16:37
• I've updated the question and the way $BT$ is calculated. – Melab Feb 10 '16 at 7:20