# CTR mode encryption using PRG

In CTR mode encryption, the encryption block is not required to be invertible. Thus, a PRF can be used instead of a PRP. However most of the implementations of CTR mode are based on AES which is a PRP.

This made me think if we can have a PRG as the encryption block where the (key || counter_i) can be supplied as a seed.

If we use a secure PRG such as SALSA20 instead of AES, do we achieve a secure CTR mode encryption?

• Using Salsa20Core in CTR mode certainly results in a secure stream cipher -- that's precisely the way Salsa20 is defined in the first place. – CodesInChaos Aug 12 '14 at 12:30

Concretely, here is a secure PRG $G$ for which your construction is completely insecure: let $G'$ be a secure PRG, and define $G(s \| \text{ctr}) = G'(s) \| \text{ctr}$, where $\text{ctr}$ has the same length as the counter you use in your construction. This is still a secure PRG because in proper usage, $s$ and $\text{ctr}$ are uniform and independent. However, your construction is insecure when instantiated with $G$ because the (public, non-random) $\text{ctr}$ part is simply "passed through" to the output, and the successive calls to $G$ always produce the same $G'(s)$ part.
• It's the standard definition of PRG in cryptography, dating back to Blum-Micali/Yao. See, e.g., Definition 1 in lucatrevisan.wordpress.com/2009/01/30/… . The definition guarantees that $G$ is "well-behaved" on a uniformly random seed, but says nothing about other seed distributions. (This does not rule out the possibility special PRGs that behave well on non-uniform seeds, but that would be an extra property, not part of the core definition.) – Chris Peikert Aug 12 '14 at 17:38