Mixing
Attack of the Middle Square Weyl Sequence PRNG
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer. This PRNG was introduced (without claim of cryptographic security) by Bernard Widynski in Middle Square Weyl Sequence RNG (arXiv, 2017).
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>0$) by
$$beginalign
w_i&gets(w_i-1+s)bmod 2^64\
x_i&gets(((x_i-1)^2+w_i)bmod 2^64)ggg32\
r_i&gets x_ibmod2^32
endalign$$
where $ggg32$ swaps the halves of its 64-bit left argument.
The paper gives a reference C99 implementation (for $x_0=w_0=0$ and the sated $s$)
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws()
x *= x; x += (w += s); return x = (x>>32)
Assume we have a $r_i$ for $1le ile10$. 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.
cryptanalysis pseudo-random-generator
asked 2 hours ago
fgrieu
73.5k6151313
add a comment |Â
up vote
1
down vote
favorite
The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer. This PRNG was introduced (without claim of cryptographic security) by Bernard Widynski in Middle Square Weyl Sequence RNG (arXiv, 2017).
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>0$) by
$$beginalign
w_i&gets(w_i-1+s)bmod 2^64\
x_i&gets(((x_i-1)^2+w_i)bmod 2^64)ggg32\
r_i&gets x_ibmod2^32
endalign$$
where $ggg32$ swaps the halves of its 64-bit left argument.
The paper gives a reference C99 implementation (for $x_0=w_0=0$ and the sated $s$)
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws()
x *= x; x += (w += s); return x = (x>>32)
Assume we have a $r_i$ for $1le ile10$. 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.
cryptanalysis pseudo-random-generator
asked 2 hours ago
fgrieu
73.5k6151313
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.
– Paul Uszak
1 hour ago
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?
– Ella Rose
1 hour ago
1
@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)
– poncho
52 mins ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer. This PRNG was introduced (without claim of cryptographic security) by Bernard Widynski in Middle Square Weyl Sequence RNG (arXiv, 2017).
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>0$) by
$$beginalign
w_i&gets(w_i-1+s)bmod 2^64\
x_i&gets(((x_i-1)^2+w_i)bmod 2^64)ggg32\
r_i&gets x_ibmod2^32
endalign$$
where $ggg32$ swaps the halves of its 64-bit left argument.
The paper gives a reference C99 implementation (for $x_0=w_0=0$ and the sated $s$)
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws()
x *= x; x += (w += s); return x = (x>>32)
Assume we have a $r_i$ for $1le ile10$. 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.
cryptanalysis pseudo-random-generator
asked 2 hours ago
fgrieu
73.5k6151313
The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer. This PRNG was introduced (without claim of cryptographic security) by Bernard Widynski in Middle Square Weyl Sequence RNG (arXiv, 2017).
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>0$) by
$$beginalign
w_i&gets(w_i-1+s)bmod 2^64\
x_i&gets(((x_i-1)^2+w_i)bmod 2^64)ggg32\
r_i&gets x_ibmod2^32
endalign$$
where $ggg32$ swaps the halves of its 64-bit left argument.
The paper gives a reference C99 implementation (for $x_0=w_0=0$ and the sated $s$)
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws()
x *= x; x += (w += s); return x = (x>>32)
Assume we have a $r_i$ for $1le ile10$. 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.
cryptanalysis pseudo-random-generator
cryptanalysis pseudo-random-generator
asked 2 hours ago
fgrieu
73.5k6151313
asked 2 hours ago
fgrieu
73.5k6151313
asked 2 hours ago
fgrieu
73.5k6151313
asked 2 hours ago
fgrieu
73.5k6151313
asked 2 hours ago
fgrieu
73.5k6151313
73.5k6151313
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.
– Paul Uszak
1 hour ago
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?
– Ella Rose
1 hour ago
1
@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)
– poncho
52 mins ago
add a comment |Â
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.
– Paul Uszak
1 hour ago
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?
– Ella Rose
1 hour ago
1
@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)
– poncho
52 mins ago
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.
– Paul Uszak
1 hour ago
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.
– Paul Uszak
1 hour ago
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?
– Ella Rose
1 hour ago
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?
– Ella Rose
1 hour ago
1
1
@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)
– poncho
52 mins ago
@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)
– poncho
52 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Lets look at the computations that the function does to the internal state.
We'll denote the initial $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)
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 & text0xffffffff)$. As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a, h_1)$, where $h_0, h_1$ 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 + 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 + c + epsilon_0)$, and outputs the lower 32 bits $h_0a + c + epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + 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).
answered 54 mins ago
poncho
86.2k2128217
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Lets look at the computations that the function does to the internal state.
We'll denote the initial $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)
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 & text0xffffffff)$. As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a, h_1)$, where $h_0, h_1$ 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 + 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 + c + epsilon_0)$, and outputs the lower 32 bits $h_0a + c + epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + 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).
answered 54 mins ago
poncho
86.2k2128217
add a comment |Â
up vote
2
down vote
Lets look at the computations that the function does to the internal state.
We'll denote the initial $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)
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 & text0xffffffff)$. As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a, h_1)$, where $h_0, h_1$ 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 + 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 + c + epsilon_0)$, and outputs the lower 32 bits $h_0a + c + epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + 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).
answered 54 mins ago
poncho
86.2k2128217
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Lets look at the computations that the function does to the internal state.
We'll denote the initial $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)
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 & text0xffffffff)$. As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a, h_1)$, where $h_0, h_1$ 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 + 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 + c + epsilon_0)$, and outputs the lower 32 bits $h_0a + c + epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + 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).
answered 54 mins ago
poncho
86.2k2128217
Lets look at the computations that the function does to the internal state.
We'll denote the initial $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)
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 & text0xffffffff)$. As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a, h_1)$, where $h_0, h_1$ 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 + 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 + c + epsilon_0)$, and outputs the lower 32 bits $h_0a + c + epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + 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).
answered 54 mins ago
poncho
86.2k2128217
edited 2 mins ago
answered 54 mins ago
poncho
86.2k2128217
answered 54 mins ago
poncho
86.2k2128217
answered 54 mins ago
poncho
86.2k2128217
86.2k2128217
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62750%2fattack-of-the-middle-square-weyl-sequence-prng%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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.
– Paul Uszak
1 hour ago
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?
– Ella Rose
1 hour ago
1
@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)
– poncho
52 mins ago