Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2018-07-25

AUTHORS

Qingju Wang , Yonglin Hao , Yosuke Todo , Chaoyun Li , Takanori Isobe , Willi Meier

ABSTRACT

The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range, e.g., typically 40. These limits were first overcome by the division property based cube attacks proposed by Todo et al. at CRYPTO 2017. Based on MILP modelled division property, for a cube (index set) I, they identify the small (index) subset J of the secret key bits involved in the resultant superpoly. During the precomputation phase which dominates the complexity of the cube attacks, 2|I|+|J|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{|I|+|J|}$$\end{document} encryptions are required to recover the superpoly. Therefore, their attacks can only be available when the restriction |I|+|J| More... »

PAGES

275-305

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-96884-1_10

DOI

http://dx.doi.org/10.1007/978-3-319-96884-1_10

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg", 
          "id": "http://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "Shanghai Jiao Tong University, Shanghai, China", 
            "Technical University of Denmark, Kongens Lyngby, Denmark", 
            "SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Qingju", 
        "id": "sg:person.011431743334.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "State Key Laboratory of Cryptology, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.496622.d", 
          "name": [
            "State Key Laboratory of Cryptology, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hao", 
        "givenName": "Yonglin", 
        "id": "sg:person.014270173173.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NTT Secure Platform Laboratories, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "NTT Secure Platform Laboratories, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Todo", 
        "givenName": "Yosuke", 
        "id": "sg:person.013247762751.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "imec-COSIC, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Chaoyun", 
        "id": "sg:person.012162474100.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162474100.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Hyogo, Kobe, Japan", 
          "id": "http://www.grid.ac/institutes/grid.266453.0", 
          "name": [
            "University of Hyogo, Kobe, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Isobe", 
        "givenName": "Takanori", 
        "id": "sg:person.07676572757.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676572757.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "FHNW, Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meier", 
        "givenName": "Willi", 
        "id": "sg:person.07653531142.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-07-25", 
    "datePublishedReg": "2018-07-25", 
    "description": "The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range, e.g., typically 40. These limits were first overcome by the division property based cube attacks proposed by Todo et al. at CRYPTO 2017. Based on MILP modelled division property, for a cube (index set) I, they identify the small (index) subset J of the secret key bits involved in the resultant superpoly. During the precomputation phase which dominates the complexity of the cube attacks, 2|I|+|J|\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{|I|+|J|}$$\\end{document} encryptions are required to recover the superpoly. Therefore, their attacks can only be available when the restriction |I|+|J|
 

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/978-3-319-96884-1_10'

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/978-3-319-96884-1_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-96884-1_10'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-96884-1_10'


 

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

191 TRIPLES      23 PREDICATES      99 URIs      92 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-96884-1_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N47b2bd2dec3c4b8cbd99170894998f5f
4 schema:datePublished 2018-07-25
5 schema:datePublishedReg 2018-07-25
6 schema:description The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range, e.g., typically 40. These limits were first overcome by the division property based cube attacks proposed by Todo et al. at CRYPTO 2017. Based on MILP modelled division property, for a cube (index set) I, they identify the small (index) subset J of the secret key bits involved in the resultant superpoly. During the precomputation phase which dominates the complexity of the cube attacks, 2|I|+|J|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{|I|+|J|}$$\end{document} encryptions are required to recover the superpoly. Therefore, their attacks can only be available when the restriction |I|+|J|<n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|I|+|J|<n$$\end{document} is met.In this paper, we introduced several techniques to improve the division property based cube attacks by exploiting various algebraic properties of the superpoly.We propose the “flag” technique to enhance the preciseness of MILP models so that the proper non-cube IV assignments can be identified to obtain a non-constant superpoly.A degree evaluation algorithm is presented to upper bound the degree of the superpoly. With the knowledge of its degree, the superpoly can be recovered without constructing its whole truth table. This enables us to explore larger cubes I’s even if |I|+|J|≥n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|I|+|J|\ge n$$\end{document}.We provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced.As an illustration, we apply our techniques to attack the initialization of several ciphers. To be specific, our key recovery attacks have mounted to 839-round Trivium, 891-round Kreyvium, 184-round Grain-128a and 750-round Acornrespectively.
7 schema:editor N385096dca47b414ab4e3dc044e94a097
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nae33cea27b11455fb55e929acb88d5e5
12 schema:keywords Based Cube Attacks
13 CRYPTO 2017
14 Division Property Based Cube Attacks
15 Grain-128a
16 Kreyvium
17 MILP
18 MILP model
19 Property Based Cube Attacks
20 Todo et al
21 Traditional cube attack
22 Trivium
23 adversary
24 al
25 algebraic properties
26 algorithm
27 assignment
28 attacks
29 bits
30 cipher
31 complexity
32 cryptanalysis
33 cube
34 cube attack
35 cubes I
36 degree
37 degree evaluation algorithm
38 division property
39 encryption
40 enumeration algorithm
41 et al
42 evaluation algorithm
43 experimental range
44 flags
45 illustration
46 important technique
47 initialization
48 key bits
49 key primitives
50 key recovery attack
51 knowledge
52 larger cubes I
53 limit
54 long time
55 model
56 monomials
57 non-constant superpoly
58 paper
59 phase
60 plaintext
61 preciseness
62 precomputation phase
63 primitives
64 properties
65 proposal
66 quadratic superpolies
67 range
68 recovery attack
69 restriction
70 resultant superpoly
71 secret key bits
72 set
73 size
74 small (index) subset J
75 stream cipher
76 subset J
77 superpoly
78 symmetric key primitives
79 table
80 technique
81 term enumeration algorithm
82 time
83 truth table
84 upper
85 whole truth table
86 schema:name Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly
87 schema:pagination 275-305
88 schema:productId N2e9ffa30bed043159e309a2d619791b5
89 N39937d2c5c7340b5a7d456d6f512430a
90 schema:publisher Nde225e2246c34f2e927a6af90fa780c4
91 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105813840
92 https://doi.org/10.1007/978-3-319-96884-1_10
93 schema:sdDatePublished 2022-01-01T19:27
94 schema:sdLicense https://scigraph.springernature.com/explorer/license/
95 schema:sdPublisher N65ad9f46e96c42fda54359ae752b57f9
96 schema:url https://doi.org/10.1007/978-3-319-96884-1_10
97 sgo:license sg:explorer/license/
98 sgo:sdDataset chapters
99 rdf:type schema:Chapter
100 N1de257302df1493a9bc97f880991ca1a rdf:first sg:person.012162474100.06
101 rdf:rest Nd095e3f65cfc43eb9bc186f27f8c5968
102 N21aa81dc04564dbb82261fae96bdaf44 rdf:first sg:person.014270173173.47
103 rdf:rest Na575825b817b46bcab7e18a65f7bf454
104 N2e9ffa30bed043159e309a2d619791b5 schema:name dimensions_id
105 schema:value pub.1105813840
106 rdf:type schema:PropertyValue
107 N385096dca47b414ab4e3dc044e94a097 rdf:first Nd111f651afe041d5870ca285ca49f83d
108 rdf:rest N78d79860db2e45f28fdbb07c916e5572
109 N39937d2c5c7340b5a7d456d6f512430a schema:name doi
110 schema:value 10.1007/978-3-319-96884-1_10
111 rdf:type schema:PropertyValue
112 N47b2bd2dec3c4b8cbd99170894998f5f rdf:first sg:person.011431743334.40
113 rdf:rest N21aa81dc04564dbb82261fae96bdaf44
114 N62eb5bd45ea74d3b989e54fae396c006 rdf:first sg:person.07653531142.18
115 rdf:rest rdf:nil
116 N65ad9f46e96c42fda54359ae752b57f9 schema:name Springer Nature - SN SciGraph project
117 rdf:type schema:Organization
118 N78d79860db2e45f28fdbb07c916e5572 rdf:first N7ee264f408c74758b34b316fe1176346
119 rdf:rest rdf:nil
120 N7ee264f408c74758b34b316fe1176346 schema:familyName Boldyreva
121 schema:givenName Alexandra
122 rdf:type schema:Person
123 Na575825b817b46bcab7e18a65f7bf454 rdf:first sg:person.013247762751.78
124 rdf:rest N1de257302df1493a9bc97f880991ca1a
125 Nae33cea27b11455fb55e929acb88d5e5 schema:isbn 978-3-319-96883-4
126 978-3-319-96884-1
127 schema:name Advances in Cryptology – CRYPTO 2018
128 rdf:type schema:Book
129 Nd095e3f65cfc43eb9bc186f27f8c5968 rdf:first sg:person.07676572757.38
130 rdf:rest N62eb5bd45ea74d3b989e54fae396c006
131 Nd111f651afe041d5870ca285ca49f83d schema:familyName Shacham
132 schema:givenName Hovav
133 rdf:type schema:Person
134 Nde225e2246c34f2e927a6af90fa780c4 schema:name Springer Nature
135 rdf:type schema:Organisation
136 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
137 schema:name Information and Computing Sciences
138 rdf:type schema:DefinedTerm
139 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
140 schema:name Computation Theory and Mathematics
141 rdf:type schema:DefinedTerm
142 sg:person.011431743334.40 schema:affiliation grid-institutes:grid.16008.3f
143 schema:familyName Wang
144 schema:givenName Qingju
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40
146 rdf:type schema:Person
147 sg:person.012162474100.06 schema:affiliation grid-institutes:grid.5596.f
148 schema:familyName Li
149 schema:givenName Chaoyun
150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162474100.06
151 rdf:type schema:Person
152 sg:person.013247762751.78 schema:affiliation grid-institutes:None
153 schema:familyName Todo
154 schema:givenName Yosuke
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78
156 rdf:type schema:Person
157 sg:person.014270173173.47 schema:affiliation grid-institutes:grid.496622.d
158 schema:familyName Hao
159 schema:givenName Yonglin
160 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47
161 rdf:type schema:Person
162 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
163 schema:familyName Meier
164 schema:givenName Willi
165 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
166 rdf:type schema:Person
167 sg:person.07676572757.38 schema:affiliation grid-institutes:grid.266453.0
168 schema:familyName Isobe
169 schema:givenName Takanori
170 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676572757.38
171 rdf:type schema:Person
172 grid-institutes:None schema:alternateName NTT Secure Platform Laboratories, Tokyo, Japan
173 schema:name NTT Secure Platform Laboratories, Tokyo, Japan
174 rdf:type schema:Organization
175 grid-institutes:grid.16008.3f schema:alternateName SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
176 schema:name Shanghai Jiao Tong University, Shanghai, China
177 SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
178 Technical University of Denmark, Kongens Lyngby, Denmark
179 rdf:type schema:Organization
180 grid-institutes:grid.266453.0 schema:alternateName University of Hyogo, Kobe, Japan
181 schema:name University of Hyogo, Kobe, Japan
182 rdf:type schema:Organization
183 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
184 schema:name FHNW, Windisch, Switzerland
185 rdf:type schema:Organization
186 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, Beijing, China
187 schema:name State Key Laboratory of Cryptology, Beijing, China
188 rdf:type schema:Organization
189 grid-institutes:grid.5596.f schema:alternateName imec-COSIC, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
190 schema:name imec-COSIC, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
191 rdf:type schema:Organization
 




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


...