# Why is there a strong distinction between stream and block ciphers?

If I don't err, in the literature a stream cipher is one in which each plaintext bit is processed individually, commonly via xor-ing with one bit of a random or pseudo-random bit stream, while a block cipher (in ECB mode, i.e. ignoring the add-on processing operations like CBC etc.) operates on n bits at a time with operations that are the same for a given key, i.e. each successive groups of n bits are processed in exactly the same manner.

If one looks at the corresponding literatures, one finds in the first case mostly works on linear or non-linear feedback shift registers and in the second case ideas of design of a rather different genre. That could justify the differentiation in terminolgy however IMHO only on the assumption that no cipher designs could lie inbetween the two categories. But that assumption seems to me to be an invalid one. Anyway, let's consider the classical ciphers. Is a Vigenere cipher or a (additive) cipher with a running key a stream cipher or a block cipher? That question seems not to be very satisfactorily to be answered, I am afraid.

-
The last paragraph makes this seem more like an argument than a question. Please note that you should only ask practical, answerable questions based on actual problems that you face here. If you don't want to risk your question being closed or downvoted, I'd strongly suggest rewriting it to be more of an actual question (perhaps just deleting the last paragraph outright). –  Ilmari Karonen Sep 22 '12 at 14:11
"in the first case the dynamics or variability" What's that supposed to mean? –  CodesInChaos Sep 22 '12 at 14:29
As for your own cipher, why do you think a cipher that's 10000 times as slow as AES is acceptable? There are dozens of open source implementations of AES, so your "commercial proprietary (black-box) IT-security software, which generally have very excellent computing efficiency but which are absolutely unknown (since by definition un-knowable) of being free or not of dormant backdoors implanted by mafias or malicious agencies of certain mighty pseudo-righteous pseudo-humanitarian pseudo-peace-loving pseudo-democratic regimes of the world" argument certainly doesn't apply to AES. –  CodesInChaos Sep 22 '12 at 14:39
Welcome to Cryptography Stack Exchange. Please note that this is not a discussion forum, but a question-and-answer site, and as such we prefer constructive questions, as mentioned by Ilmari. There is a constructive core in your question, but towards the end it is mostly argumenting. –  Paŭlo Ebermann Sep 22 '12 at 15:51
In an effort to keep this question from being closed, I've edited it to remove the argumentative last paragraph, leaving only the actual question. Further improvements are welcome. –  Ilmari Karonen Sep 22 '12 at 16:34
show 1 more comment

Mathematically, a block cipher is just a keyed pseudorandom permutation family on the set $\{0,1\}^n$ of $n$-bit blocks. (In practice, we usually also require an efficient way to compute the inverse permutation.) A block cipher on its own is not very useful for practical cryptography, at least unless you just happen to need to encrypt small messages that each fit into a single block.

However, it turns out that block ciphers are extremely versatile building blocks for constructing other cryptographic tools: once you have a good block cipher, you can easily build anything from stream ciphers to hash functions, message authentication codes, key derivation functions, pseudorandom number generators, entropy pools, etc. based on just one block cipher.

Not all of these applications necessarily need a block cipher; for example, many of them could be based on any pseudorandom function which need not be a permutation (but, conveniently, there's a lemma that says a pseudorandom permutation will, nonetheless, work). Also, many of the constructions are indirect; for example, you can construct a key derivation function from a message authentication code, which you can construct from a hash function, which you can — but don't have to — construct from a block cipher. But still, if you have a block cipher, you can build all the rest out of it.

Furthermore, these constructions typically come with (conditional) security proofs that reduce the security of the constructed functions to that of the underlying block cipher. Thus, you don't need to carry out the laborious and unreliable task of cryptanalyzing each of these functions separately — instead, you're free to concentrate all your efforts on the block cipher, knowing that any confidence you'll have on the security of the block cipher directly translates into confidence on all the functions based on it.

Obviously, all this is very convenient if you're, say, working on a small embedded platform where including efficient and secure code for lots of separate crypto primitives could be difficult and expensive. But even if you're not on such a constrained platform, writing and analyzing low-level crypto code can be laborious due to the need to pay attention to things like side-channel attacks. It's easier to restrict yourself to a limited number of low-level building blocks and to build everything you need out of those.

Also, even on fast platforms with lots of memory, like desktop CPUs, implementing low-level crypto operations directly in hardware can be much faster than doing them in software — but it's not practical to do that for more than a few of them. Due to their versatility, block ciphers are excellent candidates for hardware implementation (as in the AES instruction set for modern x86 CPUs).

Mathematically, a stream cipher — in the most general sense of the term — is also a keyed invertible pseudorandom function family, but on the set $\{0,1\}^*$ of arbitrary-length bitstrings rather than on blocks of limited length.

(There are some subtleties here; for example, most stream cipher constructions require the input to include a unique nonce value, and do not guarantee security — in the sense of indistinguishability from a truly random function — if the same nonce is used for two different inputs. Also, as there is no uniform distribution on invertible functions from $\{0,1\}^*$ to itself to choose random functions from, we need to define carefully just what it means for a stream cipher to look "indistinguishable from random", and this definition does have practical security implications — for example, most stream ciphers leak the length of the message. Practically, we usually also require that stream ciphers, in fact, be "streaming", in the sense that arbitrarily long input bitstreams can be encrypted — and decrypted — using only constant storage and time linear in the message length.)

Of course, stream ciphers are much more immediately useful than block ciphers: you can use them directly to encrypt messages of any length. However, it turns out that they're also much less useful as building blocks for other cryptographic tools: if you have a block cipher, you can easily turn it into a stream cipher, whereas turning an arbitrary stream cipher into a block cipher is difficult if not impossible.

So why do people bother designing dedicated stream ciphers at all, then, if block ciphers can do the job just as well? Mostly, the reason is speed: sometimes, you need a fast cipher to encrypt lots of data, and there are some really fast dedicated stream cipher designs out there. Some of these designs are also designed to be very compact to implement, either in software or hardware or both, so that if you really only need a stream cipher, you can save on code/circuit size by using one of those ciphers instead of a general block cipher based one.

However, what you gain in speed and compactness, you lose in versatility. For example, there doesn't seem to be any simple way to make a hash function out of a stream cipher, so if you need one of those (and you often do, because hash functions, besides being useful on their own, are also common building blocks for other crypto tools), you'll have to implement them separately. And, guess what, most hash functions are based on block ciphers, so if you have one, you might as well reuse the same block cipher for encryption too (unless you really need the raw speed of the dedicated stream cipher).

-
I questioned whether it is necessary to have two different terms. According to what you explained, a stream cipher is simply a special case of a block cipher, i.e. one for the limiting case where the n in the set {0,1}^n is 1. So I would argue for not maintaining the current distinction of terminologies. –  Mok-Kong Shen Sep 22 '12 at 15:42
@Mok-KongShen Actually, a stream cipher is not simply a block cipher with block size 1 (other than classic monoalphabetic ciphers, which can be assumed to be both). A stream cipher usually translates the bits/bytes/... of the stream differently, depending on the current internal state of the cipher, while a block cipher for same input has same output (and thus is usually used in a "mode of operation" to create a stream cipher). –  Paŭlo Ebermann Sep 22 '12 at 15:57
@PauloEbermann. IMHO you answered for me a question of CodesinChaos conscerning "dynamics and variability". –  Mok-Kong Shen Sep 22 '12 at 16:50
@Mok-KongShen No he didn't. The only advantage a dedicated stream cipher has over a block cipher in an appropriate mode is performance. You can't disregard chaining modes, since nobody sane uses block ciphers without appropriate chaining. –  CodesInChaos Sep 22 '12 at 17:48
@CodesInChaos. Different applications have different performance requirements. To encrypt e.g. an email, one doesn't need the performance that would be desirable for encryption of, say, a video-file. –  Mok-Kong Shen Sep 22 '12 at 18:02

A block cipher by itself does map n bits to n bits using a key. i.e. it's a keyed pseudo-random permutation. It cannot accept longer or shorter texts.

To actually encrypt a message you always need a chaining mode. ECB is one such chaining mode(and a really bad one), and it's not the pure block cipher. Even ECB consists of "add-on processing operations". These chaining modes can have quite different properties.

One of the most popular chaining modes, Counter mode (CTR) constructs a synchronous stream cipher from a block cipher. Another mode, CFB constructs a self synchronizing stream cipher, with properties somewhere between those of CBC and a synchronous stream cipher.

So your assumption that there are no ciphers between stream and blockciphers isn't really true. Cryptographers just prefer building them from the well understood block cipher primitive, instead of creating a completely new system.

I'd call Vigenère a stream cipher, albeit one with a much too short period. It uses a 26 symbol encoding instead of a 2 symbol encoding, but that doesn't mean it's not a stream cipher. Look at Solitaire/Pontifex for a modern construction of a stream cipher with 26 symbols.

-
If I don't err, "chaining" in block encryption is normally employed in the context of "block chaining", i.e. rendering the successive blocks dependent on one another so as to make the analysis more difficult. So IMHO ECB would have by definition no chaining effect as such. –  Mok-Kong Shen Sep 22 '12 at 17:20