International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Key-Recovery Attacks on Full Kravatte

Authors:
Colin Chaigneau , UVSQ, Versailles
Thomas Fuhr , ANSSI Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP
Henri Gilbert , UVSQ, Versailles; ANSSI, Paris
Jian Guo , Nanyang Technological University
Jérémy Jean , ANSSI Crypto Lab, Paris
Jean-René Reinhard , ANSSI Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP
Ling Song , Nanyang Technological University, Singapore; Institute of Information Engineering, Chinese Academy of Sciences
Download:
DOI: 10.13154/tosc.v2018.i1.5-28
URL: https://tosc.iacr.org/index.php/ToSC/article/view/842
Search ePrint
Search Google
Award: Best Paper FSE 2018
Abstract: This paper presents a cryptanalysis of full Kravatte, an instantiation of the Farfalle construction of a pseudorandom function (PRF) with variable input and output length. This new construction, proposed by Bertoni et al., introduces an efficiently parallelizable and extremely versatile building block for the design of symmetric mechanisms, e.g. message authentication codes or stream ciphers. It 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. The key is expanded and used to mask the inputs and outputs of the construction. Kravatte instantiates Farfalle using linear rolling functions and permutations obtained by iterating the Keccak round function.We develop in this paper several attacks against this PRF, based on three different attack strategies that bypass part of the construction and target a reduced number of permutation rounds. A higher order differential distinguisher exploits the possibility to build an affine space of values in the cipher state after the compression layer. An algebraic meet-in-the-middle attack can be mounted on the second step of the expansion layer. Finally, due to the linearity of the rolling function and the low algebraic degree of the Keccak round function, a linear recurrence distinguisher can be found on intermediate states of the second step of the expansion layer. All the attacks rely on the ability to invert a small number of the final rounds of the construction. In particular, the last two rounds of the construction together with the final masking by the key can be algebraically inverted, which allows to recover the key.The complexities of the devised attacks, applied to the Kravatte specifications published on the IACR ePrint in July 2017, or the strengthened version of Kravatte recently presented at ECC 2017, are far below the security claimed.
BibTeX
@article{tosc-2018-28400,
  title={Key-Recovery Attacks on Full Kravatte},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 1},
  pages={5-28},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/842},
  doi={10.13154/tosc.v2018.i1.5-28},
  author={Colin Chaigneau and Thomas Fuhr and Henri Gilbert and Jian Guo and Jérémy Jean and Jean-René Reinhard and Ling Song},
  year=2018
}