SYMLAB talked about algebraic attacks on constructions like block ciphers or hash functions. Algebraic attacks model the primitive in question using a set of multivariate, nonlinear equations and then use generic techniques to solve these equations. The work complexity for this method is the complexity of the algebraic attack. Algebraic attacks are far from new but were dismissed early on as a problem that designers could easily deal with - indeed the generic approach for setting up equation systems is not particularly efficient.
But in 2003 algebraic attacks were rediscovered in the form of an efficient attack on a new stream cipher.
The example in the talk considered a keystream built from a n-bit LFSR initialised to the n-bit key whose outputs are fed through a compression function with one-bit range (so the construction produces one bit per clock of the LFSR). Writing this as a set of equations with L the LFSR and F the compression function, k the key and s the stream, the derived equation system looks something like
s[0] = F(L(k))
s[1] = F(L(L(k))
s[2] = F(L(L(L(k)))
and so on, which at some point becomes overdetermined and thus solvable in k (the s values are obviously known). L is linear so F is the main stumbling block here. In particular, creating and solving the equations takes polynomial time in the length of k but exponential in the degree of F.
It looks as if one can just pick the degree of F large enough to defeat this attack. The 2003 paper looked at an example where F had high degree but a low-degree annihilator (a function G with F.G = 0) and one could perform the attack using G instead.
The speaker argued that further such tricks could make algebraic attacks feasible against other ciphers; algebraic attacks should therefore not be written off too lightly.
No comments:
Post a Comment