0
$\begingroup$

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....

$\endgroup$
1
$\begingroup$

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$).

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 ! $\endgroup$ – Kamel Mohamed Apr 7 '17 at 17:25
  • $\begingroup$ 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 $\endgroup$ – Kamel Mohamed Apr 7 '17 at 17:31
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.