# How does using a really small block size reduce the key space?

I read this online and was confused:

Modern block ciphers tend to have block sizes of 128 bits or larger, because if the block size is too small there is the same problem as a small key space as described previously—the adversary can enumerate all the possible options and thus undermine the algorithm.

How does a small block size reduce the key space?

How does a small block size reduce the key space?

Let $$b$$ be the block bit size of a block cipher. There are $$2^b$$ possible block values, for a plaintext, and for a ciphertext. For a fixed key, there is a single ciphertext corresponding to any given plaintext, and vice-versa. A key and the block cipher thus implement a bijection on the set of $$n=2^b$$ possible block values. Given a set of $$n$$ elements, there are $$n!$$ bijections on this set. Thus there are at most $$(2^b)!$$ possible plaintext-to-ciphertext correspondences/bijections for our block cipher.

No matter how large a key for our block cipher is, it is bound to generate one of these $$(2^b)!$$ correspondences/bijections. A $$k$$-bit key can take $$v=2^k$$ values, thus for $$v$$ values we need $$k=\log_2(v)$$ bits of key. Thus the effective key space is limited to $$k=\log_2((2^b)!)$$ bits. $$\begin{array}{r|rr} b&1&2&3&4&5&6&7&8&9&10\\ \hline k&1&4.6&15.3&44.3&117.7&296.0&716.2&1684.0&3875.2&8769.0 \end{array}$$ For example, with $$b=3$$, there are $$2^3=8$$ possible block values, thus $$8!=40320$$ possible plaintext-to-ciphertext correspondences, corresponding to a key somewhere between $$15$$ and $$16$$ bits (giving $$2^{15}=32768$$ and $$2^{16}=65536$$ keys).

Thus for REALLY small block size (less than about 6 bits), the block size indeed limits the key space.

But the quote¹ in the question is about something else: the risk of reuse of a block value, without consideration about the keyspace. For a random distribution of block values, there's >39% chance that a value gets reused after $$2^{b/2}$$ blocks (see this). This is a concern for less small blocks.

For $$b=64$$ (as in TDES), $$2^{b/2}$$ blocks is a mere 32GiB of data. If we have two 32GiB files TDES-CBC-encrypted with the same key, and the first file is known, there is >63% chance we can decipher at least 8 bytes of the second file, because a block in the second file matches one in the first file.

¹ That quote does not say that we moved to larger blocks like 128-bit because smaller blocks dangerously reduce the key space, which would be wrong. It says small blocks harm security, much like small key space does, and that is correct (even if the justification given is rather vague).

• Thank you so much fgrieu! Are you able explain a bit more simply how you got the effective key space formula? Apr 10 at 11:09
• @fgrieu The round is the other important parameter. One can design a stupid key schedule that uses a 1024-bit key and hash it the derive sub-keys. We have 64-bit block ciphers that use the 128-bit keys, too. Simon, Speck, Serpent, etc. Apr 10 at 14:05
• Based on just that quote, and esp. the reference to an adversary enumerating all possible values, I'm not sure I'd give them the benefit of assuming they indeed refer to the issue of ciphertext blocks colliding. I mean, it looks more like that they're handwaving vaguely since they've heard that small blocks == bad, without understanding exactly why that is... Apr 10 at 17:06
• That made a lot more sense, thank you! The only other thing I was wondering, isn't a stream cipher like a 1 bit block cipher meaning it should have an effective keyspace of 1? Sorry if this is a really silly question. I'm only just learning this stuff Apr 10 at 18:41
• @Joe lBelton: there are differences between a stream cipher and a 1 bit block cipher. The main one is that the stream cipher has a state, typically large: where the block cipher has none (a block cipher in CBC mode has a state just as large as the block).
– fgrieu
Apr 10 at 19:04