I have three messages, each known to be XOR-encoded, with the same key used for each message of this XOR cipher.

  • Encoded message 1: $e_1\,=\,00100111010$
  • Encoded message 2: $e_2\,=\,01001110110$
  • Encoded message 3: $e_3\,=\,11010110101$

I also have an extra information: I know that the decoded contents of $e_1\oplus e_2$ is equal to the decoded contents of $e_3$.

How would one go about solving this problem, in order to get the key and decode the contents of the message?

  • 2
    $\begingroup$ Hint. $c_1 \oplus c_2 = (m_1\oplus key) \oplus (m_2 \oplus key) = m_1 \oplus m_2$. Then, since $m_1 \oplus m_2 = m_3$, you can get the key. $\endgroup$
    – kelalaka
    May 18 '20 at 17:23
  • $\begingroup$ I still don't get how to solve it, I'm pretty new to XOR operators, Is there a property I'm not aware of? $\endgroup$ Jun 30 '20 at 23:51

I'm somewhat new at this, so there might be a better way to solve this, but this is how I solved it. If I understand right, the extra parameter given is written as: $$\mathtt{}({e}_{1} \oplus k) \oplus ({e}_{2} \oplus k) = e_{3} \oplus k$$ (that is, the decoded contents of e1 xor'd with the decoded contents of e2 is equal to the decoded contents of e3)

The brackets only provide readability, and so the equation is the same without them. This means that we have $$\mathtt{}{e}_{1} \oplus k \oplus {e}_{2} \oplus k = e_{3} \oplus k$$

There are 2 "$\mathtt{}\oplus k$"'s on the left hand side here, so they can be removed to get the following:

$$\mathtt{}{e}_{1}\oplus {e}_{2} = e_{3} \oplus k$$

The right hand side can also be replaced with $\mathtt{}m_{3}$ to denote decrypted $\mathtt{}e_{3}$:

$$\mathtt{}{e}_{1}\oplus {e}_{2} = m_{3}$$

$\mathtt{}e_{1}$ and $\mathtt{}e_{2}$ are given, and by xoring them we can get:

$$\mathtt{}{m}_{3} = 1101001100$$ and we also know that: $$\mathtt{}{m}_{3} = {e}_{3} \oplus {k}$$

Now we have both $\mathtt{}m_{3}$ and $\mathtt{}e_{3}$, and we can now solve for $\mathtt{}k$:

  1. xor both sides by $\mathtt{}e_{3}$ $$\mathtt{}{m}_{3} \oplus {e}_{3} = {e}_{3} \oplus {e}_{3} \oplus {k}$$
  2. remove $\mathtt{}e_{3} \oplus e_{3}$ from right hand side: $$\mathtt{}{m}_{3} \oplus {e}_{3} = {k}$$
  3. substitute in $\mathtt{}m_{3}$ and $\mathtt{}e_{3}$'s values: $$\mathtt{}1101001100 \oplus 11010110101 = {k}$$
  4. giving...: $$\mathtt{}k = 10111111001$$

You can now decode all 3 encrypted messages: $$\mathtt{}m_{1} = 10011000011$$ $$\mathtt{}m_{2} = 11110001111$$ $$\mathtt{}m_{3} = 01101001100$$ Hope that helps.

  • $\begingroup$ Welcome to crypto.SE! Your answer is nice and useful. FYI, we prefer to not give the solution for what obviously amounts to homework, except for self-answers, or after a delay (as is the case here). Instead, practice is to give a hint in comment, or perhaps an answer giving the notions needed. Should you want to improve your answer, you will find help on $\LaTeX$ / Mathjax there and there. Specifically, \mathtt{} does nothing when the brace is empty; alignment can be obtained with begin{align} $\endgroup$
    – fgrieu
    Jul 1 '20 at 6:27

This question is about the properties of the bitwise eXclusive-OR operator (also known as XOR or $\oplus$), which is very common in cryptography. It's the bitwise operator for the similarly named and noted bit operator XOR, which truth table is

$$\begin{array}{c|c|c|c|c|c} \text{first/left input}&a&0&0&1&1\\ \text{second/right input}&b&0&1&0&1\\ \hline \text{output}&a\oplus b&0&1&1&0 \end{array}$$

A bitwise operator operates on bitstrings of equal length, and applies a boolean operator to bits of equal ranks in its inputs to form the bit of that rank in the output. Thus the bitwise XOR operator simply applies the above table for each bits of the input. An example with $8$-bit bitstrings:

$$\begin{array}{c|c|c|c} &\text{bitstrings}&\text{binary}&\text{hexadecimal}\\ \hline \text{first/left input}&A&00110001&\tt{31_h}\\ \text{second/right input}&B&01011100&\tt{5c_h}\\ \hline \text{output}&A\oplus B&01101101&\tt{6d_h}\\ \end{array}$$

The bitwise XOR operator $\oplus$ inherits the properties of the bit operator $\oplus$:

  • associativity: $\forall X$, $\forall Y$, $\forall Z$, $\ (X\oplus Y)\oplus Z\,=\,X\oplus(Y\oplus Z)$
  • commutativity: $\forall X$, $\forall Y$, $\ X\oplus Y\,=\,Y\oplus X$
  • there's an identity element, that's the all-zero bitstring: $$\forall X,\ X\oplus{\underbrace{0\ldots0}_{|X|\text{ bits}}}\,=\,X\,=\,{\underbrace{0\ldots0}_{|X|\text{ bits}}}\oplus X$$ where $|X|$ is the bit width of $X$.
    Equivalently: $\forall X$, $\ X\oplus0^{|X|}\,=\,X\,=\,0^{|X|}\oplus X$.

    For $8$-bit operands as in the example above, $0^{|X|}$ is $00000000$ or $\tt{00_h}$.
  • Each element is it's own inverse (or opposite): $\forall X$, $\ X\oplus X\,=\,0^{|X|}\,=\,{\underbrace{0\ldots0}_{|X|\text{ bits}}}$

The first three properties are that of the internal law (equivalently: operation) of a commutative group (equivalently: Abelian group).

The last property makes the group a Boolean group. Specifically, the Boolean group of bitstrings of $n$ bits, noted $\left(\{0,1\}^n,\oplus\right)$

The question operates on that group for $n$ of eleven. It boils down to writing the statement a equations, and solving these by applying the stated properties. If one gets stuck, there are hints in comment, and a worked solution in the other answer.


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.