# Double the key in block cipher - which approach is better?

Assume than you have a block cipher $E(k,m)$ for which the only attack exists has complexity of $2^{64}$. You consider to double the key size by either:

$E'_1(k_1,k_2) := k_1 \oplus E(k_2,m)$

$E'_2(k_1,k_2) := E(k_1,k_2 \oplus m)$

Analyze which approach is better. What is the complexity of attacks on both new schemes?

Find the attack which has the complexity smaller than $2^{192}$ on the following construction: $E'_3(k_1,k_2,k_3):=k_1\oplus E(k_2,k_3\oplus m)$, where each key has 64 bits.

My solution:

$E(k_2,m)$ can be break in $2^{64}$.

$k_1$ can have one of $2^{64}$ values, so brute force attack on $E'_1(k_1,k_2)$ is $2^{64+64}=2^{128}$.

$E'_2(k_1,k_2)$ is still $2^{64}$ because $k_2\oplus m$ has also 64 bits.

similarly, $E'_3(k_1,k_2,k_3)$ can be break in $2^{64}$.

-
Like I said on your other question, what have you tried? Where are you stuck? This isn't a question answering service. –  mikeazo Jun 29 at 16:49
@mikeazo, allright :) could you check my updated post? –  nopenope Jun 29 at 17:33
Is $m$ a single block? Is $m$ known to the attacker? –  mikeazo Jun 29 at 17:37
How much storage space does the attacker have? –  mikeazo Jun 29 at 17:38
Let's assume that $m$ is a single block, and is not know to the attacker. And space is infinite –  nopenope Jun 29 at 17:41

They're both broken under known plaintext attack, where attacker knows two (plaintext, ciphertext) pairs, $(m_1,c_1)$ and $(m_2,c_2)$:

• $E'_1(k_1,k_2) := k_1 \oplus E(k_2,m)$

$E'_1(k1,m_1) \oplus E'_1(k1,m_2)=E(k1,m_1) \oplus E(k1,m_2)$

The attacker simply computes $E(k1,m_1) \oplus E(k1,m_2)$ for every possible value of $k_1$ and compares it with $c_1 \oplus c_2$. This eliminates $k_2$ from the attack for a computational complexity of $2^{64}$ with negligible memory.

• $E'_2(k_1,k_2) := E(k_1,k_2 \oplus m)$

$D'_2(k_1,k_2) := D(k_1, c) \oplus k_2$

Where $D$ is the decryption function corresponding to $E$. Thus $E'_2$ is equivalent to $E'_1$, except that $c$ and $m$ are swapped, so the same attack applies:

$D'_1(k_1,c_1) \oplus D'_1(k1,c_2)=D(k1,c_1) \oplus D(k1,c_2) = m_1 \oplus m_2$

• $E'_3(k_1,k_2,k_3):=k_1\oplus E(k_2,k_3\oplus m)$

The attacker can either eliminate $k_1$ or $k_3$ with the same technique as above, so they either need to brute-force $k_1|k_2$ or $k_2|k_3$ for a cost of $2^{64+64}=2^{128}<2^{192}$.

Under a ciphertext only attack, $E'_2$ is weaker since the attacker can compute $D(k_1,c_1) \oplus E(k_1,c_2)$, obtaining $m_1 \oplus m_2$. Since $m_1 \oplus m_2$ is often distinguishable from random, this should suffice to break it in many applications.

But since known-plaintext is already a very weak assumption (compared to the common adaptive-chosen-plaintext attacks), cryptographers rarely bother with ciphertext only attacks. So I'd consider them equally weak.

You should instead xor the key into both $m$ and $c$, a construction known as Even Mansour, or Xor-encrypt-xor.

-
thanks a lot. Please explain... why $E'_2$ is equivalent to $E'_1$ in known plaintext attack? I don't see why swapping works... –  nopenope Jun 30 at 19:40
@nopenope If you look at the decryption operation $D^\prime_2$ instead of the decryption operation, you get the same formula as for for $E^\prime_1$, except that $c$ and $m$ are swapped. Since an attacker knows both $m$ and $c$, they don't care if they're attacking $E^\prime_1$ or $D^\prime_2$. –  CodesInChaos Jun 30 at 19:42