International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Mind the Composition: Birthday Bound Attacks on EWCDMD and SoKAC21

Authors:
Mridul Nandi , Indian Statistical Institute
Download:
DOI: 10.1007/978-3-030-45721-1_8 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: In an early version of CRYPTO'17, Mennink and Neves proposed \textsf{EWCDMD}, a dual of \textsf{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 \textsf{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 \textsf{EWCDMD} and \textsf{SoKAC21}, invalidating their security claims. Both attacks exploit an inherent composition 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 \textsf{SoKAC21} and \textsf{EWCDMD} are direct consequences of (1) and (2) respectively.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30176,
  title={Mind the Composition: Birthday Bound Attacks on EWCDMD and SoKAC21},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={PRF;birthday bound;SoKAC21;EWCDMD},
  volume={12105},
  doi={10.1007/978-3-030-45721-1_8},
  author={Mridul Nandi},
  year=2020
}