**What is the Effective Key Length for a Block Cipher: an Attack on Every Block Cipher**

*Jialin Huang and Xuejia Lai*

**Abstract: **Recently, several important block ciphers are considered to
be broken by the bruteforce-like cryptanalysis, with a time complexity
faster than exhaustive key search by going over the entire key space but performing less than a full encryption for each possible key. Motivated by this observation, we describe a meet-in-the-middle attack that can always be successfully mounted against any practical block ciphers with success probability one. The data complexity of this attack is the smallest according to the unicity distance. The time complexity can be written as $2^k(1-\epsilon)$ where $\epsilon > 0$ for all block ciphers. Previously, the security bound that is commonly accepted is the length k of the given master key. From our result we point out that actually this k-bit security is always overestimated and can never be reached due to the inevitable key bits loss. No amount of clever design can prevent it, but increments of the number of rounds can reduce this key loss as much as possible. We give more insight in the problem of the upper bound of eective key bits in block ciphers, and show a more accurate bound. A suggestion about the relation between the key size and block size is given. That is, when the number of rounds is xed, it is better to take a key size equal to the block size. Moreover, eective key bits of many well-known block ciphers are calculated and analyzed, which also conrm their lower security margin than thought before.

**Category / Keywords: **secret-key cryptography /

**Date: **received 30 Nov 2012

**Contact author: **jlhuang cn at gmail com, lai-xj@cs sjtu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20121130:150836 (All versions of this report)

**Short URL: **ia.cr/2012/677

[ Cryptology ePrint archive ]