Paper 2016/1098

Multi-key Analysis of Tweakable Even-Mansour with Applications to Minalpher and OPP

Zhiyuan Guo, Wenling Wu, Renzhang Liu, and Liting Zhang

Abstract

The tweakable Even-Mansour construction generalizes the conventional Even-Mansour scheme through replacing round keys by strings derived from a master key and a tweak. Besides providing plenty of inherent variability, such a design builds a tweakable block cipher from some lower level primitive. In the present paper, we evaluate the multi-key security of TEM-1, one of the most commonly used one-round tweakable Even-Mansour schemes (introduced at CRYPTO 2015), which is constructed from a single $n$-bit permutation $E$ and a function $f(k,t)$ linear in $k$ from some tweak space to ${\{ 0,1\} ^n}$. Based on giant component theorem in random graph theory, we propose collision-based multi-key attacks on TEM-1 in the known-plaintext setting. Furthermore, inspired by the methodology of Fouque et al. presented at ASIACRYPT 2014, we devise a novel way of detecting collisions to obtain memory-efficient attacks in the blockwise-adaptive chosen-plaintext setting. As applications, we utilize our techniques to analyze the authenticated encryption algorithm Minalpher (a second-round candidate of CAESAR) and OPP (proposed at EUROCRYPT 2016) in the multi-key setting. First, we present our known-plaintext attacks on Minalpher and OPP without nonce misuse, which enable us to recover almost all $O(2^{(n/3)})$ independent equivalent keys by making $O(2^{(n/3)})$ queries per key and costing $O(2^{(2n/3)})$ memory overall. Moreover, after defining appropriate iterated functions and accordingly changing the mode of creating chains, we improve the basic blockwise-adaptive chosen-plaintext attack to make it applicable for the nonce-respecting setting. While our attacks do not contradict the security proofs of Minalpher and OPP in the classical setting, nor pose an immediate threat to their uses, our results demonstrate their security margins in the multi-user setting should be carefully considered. We emphasize this is the very first third-party analysis on Minalpher and OPP.