How does blocksize affect security?

Question

I have recently read about how blockciphers and how stream ciphers work, and although I think I finally got everything right, I'm still wondering how increasing blocksize increases security.

Answer 1

Block ciphers are usually used in modes of operation. The security of a mode of operation depends on two things: the security of the underlying block cipher, and the security of the mode itself when you replace the block cipher with an "ideal" permutation.

Say you're using a block cipher with block size $n$ bits, so with AES-256, $n = 128$ (the 256 refers to the key size). A good block cipher should be a pseudorandom permutation, meaning when you give it a uniformly distributed key, it should be difficult to distinguish it from an ideal permutation. An ideal permutation is a uniformly randomly generated permutation over all permutations from $n$ bits to $n$ bits, basically a mathematical object.

Determining whether a given block cipher is secure means cryptanalyzing it to make sure there are no obvious attacks. Such attacks make use of the structure of the block cipher, so for example, this would mean looking at the S-boxes in AES-256 and seeing how they interact with each other, and performing differential, linear, and other types of cryptanalysis. None of these techniques make explicit use of the block size, hence having a smaller block size does not mean you will be able to distinguish a block cipher from an ideal permutation more easily. So when it comes down to block cipher security, the block size does not play an important role.

In contrast, mode security depends strongly on the block size. I mentioned earlier that you also need to look at mode security when the block cipher is replaced with an ideal permutation. Once you do this, you can theoretically analyze the modes and even explicitly compute how its security degrades as you use it. To give an example, GCM has a security degradation of roughly $\sigma^2/2^n$, which represents adversary success probability, with $\sigma$ the number of permutation calls. This means that the more data you process with GCM, the more exposed the mode becomes. The reason this happens is because GCM's security relies on the ideal permutation being "hidden" from the adversary, and as you use GCM you increasingly expose the hidden permutation.

So putting everything together, even if you know that your block cipher on $n$ bits is indistinguishable from an ideal permutation on $n$ bits, your security will still degrade when you use the block cipher in a mode. Hence if you have the option of using a block cipher with small block size, or a block cipher with large block size, then it is better to use the block cipher with larger block size since you'll be able to use it in a mode much longer (assuming all else equal, meaning the cipher is secure for both block sizes).

Answer 2

Block size does not directly affect the security of the cipher. However, if block size is too small, it can prevent you from using the cipher securely.

The main effect of block size is due to the fact that a block cipher is meant to be a pseudorandom permutation (PRP). That means that any two inputs will have outputs that differ iff the inputs differ. So seeing two equal block cipher outputs under the same key you know the inputs were equal as well.

With most modes of operation, this means that you can only use the block cipher as long as these collisions remain unlikely. This limit is determined by the block size: as you approach the birthday bound of $2^{b/2}$ blocks encrypted (with $b$ the block size in bits}, it is increasingly likely the output is equal to some output seen before.

The exact boundary and effect of block size depends on the mode used.