It is well known that polynomial system solving algorithms (in particular Gröbner basis algorithm) are more efficient if the polynomial system is overdefined. Thus, a standard approach when trying to cryptanalyse block ciphers using algebraic techniques is to make the system more overdefined. One approach is to use differential characteristics; another one is to use higher-order differential cryptanalysis methods to produce a system where many state variables can be identified.
In order to speed up the computations in practice it is often beneficial to remove “redundant” variables, for instance one can remove and replace it by if the polynomial is in the system. This is, in fact, what is done by the Sage function
However, this only works well if the variable which ought to be replaced is actually the leading term of a polynomial. If we consider for example algebraic higher-order differential techniques we have quite a few polynomials of the form for each of the plaintext-ciphertext pairs (those encode the first key addition). Those allow us to replace by but not to identify and .
Now, note that, e.g.,
(where are constants) which is exactly of the form needed by the simplification rules applied by the eliminate_linear_variables() function.
Thus, it might be beneficial to not consider a polynomial system of multiple plaintext-ciphertext pairs but instead to consider a system for and for .
To apply this trick to my algebraic integral attackpolynomial system generator for PRESENT, replace the code:
for j in range(min_round,len(rounds)): L.append(rounds[j].gens())
for j in range(min_round,len(rounds)): if i == 0: L.append(rounds[j].gens()) else: L.append(map(add,zip(L[j],rounds[j])))
Using the straightforward modelling for five rounds of PRESENT we end up with an equation system with 30423 polynomials in 2410 variables. PolyBoRi takes 1370.19 seconds on my Macbook Pro 6,2.
Using the little trick we end up with an equation system with 19704 polynomials in 1802 variables which PolyBoRi solves in 458.89 seconds on my machine. In both cases the same key and plaintexts were used.
Here’s the testcode:
set_random_seed(0) F,s = present_ia(PRESENT(80,5)) t = cputime() F = F.eliminate_linear_variables() gb = F.groebner_basis(prot=True) print "%s; CPU Time: %7.2f"%(F, cputime(t))