Paper 2020/1201

Algebraic Key-Recovery Attacks on Reduced-Round Xoofff

Tingting Cui and Lorenzo Grassi

Abstract

Farfalle, a permutation-based construction for building a pseudorandom function (PRF), is really versatile. It can be used for message authentication code, stream cipher, key derivation function, authenticated encryption and so on. Farfalle construction relies on a set of permutations and on so-called rolling functions: it can be split into a compression layer followed by a two-step expansion layer. As one instance of Farfalle, Xoofff is very efficient on a wide range of platforms from low-end devices to high-end processors by combining the narrow permutation Xoodoo and the inherent parallelism of Farfalle. In this paper, we present key-recovery attacks on reduced-round Xoofff. After identifying a weakness in the expanding rolling function, we first propose practical attacks on Xoofff instantiated with 1-/2-round Xoodoo in the expansion layer. We next extend such attack on Xoofff instantiated with 3-/4-round Xoodoo in the expansion layer by making use of Meet-in-the-Middle algebraic attacks and the linearization technique. All attacks proposed here -- which are independent of the details of the compression and/or middle layer -- have been practically verified (either on the "real" Xoofff or on a toy-version Xoofff with block-size of 96 bits). As a countermeasure, we discuss how to slightly modified the rolling function for free to reduce the number of attackable rounds.