# Mixing xor with modular addition

Having two known constant A and B, and one unknown X, can we solve the following equation :

(A xor X)+ X=B

where xor is the bit-wise xor operator and + is the modular addition. For example, A,B and X can belong to the set{0,1,...,255} so the addition is modulo 256. This equation can be a replacement for classical xor operation used by stream ciphers. If this equation cannot deterministically be solved then a known plain-text attack cannot be mounted against the cipher to deduce the keystream....

For any $n>0$ and any fixed $A$ the function $f_A : x \mapsto (A \oplus x) + x \bmod 2^n$ is affine over the field with 2 elements, i.e., $f_A(x\oplus y) = f_A(x)\oplus f_A(y)\oplus A$ (as $A = f_A(0)$).

A proof that the analog map $g_A : x \mapsto (A \oplus x) - x \bmod 2^n$ is affine, you can find in Louis Goubin's CHES 2001 paper A Sound Method for Switching between Boolean and Arithmetic Masking. For $f_A$ I do not know any published reference.

$f_A(x) = B$ is equivalent to $f_A(x)\oplus A = B\oplus A$, so you have to find out if the vector $B\oplus A$ is in the image of the $\mathbb F_2$-linear map $x\mapsto f_A(x)\oplus A$, and if it is, a preimage $x$. This is linear algebra, hence easy from a complexity-theoretical point.

For solving the linear equation you have first to check if $B\oplus A$ is a linear combination of the image of a bases, so taking the base $1, 2, 4, 8, 16, \dots$ you have to look if $B\oplus A$ can be written as a sum of a subset of the vectors $f_A(1)\oplus A=((A\oplus 1)+1\bmod 2^n)\oplus A$, $f_A(2)\oplus A=((A\oplus 2)+2\bmod 2^n)\oplus A$, $f_A(4)\oplus A=((A\oplus 4)+4\bmod 2^n)\oplus A, \dots$ using something like Gaussian elimination.

If it is, and let's say, for $I\subseteq \{0, 1, \dots, n-1\}$ you get $B\oplus A = \bigoplus_{i\in I} (f_A(2^i)\oplus A)$, then $x = \bigoplus_{i\in I} 2^i$ is your solution. EDIT: In general, you will get all solutions in this way. Linear algebra tells us that the set of solutions is either empty or an affine subspace, i.e., of the form $\{x_0+v| v\in W\}$ where $x_0$ is any solution and $W$ is an $\mathbb{F}_2$-subspace of the $n$-dimensional vector space of $n$-bit vectors.

So from a security point, I do not expect an improvement using this equation, (EDIT:) as the solution set can be efficiently calculated and described (using one solution and a basis of $W$ of order $\le n$).

• But for a fixed values of A and B, the solution is not unique : if working on 8bits as example; with a single case like A=0x55 and B=0xAa there are 32 candidate keys that work...., so your approach can only gives a one possible solution and not the exact expected (used perviously to encipher) one ! – Kamel Mohamed Apr 7 '17 at 17:25
• I think that the correct question is :how many solutions exist for such equation, and if the number is sufficiently large to avoid an exhaustive search (for groups on 2^n bits) then the approach is secure with respect to classical applying of a xor only . Thanks for the interest – Kamel Mohamed Apr 7 '17 at 17:31

For an arbitrary $A$ and $B$, we can not find the unique $X$.

Example: Let $A$ and $B$ are $(00001111)_2$ and $(00001111)_2$ respectively. Several solutions of $X$ in the equation $((A \oplus X)+ X) \pmod {256}=B$ are as follows:

$(00000000)_2$, $(00000001)_2$, $(00000010)_2$, $(00000011)_2$, $(00000100)_2$, $(00000101)_2$, $(00000110)_2$, $(00000111)_2$, ....

Let $A_i$ be the $i$-th bit of $A$. The truth table of equation is as follow:

$\begin{matrix}A_i& X_i&((A_i \oplus X_i)+ X_i) \pmod {2^n}=B_i\\ \hline 0&0&0\\0&1&0+carry\\1&0&1\\1&1&1\\ \end{matrix}$

So, $B_i=A_i$ and when $A_i$ is $1$, The value of $X_i$ can not affect the equation.