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?

  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Jan 26 '17 at 20:53
  • $\begingroup$ 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? $\endgroup$
    – fgrieu
    Jan 27 '17 at 8:02
  • $\begingroup$ @fgrieu Time to break the block cipher. I should've made that clear. $\endgroup$
    – tinkuge
    Feb 3 '17 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.

Even if the cipher is proved to be computationally secure there is another (sometimes underestimated) security issue related to the cipher block size.

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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.