What is the difference between substitution cipher and block cipher?

Question

I'm studying(and clearing my head) about block cipher. I started from Caesar Cipher which can be considered as a kind of substitution cipher (if my understanding is right).

And an ideal substitution cipher (in 26 alphabets) is the two functions $E(x,k)$ and $D(x,k)$ where $0 \leq k < 26!$. And given $k$, one of the bijection(substitution) functions is (uniformly)selected and used to substitute a letter.

What I thought here is that this is also a block cipher. (1 letter is 1 block) I read https://en.wikipedia.org/wiki/Substitution_cipher and it says

Although the number of possible keys is very large ($26! \approx 2^{88.4}$, or about 88 bits), this cipher is not very strong, and is easily broken. Provided the message is of reasonable length (see below), the cryptanalyst can deduce the probable meaning of the most common symbols by analyzing the frequency distribution of the ciphertext—frequency analysis.

I feel this description is talking about the problem of ECB mode in block cipher.

So my understanding so far is that substitution cipher can be considered as a block cipher. But I'm wondering if a block cipher is always substitution cipher.

What is the difference between them in general.

Answer 1

I feel this description is talking about the problem of ECB mode in block cipher.

So my understanding so far is that substitution cipher can be considered as a block cipher. But I'm wondering if a block cipher is always substitution cipher.

(1) let us compare a block cipher with ECB mode to a substitution cipher.

With ECB Mode and a given key, a block cipher can be seen as a substitution cipher which maps one block to another block. For example, AES, twofish, or serpent has a block size of 128 bits; you may say, "one 128-bit block is substituted to another 128-bit block".
(Note: this is just a simple comparison. If a block cipher has a "state", the same input blocks might get different output blocks. In this case, the block cipher might be compared to Vigenère cipher.)

While a Caesar Cipher maps one letter to another letter. That is from a 5-bit to a 5-bit, or at most a byte to a byte. (From this point, you could be right to say "substitution cipher can be considered as a block cipher"; but the block size is quite small.)

So, I might say a Caesar Cipher is a special block cipher which has a small block size; or, on the other hand, a 128-bit block cipher (with ECB mode) is a "monster Caesar Cipher with 2¹²⁸ letters".

(2) a block cipher with certain mode (except ECB)
This is a fun part. From my point of view, if you want, you can actually create a Caesar Cipher with CBC, PCBC, OFB, CFB, CTR modes by replacing the IV or counter with a letter.

What is the difference between them in general.

(3) difference

They are quite different in practice.

But the main one is size: block size, key size, IV size, and counter size. (The last two is really the block size for different uses).

If a monster Caesar Cipher has 2¹²⁸ letters and has CBC, PCBC, OFB, CFB, CTR modes, it might be as strong as a 128-bit block cipher.

Answer 2

A block cipher performs some sort of encryption over blocks of data. Whether this encryption is a substitution or transposition cipher doesn't matter. If it operates over blocks of data, it is a block cipher.

A stream cipher can work on any sized data as there is no "block size" plaintext must fit to.

A substitution cipher can operate either on blocks or on streams.

Answer 3

There is a bunch of topics to discuss, which usually get chained to build more complex schemes, and thus might or might not be related.

Substitution and transposition

I am used to this naming, but you can find these concepts also as difusion and confusion. These are the two basic operations that you can perform on data to obfuscate its content. Substitution consists on taking the $i$-th element of your string and change it for another value. For most of the classical ciphers, that's it. Caesar, Vigenère, One Time Pad and other related algorithms take each token (character/bit) individually and the result is independent from the rest of the string. Transposition consists on keeping the same values, but modifying the order. Think of it like anagrams.

Modern ciphers use a combination of both procedures.

Stream and block ciphers

Stream ciphers encrypt each token as it arrives. Maybe with a short fixed key, like Caesar, or a key as long as the plaintext, like OTP. In both cases, some limitations, vulnerabilities and practical issues may arise. Block ciphers operate on blocks of fixed size. As a result, the difficulty of breaking one block is roughly the same than the difficulty for breaking a whole encrypted file. This is way less than the perfect secrecy promised by OTP, but for reasonable block sizes, it's the most practical approach to follow.

Your question

Taking a stream cipher as a block cipher of block size 1 is almost a philosophical consideration. Given the way in which they have been described, it is possible to do so, but it is not a useful approach. For instance, a normal block cipher will use transposition inside the block, but if the block size is 1, there is no possible way to scramble it.

In general, take classic ciphers with a pinch of salt, since they are extremely useful to build a mindset, and reduce the effort to understand more modern and abstract constructions, but might lead to oversimplification. As I said, I believe your observation is not mistaken, just not very helpful to the analysis.