1
$\begingroup$

From Definition of CSPRNG, it has two characteristics

  1. It satisfies the next-bit test.
  2. It withstands 'state compromise extensions' - part of all of the state being compromised does not allow for reconstruction of the prior stream of random numbers.

I am looking for PRNGs which fail the 2nd Characteristic. Infact they are PRNG but not CSPRNG.

$\endgroup$
  • $\begingroup$ Is there something missing from your question that requires more specificity? Otherwise aren't you just looking for all the common random number generators like LFSRs, XORShift, Twister..? $\endgroup$ – Paul Uszak Jun 1 '17 at 10:58
  • $\begingroup$ every PRNG is not CSPRNG ( i think so it may be wrong ) $\endgroup$ – khan Jun 1 '17 at 19:07
4
$\begingroup$

Item (2) is not part of the definition of a standard CSPRNG. If you look at where this definition was taken from in Wikipedia, this item refers to a "forward secure CSPRNG". So, this is a definition of forward security and not the standard notion.

Also, the next-bit test is one way of defining, but certainly not the only way.

In any case, it is easy to construct a CSPRNG that is not forward secure; simply always store the initial state.

$\endgroup$
  • $\begingroup$ Please refer the Correct definition of CSPRNG and forward secure CSPRNG $\endgroup$ – khan Jun 1 '17 at 9:38
  • 1
    $\begingroup$ @Raza that might be tricky, they are cryptographically secure until they are not. Dual_EC_DRBG is now not a CSRNG, but it was in 2006 $\endgroup$ – daniel Jun 1 '17 at 9:43
  • $\begingroup$ @daniel It still is, but a flawed one. In the same way, MD5 is a cryptographic hash algorithm, but a broken one. Whether or not something is cryptographically secure is dictated by the design of the algorithm, not the existence of attacks or lack thereof. Compare MD5's (unmet) design goals with something like Fletcher-128 which was never designed for collision resistance in the first place. $\endgroup$ – forest Jul 10 '18 at 23:09
  • $\begingroup$ @forest I like my words better. MD5 is not a good example as it is not a provably secure hash function, the secure word is the one I'm poking fun at. A locked door is secure, if it's kicked in it was secure, but it's not secure anymore. $\endgroup$ – daniel Jul 11 '18 at 12:34
  • 1
    $\begingroup$ @daniel Indeed, when we say that something is "secure" it is always only a conjecture (unless it doesn't rely on any assumption). Ideally, we can say that it is secure under a well-established assumption. However, EC_DBRG is still a secure PRG, under the DDH assumption, just one that can have a backdoor. This possibility is not ruled out by the definition. MD5 is indeed not secure, and in hindsight it never was; we just didn't know it back then. $\endgroup$ – Yehuda Lindell Jul 11 '18 at 15:33
1
$\begingroup$

The ChaCha cipher is definitely not forward secure: the only state modification is to increment a counter.

$\endgroup$
  • $\begingroup$ While technically correct, ChaCha is not a CSPRNG by itself (it is a stream cipher), it can be a building block of a CSPRNG (e.g. the Linux kernel's CRNG which uses ChaCha20 and involves backtrack protection that makes it forward secure). $\endgroup$ – forest May 12 '18 at 8:55
  • 1
    $\begingroup$ The word ‘ChaCha’ can comfortably refer to (a) the pseudorandom function family sometimes specifically called the ‘ChaCha core’; (b) the pseudorandom function family obtained by applying the ChaCha core to a sequence of consecutive inputs; and (c) the stream cipher that uses the ChaCha core on a sequence of conescutive inputs to generate a one-time pad with which to xor a message to encrypt it. Presumably @dhardy was referring to (b). $\endgroup$ – Squeamish Ossifrage May 12 '18 at 13:45

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.