Paper 2019/1243

On The Distinguishability of Ideal Ciphers

Roberto Avanzi and Yvo Desmedt

Abstract

We present distinguishing attacks (based on the Birthday Paradox) which show that the use of $2^{\ell}$ permutations for a block cipher is insufficient to obtain a security of $\ell$ bits in the Ideal Cipher Model. The context is that of an Oracle that can provide an Adversary the ciphertexts of a very small number of known plaintexts under a large number of (session) keys and IVs/nonces. Our attacks distinguish an ideal cipher from a ``perfectly ideal'' block cipher, realised as an Oracle that can always produce new permutations up to the cardinality of the symmetric group on the block space. The result is that in order to guarantee that an Adversary which is time limited to $O(2^{\ell})$ encryption requests has only a negligible advantage, the cipher needs to express $2^{3\ell}$ distinct permutations. This seems to contradict a folklore belief about the security of using a block cipher in the multi-key setting, i.e.\ to obtain $\ell$-bit security it is sufficient to use $\ell$- or $2\,\ell$-bit keys depending on the mode of operation and the use case.