Return to Answer

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 implements 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).

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).

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 thus implements 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).

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 implements 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).

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 thus implements 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 $(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).

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 thus implements 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).