Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Block Ciphers, Cryptanalysis, Cryptographic Foundations, Ideal Cipher Model, Random Oracle

Date: received 23 Oct 2019, last revised 23 Oct 2019, withdrawn 7 Oct 2020

Contact author: roberto avanzi at gmail com

Available format(s): (-- withdrawn --)

Version: 20201007:094001 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]