# How does the time complexity of block cipher change with increase in key length?

I am interested especially in the case when the keylength exceeds the length of the plaintext.

Intuitively, it should be harder to crack the key with an increase in key length even if it exceeds the plaintext length but does it actually hold true or there any caveats to this particular scenario?

• A configured block cipher, in itself, has one size of plaintext: the block size. If keys larger than the block size were a problem then AES-256 - which has a block size of 128 bits - would be in serious problems. Jan 26, 2017 at 20:53
• Please clarify what "time complexity of block cipher" is in the context of the question. Is that about time to compute the cipher; time to find by brute force a key of the cipher matching some number of plaintext/ciphertext pairs; or time complexity of some other form of attack?
– fgrieu
Jan 27, 2017 at 8:02
• @fgrieu Time to break the block cipher. I should've made that clear. Feb 3, 2017 at 8:27

Usually we want a block cipher to be resistant to an exhaustive search attack on the key, if the key space $\mathcal K$ is the set of all binary strings of length $n$ then for a particular $k$ the attacker would have to search against $2^n$ possible keys, so the key length is chosen to make the mentioned attack infeasible.
When we encrypt a message of arbitrary length it gets broken in chunks and the cipher is used within a particular mode of operation (ECB, CBC, etc) and because of the birthday paradox if the block size is not large enough the cipher could be vulnerable to a birthday attack which shows that after $2^{m/2}$ message blocks, where $m$ is the block size, we already have a 50% probability of having a ciphertext block collision and therefore leaking information about the original plaintext blocks.
For example 3DES works with key of length 168, which makes theoretically the exhaustive search attack unfeasible$^*$, but it's designed to accept blocks of 64 bits which means that after we collect $2^{32}$ encrypted blocks ($\sim$32GB of data) we expect to have a collision with 50% probability.
$^*$there is a known attack that runs in time $2^{112}$ instead of $2^{168}$