Score:1

PRNG generator which could repeats blocks

tf flag
Tom

Let's use AES as stream cipher, and let's use as an input numbers $1,2,3,...$. This way we should get the random blocks and every block will be different from each other.

But I have a pseudorandom blocks generator which generate not always different blocks. So we could get block $B$ once and then for example again after let's say milion blocks it is possible to get again the same block $B$ (but it could be rare).

It is still good random blocks generator (passes all tests). Could it be a problem if someone would like to use it as a PRNG or if someone would like to use it as a stream for encryption?

Most ciphers meet the condition that they generate unique values, but in this case we can get the same encryption of the same block after less than $2^{128}$ blocks.

Maarten Bodewes avatar
in flag
By the way, there are multiple ways to create a stream cipher from AES; it seems like you are explicitly describing AES in CTR mode though, not e.g. CFB or OFB.
Score:2
in flag

For a CSPRNG I would say the fact that it can repeat blocks is a good thing; predicting that a pattern cannot repeat is problematic. The only reason why it is usually acceptable is that the chance of repetition of larger blocks is negligible anyway.

Say that you'd use a CSPRNG to create a set of 128 bit blocks, the block size of AES. A million is about $2^{20}$. you would expect a chance of $1 - (1 - {1 \over 2^{128}})^{1000000} \approx 2^{-108}$ for a the initial block to be repeated, and ${1000000 \over 2^{128}} \approx 2^{-(128 - 20)} = 2^{-108}$ for any collision in the first million blocks to occur. The reason why these values are about the same is that a million is next to nothing for 128 bit values. As you can see, the likelihood of a collision is so low that it can be seen as negligible. This is why a stream cipher such as AES-CTR can be thought of as a CSPRNG itself.

Generally CSPRNG's have a large internal state, which means that it is impossible to know when the PRNG repeats. More importantly, the chance that they hit a cycle is extremely low (if a cycle is hit then the CSPRNG would generate the same - large - pattern in repetition). So because of the unpredictability you can use a CSPRNG as stream cipher. This is true for AES / CTR as well of course, if you look at patterns other than 128 bits at precisely the right location. Obviously a pattern of a single bit will repeat extremely often - it's just that you cannot know which bit value you'll find at a given position. The problem with AES-CTR is that it will hit a cycle precisely after the counter has been depleted.

However, because many CSPRNG implementations have not been designed to generate the same deterministic stream, you should be extremely careful of using one as a stream cipher. For instance, they may reseed, use the given seed as additional entropy, generate different output when methods are called differently or even have the algorithm revised. If you are unlucky you will never be able to regenerate the same key stream and your data would be lost (see e.g. getRawKey() on Android devices).

Of course, AES-CTR will generally be a lot faster than a CSPRNG as well. If you don't like AES or don't have hardware acceleration then a stream cipher such as ChaCha would normally be the way to go. Usually you would use these ciphers in an authenticated mode using GMAC (AES-GCM) or Poly1305.

In cryptographic literature you'll often find that the terms "stream cipher" and "CSPRNG" are used interchangeably, but beware of the practical differences in the last two sections.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.