Qichun Wang and Thomas Johansson
Higher Order Algebraic Attacks on Stream Ciphers
Plagiarism or ignorance of (very ample) literature on this topic???
The authors write:
"In this paper we introduce a new type of algebraic attacks, called higher order algebraic
attacks, with applications towards cryptanalysis of stream ciphers."
The authors claim that their attack is new while it is entirely old.
There is no new attack in this paper and it is just applying already known attacks to some new special cases.
There are tens of papers which already explain and use countless variants of this type of attack.
In Section 4 we read:
"If we add the 1st equation and the ith equation..."
"Remark 1: The classical algebraic attack is the special case r =1"
No, the case with several shifted versions of one single Boolean function was already covered as early in 2003.
What the authors call here a "new attack" is actually described in Section 7.1. page 15 of
the extended version of the Courtois-Meier original paper from 2003
under the name of scenario S5 in
S5 and variants are also covered in countless other papers.
I recommend also to read these slides from 2002-2007 which contain many important remarks not found in papers:
A very general formulation of an algebraic attack on a stream cipher appears also here:
Nicolas Courtois: General Principles of Algebraic Attacks and New Design Criteria for Components of Symmetric Ciphers, Invited talk, AES 4 Conference, LNCS 3373, Springer.
Nicolas Courtois: Algebraic Attacks on Combiners with Memory and Several Outputs, In ICISC 2004, LNCS, Springer. The extended and recently updated version of this paper is available at eprint.iacr.org/2003/125/.
however in these definitions the states of the cipher used are assume to be consecutive
(mostly because it used used to prove many worst-case attacks whcih are proven to exist always for components of certain size).
The fact that the outputs used do NOT have to be consecutive or regularly spaced is widely known since the initial Eurocrypt 2003 attack on LILI-128.
S5 is also actually a basis of all the "fast" algebraic attacks on stream ciphers [Crypto 2003],
so it is really very strange to claim that this type of attack has any novelty while the authors
amply cite work on fast algebraic attacks and on Ronjom-Helleseth attack
which is also a special case of a fast algebraic attack from Crypto 2004 and thus also a sub-class of S5 attacks
with a specific kind of final step.
"To measure the resistance against algebraic attacks, the notion of algebraic immunity
has been proposed by Courtois and Meier:
for a given Boolean function f, any Boolean function g =0
such that f*g =0 or (f +1)*g =0 should have high algebraic degree."
Indeed but the exact name of "algebraic immunity" was only used 1 year later
at Eurocrypt 2004: C.Carlet, W. Meier, E. Pasalic "Algebraic attacks and decomposition of Boolean functions",
Again the authors show that they do NOT know the (very ample) literature on this topic.
Remark: even the annihiliators are already there
see sub-scenario S3_0 and S3_1 in Table 5 on page 19 in [www.nicolascourtois.me.uk
which sets cover exactly the sets of annihilators for f and f+1
BUT again the exact name of annihilator was only used 1 year later at Eurocrypt 2004 C.Carlet, W. Meier, E. Pasalic
see slide 133 in [www.nicolascourtois.com