Skip to main content
5 of 9
Polish
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

The question likely really is:

It is known $c$ with $c = E_{K_1}(m \oplus K_1 \oplus K_2)$, and a few distinct plaintext/ciphertext pairs $(m_i,c_i)$, that is with $c_i = E_{K_1}(m_i \oplus K_1 \oplus K_2)$. However, $c$ is not one of the $c_i$ (which would make finding $m$ trivial).

Define a strategy to find $m$, despite the terms $\oplus K_1 \oplus K_2$ in how the cipher operates. That should work whatever the internals of $E$ (which is assumed known per Kerckhoffs's principle, but not given). If necessary, assume that a lot of computing power is available, enough for about $2^\ell$ encryptions or decryptions using $E$ and whatever key, which would be enough to brute-force a normal use of $E$ as $m\mapsto E_K(m)$.


Hint 1: How would you confirm (with excellent confidence) or infirm (overwhelmingly often) an hypothetic guess of $K_1$, despite not knowing $K_2$?


Hint 2: Put yourself in the skin of an attacker. You have a black box implementing $E$, where you can enter key and data each as $\ell$ bits, press one of two buttons marked "encrypt" or "decrypt", and that applies $E$ or $E^{-1}$ as asked, data gets changed, and you see the new value thanks to $\ell$ LEDs wired on the data bits. In particular, if you press the other button, the data gets back to the previous value. That black box is an encryption/decryption oracle for $E$ (though one not knowing the key, as some oracles do; rather, it operates with any given key).

Assume that some fairy gave a tip that $K_1$ is that $\ell$-bit value. How do you put that box and what you know (stated in this answer) to use in order to confirm or infirm the tip, then (if confirmed) find $m$ ?

Next, replace the fairy (these are harder to implement with silicon chips than oracles are) by a lot of uses of the black box.


Hint 3: (hover mouse to see)

You'll need at least two plaintext/ciphertext pairs to check the fairy's tip, and three to carry the attack.

fgrieu
  • 145.5k
  • 12
  • 319
  • 611