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.

Metadata
Available format(s)
-- withdrawn --
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Block CiphersCryptanalysisCryptographic FoundationsIdeal Cipher ModelRandom Oracle
Contact author(s)
roberto avanzi @ gmail com
History
2020-10-07: withdrawn
2019-10-24: received
See all versions
Short URL
https://ia.cr/2019/1243
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.