Paper 2020/236

Mind the Composition: Birthday Bound Attacks on EWCDMD and SoKAC21

Mridul Nandi

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2020
Keywords
PRFbirthday boundSoKAC21EWCDMD
Contact author(s)
mridul nandi @ gmail com
History
2020-02-24: received
Short URL
https://ia.cr/2020/236
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/236,
      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{https://eprint.iacr.org/2020/236}},
      url = {https://eprint.iacr.org/2020/236}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.