# 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. Sep 11, 2014 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$ ? Sep 11, 2014 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. Sep 11, 2014 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. Sep 15, 2014 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$.