Cryptanalysis of Block Ciphers with Overdefined Systems of Equations View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-11-08

AUTHORS

Nicolas T. Courtois , Josef Pieprzyk

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 Nrr.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. More... »

PAGES

267-287

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-36178-2_17

DOI

http://dx.doi.org/10.1007/3-540-36178-2_17

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1046297994


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "CP8 Crypto Lab, SchlumbergerSema, 36-38, rue de la Princesse, BP 45, 78430, Louveciennes Cedex, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "CP8 Crypto Lab, SchlumbergerSema, 36-38, rue de la Princesse, BP 45, 78430, Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Courtois", 
        "givenName": "Nicolas T.", 
        "id": "sg:person.013151403707.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Center for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1004.5", 
          "name": [
            "Center for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pieprzyk", 
        "givenName": "Josef", 
        "id": "sg:person.014746733025.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014746733025.45"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-11-08", 
    "datePublishedReg": "2002-11-08", 
    "description": "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 Nrr.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\u201900, 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.", 
    "editor": [
      {
        "familyName": "Zheng", 
        "givenName": "Yuliang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-36178-2_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00171-3", 
        "978-3-540-36178-7"
      ], 
      "name": "Advances in Cryptology \u2014 ASIACRYPT 2002", 
      "type": "Book"
    }, 
    "keywords": [
      "overdefined system", 
      "XSL attack", 
      "algebraic equations", 
      "huge constants", 
      "redundant equations", 
      "polynomial equation", 
      "probabilistic characteristics", 
      "probability 1", 
      "equations", 
      "classical methods", 
      "additional hypotheses", 
      "parameter p", 
      "number of rounds", 
      "exact complexity", 
      "exhaustive search", 
      "general method", 
      "new criterion", 
      "new method", 
      "specific structure", 
      "such ciphers", 
      "sparsity", 
      "system", 
      "estimation", 
      "cryptanalysis", 
      "complexity", 
      "block cipher", 
      "number", 
      "version", 
      "such attacks", 
      "cipher", 
      "XSL", 
      "design", 
      "Serpent", 
      "Rijndael", 
      "box", 
      "criteria", 
      "search", 
      "fact", 
      "security", 
      "structure", 
      "inefficiency", 
      "XL", 
      "attacks", 
      "constants", 
      "relation", 
      "size", 
      "characteristics", 
      "rounds", 
      "layer", 
      "hypothesis", 
      "NR", 
      "method", 
      "NRR", 
      "paper", 
      "example Rijndael", 
      "linear key-dependent layers", 
      "key-dependent layers", 
      "rounds Nrr", 
      "Eurocrypt\u201900"
    ], 
    "name": "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations", 
    "pagination": "267-287", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046297994"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-36178-2_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-36178-2_17", 
      "https://app.dimensions.ai/details/publication/pub.1046297994"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_210.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-36178-2_17"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-36178-2_17'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-36178-2_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36178-2_17'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36178-2_17'


 

This table displays all metadata directly associated to this object as RDF triples.

129 TRIPLES      23 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-36178-2_17 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N58dcf19c2bc147dfbad7f4a5be130686
4 schema:datePublished 2002-11-08
5 schema:datePublishedReg 2002-11-08
6 schema:description 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 Nrr.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.
7 schema:editor Nac725d46736c44c79b608178e1a8b622
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfd40b32aaede4b7cb6ec00fa7da85acd
12 schema:keywords Eurocrypt’00
13 NR
14 NRR
15 Rijndael
16 Serpent
17 XL
18 XSL
19 XSL attack
20 additional hypotheses
21 algebraic equations
22 attacks
23 block cipher
24 box
25 characteristics
26 cipher
27 classical methods
28 complexity
29 constants
30 criteria
31 cryptanalysis
32 design
33 equations
34 estimation
35 exact complexity
36 example Rijndael
37 exhaustive search
38 fact
39 general method
40 huge constants
41 hypothesis
42 inefficiency
43 key-dependent layers
44 layer
45 linear key-dependent layers
46 method
47 new criterion
48 new method
49 number
50 number of rounds
51 overdefined system
52 paper
53 parameter p
54 polynomial equation
55 probabilistic characteristics
56 probability 1
57 redundant equations
58 relation
59 rounds
60 rounds Nrr
61 search
62 security
63 size
64 sparsity
65 specific structure
66 structure
67 such attacks
68 such ciphers
69 system
70 version
71 schema:name Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
72 schema:pagination 267-287
73 schema:productId N72f18a79a4934ed18c6129206d68ec94
74 Nd4f5392d0e31474fad7d44853b745db1
75 schema:publisher Ne4e044841dc84eb9bfe17d887a735d13
76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046297994
77 https://doi.org/10.1007/3-540-36178-2_17
78 schema:sdDatePublished 2021-11-01T18:50
79 schema:sdLicense https://scigraph.springernature.com/explorer/license/
80 schema:sdPublisher N1ae9301f18e84cbabea3aa1f57a0c43c
81 schema:url https://doi.org/10.1007/3-540-36178-2_17
82 sgo:license sg:explorer/license/
83 sgo:sdDataset chapters
84 rdf:type schema:Chapter
85 N1ae9301f18e84cbabea3aa1f57a0c43c schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 N218652782b4542f3ad38e85ecf7a8c8c rdf:first sg:person.014746733025.45
88 rdf:rest rdf:nil
89 N58dcf19c2bc147dfbad7f4a5be130686 rdf:first sg:person.013151403707.45
90 rdf:rest N218652782b4542f3ad38e85ecf7a8c8c
91 N5b88a8e0838b4b60842bc998da8bd42f schema:familyName Zheng
92 schema:givenName Yuliang
93 rdf:type schema:Person
94 N72f18a79a4934ed18c6129206d68ec94 schema:name doi
95 schema:value 10.1007/3-540-36178-2_17
96 rdf:type schema:PropertyValue
97 Nac725d46736c44c79b608178e1a8b622 rdf:first N5b88a8e0838b4b60842bc998da8bd42f
98 rdf:rest rdf:nil
99 Nd4f5392d0e31474fad7d44853b745db1 schema:name dimensions_id
100 schema:value pub.1046297994
101 rdf:type schema:PropertyValue
102 Ne4e044841dc84eb9bfe17d887a735d13 schema:name Springer Nature
103 rdf:type schema:Organisation
104 Nfd40b32aaede4b7cb6ec00fa7da85acd schema:isbn 978-3-540-00171-3
105 978-3-540-36178-7
106 schema:name Advances in Cryptology — ASIACRYPT 2002
107 rdf:type schema:Book
108 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
109 schema:name Mathematical Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
112 schema:name Pure Mathematics
113 rdf:type schema:DefinedTerm
114 sg:person.013151403707.45 schema:affiliation grid-institutes:None
115 schema:familyName Courtois
116 schema:givenName Nicolas T.
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45
118 rdf:type schema:Person
119 sg:person.014746733025.45 schema:affiliation grid-institutes:grid.1004.5
120 schema:familyName Pieprzyk
121 schema:givenName Josef
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014746733025.45
123 rdf:type schema:Person
124 grid-institutes:None schema:alternateName CP8 Crypto Lab, SchlumbergerSema, 36-38, rue de la Princesse, BP 45, 78430, Louveciennes Cedex, France
125 schema:name CP8 Crypto Lab, SchlumbergerSema, 36-38, rue de la Princesse, BP 45, 78430, Louveciennes Cedex, France
126 rdf:type schema:Organization
127 grid-institutes:grid.1004.5 schema:alternateName Center for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia
128 schema:name Center for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia
129 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...