Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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}$.

share|improve this question
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

1 Answer 1

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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