Algebraic Attacks on Stream Ciphers with Linear Feedback

Algebraic Attacks on Stream Ciphers with Linear Feedback

2003 | Nicolas T. Courtois and Willi Meier
This paper presents a new algebraic attack on stream ciphers with linear feedback, which significantly reduces the complexity of breaking certain stream ciphers. The attack is based on solving a system of multivariate equations derived from the cipher's structure. The key idea is to multiply the original equations by well-chosen multivariate polynomials to lower their degree, making them easier to solve. This approach allows for more efficient attacks compared to previous methods. The authors demonstrate their method on two stream ciphers: Toyocrypt and LILI-128. For Toyocrypt, the new attack reduces the complexity from $ 2^{92} $ to $ 2^{49} $ CPU clocks, requiring only 20 Kbytes of keystream. For LILI-128, the attack complexity is $ 2^{57} $ CPU clocks, though it is not the fastest known attack. The attack works by exploiting the fact that the Boolean function used in the cipher may use only a small subset of state bits, making the cipher vulnerable to algebraic attacks regardless of the specific function used. The paper also shows that if a stream cipher uses only a small subset of state bits, it can be broken, even if it meets all previously known design criteria. The new algebraic attack can break such ciphers in a time complexity that is at most the square root of the complexity of the previously known generic attack. The authors propose a general design criterion for stream ciphers: the non-existence of multivariate relations of low degree relating the key bits and the output bits. This criterion is shown to be equivalent to the security criteria defined in previous works for multivariate trapdoor functions and S-boxes in block ciphers. The paper concludes that stream ciphers should use many state bits and avoid sparse functions to resist algebraic attacks. The new attack method is effective against a wide range of stream ciphers, particularly those that use a small subset of state bits or have sparse Boolean functions. The results highlight the importance of designing stream ciphers with strong algebraic properties to resist such attacks.This paper presents a new algebraic attack on stream ciphers with linear feedback, which significantly reduces the complexity of breaking certain stream ciphers. The attack is based on solving a system of multivariate equations derived from the cipher's structure. The key idea is to multiply the original equations by well-chosen multivariate polynomials to lower their degree, making them easier to solve. This approach allows for more efficient attacks compared to previous methods. The authors demonstrate their method on two stream ciphers: Toyocrypt and LILI-128. For Toyocrypt, the new attack reduces the complexity from $ 2^{92} $ to $ 2^{49} $ CPU clocks, requiring only 20 Kbytes of keystream. For LILI-128, the attack complexity is $ 2^{57} $ CPU clocks, though it is not the fastest known attack. The attack works by exploiting the fact that the Boolean function used in the cipher may use only a small subset of state bits, making the cipher vulnerable to algebraic attacks regardless of the specific function used. The paper also shows that if a stream cipher uses only a small subset of state bits, it can be broken, even if it meets all previously known design criteria. The new algebraic attack can break such ciphers in a time complexity that is at most the square root of the complexity of the previously known generic attack. The authors propose a general design criterion for stream ciphers: the non-existence of multivariate relations of low degree relating the key bits and the output bits. This criterion is shown to be equivalent to the security criteria defined in previous works for multivariate trapdoor functions and S-boxes in block ciphers. The paper concludes that stream ciphers should use many state bits and avoid sparse functions to resist algebraic attacks. The new attack method is effective against a wide range of stream ciphers, particularly those that use a small subset of state bits or have sparse Boolean functions. The results highlight the importance of designing stream ciphers with strong algebraic properties to resist such attacks.
Reach us at info@study.space
[slides] Algebraic Attacks on Stream Ciphers with Linear Feedback | StudySpace