New Cryptanalysis of Block Ciphers with Low Algebraic Degree

Improved interpolation attack and new integral attack are proposed in this paper, and they can be applied to block ciphers using round functions with low algebraic degree. In the new attacks, we can determine not only the degree of the polynomial, but also coefficients of some special terms. Thus instead of guessing the round keys one by one, we can get the round keys by solving some algebraic equations over finite field. The new methods are applied to

$\mathcal{PURE}$

block cipher successfully. The improved interpolation attacks can recover the first round key of 8-round

$\mathcal{PURE}$

in less than a second;

r

-round

$\mathcal{PURE}$

with

r

 ≤ 21 is breakable with about 3

r

 − 2

chosen plaintexts and the time complexity is 3

r

 − 2

encryptions; 22-round

$\mathcal{PURE}$

is breakable with both data and time complexities being about 3×3

20

. The new integral attacks can break

$\mathcal{PURE}$

with rounds up to 21 with 2

32

encryptions and 22-round with 3×2

32

encryptions. This means that

$\mathcal{PURE}$

with up to 22 rounds is breakable on a personal computer.