[Crypto] Is Fibonacci-XOR-rotate one-way-ish?

Solution 1:

Given some output of unknown seeds after an unknown number of steps, is it "computationally hard" to find a pair of seeds that produce the given output after a number of steps?

Nope; two observations:

• With two successive outputs, you can compute the internal state; if you see the outputs $y_1, y_2$, then the internal state immediately after the first output was $x_1 = y_1, x_2 = y_2$

• Given the internal state, you can compute previous states; if the state at time $t$ was $x_1 = y_1, x_2 = y_2$, then the state at time $t-1$ was $x_1 = rotl(y_2) \oplus y_1, x_2 = y_1$ (where $rotl$ is 'rotate shift left by one')

These two observations allow an attacker to revert this generator as far as he needs to.

Actually, for reverting arbitrarily long distances, there are other tricks that reduce the number of computations needed (logarithmic in the size of the time delta; constant time is likely possible, but I don't want to promise that), however we don't need to go to that extent to show that this is weak.

---

Solution 2:

The output bits of this process are $\mathbb{Z}_2$-linear functions of the input bits. Specifically, if you write $x_1, x_2$ as column vectors of bits, then

$$ \begin{bmatrix} x'_1 \\ x'_2 \end{bmatrix} = \left[ \begin{array}{cccc|cccc} 0 & 0 &\cdots & 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 &\cdots & 0 & 0 & 1 & \cdots & 0 \\ \vdots &\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 1 \\ \hline 0 & 0 & \cdots & 1 & 0 & 0 & \cdots & 1 \\ 1 & 0 & \cdots & 0 & 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & 0 & 1 & \cdots & 0 \\ \vdots &\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \end{array} \right] \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} $$ This matrix is invertible, meaning that you can easily reverse one iteration of your process. Of course, then you can reverse any number of iterations.

The actual inverse is as follows. If $x'_1 = x_2$ and $x'_2 = \textsf{rot}_R(x_1 \oplus x_2)$, then you already have $x_2 (=x'_1)$ and you can compute $x_1$ as: \begin{align*} x'_1 \oplus \textsf{rot}_L(x'_2) &= x'_1 \oplus \textsf{rot}_L(\textsf{rot}_R(x_1 \oplus x_2)) \\ &= x'_1 \oplus x_1 \oplus x_2 \\ &= x_2 \oplus x_1 \oplus x_2 \\ &= x_1 \end{align*}