Interpolation attack

In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers.

In the attack, an algebraic function is used to represent an S-box. This may be a simple quadratic, or a polynomial or rational function over a Galois field. Its coefficients can be determined by standard Lagrange interpolation techniques, using known plaintexts as data points. Alternatively, chosen plaintexts can be used to simplify the equations and optimize the attack.

Thomas Jakobsen introduced a probabilistic version of the interpolation attack using Madhu Sudan's algorithm for improved decoding of Reed-Solomon codes. This attack can work even when an algebraic relationship between plaintexts and ciphertexts holds for only a fraction of values.

References

* cite conference
author = Thomas Jakobsen, Lars Knudsen
title = The Interpolation Attack on Block Ciphers
booktitle = 4th International Workshop on Fast Software Encryption (FSE '97), LNCS 1267
pages = pp.28–40
publisher = Springer-Verlag
month = January | year = 1997
location = Haifa
url = http://citeseer.ist.psu.edu/jakobsen97interpolation.html
format = PDF/PostScript
accessdate = 2007-07-03
* cite conference
author = Thomas Jakobsen
title = Cryptanalysis of Block Ciphers with Probabilistic Non-linear Relations of Low Degree
booktitle = Advances in Cryptology — CRYPTO '98
pages = pp.212–222
publisher = Springer-Verlag
date = August 25 1998
location = Santa Barbara, California
url = http://citeseer.ist.psu.edu/jakobsen98cryptanalysis.html
format = PDF/PostScript
accessdate = 2007-07-06 ( [http://video.google.com/videoplay?docid=-502705185794473481&hl=en Video of presentation] at Google Video—uses Flash)
* cite conference
author = Shiho Moriai, Takeshi Shimoyama, Toshinobu Kaneko
title = Interpolation Attacks of the Block Cipher: SNAKE
booktitle = FSE '99
pages = pp.275–289
publisher = Springer-Verlag
month = March | year = 1999
location = Rome
url = http://www.mathmagic.cn/Crypt1998-2003/bibs/1636/16360275.htm
format = PDF
accessdate = 2007-09-16
* cite conference
author = Amr M. Youssef, Guang Gong
title = On the Interpolation Attacks on Block Ciphers
booktitle = FSE 2000
pages = pp.109–120
publisher = Springer-Verlag
month = April | year = 2000
location = New York City
url = http://users.encs.concordia.ca/~youssef/fse2000.pdf
format = PDF
accessdate = 2007-07-06
* cite conference
author = Kaoru Kurosawa, Tetsu Iwata, Viet Duong Quang
title = Root Finding Interpolation Attack
booktitle = Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography (SAC 2000)
pages = pp.303–314
publisher = Springer-Verlag
month = August | year = 2000
location = Waterloo, Ontario
url = http://citeseer.ist.psu.edu/kurosawa00root.html
format = PDF/PostScript
accessdate = 2007-07-06