3
$\begingroup$

$G$ is a PRNG used in a stream cipher and defined in the following way:

  1. G receives $s_0$ as an input, which is a random string drawn from a uniform distribution.

  2. The output of step $i$ is $s_i = (s_{i-1}\cdot (N+1) + 1) \bmod{N}$, for $i=1,2,3\dots$

Is this PRNG secure? If not, what is the distinguisher?

$\endgroup$
  • 4
    $\begingroup$ Hint: Try choosing some $s_0$ and compute a few elements of the generated sequence. $\endgroup$ – yyyyyyy Apr 30 '16 at 12:00
  • 1
    $\begingroup$ Part of the problem is I didn't manage to understand what is the output of $s_0(N+1)$... Thought it was a function, not simple multiplication. Thank's to Vitor I see through my stupidity ;9 $\endgroup$ – Jjang Apr 30 '16 at 16:59
9
$\begingroup$

$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$

but $s_{i-1} \cdot N = 0 \pmod N$, so

$s_i = s_{i-1} + 1 \pmod N$

which means you can discover the next number to be generated just looking to the current one...

$\endgroup$
  • $\begingroup$ Thanks. For some reason I thought $s_i(N+1)$ was passing N+1 as a parameter for $s_i$, but it's a string, so I was confused. Now that I see that it's simple multiplication... oh well. Thanks :) $\endgroup$ – Jjang Apr 30 '16 at 17:00
4
$\begingroup$

See Vitor's answer for the answer your professor was looking for.

However, for any PRNG of the form $s_{i+1} = F(s_{i})$, where the attacker sees the $s_i$ values, and knows $F$, then he can distinguish it. Given a sequence of values $r_1, r_2, ...$, he can determine whether it was generated by that PRNG by checking if $r_2 = F(r_1)$; this is always true for the real PRNG, and rarely true for a random stream.

Because of this, a cryptographically secure PRNG must either:

  • Have $F$ include some secret information (so that the attacker cannot compute it), or
  • Some function $G$ that disguises the state; so that while the internal state updates are of the form $s_{i+1} = F(s_i)$, the outputs that the attacker sees are actually $G(s_{i+1})$
$\endgroup$

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.