Cryptanalysis of block ciphers with overdefined systems of equations

Nicolas T. Courtois, Josef Pieprzyk

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

Abstract

Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in Nr, with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.

LanguageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2002
Subtitle of host publication8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings
Place of PublicationBerlin, Germany
PublisherSpringer, Springer Nature
Pages267-287
Number of pages21
Volume2501
ISBN (Electronic)9783540361787
ISBN (Print)3540001719, 9783540001713
DOIs
Publication statusPublished - 2002
Event8th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2002 - Queenstown, New Zealand
Duration: 1 Dec 20025 Dec 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2501
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other8th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2002
CountryNew Zealand
CityQueenstown
Period1/12/025/12/02

Fingerprint

S-box
Block Ciphers
Cryptanalysis
System of equations
Rijndael
Attack
Polynomials
Linear Cryptanalysis
Differential Cryptanalysis
Exhaustive Search
Polynomial equation
Sparsity
Algebraic Equation
Polynomial
Dependent

Cite this

Courtois, N. T., & Pieprzyk, J. (2002). Cryptanalysis of block ciphers with overdefined systems of equations. In Advances in Cryptology - ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings (Vol. 2501, pp. 267-287). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2501). Berlin, Germany: Springer, Springer Nature. https://doi.org/10.1007/3-540-36178-2_17
Courtois, Nicolas T. ; Pieprzyk, Josef. / Cryptanalysis of block ciphers with overdefined systems of equations. Advances in Cryptology - ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings. Vol. 2501 Berlin, Germany : Springer, Springer Nature, 2002. pp. 267-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{2dcf32b566e542ccbc9435b9f95d3829,
title = "Cryptanalysis of block ciphers with overdefined systems of equations",
abstract = "Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in Nr, with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.",
keywords = "AES, Block ciphers, Camellia, Gr¨obner bases, MQ problem, Multivariate cryptanalysis, Multivariate quadratic equations, Overdefined systems of multivariate equations, Rijndael, Serpent, Sparse multivariate polynomials, Square, XL algorithm",
author = "Courtois, {Nicolas T.} and Josef Pieprzyk",
year = "2002",
doi = "10.1007/3-540-36178-2_17",
language = "English",
isbn = "3540001719",
volume = "2501",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer, Springer Nature",
pages = "267--287",
booktitle = "Advances in Cryptology - ASIACRYPT 2002",
address = "United States",

}

Courtois, NT & Pieprzyk, J 2002, Cryptanalysis of block ciphers with overdefined systems of equations. in Advances in Cryptology - ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings. vol. 2501, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2501, Springer, Springer Nature, Berlin, Germany, pp. 267-287, 8th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2002, Queenstown, New Zealand, 1/12/02. https://doi.org/10.1007/3-540-36178-2_17

Cryptanalysis of block ciphers with overdefined systems of equations. / Courtois, Nicolas T.; Pieprzyk, Josef.

Advances in Cryptology - ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings. Vol. 2501 Berlin, Germany : Springer, Springer Nature, 2002. p. 267-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2501).

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

TY - GEN

T1 - Cryptanalysis of block ciphers with overdefined systems of equations

AU - Courtois,Nicolas T.

AU - Pieprzyk,Josef

PY - 2002

Y1 - 2002

N2 - Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in Nr, with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.

AB - Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in Nr, with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.

KW - AES

KW - Block ciphers

KW - Camellia

KW - Gr¨obner bases

KW - MQ problem

KW - Multivariate cryptanalysis

KW - Multivariate quadratic equations

KW - Overdefined systems of multivariate equations

KW - Rijndael

KW - Serpent

KW - Sparse multivariate polynomials

KW - Square

KW - XL algorithm

UR - http://www.scopus.com/inward/record.url?scp=84958765510&partnerID=8YFLogxK

U2 - 10.1007/3-540-36178-2_17

DO - 10.1007/3-540-36178-2_17

M3 - Conference proceeding contribution

SN - 3540001719

SN - 9783540001713

VL - 2501

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 267

EP - 287

BT - Advances in Cryptology - ASIACRYPT 2002

PB - Springer, Springer Nature

CY - Berlin, Germany

ER -

Courtois NT, Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. In Advances in Cryptology - ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings. Vol. 2501. Berlin, Germany: Springer, Springer Nature. 2002. p. 267-287. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-36178-2_17