Paper 2020/236

Mind the Composition: Birthday Bound Attacks on EWCDMD and SoKAC21

Mridul Nandi


In an early version of CRYPTO’17, Mennink and Neves pro- posed EWCDMD, a dual of EWCDM, and showed n-bit security, where n is the block size of the underlying block cipher. In CRYPTO’19, Chen et al. proposed permutation based design SoKAC21 and showed 2n/3- bit security, where n is the input size of the underlying permutation. In this paper we show birthday bound attacks on EWCDMD and SoKAC21, invalidating their security claims. Both attacks exploit an inherent com- position nature present in the constructions. Motivated by the above two attacks exploiting the composition nature, we consider some generic relevant composition based constructions of ideal primitives (possibly in the ideal permutation and random oracle model) and present birthday bound distinguishers for them. In particular, we demonstrate a birthday bound distinguisher against (1) a secret random permutation followed by a public random function and (2) composition of two secret random functions. Our distinguishers for SoKAC21 and EWCDMD are direct con- sequences of (1) and (2) respectively.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2020
PRFbirthday boundSoKAC21EWCDMD
Contact author(s)
mridul nandi @ gmail com
2020-02-24: received
Short URL
Creative Commons Attribution


      author = {Mridul Nandi},
      title = {Mind the Composition: Birthday Bound Attacks on EWCDMD and SoKAC21},
      howpublished = {Cryptology ePrint Archive, Paper 2020/236},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.