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.
