2
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Sep 11 '14 at 13:03
  • $\begingroup$ 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$ ? $\endgroup$ – Dingo13 Sep 11 '14 at 16:58
  • 3
    $\begingroup$ 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. $\endgroup$ – poncho Sep 11 '14 at 21:50
  • $\begingroup$ 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. $\endgroup$ – Dingo13 Sep 15 '14 at 8:22
6
$\begingroup$

For any typical stream cipher (including block ciphers in streaming modes like CBC / CFB / OFB / CTR), the time needed to encrypt a message consists of two parts:

  1. the time needed to set up the cipher, which is approximately constant, and
  2. the time needed to encrypt a chunk of the message (also approximately constant), multiplied by the number of chunks in the message (rounded up).

Most ciphers will process the message (or at least generate the keystream) in chunks of more than one bit at a time. For block ciphers in streaming modes, the chunk size will typically equal the block size of the underlying block cipher. For dedicated stream ciphers, the chunk size may vary, even between different implementations of the same cipher. For some examples, RC4 generates its keystream in chunks of 8 bits, whereas Trivium can generate anything from 1 to 64 bits at a time, depending on how strongly the implementation is parallelized.

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$.

Also, it should be noted that these are all theoretical timings. In the real world, if you graph the time needed to encrypt messages of varying size on a real CPU, you're likely to see all sorts of weird jags, kinks and noise due to things like cache misses, branch prediction, microcode optimizations, interrupts, concurrent threads, etc. On a large enough scale, though, the overall pattern will still generally look approximately linear in the message length.

|improve this answer
$\endgroup$

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.