# How can I (generally) calculate a stream cipher computation cost?

With AES-CTR the computation time to encrypt a message of lengh $n$ blocks is $n$ computations of the block cipher.

What is the running time to encrypt a message of $n$ bits using a stream cipher, like Salsa, Snow, trivium or any other stream cipher? How can I (generally) calculate a stream cipher computation cost?

• Depends on the specific cipher. Salsa20/ChaCha have 512 bit blocks (it's very similar to CTR mode), RC4 outputs bytes. Other ciphers can have different word/block sizes. – CodesInChaos Sep 11 '14 at 13:03
• Thank you @CodesInChaos . So, for RC4 the computation cost unit is the byte ? And in this case we can say that to encrypt an $n$-bits message, the cost is $n$ ? – Dingo13 Sep 11 '14 at 16:58
• I have no idea what would be a good answer other than "any decent symmetric cipher takes $\Theta(n)$ time to encrypt a message $n$ bits long". A decent cipher can't take less time than that (because it needs to modify at least half of the bits in the message); and since we have algorithms that take that much time, we don't really consider algorithms that take superlinear time. Of course, if your question is about the constant of proportionality (that is, the part that is hidden by the $\Theta$ notation), well, that's implementation dependent. – poncho Sep 11 '14 at 21:50
• CBC takes times $\lceil n / 128 \rceil$ for an $n$ bits message... I would like to know what is the time for real stream cipher. – Dingo13 Sep 15 '14 at 8:22

In any case, the typical runtime will be of the form $a + b \lceil n / c \rceil$, where $a$ is the setup (+ teardown) time, $b$ is the time per chunk, $c$ is the chunk length and $n$ is the message length (in appropriate units, typically bits or bytes). Asymptotically, this will be ${\rm O}(n)$.
One peculiar corner case is that, for ciphers that require the message to be unambiguously padded to a multiple of the chunk size (such as block ciphers in CBC mode), messages that already happen to be a whole number of chunks long will typically need to have an extra chunk appended, so that the time cost becomes of the form $a + b \lceil (n + 1) / c \rceil$.