article

Attacks on Block Ciphers of Low Algebraic Degree

Authors:

Thomas Jakobsen,

Lars R. KnudsenAuthors Info & Claims

Journal of Cryptology, Volume 14, Issue 3

Pages 197 - 210

https://doi.org/10.1007/s00145-001-0003-x

Published: 01 January 2001 Publication History

Abstract

In this paper an attack on block ciphers is introduced, the interpolation attack. This method is useful for attacking ciphers that use simple algebraic functions (in particular quadratic functions) as S-boxes. Also, attacks based on higher-order differentials are introduced. They are special and important cases of the interpolation attacks. The attacks are applied to several block ciphers, the six-round prototype cipher by Nyberg and Knudsen, which is provably secure against ordinary differential cryptanalysis, a modified version of the block cipher SHARK, and a block cipher suggested by Kiefer.

References

[1]

E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. Springer-Verlag, New York, 1993.

Digital Library

Google Scholar

[2]

P.M. Cohn. Algebra, Volume 1. Wiley, New York, 1982.

Google Scholar

[3]

T. Jakobsen. Cryptanalysis of block ciphers with probabilistic non-linear relations of low degree. In H. Krawczyk, editor, Advances in Cryptology: CRYPTO '98, LNCS 1462, pages 212-222. Springer-Verlag, Berlin, 1998.

Digital Library

Google Scholar

[4]

K. Kiefer. A new design concept for building secure block ciphers. In J. Pribyl, editor, Proceedings of the 1st International Conference on the Theory and Applications of Cryptology, PRAGOCRYPT '96, Prague, Czech Republic, pages 30-41. CTU, Prague, 1996.

Google Scholar

[5]

L.R. Knudsen. Block Ciphers - Analysis, Design and Applications. Ph.D. thesis, Aarhus University, Denmark, 1994.

Google Scholar

[6]

L.R. Knudsen. Truncated and higher order differentials. In B. Preneel, editor, Fast Software Encryption - Second International Workshop, Leuven, Belgium, LNCS 1008, pages 196-211. Springer-Verlag, Berlin, 1995.

Crossref

Google Scholar

[7]

X. Lai. Higher order derivatives and differential cryptanalysis. In R. Blahut, editor, Communication and Cryptography, Two Sides of One Tapestry. Kluwer, Dordrecht, 1994. ISBN 0-7923-9469-0.

Google Scholar

[8]

M. Matsui. Linear cryptanalysis method for DES cipher. In T. Helleseth, editor, Advances in Cryptology - EUROCRYPT '93, LNCS 765, pages 386-397. Springer-Verlag, Berlin, 1993.

Digital Library

Google Scholar

[9]

K. Nyberg. Linear approximations of block ciphers. In A. De Santis, editor, Advances in Cryptology - EUROCRYPT '94, LNCS 950, pages 439-444. Springer-Verlag, Berlin, 1995.

Google Scholar

[10]

K. Nyberg and L.R. Knudsen. Provable security against a differential attack. Journal of Cryptology, 8(1):27-38, 1995.

Digital Library

Google Scholar

[11]

V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers, and E. De Win. The cipher SHARK. In D. Gollmann, editor, Fast Software Encryption, Third International Workshop, Cambridge, UK, February 1996, LNCS 1039, pages 99-112. Springer-Verlag, Berlin, 1996.

Digital Library

Google Scholar

[12]

T. Shimoyama, S. Moriai, and T. Kaneko. Improving the higher order differential attack and cryptanalysis of the KN cipher. Presented at Information Security Workshop '97, ISW 97, Kanazawa, Sept. 1997.

Digital Library

Google Scholar

Cited By

View all

Vahi AJafarali Jassbi S(2020)SEPAR: A New Lightweight Hybrid Encryption Algorithm with a Novel Design Approach for IoTWireless Personal Communications: An International Journal10.1007/s11277-020-07476-y114:3(2283-2314)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s11277-020-07476-y
Li CPreneel B(2019)Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic DegreeSelected Areas in Cryptography – SAC 201910.1007/978-3-030-38471-5_8(171-193)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-38471-5_8
Miles EViola E(2015)Substitution-Permutation Networks, Pseudorandom Functions, and Natural ProofsJournal of the ACM10.1145/279297862:6(1-29)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2792978
Show More Cited By

Attacks on Block Ciphers of Low Algebraic Degree

Recommendations

New Cryptanalysis of Block Ciphers with Low Algebraic Degree
Fast Software Encryption

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 ...
Improved meet-in-the-middle attacks on reduced-round tweakable block ciphers Kiasu-BC and Deoxys-BC
Abstract
Tweakable block ciphers Kiasu-BC and Deoxys-BC are both the internal block ciphers of the candidates for the CAESAR authenticated encryption competition. The cryptanalysis of Kiasu-BC and Deoxys-BC is helpful to promote the cryptanalysis process ...
Biclique cryptanalysis on lightweight block cipher: HIGHT and Piccolo
Advanced Computer Mathematics based Cryptography and Security Technologies

Biclique cryptanalysis is an attack that improves the computational complexity by finding a biclique which is a kind of bipartite graph. We present a single-key full-round attack of lightweight block ciphers, HIGHT and Piccolo by using biclique ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Cryptology Volume 14, Issue 3

January 2001

70 pages

ISSN:0933-2790

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vahi AJafarali Jassbi S(2020)SEPAR: A New Lightweight Hybrid Encryption Algorithm with a Novel Design Approach for IoTWireless Personal Communications: An International Journal10.1007/s11277-020-07476-y114:3(2283-2314)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s11277-020-07476-y
Li CPreneel B(2019)Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic DegreeSelected Areas in Cryptography – SAC 201910.1007/978-3-030-38471-5_8(171-193)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-38471-5_8
Miles EViola E(2015)Substitution-Permutation Networks, Pseudorandom Functions, and Natural ProofsJournal of the ACM10.1145/279297862:6(1-29)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2792978
Yap HKhoo KPoschmann A(2013)Parallelisable variants of Camellia and SMS4 block cipherInternational Journal of Applied Cryptography10.1504/IJACT.2013.0534323:1(1-20)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1504/IJACT.2013.053432
Mekhaznia TElçi AGaur MOrgun MMakarevich O(2013)Nature inspired heuristics for attack of simplified DES algorithmProceedings of the 6th International Conference on Security of Information and Networks10.1145/2523514.2527010(311-315)Online publication date: 26-Nov-2013
https://dl.acm.org/doi/10.1145/2523514.2527010
Miles EViola E(2012)Substitution-Permutation Networks, Pseudorandom Functions, and Natural ProofsProceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 741710.1007/978-3-642-32009-5_5(68-85)Online publication date: 19-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-32009-5_5
Choy JChew GKhoo KYap H(2011)Cryptographic properties and application of a Generalized Unbalanced Feistel Network structureCryptography and Communications10.1007/s12095-011-0042-63:3(141-164)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1007/s12095-011-0042-6
Pasalic E(2009)Probabilistic versus deterministic algebraic cryptanalysisIEEE Transactions on Information Theory10.1109/TIT.2009.203048955:11(5233-5240)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1109/TIT.2009.2030489
Jackson WMurphy S(2007)Projective aspects of the AES inversionDesigns, Codes and Cryptography10.1007/s10623-007-9059-443:2-3(167-179)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1007/s10623-007-9059-4
Courtois NGoubin L(2005)An algebraic masking method to protect AES against power attacksProceedings of the 8th international conference on Information Security and Cryptology10.1007/11734727_18(199-209)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.1007/11734727_18
Show More Cited By

Abstract

References

Cited By

Recommendations

New Cryptanalysis of Block Ciphers with Low Algebraic Degree

Improved meet-in-the-middle attacks on reduced-round tweakable block ciphers Kiasu-BC and Deoxys-BC

Biclique cryptanalysis on lightweight block cipher: HIGHT and Piccolo

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations