Fast algebraic attacks

What are Fast Algebraic Attacks?

Stream Ciphers are a special class of encryption primitives, and filter generators are a special class of stream ciphers. In a filter generator, the state is updated with a linear feedback shift register, and the state is filtered with a nonlinear Boolean function f to produce a keystrem bit. In fast algebraic attacks (FAA) on filter generators, the adversary knows the Boolean function f and the goal is to find two other functions g and h with f⋅g = h in GF(2), such that g and h both have low degrees. Such a relation can be used to recover the internal state in a known-plaintext attack.


Download the console application „FAAconsole.exe“ and create an input file „input.txt“, which must be located in the same folder. The input file must be filled with the truth table of f (where 2n elements 0 or 1 are required for a function with n input variables). Starting the application, the user can choose three parameters: n are the number of input variables to the Boolean function f, e is an upper bound for the degree of g, and d is an upper bound for the degree of h. The algorithm searches for solutions g and h bounded by the degrees e and d, the result is stored in the file „output.txt“. If you have the .NET framework installed, you may also use a windows form application (available on request).


This program uses the algorithm presented in the paper by Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon K&uumlnzli, Willi Meier, Olivier Ruatta, Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks, in Eurocrypt 2006. The computation of the solutions is deterministic, words are represented in 32 bits (i.e. n is limited by 32). Matrices in GF(2) are solved with Victor Shoup’s library NTL.

Something more about Boolean functions

Consider a Boolean function f with n input variables x = (x1,x2,x3,…,xn) in GF(2), i.e. each variable xi can take the value 0 or 1. The input x can also be represented by its integer value x = Σi xi⋅2i-1.This function can be represented by its truth table (TT) according to TT(f) = [f(0),f(1),f(2),…,f(2n-1)]. Another representation of a Boolean function is the algebraic normal form (ANF) according to f(x) = Σ fα⋅xα, where α = (α012,…,αn-1) is a multi-index (which can also be represented by its integer value), and a monomial xα is defined by x1α1⋅x2α2⋅x3α3⋅…⋅xnαn. The coefficients fα are elements in GF(2), indicating if f contains the monomial xα (notice that xi⋅xi = xi and xi+xi = 0 in GF(2)). The ANF can be represented by the coefficient table CT = [f0,f1,f1,f2,…,fn-1]. The algebraic degree of f is defined by max{|α|; fα=1}. The coefficient table and the truth table are transormed to each other by the Walsh-Hadamard transformation.


Let f = 1 + x3 + x1x2x3. Then TT = [1,1,1,1,0,0,0,1] and CT = [1,0,0,0,1,0,0,1]. There exists exactly one function g of degree 1 such that h has also degree 1, namely g = 1 + x3 and h = 1 + x3.


To be updated…