Pierre-Louis Cayrel (Université de Limoges)

will speak on

Algebraic attacks against stream ciphers

Time: 4:00PM
Date: Mon 3rd March 2008
Location: Mathematical Sciences Seminar Room [map]

Further information

Abstract: Algebraic attacks have been established as an important tool for cryptanalyzing LFSR-based keystream generators. All stream ciphers with linear feedback (one or several LFSR, linear cellular automata etc..) are concerned. Crucial for an efficient attack is to find appropriate equations of a degree as low as possible. Hereby, lower degrees are possible if many keystream bits are involved in one equation. It is known that valid equations correspond to annihilators of certain sets. The effort to compute the sets and to find annihilators on them are exponential in $r$ (consecutive outputs), making efficient algorithms desirable.

Firs we present filtered and combined LFSRs and second we deal with algebraic attacks. Next, we describe several improvements for computing the equations of degree 3 for $r={5,6,7}$ in the case of the keystream generator $E_0$ employed in Bluetooth, where equations of degree 4 exist for $r={4,5}$ and one equation of degree 3 for $rapprox 8,822,188$.

(This talk is part of the Algebra and Number Theory series.)

PDF notice

Return to all seminars