Take the 2-minute tour ×
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
2  
Like I said on your other question, what have you tried? Where are you stuck? This isn't a question answering service. –  mikeazo 2 days ago
    
@mikeazo, allright :) could you check my updated post? –  nopenope 2 days ago
    
Is $m$ a single block? Is $m$ known to the attacker? –  mikeazo 2 days ago
    
How much storage space does the attacker have? –  mikeazo 2 days ago
    
Let's assume that $m$ is a single block, and is not know to the attacker. And space is infinite –  nopenope 2 days ago

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 23 hours ago
1  
@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 23 hours ago

Your Answer

 
discard

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.