I have a block cipher $E$ that is a permutation of $\{0,1\}^\ell$ for key $K\in\{0,1\}^\ell$.

$c = E_{K_1}(m \oplus K_1 \oplus K_2)$ for unknown keys $K_1, K_2$ is given. I need to figure out the strategy to find the message $m$ and its complexity.

However, before choosing which attack to find the message, I have no idea how to break this block cipher. I'm new to block cipher and it's hard to break a new kind of cipher I haven't seen. I need some help.

If we have some (m, c), and permutation is usually known, then I guess we can figure out $K_1 \oplus K_2$. Is this right? And then, how can we find $K_1$ and $K_2$ respectively? Or $K_1 \oplus K_2$ is sufficient to find the original message?

  • 1
    $\begingroup$ Oh, regarding $E$, you are right. That's what I meant above. $\endgroup$ – achilles Apr 8 at 13:52
  • $\begingroup$ You mean I need to use stronger attack model, such as chosen plaintext/ciphertext atttack? $\endgroup$ – achilles Apr 8 at 13:53
  • $\begingroup$ I took the liberty to partially clarify the original question in the way the OP confirmed that it should be. $\endgroup$ – fgrieu Apr 8 at 14:29
  • $\begingroup$ Is this a homework question? $\endgroup$ – kelalaka Apr 8 at 15:39
  • $\begingroup$ @kelalaka Yes, which I struggle to solve :( I prefer to challenge and think on my own but deadline is coming $\endgroup$ – achilles Apr 8 at 15:42

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.

Further hints (hover mouse to see)

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


4. You'll need a mere two uses of the box to check that fairy's claim, and very little extra computations that one can carry with pencil and paper to note intermediary results. Addition seems complicated in comparison.


5. You can achieve that with a single button of the black box, but not any button.


6. If the fairy gave the right $K_1$, also putting the values of $m_0$ and $c_0$ to use, a single precise use of the black box plus a little extra allows to find $K_2$. The rest is easy.

| improve this answer | |
  • $\begingroup$ Oh, is there a way to confirm our guess of $K_1$ which implies we can get m with $2^l$ complexity? Let me think for some time to find that. $\endgroup$ – achilles Apr 8 at 15:04
  • $\begingroup$ I got to know that $c' = m \oplus K_1 \oplus K_2$ is just a linear scheme and it's easy to break. Is your method also related to break linear scheme? $\endgroup$ – achilles Apr 8 at 15:40
  • $\begingroup$ Is your method a Matsui's algorithm? $\endgroup$ – achilles Apr 8 at 16:00
  • $\begingroup$ Oh, I just thought Matsui's linear cryptanalysis is a solution for linear scheme because there are the word 'linear' in common and was reading Matsui's paper and there is a maximum likelihood and other hard to understand stuff.. $\endgroup$ – achilles Apr 8 at 16:17
  • $\begingroup$ To check the $K_1$ that fairy gives me is the correct value , I think I have to check $2^l$ times because there are $2^l$ possible values of $K_2$. Then $(2^l)^2$ times will be needed to finally confirm $K_1$ and $K_2$ value. $\endgroup$ – achilles Apr 8 at 17:21

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.