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.

Improve this question
$\endgroup$
2
  • $\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, 2017 at 10:58
  • $\begingroup$ every PRNG is not CSPRNG ( i think so it may be wrong ) $\endgroup$
    – crypt
    Jun 1, 2017 at 19:07

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Please refer the Correct definition of CSPRNG and forward secure CSPRNG $\endgroup$
    – crypt
    Jun 1, 2017 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, 2017 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, 2018 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, 2018 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, 2018 at 15:33
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2018 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, 2018 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.