Block size vs key size confusion I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k&gt;n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k-n}$ possible keys, right? But doesn't DES/AES have a similar system as a block cipher with keys bigger than the blocks. So surely finding one message-ciphertext pair doesn't narrow down the key search so much!?

As you can see, I'm quite confused and so any help would be appreciated!
I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k&gt;n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k−n}$ possible keys, right?


That is approximately correct (if the block cipher with the wrong key acts like a random permutation; this is generally a safe assumption); if block "one message-ciphertext pair", you mean "a single $n$-bit plaintext/ciphertext block.

However, that's not necessarily what we mean by a "message-ciphertext pair".  We often want to encrypt messages that are larger than $n$ bits; to do this, we use a mode of operation (which uses the block cipher to encrypt larger messages); if we have a larger message (and we know the plaintext and the ciphertext of this larger message), then we usually (depending on the exact mode used) have a number of $n$-bit plaintext/ciphertext blocks.

The upshot of this is that if we have a $k$-bit message (and corresponding ciphertext), this is usually sufficient to allow us to recognize the key (with a possible 1 or 2 false hits; those can be eliminated if we take a message slightly larger than $k$ bits); if $k&gt;n$, then we would get several plaintext/ciphertext pairs against the underlying block cipher