Update on F-FCSR Stream Cipher

Abstract

The F-FCSR family of algorithms have been presented about one year ago with [2] and [1]. While some flaws where found in the initial propositions (on the IV-setup procedure, and a TMD tradeoff attack), there are yet no known weaknesses of the core of these algorithms. We sum up here some of the properties of the automaton that are better understood now, and that have been presented in [2], [3], [4], and [6] and we propose two revised algorithms correcting all known weaknesses. 1 Recalls on F-FCSR 1.1 FCSR automaton Detailed descriptions can be found in [3, 1, 2]. A Feedback with Carry Shift Register (FCSR) is an automaton which computes the binary expansion of a 2-adic number p/q, where p and q are some integers, with q is odd. We will assume that q < 0 < p < |q|. The size n of the FCSR is such that n + 1 is the bitlength of |q|. In our applications, p depends on the secret key (and the IV), and q is a public parameter. The choice of q induces many properties of the keystream. The most important one is that it completely determines the length of the period of the keystream. The conditions for an optimal choice are: Conditions 1 • q is a (negative) prime of bitsize n + 1. • The order of 2 modulo q is |q| − 1. • T = (|q| − 1)/2 is also prime. • Set d = (1 + |q|)/2. The Hamming weight W (d) of the binary expansion of d is not too small. Typically, W (d)> n/2. 1.1.1 Software description of the transition function The FCSR automaton contains two registers (sets of cells): the main register M and the carries register C. The main register M contains n cells. We denote mi (0 ≤ i ≤ n − 1) the binary digits contained in these cells and we call the integer m = ∑n−1 i=0 mi2 i the content (or state) of M.