Any discernible pattern between two strings that are each XOR'd against a common string?

81 Views Asked by At

Given:

three random strings that are of the same length - A, B, C
RB = A xor B
RC = A xor C

Are there any discernible bit-string patterns to be found between the RB and RC strings?

In other words .... If I hide A before showing you RB and RC - can you figure out that RB and RC were each xor'd against a common string?

1

There are 1 best solutions below

0
On BEST ANSWER

No, there are no patterns or information to be gleaned, provided you keep all three of $A, B$, and $C$ secret -- this "decomposition" of $R_B$ and $R_C$ into $$[\text{the same thing for each}] + [\text{something else, that may be different between the two}]$$

is not unique. In fact, the person receiving $R_B$ and $R_C$ can pick anything they like for $[\text{the same thing for each}]$ (playing the role of $A$ in your example), and find such a decomposition. In particular, there's no way of recovering your $A, B$, and $C$ from $R_B$ and $R_A$ alone, and no hope for a pattern since there are as many "decompositions" of a fixed $R_B$ and $R_C$ as there are bit strings.

I'd like to use the notation $R_B = A + B$ and $R_C = A + C$. This is because the set of all strings of a given length form a vector space over the field with two elements, where the addition $A + B$ is exactly the "exclusive or" of bits in corresponding positions of $A$ and $B$ (also called addition modulo $2$).

You choose your $A, B, C$ and keep them secret. I'll use $\overline{A}, \overline{B}$, and $\overline{C}$ as the notation for my versions of $A, B$, and $C$.

Given $R_B$, I pick any old string $\overline{A}$ and define $\overline{B} = \overline{A} + R_B$, from which it follows $R_B = \overline{A} + \overline{B}$ by adding $\overline{A}$ to both sides, since $\overline{A} + \overline{A} = 0$. Similarly, I'll define $\overline{C} = \overline{A} + R_C$.


As an example: Let's say you choose $A = 1101,\, B = 1000,\, C = 0010$, and hand me $$R_B = 1101 + 1000 = 0101; \qquad R_C = 1101 + 0010 = 1111.$$

I can choose my $\overline{A} = 0110$, calculate my $\overline{B} = \overline{A} + R_B = 0110 + 0101 = 0011$, and write

$$R_B = 0101 = 0110 + 0011 = \overline{A} + \overline{B}.$$ Similarly, I would define my $\overline{C} = \overline{A} + R_C = 0110 + 1111 = 1001$, and write $$R_C = 1111 = 0110 + 1001 = \overline{A} + \overline{C}.$$

But there was nothing special about the $\overline{A}$ I chose, I'd get a different pair $\overline{B}$ and $\overline{C}$ for each one, and any would be viable. However, if you let me know even one of your $A, B$, or $C$, I could find the remaining ones you'd picked.