Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / PRF, birthday bound, SoKAC21, EWCDMD

Original Publication (in the same form): IACR-EUROCRYPT-2020

Date: received 21 Feb 2020

Contact author: mridul nandi at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200224:144515 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]