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.