Paper 2016/1188

Farfalle: parallel permutation-based cryptography

Guido Bertoni and Joan Daemen and Michaël Peeters and Gilles Van Assche and Ronny Van Keer

Abstract

In this paper, we introduce Farfalle, a new mode for building a pseudorandom function (PRF) from a b-bit cryptographic permutation. The constructed PRF takes as input a b-bit key and a sequence of variable-length data strings, and it generates a variable-length output. It consists of a compression layer and an expansion layer, each of them involving the parallel application of the permutation. The construction aims for simplicity and efficiency, among others with the ability to compute it for incremental inputs and with its inherent parallelism. Thanks to its input-output characteristics, Farfalle is very versatile. We specify concrete modes on top of it, for authentication, encryption and authenticated encryption, as well as a wide block cipher mode. Farfalle can be instantiated with any permutation. In particular, we instantiate it with one of the Keccak-p permutations, attach concrete security claims to it and call the result Kravatte. To offer protection against attacks that exploit the low algebraic degree of the round function of Keccak-p, we do domain separation with a particular rolling function that aims at preventing the construction of input sets that form affine spaces of large dimension.