Attacks on block ciphers of low algebraic degree

In this paper an attack on block ciphers is introduced, the interpolation a ttack. This method is useful for attacking ciphers that use simple algebrai c functions tin particular quadratic functions) as S-boxes. Also, attacks b ased on higher-order differentials are introduced. They are special and imp ortant cases of the interpolation attacks. The attacks are applied to sever al block ciphers, the six-round prototype cipher by Nyberg and Knudsen, whi ch is provably secure against ordinary differential cryptanalysis, a modifi ed version of the block cipher SHARK, and a block cipher suggested by Kiefe r.