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

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

  • $\begingroup$ thanks a lot. Please explain... why $E'_2$ is equivalent to $E'_1$ in known plaintext attack? I don't see why swapping works... $\endgroup$ – nopenope Jun 30 '15 at 19:40
  • 1
    $\begingroup$ @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$. $\endgroup$ – CodesInChaos Jun 30 '15 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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