XOR cipher with fixed key and known relation among plaintexts

Question

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?

Answer 1

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.

Answer 2

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.