# 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>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>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>n$, then we would get several plaintext/ciphertext pairs against the underlying block cipher

• So it is true that one can massively reduce the key space just by knowing a single block and it's encryption? How many plaintext-ciphertext blocks would you need to find the key exactly? – shin Dec 7 '14 at 16:11
• @shin: you're looking at the concept of Unicity Distance; how much ciphertext (and in this case exact plaintext) you need before the key becomes unique; again, it is typically $k+\epsilon$ bits (where $k$ is the number of unknown bits; that would include key bits, and any implicit IV bits). On the other hand, this analysis rather assumes that the attacker can step through all $2^k$ possibilities (or has another short cut); for ciphers that we use in practice, this is believed to be infeasible. – poncho Dec 7 '14 at 17:53

You're missing a component : a padding convention. Yes, if you're trying to reduce a block size, it will reduce the cipher strength. That's why the less-sized blocks are padded/filled to fit the exact size. What to do : pad or fill or both - that is a question. First you need to understand, that the more predictible the message, the less secure the transmission of ciphertext : you're aware that it's a TCP packet, for example, and then you KNOW that it has a header e.t.c... So the filling and padding are usually performed both and with the random data, not filling by, for example, zeros. As an example we can say that for cipher AES-256 the first 8 bits will be actual packet size in bits, and if it's less than a full one - 1 = 255, the remainder will be filled equally from the beginning and from an end with random data with the remainder(if any) in a trail. So - AES-256 will receive it's full block and it will not make a reduction you're mentioned, and you'll be able to trim the message data from random-data in a partial package. It's just an example, but I think it will give you the main idea.

• Good point. However, without padding, the statement is true I guess? – shin Dec 7 '14 at 16:12
• Yes, you're correct : encipherment strength is based not just in key size itself. Keysize AND matching Blocksize are complementary here and both of them are required to achive the necessary privacy. However, a computational difficulty can decrease not precisely as you're specified - it's an algo-dependent value. But it will decrease for sure. – Alexey Vesnin Dec 8 '14 at 18:27