1
$\begingroup$

In reality, it is not practical for ciphers such as stream ciphers and AES to generate keys using a TRNG, so instead they have to use a CSPRNG. As an LFSR can generate pseudo random numbers,so can a LFSR be adapted so it can be used as CSPRNG, and what are the other ways to construct a CSPRNG.

$\endgroup$
  • 1
    $\begingroup$ ("What are the other ways to construct a CSPRNG" is incredibly broad.) $\endgroup$ – otus Aug 15 '16 at 9:57
3
$\begingroup$

LFSR as such isn't a CSPRNG. There are diverse CSPRNGs, see crypto textbooks, also A. Menezes et al., Handbook of Applied Cryptography (freely available online). I have a code for a CSPRNG based on RSA, see Ex. 5 in s13.zetaboards.com/Crypto/topic/7234475/1/

$\endgroup$
1
$\begingroup$

LFSR's are not secure because they are linear, and the linearity can be exploited - see Berlekamp–Massey algorithm.

A common method to obtain a secure PRG is to take a secure cipher and generate a keystream; the cipher's key is the seed of the PRG. Currently ChaCha20 cryptoalgorithm is becoming widely used as secure PRG because it is considered secure and fast, but any secure cryptoalgorithm can be used as secure PRG. For block ciphers such as AES a keystream can be generated by applying the cryptoalgorithm to an incremental counter, like in CTR mode of operation.

Real-world secure PRG's also include "rekey" step, but in theory it is not necessary.

$\endgroup$
1
$\begingroup$

In reality, it is not practical for ciphers such as stream ciphers and AES to generate keys using a TRNG, so instead they have to use a CSPRNG.

This quote really needs to be nitpicked quite a bit:

  • With stream ciphers, using a true random number generator for the keystream wouldn't just be "impractical," but impossible, because the keystream is a shared secret—to decrypt the message Bob needs to reconstruct the keystream that Alice got when she encrypted it.
  • AES, strictly speaking, doesn't specify a mechanism for generating keys. There's generally a requirement that keys should be picked at "random" in the sense that, from the point of view of a computationally limited attacker, all keys should be equiprobable.
  • Cipher keys are very often not chosen by a PRNG at all. For example, in most SSL sessions the PRNG is used to generate ephemeral keys for a Diffie-Hellman key exchange, which produces a shared secret from which pseudorandom symmetric keys are then derived.

As an LFSR can generate pseudo random numbers,so can a LFSR be adapted so it can be used as CSPRNG, and what are the other ways to construct a CSPRNG.

There's a bunch of them. First I'd highlight that there's a bunch theoretical PRNGs like Blum Blum Shub, which have a security proof that reduces their security to common but unproven assumptions (e.g., some mathematical problem believed to be computationally hard). These are not often used, however. The most famous of these, which did and still does see some practical use, is the most infamous PRNG of them all: the NSA-backdoored Dual EC DRBG.

Then there's a number of heuristic PRNGs, which is what we normally do use. Many designs take LFSRs as their starting point and make modifications or additions for security. But there's also many CSPRNGs based on repurposing well-known cryptographic primitives or constructions to serve as PRNGs.

For example, there's many CSPRNGs based on pseudorandom functions used in an appropriate mode of operation like CTR or OFB. For example:

  • The Fortuna RNG as described in Ferguson, Schneier and Kohno's book uses AES-CTR (AES in counter mode) as its core.
  • The ChaCha20 stream cipher, which some systems use as a PRNG, is also a counter-mode construction based on the internal "ChaCha20 core" pseudorandom function that maps key, nonce and counter to a keystream block.
  • HMAC-DRBG (one of the NIST recommended designs) uses HMAC in OFB mode (see these slides that say it directly).
  • Various hash-based RNGS, which rely on the hash function behaving like a pseudo-random function when the PRNG's state is secret.

But this is an open-ended problem so there's no requirement for solutions to look anything like my examples.

$\endgroup$

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