Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
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 at 12:30

1 Answer 1

This will not be secure in general, and is not recommended. The reason is that a PRG is guaranteed to produce a pseudorandom output only if its input is uniformly random (or pseudorandom). Moreover, several PRG outputs are jointly pseudorandom only if the PRG is run on independent seeds. But here you are invoking the PRG on "structured" inputs, i.e., the counter part is known and predictable (hence not (pseudo)random), and the key part is reused multiple times.

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.

CTR mode with a PRF is OK because a PRF has the property that even for adversarially chosen inputs (e.g., the counter values), the outputs of the PRF (on the same random secret key) are jointly pseudorandom.

share|improve this answer
    
"The reason is that a PRG is guaranteed to produce a pseudorandom output only if its input is uniformly random (or pseudorandom)". Do you have a reference to this? –  BlaX Aug 12 at 17:24
3  
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 at 17:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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