# Recovering original bit vectors that constituted XORed binary vectors

I am trying to unscramble received data packets. Each packet is divided into 3 parts ($$A$$, $$B$$ and $$D$$) with equal lengths. In every packet, each of these parts are scrambled/encrypted with an unknown code $$C_i$$.

We can tabulate these received packets in the format shown in the table below, where $$\oplus$$ denotes the XORx operation:

﻿ $$\bf{A}$$ $$\bf{B}$$ $$\bf{D}$$
$$\bf{C_1}$$ $$A \oplus C_1$$ $$B \oplus C_1$$ $$D \oplus C_1$$
$$\bf{C_2}$$ $$A \oplus C_2$$ $$B \oplus C_2$$ $$D \oplus C_2$$
$$\bf{C_3}$$ $$A \oplus C_3$$ $$B \oplus C_3$$ $$D \oplus C_3$$
$$\bf\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$
$$\bf{C_n}$$ $$A \oplus C_n$$ $$B \oplus C_n$$ $$D \oplus C_n$$

What I have is the XOR-ed values ($$A \oplus C_1 \dots D \oplus C_n$$) and I am trying to retrieve the original values of $$A$$, $$B$$ and $$D$$, as well as all the $$C_1$$ through $$C_n$$.

Some of the packets (in HEX) that I am playing with are attached.

• What do you mean with "Some of the packets (in HEX) that I am playing with are attached."? Aug 12, 2022 at 10:28

I'm afraid that you can't!

If the values that you want to recover are $$A$$, $$B$$, $$D$$ and $$C_i$$, let $$X$$ be any value of the same length. Now let $$A'=A\oplus X$$, $$B'=B\oplus X$$, $$D'=D\oplus X$$ and $$C_i'=C_i\oplus X$$ for all $$1\le i\le n$$. Now note that $$A'\oplus C_i'=A\oplus C_i,\quad B'\oplus C_i'=B\oplus C_i,\quad D'\oplus C_i'=D\oplus C_i$$ for all $$1\le i\le n$$ so that $$A'$$, $$B'$$, $$D'$$ and $$C_i'$$ are also a legitimate solution to the problem. There's no way to distinguish the original answer form all of the non-causal answers.

You can recover $$A\oplus B=(A\oplus C_1)\oplus (B\oplus C_1)$$ or the XOR of any other two unknowns. Likewise if you know any one of the unknowns, you can solve for all the others. However without information beyond that presented in the question, you cannot.

• Yep, but any information about the plaintext of either $A$, $B$ or $D$ at a certain location that influences a bit value will immediately also leak information about $C$ and then the other plaintext values as well, of course. Aug 12, 2022 at 10:31

Daniel's answer explains that it's impossible in general, and trivial if you know one of the messages.

But all is not lost, you simply most know something about the messages. It need not be the whole message so ask yourself what do you know?

can you guess a substring? If you were given a part of a message can you guess what happened just before or after? Do you know anything about token frequencies or ngram frequencies?

For natural language one of the techniques is crib draggibg. Guess a common substing, e.g "the" try to place it at various locations for message A which positions leaf to likely message fragements on the other messages? repeat with several common segmenta and different starting messages? can you infer continuation for some of the revealed sections do they lead to meaningfull message fragements on other message.

Many binary formats have internal structure as well, with guessable components, It's not unique to natural language but you do need to know something.