International Association for Cryptologic Research

International Association
for Cryptologic Research


Bishwajit Chakraborty


On Length Independent Security Bounds for the PMAC Family 📺
At FSE 2017, Gaži et al. demonstrated a pseudorandom function (PRF) distinguisher (Gaži et al., ToSC 2016(2)) on PMAC with Ω(lq2/2n) advantage, where q, l, and n, denote the number of queries, maximum permissible query length (in terms of n-bit blocks), and block size of the underlying block cipher. This, in combination with the upper bounds of Ο(lq2/2n) (Minematsu and Matsushima, FSE 2007) and Ο(qσ/2n) (Nandi and Mandal, J. Mathematical Cryptology 2008(2)), resolved the long-standing problem of exact security of PMAC. Gaži et al. also showed that the dependency on l can be dropped (i.e. O(q2/2n) bound up to l ≤ 2n/2) for a simplified version of PMAC, called sPMAC, by replacing the Gray code-based masking in PMAC with any 4-wise independent universal hash-based masking. Recently, Naito proposed another variant of PMAC with two powering-up maskings (Naito, ToSC 2019(2)) that achieves l-free bound of O(q2/2n), provided l ≤ 2n/2. In this work, we first identify a flaw in the analysis of Naito’s PMAC variant that invalidates the security proof. Apparently, the flaw is not easy to fix under the existing proof setup. We then formulate an equivalent problem which must be solved in order to achieve l-free security bounds for this variant. Second, we show that sPMAC achieves O(q2/2n) bound for a weaker notion of universality as compared to the earlier condition of 4-wise independence. Third, we analyze the security of PMAC1 (a popular variant of PMAC) with a simple modification in the linear combination of block cipher outputs. We show that this simple modification of PMAC1 has tight security O(q2/2n) provided l ≤ 2n/4. Even if l < 2n/4, we still achieve same tight bound as long as total number of blocks in all queries is less than 22n/3.
On the Security of Sponge-type Authenticated Encryption Modes 📺
Bishwajit Chakraborty Ashwin Jha Mridul Nandi
The sponge duplex is a popular mode of operation for constructing authenticated encryption schemes. In fact, one can assess the popularity of this mode from the fact that around 25 out of the 56 round 1 submissions to the ongoing NIST lightweight cryptography (LwC) standardization process are based on this mode. Among these, 14 sponge-type constructions are selected for the second round consisting of 32 submissions. In this paper, we generalize the duplexing interface of the duplex mode, which we call Transform-then-Permute. It encompasses Beetle as well as a new sponge-type mode SpoC (both are round 2 submissions to NIST LwC). We show a tight security bound for Transform-then-Permute based on b-bit permutation, which reduces to finding an exact estimation of the expected number of multi-chains (defined in this paper). As a corollary of our general result, authenticated encryption advantage of Beetle and SpoC is about T(D+r2r)/2b where T, D and r denotes the number of offline queries (related to time complexity of the attack), number of construction queries (related to data complexity) and rate of the construction (related to efficiency). Previously the same bound has been proved for Beetle under the limitation that T << min{2r, 2b/2} (that compels to choose larger permutation with higher rate). In the context of NIST LwC requirement, SpoC based on 192-bit permutation achieves the desired security with 64-bit rate, which is not achieved by either duplex or Beetle (as per the previous analysis).