# Are there secure stream ciphers that cannot be parallelized?

Are there any stream ciphers (or a deterministic random number generators, that should work as well I guess?) that cannot be parallelized? So for example if I seed it with a specific value, and then "run" it for a year, generating more and more bits, and finally get a bitstream off it, then that bitstream will be impossible (unless somebody "breaks" the cipher) to get a hold on without doing all that work synchronously and requiring at least a similar amount of time. (So that nobody will be able to get 100x cores to do all that work in 100x shorter time. They coult always get a faster processor, or build a specialized chip or something, but it would still run the calculation single-threaded, synchronously still requiring a lot of time to get to the needed bitstream from the initial seed value.)

Do algorithms with similar properties exist? Or can everything be parallelized?

-
Can you elaborate more on the actual problem you're trying to solve? –  Stephen Touset Oct 15 '12 at 23:52
Well, umm, current stream ciphers cannot be parallelized in general, the keystream generation is strictly sequential, although there are random-access schemes (such as a block cipher in CTR mode). –  Thomas Oct 16 '12 at 0:11
(The problem is not completely finalized yet, I have to know if all the components work forst :). About the random-access schemes: do they exist even for true stream ciphers, like RC4? Is there a cipher that doesn't parralellize and doesn't have any random access possibility? –  Cray Oct 16 '12 at 7:04
Do you want this to be slow only for an attacker, or also for a legitimate user which has the "key"? –  Paŭlo Ebermann Oct 16 '12 at 7:33
In the design of this question, both the "attacker" and "user" start with the same known initial cipher state, (same "key", if you will). I only want it reliably taking long time to get from the initial state to some specific state in the future (x many bits from the start of the stream.) (So to answer your question, primarily for the attacker, but the design doesn't give the user any more information than the attacker so it's going to be slow for the user also.) –  Cray Oct 16 '12 at 8:10

As Thomas notes, most stream ciphers cannot be parallelized (in the sense that generating a single keystream would be significantly faster with multiple processors than with one) or randomly accessed (in the sense that the mimimum time needed to compute the $k$-th bit of the keystream would be sub-linear in $k$).

Examples of stream ciphers that cannot be parallelized include:

• As far as I know, ther's no known way to parallelize the RC4 stream cipher in any useful way.

• Block ciphers used in OFB mode are not parallelizable, except insofar as the underlying block cipher itself can be parallelized. I suspect it might even be possible to prove this, given suitable indistinguishability assumptions on the block cipher, although I'm not personally aware of such a proof.

Nonetheless, some stream ciphers do exist which can be parallelized or even randomly accessed. Particularly notable among these is the CTR mode of operation, which turns a block cipher into a randomly accessible (and thus also fully parallelizable) stream cipher.

Some modern stream ciphers are also designed to exhibit at least a limited degree of parallelizability in hardware. For example, the Trivium stream cipher is designed so that it can be used to generate anywhere from one up to 64 bits in parallel. However, any reasonable software implementation of Trivium would already exploit this parallellism to a high degree by operating on 32- or 64-bit blocks of data, so, for all practical purposes, Trivium in software is not (further) parallelizable.

More generally, eseentially all synchronous stream ciphers (including all those mentioned above) may be written in the following form:

\begin{aligned} x_0 &= i \\ x_n &= f(x_{n-1}) &\forall n \in \{1,2,3,\dotsc\} \\ o_n &= g(x_n) &\forall n \in \{1,2,3,\dotsc\} \end{aligned}

where

• $i$ is the initial state of the cipher (derived based on, and possibly including, the key as well as any IVs, tweaks, etc.),
• $x_n$ denotes the internal state of the cipher at step $n$,
• $o_n$ is the keystream output at step $n$,
• $f$ is the function that updates the internal state at each step, and
• $g$ is the function used to map the internal state into the output.

For most stream ciphers, which are not efficiently parallelizable, the cryptographic strength comes from the internal update function $f$, while the output function $g$ is fairly trivial (typically just extracting some part of the internal state). On the other hand, to allow random access into the keystream (as with CTR mode), the update function $f$ must be trivial (for CTR mode, just incrementing a counter by one), so that $x_n$ can be quickly computed from $x_0$ for any $n$, while the cryptographic strength must come solely from the function $g$ (which, for CTR mode, is the underlying block cipher).

One reason why the random access type of stream cipher design is not more widely used is that relying on $g$ instead of $f$ for strength puts much harder demands on it: the fact that $f$ is iteratively applied to its own output allows its strength to build up gradually over many steps, whereas any security coming from $g$ must come from just one single application of it. Most of the update functions $f$ used in traditional stream ciphers like RC4 would be hopelessly insecure if used as $g$ with a trivial $f$.

(Also, if you do manage to design a function that can be used securely as $g$ with a trivial $f$, what you have is basically a secure block cipher or something very close to one. So, in that sense, the CTR mode construction is the generic random access stream cipher, with any other random access stream cipher being essentially the same thing with just cosmetic differences.)

However, I should note that there's another kind of parallelism which may be more relevant: if an attacker wants to crack the cipher by brute force, he will typically do so by generating multiple keystreams from different keys and seeing which of them yields a meaningful decryption. In that case, even if the generation of a single keystream is not parallelizable, the attacker can just take multiple processors (or, say, cores in a GPGPU) and set each of them to generate a different keystream.

This kind of parallelism is quite hard to avoid, since, fundamentally, the generation of many independent keystreams is an embarrassingly parallel task regardless of how each individual keystream is generated. One way to try to slow down such attacks is to make the keystream generation (or other computation) require a lot of memory, on the basis that, with current technology, it's a lot cheaper to build a lot of simple parallel processors than to provide each of them with a large amount of memory to work with.

One example of such a design is the scrypt key derivation function, which is designed to use an adjustable amount of random access memory in an essential way, such that, hopefully, any attempts to compute the function using significantly less memory would only be possible at the expense of a prohibitive increase in computation time.

In fact, reading the scrypt paper, what the ROMix construction used in scrypt does is to first use a non-random-access stream cipher (actually, an iterated hash function) to construct a large (pseudo)random lookup table, and then to use that lookup table to perturb the state of the stream cipher while generating the actual keystream (the end of which, in ROMix, is then taken as the output). It certainly seems feasible to apply a similar construction to actual stream ciphers, although there are various subtle details, as noted in the scrypt paper, to consider.

-
One could simply derive the actual stream cipher key using scrypt from some initial non-secret, which would give about the desired property. –  Paŭlo Ebermann Oct 16 '12 at 17:29
@Paŭlo: Depends on exactly what the "desired property" is, which I'm not too clear about. By my reading of the question, something like iterated (or arbitrarily extended) scrypt would seem closer to what he wants (paraphrased, "if I run this for a year on a fast CPU and then extract a value, nobody else should be able to derive the same value without spending at least a year on it unless they have a faster CPU"). –  Ilmari Karonen Oct 16 '12 at 18:52
Thank's for this answer, very informative, it even goes in depth into different ways the question could be interpreted. –  Cray Oct 17 '12 at 19:46