Is a larger block size less secure against a brute-force known cipertext attack?

Question

Suppose a ciphertext $c$ was encrypted from plaintext $m$, and we know something about the form of $m$; say, for example, that $m$ is English text. We can attempt to brute-force $m$ from $c$ by computing $E^{-1}(c)$ for all possible encryption functions $E$ and discarding the values of $E^{-1}(c)$ which are not English text. However, the probability of $E^{-1}(c)$ consisting entirely of English text (assuming $E$ behaves ''randomly'') decreases as a function of the block size. Hence, it seems that a larger block size results in fewer false positives.

Am I correct in saying that large block sizes are more susceptible to this kind of attack? Do we have to keep this in mind when designing encryption techniques, or are other factors (e.g. key length) more likely to be security bottlenecks?

Answer 1

Do we have to keep this in mind when designing encryption techniques, or are other factors (e.g. key length) more likely to be security bottlenecks?

The short answer is no, you do not have to keep this in mind.

Any modern encryption scheme that is assumed to be secure has large enough keys that the step of "computing $E^{−1}(c)$ for all possible encryption functions $E$" is infeasible. If this is not the case, and the number of candidate keys you receive after such an attack is relevant for the security of the encryption scheme, then the problem lies in the key being too short.

Answer 2

The answer depends on the size of the plaintext you are attacking and the number of ciphertext blocks you have.

Assume that you have a 64-bit block-sized cipher named C64 and 128-bit block cipher named C128.

If you know that the $m$ is smaller than 64-bit than you will have only one ciphertext for C64 and C128. There is a need for padding at the end of the plaintext. This padding can be removed and more importantly it can also be used to detect the correct plaintext like in the DES challanges. There is no difference here.

If the $m$ between 64 and 128 bit than the question, do you have the second block for C64? If not then C128 is better here. Otherwise, the are the same.

Similar comments can be made to other cases. But, in short, if you have the all necessary ciphertexts they are the same. If you have all, the only difference is that you need to run almost C64 double times of C128. But this is not counting the actual running times of the ciphers. C128 is expected to be slower than C64.

Not that: a 64-bit block size is not secure; see sweet32. I've used to demonstrate and historical reasons. We don't have a common 256-bit clock cipher also. Also, brute force is not applicable to block ciphers who have a key size larger than 128. We can see this from the collective power of the bitcoin miners that can reach $2^{94}$ double SHA-256 hashes. Some of the nodes are ASIC that boost the attack. One still needs $2^{34}$ year to break with the enormous collective power.