Is Fibonacci-XOR-rotate one-way-ish?

Question

Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method.

Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the following algorithm (C code is given below):

1. Let r = x1 ^ x2 (bitwise XOR; the "Fibonacci" step).
2. Rotate r to the right by 1 position.
3. Let x1 = x2 and x2 = r.
4. Output x1 and repeat.

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

Here's the C code:

#include <stdio.h>

unsigned rotate (unsigned n, int len); 
       // len == length of rotation (number of bits rotated)
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len); 

// ---------------------------------
unsigned rotate (unsigned n, int len) // l == length
{
  unsigned b = n & 1; // get right-most bit
  n = n >> 1;
  n = n | (b << (len-1)); 
     // insert right-most bit at left end
  return n;
}
// ---------------------------------
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len) 
    // Fibonacci XOR and then rotate
{
  unsigned result = n1 ^ n2; // "Fibonacci" step
  return rotate(result, len);  // "Scramble" step
}
// ---------------------------------
int main()
{
  int i = 0;
  unsigned x1 = 0xd;  // seed 1
  unsigned x2 = 0x80; // seed 2
  unsigned h; // helper variable
  int my_len = 8; // length of rotation, here: 8 (-> byte length)
  while (i < 100)
  {
    printf("%x,", x2);
    h = x2;
    x2 = fibo_xor_rotate(x1, x2, my_len); // fibo xor rotate
    x1 = h; // set x1 to "old" x2
    if (i % 10 == 9) { 
       printf("\n"); // newline after 10 prints
    }
    i++;
  }
  return 0;
}

Answer 1

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*}

Answer 2

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.