10
$\begingroup$

Short version:

What is the inversion of $f(x) = x \oplus (x \lll 1) \oplus (x \lll 5)$ when the last 4 bits of $x$ are known?

Long version:

Hi,

a friend a mine and I are giving each other crypto challenges to break. This time, he gave me a "one-way" function which is defined as followed:

$R(x)= x \oplus (x \lll 1) \oplus (x \lll (x\ AND\ 15)) \oplus ((x\ AND\ 15) \lll 1)$

Or if you define $i = x\ AND\ 15$:

$R(x) = x \oplus (x \lll 1) \oplus (x \lll i) \oplus (i \lll 1)$

Given you can bruteforce $i$ (since it is ranged from 0 to 15), there are a few things you can do:

For $i = 0$: $R(x)$ can be reduced to $R(x)=x \oplus (x \lll 1) \oplus x \oplus (i \lll 1)=(x \lll 1) \oplus (i \lll 1)$ which can easily be reversed.

The same applies to $i = 1$ which allowes you to reduce $R(x)$ to $x \oplus (i \lll 1)$.

However, things get more complicated for $i \ge 2$ since the xor's no longer negate themselves, but since you "know" the last 4 bits of $x$, you can try to reverse the function by building upon $i$:

Given that $x_{28-31} = i_{0-3}$ and $0 \le i \le 3$

$x_{27} = x_{27} \oplus x_{28} \oplus x_{27 + i}$

$x_{26} = x_{26} \oplus x_{27} \oplus x_{26 + i}$

...

$x_{n} = x_{n} \oplus x_{n + 1} \oplus x_{n + i}$

($x_n$ or $i_n$ are the $n$th bit of $x$ / $i$)

However, i really have no clue when it comes to $i \gt 3$ since you cant access the plain bits anymore.

// EDIT: The $f(x)=x\oplus (x \lll 1)$ can easily be broken by defining that $x_0=0$ and then calculating the rest using $x_{n}=x_{n-1} \oplus x_{n}$ but I wasn't really able to expand this to the problem above.

$\endgroup$
9
$\begingroup$

In order to invert $f(x) = x \oplus (x \lll 1) \oplus (x \lll 5)$ (where all quantities are 32-bit), we do not need the low-order bits of $x$; given $f(x)$ we can find $x$.

Let's first solve $f(x)=1$ for $x$. We must have (where $x_i$ is bit $i$ of $x$, with $i=0$ for the low-order bit) $$\begin{align}x_{0}\oplus x_{31}\oplus x_{27}&=1\\x_{i}\oplus x_{(i+31\bmod32)}\oplus x_{(i+27\bmod32)}&=0\;\text{ for }1\le i<32\end{align}$$

This is a system of 32 linear equations with 32 unknowns, and the tried and tested method of Gaussian elimination yields $x_0=1$, $x_1=1$, $x_2=1$, $x_3=0$, $x_4=1$, $x_5=0$, $\dots$, $x_{27}=1$, $x_{28}=0$, $x_{29}=0$, $x_{30}=1$, $x_{31}=1$, which we can combine into $x=\mathtt{0xCAF84657}$ which indeed is such that $f(x)=1$ (see second part for alternative methods, based on polynomial arithmetic or brute force).

Given the rotation-invariant structure of $f$, it follows that for $0\le i<32$, the solution of $f(x)=(1\lll i)$ is $x=(\mathtt{0xCAF84657}\lll i)=k_i$.

And because $f$ is linear, we can solve $f(x)=y$ by combining with $\oplus$ those $k_i$ such that bit $i$ of $y$ is set; the combination being the desired $x$.

Or, for a more direct expression, we can write $x=y\oplus(y\lll1)\oplus(y\lll2)\oplus\dots\oplus(y\lll27)\oplus(y\lll30)\oplus(y\lll31)$ where the rotations $i$ in the terms are those such that bit $i$ is set in $k_0=\mathtt{0xCAF84657}$ (argument: this is such that $y=1$ yield $x=k_0$, and the rest follows by linearity and rotation invariance).


The Boolean matrix defining the system of equations is circulant; that allows finding $k_0$ by finding the inverse of the Boolean polynomial $1+z+z^5$ modulo $1+z^{32}$ using the Extended Euclidean algorithm for polynomials; see related answer.

More directly, with the indexes of the bits set in $x$ [resp. $y$ ] the coefficients of the Boolean polynomial $X(z)$ [resp. $Y(z)$ ], we have $$y=f(x)\iff Y(z)=F(z)\,X(z)\bmod(1+z^{32})\;\text{ with }F(z)=1+z+z^5$$ thus inverting $F$ modulo $1+z^{32}$ (if possible) gives us $G$ which is to $f^{-1}$ what $F$ is to $f$.

In Mathematica, the Extended Euclidean algorithm for Boolean polynomials $1+z+z^5$ and $1+z^{32}$ is invoked as
{g,{u,v}} = PolynomialExtendedGCD[1+z+z^5, 1+z^32, z, Modulus->2]
giving the following result, where g of 1 at the beginning confirms that $f$ is invertible, and the bits sets in $k_0$ [and the rotation counts in the expression for $f^{-1}(y)$ ] are given by the coefficients of u, which I isolated on the second line:
{1,{
1+z+z^2+z^4+z^6+z^9+z^10+z^14+z^19+z^20+z^21+z^22+z^23+z^25+z^27+z^30+z^31
,z^3+z^4}}

For my initial answer, I actually neither did this, nor solve the linear system. If the problem was for more than 32-bit variables, I'd do that; but here I used brute force and wrote this C code which output 0xCAF84657 in about 5 seconds:

#include <stdio.h>
#include <stdint.h>
int main(void) {
    uint32_t x=0;
    do
        if ((x^((x<<1)^(x>>31))^((x<<5)^(x>>27)))==1)
            printf("0x%08lX\n",(unsigned long)x);
    while(++x);
    return 0;
    }
$\endgroup$
8
$\begingroup$

The function you posted is linear

$$f(x) = x \oplus (x \lll 1) \oplus (x \lll 5)$$

Assuming x $\in F_2^{32}$ then the matrix representation is

1 . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . 1
1 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . .
. 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . .
. . 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 1 .
. . . 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 . . . 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
. 1 . . . 1 1 . . . . . . . . . . . . . . . . . . . . . . . . .
. . 1 . . . 1 1 . . . . . . . . . . . . . . . . . . . . . . . .
. . . 1 . . . 1 1 . . . . . . . . . . . . . . . . . . . . . . .
. . . . 1 . . . 1 1 . . . . . . . . . . . . . . . . . . . . . .
. . . . . 1 . . . 1 1 . . . . . . . . . . . . . . . . . . . . .
. . . . . . 1 . . . 1 1 . . . . . . . . . . . . . . . . . . . .
. . . . . . . 1 . . . 1 1 . . . . . . . . . . . . . . . . . . .
. . . . . . . . 1 . . . 1 1 . . . . . . . . . . . . . . . . . .
. . . . . . . . . 1 . . . 1 1 . . . . . . . . . . . . . . . . .
. . . . . . . . . . 1 . . . 1 1 . . . . . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . 1 1 . . . . . . . . . . . . . . .
. . . . . . . . . . . . 1 . . . 1 1 . . . . . . . . . . . . . .
. . . . . . . . . . . . . 1 . . . 1 1 . . . . . . . . . . . . .
. . . . . . . . . . . . . . 1 . . . 1 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . 1 . . . 1 1 . . . . . . . . . . .
. . . . . . . . . . . . . . . . 1 . . . 1 1 . . . . . . . . . .
. . . . . . . . . . . . . . . . . 1 . . . 1 1 . . . . . . . . .
. . . . . . . . . . . . . . . . . . 1 . . . 1 1 . . . . . . . .
. . . . . . . . . . . . . . . . . . . 1 . . . 1 1 . . . . . . .
. . . . . . . . . . . . . . . . . . . . 1 . . . 1 1 . . . . . .
. . . . . . . . . . . . . . . . . . . . . 1 . . . 1 1 . . . . .
. . . . . . . . . . . . . . . . . . . . . . 1 . . . 1 1 . . . .
. . . . . . . . . . . . . . . . . . . . . . . 1 . . . 1 1 . . .
. . . . . . . . . . . . . . . . . . . . . . . . 1 . . . 1 1 . .
. . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . 1 1 .
. . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . 1 1

This matrix is non-singular and its inverse is

1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1
1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1
1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 .
. 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1
1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 .
. 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1
1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . .
. 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 .
. . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1
1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1
1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . .
. 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . .
. . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 .
. . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1
1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . . .
. 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . . .
. . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 . .
. . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1 .
. . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1 1
1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1 1
1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1 1
1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1 1
1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 . 1
1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1 .
. 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 . 1
1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1 .
. 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . . 1
1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 . .
. 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1 .
. . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1 1
1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1 1
1 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 . . 1 . 1 . 1 1 1

From this we obtain $f^{-1}$ as follows

$$\begin{align}f^{-1}(x)=x \oplus (x \lll 1)\\ \oplus (x \lll 2)\\ \oplus (x \lll 4)\\ \oplus (x \lll 6)\\ \oplus (x \lll 9)\\ \oplus (x \lll 10)\\ \oplus (x \lll 14)\\ \oplus (x \lll 19)\\ \oplus (x \lll 20)\\ \oplus (x \lll 21)\\ \oplus (x \lll 22)\\ \oplus (x \lll 23)\\ \oplus (x \lll 25)\\ \oplus (x \lll 27)\\ \oplus (x \lll 30)\\ \oplus (x \lll 31)\end{align}$$

$\endgroup$
  • 2
    $\begingroup$ @fgrieu updated to use rotate (instead of shift) and fix $\TeX$ formatting $\endgroup$ – conchild Jun 10 '17 at 12:36

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.