Interpolation attack

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Timing Attack — Attaque temporelle En cryptanalyse, une attaque temporelle consiste à estimer et analyser le temps mis pour effectuer certaines opérations cryptographiques dans le but de découvrir des informations secrètes. Certaines opérations peuvent prendre… …   Wikipédia en Français

  • Camellia (алгоритм) — У этого термина существуют и другие значения, см. Camellia (значения). Camellia Создатель: Mitsubishi, NTT Создан: 2000 г. Опубликован: 2000 г. Размер ключа: 128, 192 или 256 бит Размер блока: 128 бит Число раундов …   Википедия

  • SHARK — Infobox block cipher name = SHARK designers = Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win publish date = 1996 derived from = derived to = KHAZAD, Rijndael related to = key size = 128 bits block size = 64 bits… …   Wikipedia

  • SHARK — Pour les articles homonymes, voir Shark. En cryptographie, SHARK est un algorithme de chiffrement par bloc utilisant des clés de 128 bits[1]. C’est un des prédécesseurs de Rijndael (l’algorithme de chiffrement symétrique employé par le… …   Wikipédia en Français

  • KN-Cipher — Infobox block cipher name = KN Cipher designers = Kaisa Nyberg and Lars Knudsen publish date = 1995 derived from = derived to = related to = certification = key size = 198 bits block size = 64 bits structure = Feistel network rounds = 6… …   Wikipedia

  • Bent function — The 2 ary bent functions with Hamming weight 1 Their nonlinearity is …   Wikipedia

  • Sampling (music) — This article is about reusing existing sound recordings in creating new works. For other uses, see Sample (disambiguation). In music, sampling is the act of taking a portion, or sample, of one sound recording and reusing it as an instrument or a… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • biblical literature — Introduction       four bodies of written works: the Old Testament writings according to the Hebrew canon; intertestamental works, including the Old Testament Apocrypha; the New Testament writings; and the New Testament Apocrypha.       The Old… …   Universalium

  • Siouxsie & The Banshees — Siouxsie and the Banshees Siouxsie Sioux 1980 in Edinburgh Gründung 1976 Auflösung 1996 2002 nach einmaligem Comeback Genre Punk (1976 1978) Post Punk/ …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”