Paper 2014/058

Cryptanalysis of FIDES

Itai Dinur and Jérémy Jean

Abstract

FIDES is a lightweight authenticated cipher, presented at CHES 2013. The cipher has two version, providing either 80-bit or 96-bit security. In this paper, we describe internal state-recovery attacks on both versions of FIDES, and show that once we recover the internal state, we can use it to immediately forge any message. Our attacks are based on a guess-and-determine algorithm, exploiting the slow diffusion of the internal linear transformation of FIDES. Our most basic attacks have time complexities of 2^{75} and 2^{90} for FIDES-80 and FIDES-96, respectively, use a very small amount of memory, and their most distinctive feature is their very low data complexity: the attacks require at most 24 bytes of an arbitrary plaintext and its corresponding ciphertext, in order to break the cipher with probability 1. In addition to the basic attacks, we describe optimized attacks which exploit additional data in order to reduce the time complexities to 2^{73} and 2^{88} for FIDES-80 and FIDES-96, respectively.

Note: Extended version of the FSE 2014 proceedings paper.