4
$\begingroup$

The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer (now deleted). This PRNG was introduced by Bernard Widynski in Middle Square Weyl Sequence RNG (arXiv, 2017). That was without claim of cryptographic security, but v5 of the paper conjectures that it would "be difficult to determine the internal state by examining the outputs".

The PRNG has a 128-bit state consisting of two 64-bit variables $x$ and $w$. The PRNG input consists of the initial $x_0$ and $w_0$, and an odd value $s$. The state's evolution and 32-bit pseudorandom outputs $r_i$ are defined (for $i\ge0$) by $$\begin{align} r_i&\gets x_i\bmod2^{32}\\ w_{i+1}&\gets(w_i+s)\bmod 2^{64}\\ x_{i+1}&\gets((x_i^2+w_{i+1})\bmod 2^{64})\ggg32 \end{align}$$ where $\ggg32$ swaps the halves of its 64-bit left argument.

[The notation was modified so that $r_0$ is output, for consistency with an answer]

The paper gives a reference C99 implementation (with input $x_0=w_0=0$ and a certain $s$; the output starts at $r_1$)

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws() {
   x *= x; x += (w += s); return x = (x>>32) | (x<<32);
}

Assume we have a $r_i$ for $0\le i\le9$. How can the rest of the sequence be predicted efficiently? That would be a total break.

If not feasible, lesser breaks (only distinguishing the output from random, or requiring more plaintext, or working only for a fraction of the inputs) are also welcome.

$\endgroup$
  • $\begingroup$ It has no NP hard form, XOR to diffuse /confuse and it's just too simple. You typically trade algorithmic entropy against NP rigidity as in ISAAC v BBS. My waters say that it can't possibly be secure. $\endgroup$ – Paul Uszak Sep 29 '18 at 16:15
  • $\begingroup$ If there are no sources of randomness used in the algorithm, distinguishing its outputs from random seems trivial: Simply check to see if the first $n$ outputs are the outputs from running the algorithm. Similarly, if you know the first $n$ outputs and want to predict the output for $n + 1$, just run the algorithm for $n + 1$ iterations and output the result. Or maybe I am misunderstanding the nature of the security game? $\endgroup$ – Ella Rose Sep 29 '18 at 16:50
  • 2
    $\begingroup$ @EllaRose: I had assumed that the attacker is not given the initial values of $x$ and $w$. If the attacker is also not given the value $s$, then my attack would still work (it just that it needs 6 outputs to recover the state) $\endgroup$ – poncho Sep 29 '18 at 17:10
  • $\begingroup$ @EllaRose The point is the $x$ and $w$ are unknown in a real implementation. It looks like $s$ can vary too as long as it remains odd. $\endgroup$ – Paul Uszak Sep 29 '18 at 19:00
  • 1
    $\begingroup$ The 5th version of that paper is now claiming it's cryptographically secure...interesting. $\endgroup$ – Daniel Hill May 29 at 9:13
6
$\begingroup$

Lets look at the computations that the function does to the internal state.

We'll denote the state of the variables when we start the attack as $x_0 = (a, b)$ and $w_0 = (c, d)$, where I will use the notation $(i, j)$ to mean the 64 bit number which has $i$ as the upper 32 bits, and $j$ as the lower 32 bits (and so $a, b, c, d$ are 32 bits each). Note that $x_0, w_0$ need not be the initial state of the PRNG, instead it's the state when the initial output was generated.

Then, the previous step exposes $b$ (and so that is known to the attacker).

Then, it squares $x_0$ modulo $2^{64}$, replacing $x_0 = (a, b)$ with $x_0^2 = (2 a b + (b^2 >> 32), b^2\ \bmod 2^{32})$. As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a + h_2, h_1)$, where $h_0, h_1, h_2$ are known (to the attacker) constants (as it gives the same mapping from previous state to new state).

Then, the algorithm adds $w$ to $x$, that can be modeled as:

$x_0^2 + w_0 = (h_0 a + h_2 + c + \epsilon_0, h_1 + d)$, where $\epsilon_0$ is either 0 or 1, depending on whether a carry from the lower 32 bits happened.

Then, it adds the constant $s$ to $w$, this can be modeled as $w + s = (c + s_{hi} + \epsilon_1, d + s_{lo})$, where $\epsilon_1$ is either 0 or 1, depending on whether a carry from the lower 32 bits happened (and $s = (s_{hi}, s_{lo})$

Then, it rotates $x$, giving $x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0)$, and outputs the lower 32 bits $h_0a + h_2 + c + \epsilon_0$.

The new state is $x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0)$ and $w_1 = (c + s_{hi} + \epsilon_1, d + s_{lo})$; that is, it is one of 4 linear functions of the previous state (depending on the values of $\epsilon_0, \epsilon_1$)

Continuing on for three more iterations, the resulting states will remain one of a small number of known linear functions of the initial state; the output will also be a linear function of the state. With four outputs, the attacker can iterate through the possible $\epsilon$ values, and solve for there the initial states. If you go through the equations, you'll find that you can recover $c, d$ from the third and fourth outputs; using the value $c$ gives you the value of $a$ from the second output (and you're given $b$ as the first output).

| improve this answer | |
$\endgroup$
  • $\begingroup$ @fgrieu: actually, I'm using $x_0$ not to signify the initial state, but instead the state of the system when the first output we were given was produced (which will likely mean that $x, w$ had gone through at least one iteration) $\endgroup$ – poncho Sep 29 '18 at 20:34
  • $\begingroup$ So, $h_0$ = $b^2 mod 2^{32}$ but how do I get $h_1$,$h_2$,$c$, $d$? $\endgroup$ – S. L. Sep 18 '19 at 19:38
  • $\begingroup$ @S.L.: actually, $h_1 = b^2 \bmod 2^{32}$, $h_0 = 2b$ and $h_2 = (b^2 >> 32)$ $\endgroup$ – poncho Sep 18 '19 at 19:59
  • $\begingroup$ I'm trying to implement. I see that $h0a+h2+c+ϵ0$ actually gives a 64 bit number, how does that work if it represents 32 bits? $\endgroup$ – S. L. Sep 19 '19 at 12:02
  • $\begingroup$ $r0,x0,w0 = 2397353388,11805728105293985196,2847934365896495385$ $r1, x1, w1 = 1956483837, 4921554038045905661, 15939140708061950914$ I can't seem to reconcile $\endgroup$ – S. L. Sep 19 '19 at 13:25

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.