Often in security proofs a certain block cipher is assumed to be a pseudorandom permutation or PRP. I wonder if this goes for stream ciphers as well, and specifically for Salsa20.

If we limit ourselves to the scope of one Salsa20 block (64 bytes), being fed 64 bytes of plaintext data, is it safe to assume $Salsa20_{key,nonce}$ to be a (strong) PRP family?

I'd very much be interested in the reasoning why or why not, and whether this extends to other stream ciphers.

  • $\begingroup$ Salsa20 takes 16 constant bytes for a reason. While it's build from a permutation, that permutation has some limitations and it has no key. $\endgroup$ – CodesInChaos Apr 16 '13 at 19:26

Salsa20 is a stream cipher based on a pseudorandom function, not a pseudorandom permutation.

For a fixed key $k$ and nonce $n$, the mapping $PRF^{S20}_{k,n}: \{0,1\}^{64} \to \{0,1\}^{512}$, which maps a "Stream position" to "keystream block", is supposed to be a pseudorandom function. It is not supposed to be injective (i.e. a permutation, even less since the input/output sizes are different), and there certainly is no easy way to produce a preimage, even knowing the key and nonce.

What you propose is the Salsa20 encryption function for the first "block" of plaintext: $$\def\Enc{\operatorname{Enc}}\Enc^{S20}_{k, n} : \{0,1\}^{512} \to \{0,1\}^{512}$$ $$\Enc^{S20}_{k, n}(P) = P \oplus PRF^{S20}_{k,n}(0)$$

This is obviously bijective (it is its own inverse), i.e. a permutation, but at the same time, it is obviously not a (pseudo)random permutation. In addition to the self-inverse-property, it for example also has the two-time-pad property:

$$\Enc^{S20}_{k, n}(P_1) \oplus \Enc^{S20}_{k, n}(P_2) = P_1 \oplus P_2,$$

which no random permutation would have.

  • $\begingroup$ What if you'd remove the applicability of the two-time-pad property through proper usage (that is, to never encode a different $P_1, P_2$ with the same key, nonce and block number)? $\endgroup$ – orlp Apr 16 '13 at 17:05
  • $\begingroup$ You might get some properties similar of a pseudorandom permutation, but you'll have to define your own term and wished security properties for that new kind of primitive. It is not a PRP, as there we can use the same function with multiple inputs without a problem. $\endgroup$ – Paŭlo Ebermann Apr 16 '13 at 17:11
  • 1
    $\begingroup$ The random function is produced by xoring a permutation with with its input, similar to the way block ciphers are turned into hashes. $\endgroup$ – CodesInChaos Apr 16 '13 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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