Paper 2015/222

Towards Understanding the Known-Key Security of Block Ciphers

Elena Andreeva, Andrey Bogdanov, and Bart Mennink


Known-key distinguishers for block ciphers were proposed by Knudsen and Rijmen at ASIACRYPT 2007 and have been a major research topic in cryptanalysis since then. A formalization of known-key attacks in general is known to be difficult. In this paper, we tackle this problem for the case of block ciphers based on ideal components such as random permutations and random functions as well as propose new generic known-key attacks on generalized Feistel ciphers. We introduce the notion of known-key indifferentiability to capture the security of such block ciphers under a known key. To show its meaningfulness, we prove that the known-key attacks on block ciphers with ideal primitives to date violate security under known-key indifferentiability. On the other hand, to demonstrate its constructiveness, we prove the balanced Feistel cipher with random functions and the multiple Even-Mansour cipher with random permutations known-key indifferentiable for a sufficient number of rounds. We note that known-key indifferentiability is more quickly and tightly attained by multiple Even-Mansour which puts it forward as a construction provably secure against known-key attacks.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2013
Block ciphersknown-key securityknown-key distinguishersindifferentiability
Contact author(s)
bart mennink @ esat kuleuven be
2015-03-09: received
Short URL
Creative Commons Attribution


      author = {Elena Andreeva and Andrey Bogdanov and Bart Mennink},
      title = {Towards Understanding the Known-Key Security of Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/222},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.