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

Category / Keywords: secret-key cryptography / Farfalle, Xoofff, Xoodoo, Key-Recovery Attacks

Original Publication (in the same form): SAC 2020

Date: received 1 Oct 2020, last revised 1 Oct 2020

Contact author: Tingting Cui at ru nl,l grassi@science ru nl

Available format(s): PDF | BibTeX Citation

Version: 20201006:093553 (All versions of this report)

Short URL: ia.cr/2020/1201


[ Cryptology ePrint archive ]