6
$\begingroup$

In a stream cipher like RC4, a message is xored with a random stream of bits, hence a n bits message will result in a n bits random-like ciphertext.

So it's a bijection, it's invertible, the output looks like a random element in {0,1}^n...

Why are stream ciphers not considered as PRPs?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Another formulation of the question, if it was unclear:<br> "Why is <KEYSTREAM> $\oplus M = C$ not considered a PRP for any fixed message length n?" $\endgroup$
    – SEJPM
    Oct 18, 2016 at 21:35
  • $\begingroup$ "looks like random" is not specific enough. "Indistinguishable from random function/element/..." is much more than that. And especially considering the RC4 example: That one is completely broken, so by that fact we can already say that this stream cipher can't be indistinguishable from a stream of truly radom bits. $\endgroup$
    – tylo
    Oct 19, 2016 at 12:43
  • $\begingroup$ @tylo Yes, maybe I shouldn't have mentionned RC4. My question was more general about stream ciphers. Thomas Prest rephrased the question perfectly. $\endgroup$
    – anselant
    Oct 19, 2016 at 19:31
  • $\begingroup$ An ideal stream cipher is a PRG, and a PRP is not a PRG. $\endgroup$
    – forest ♦
    Aug 3, 2019 at 9:31

4 Answers 4

Reset to default
6
$\begingroup$

I assume that for a fixed key $K$, you are asking why $f(m) \overset{\underset{\mathrm{def}}{}}{=} <STREAM> \oplus\ m $ is not a PRP, where $<STREAM>$ is the stream that is generated from the key $K$. $f$ verifies at least two properties that PRP in general do not verify:

  • $f(m_1) \oplus f(m_2) = m_1 \oplus m_2$
  • $f(f(m_1)) = m_1$
Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ This answer has the most accurate reason, but in its current state it's hard to understand why that is: Those equations are true for stream ciphers. And in the security game for a PRF / PRP, you are given oracle access to the function, and can test the function on any inputs. So with this, you can build a distriguisher really easily. $\endgroup$
    – tylo
    Oct 19, 2016 at 12:53
  • $\begingroup$ I agree with tylo that this is the best answer. $\endgroup$
    – Luis Casillas
    Oct 19, 2016 at 18:12
  • $\begingroup$ Yes, this answer together with tylo's comment make sense. Thanks! $\endgroup$
    – anselant
    Oct 19, 2016 at 19:54
2
$\begingroup$

It sounds to me like this really comes down to definitions. If you look closely at how people use it, you may spot that the term "stream cipher" is regularly used in two closely related but distinct senses:

  1. A function $keystream : \exists M \!\in\! \mathbb{N}.\; (Key \times Nonce) \to \{0, 1\}^M$ that maps a (secret, randomly drawn) key and a (public) nonce to a long pseudorandom bit sequence of length $M$ (the cipher's maximum supported keystream length; e.g. $2^{70}$ for Salsa20);
  2. An encryption scheme that XORs messages of length $l$ with the $l$-bit prefix of such a keystream: $cipher : \exists M \!\in\! \mathbb{N}. \forall l \!\in\! \mathbb{N}.\; (l ≤ M \times Key \times Nonce \times \{0, 1\}^l) \to \{0, 1\}^l$.

You can spot these two senses, for example, in the specification of the Salsa20 stream cipher (section 10, boldface as in the original):

Let $k$ be a 32-byte or 16-byte sequence. Let $v$ be an 8-byte sequence. Let $m$ be an $l$-byte sequence for some $l \in \{0, 1, . . . , 2^{70}\}$. The Salsa20 encryption of $m$ with nonce $v$ under key $k$, denoted $Salsa20_k(v) ⊕ m$, is an $l$-byte sequence.

The function called $Salsa20_k(v)$ in this passage fits my type #1—it maps a key and nonce to a keystream (with the intent that if the key is drawn randomly and kept secret, the keystream is pseudorandom). That function is not a permutation. But the so-called "Salsa20 encryption of $m$ with nonce $v$ under key $k$," for any fixed $l ≤ 2^{70}$, $k$ and $v$, is indeed a permutation, and an involution as well.

EDIT: But Thomas Prest's answer points out that the fact that the permutation can't be a PRP, because if you picked a permutation at random it's unlikely you'd pick one that had the same properties we can observe of a one-time pad (the ideal counterpart to a stream cipher). More generally, there are $2^l$ possible messages of length $l$, which means that there are $2^l!$ possible permutations but only $2^l$ distinct one-time pads, so the chance that you'd pick a random permutation that's equivalent to some one-time pad is $1/2^{l-1}!$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That would only be the case if $Key$ is drawn randomly each time. Could you indicate if this is (and should be) the case in your answer? $\endgroup$
    – Maarten Bodewes ♦
    Oct 19, 2016 at 8:27
  • $\begingroup$ @MaartenBodewes: I've made some edits, see if they address your point. $\endgroup$
    – Luis Casillas
    Oct 19, 2016 at 18:07
0
$\begingroup$

It depends on the stream cipher, ChaCha and Salsa are actually iterated Even-Mansour ciphers with half the key known, so they are permutations.

RC4 is not a random permutation because each key does not produce a unique keystream.

There is a possibility that the key schedule may produce a collision. RC4 is also a reversible generator and has an average cycle length of 21699. It is possible for the start of one keystream to be in the middle of another keystream (but incredibly unlikely.).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Actually, we know that there are lots of equivalent RC4 keys. Given that there are more than $256^{256}$ distinct keys, and only $256!$ possible keystreams (based on the contents of the permutation immediately after KSA), one can immediately conclude that key collisions are inevitable. $\endgroup$
    – poncho
    Oct 18, 2016 at 21:28
  • $\begingroup$ @poncho that's true, but normal key sizes for RC4 make it unlikely, not inevitable. $\endgroup$
    – user3201068
    Oct 18, 2016 at 21:52
  • $\begingroup$ The original question made no specification of 'normal key size; Actually, it can happen even with small keys; for example, the 64 bit key 0x0101010101010101 and the 128 bit key 0x01010101010101010101010101010101 generate precisely the same keystream. $\endgroup$
    – poncho
    Oct 20, 2016 at 3:23
  • $\begingroup$ Also, you state that it is incredibly unlikely that the start of one keystream is in the middle of another keystream; actually, it is quite straightforward to generate a (long) key whose RC4 output is precisely the same as a given RC4-based keystream shifted by $256n$ bytes, for any integer $n$. $\endgroup$
    – poncho
    Oct 20, 2016 at 3:28
0
$\begingroup$

To make this tractable you need finite not infinite length output.

Finite length output would make the OTP with purely random key stream a random permutation of $\{0,1\}^n.$ For other additive keystream generators the proof has in general not been attempted as far as I know.

RC4 with its huge state would likely be a bad PRP, especially since significant biases are known in its keystream.

Finally, a block cipher used in a keystream mode of operation, e.g, CTR, could probably be analysed as a PRP, treating each encryption like a round in a block cipher, but I am not an expert in this area.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I like the first part of the question, but that last paragraph does indeed leave something to be deserved, as you already guessed. CBC is not a keystream mode of operation (as it includes the plaintext in the calculations, so it doesn't create a key stream), and I'm not sure what you mean with "a round". $\endgroup$
    – Maarten Bodewes ♦
    Oct 18, 2016 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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