Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials

When designing filter functions in Linear Feedback Shift Registers (LFSR) based stream ciphers, algebraic criteria of Boolean functions such as the Algebraic Immunity (AI) become key characteristics because they guarantee the security of ciphers against the powerful algebraic attacks. In this article, we abstract the algebraic attacks proposed by Courtois and Meier on filtered LFSR twenty years ago, considering how the standard algebraic attack can be generalized beyond filtered LFSR to stream ciphers that employ a Boolean filter function to an updated state. Depending on the updating process, we use different sets of annihilators than those used in the standard algebraic attack; it leads to a generalization of the concept of algebraic immunity, and in some particular cases, potentially more efficient attacks. Motivated by the filter permutator paradigm, we focus on the case where the update function is a bit-permutation, since it maintains the degree of the monomials. For example the degree of the monomials of degree up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> </mml:mrow> </mml:math> and from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:math> to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> remains invariant, which leads us to consider annihilators having only monomials of these degrees. If this number of monomials is sufficiently low, linearization is feasible, allowing the linear system to be solved and revealing the key, as in the standard algebraic attack. This particular characteristic is restricted by the standard algebraic attacks and to analyze it we introduce a new notion called Extremal Algebraic Immunity (EAI). We perform a theoretic study of the EAI criterion and explore its relation to other algebraic criteria. We prove the upper bound of the EAI of an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-variable Boolean function and further show that the EAI can be lower bounded by the AI restricted to a subset, as defined by Carlet, Méaux and Rotella at FSE 2017. We also exhibit functions with EAI guaranteed to be lower than the AI, in particular we highlight a pathological case of functions with optimal algebraic immunity and EAI only <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math>. As applications, we determine the EAI of filter functions of some existing stream ciphers and discuss how extremal algebraic attacks using EAI could apply to variations of known ciphers. The extremal algebraic attack does not give a better complexity than Courtois and Meier's result on the existing stream ciphers. However, we see this work as a study to avoid weaknesses in the construction of future stream ciphers.