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.

Interface

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).

Algorithm

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.