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/grid.419819.c", 
          "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.

180 TRIPLES      23 PREDICATES      88 URIs      81 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 N10398877bd5f4bc3bbd32d52c9db667d
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 N026e01680bab46b097d4e93026018686
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N890fa25ec4244d9998a2def6184a3ea7
12 schema:keywords CRYPTO 2017
13 Kreyvium
14 MILP
15 MILP model
16 Todo et al
17 Trivium
18 adversary
19 al
20 algebraic properties
21 algorithm
22 assignment
23 attacks
24 bits
25 cipher
26 complexity
27 cryptanalysis
28 cube
29 cube I
30 cube attack
31 degree
32 division property
33 encryption
34 enumeration algorithm
35 et al
36 evaluation algorithm
37 experimental range
38 flags
39 grains
40 illustration
41 important technique
42 initialization
43 key bits
44 key primitives
45 key recovery attack
46 knowledge
47 limit
48 long time
49 model
50 monomials
51 paper
52 phase
53 plaintext
54 preciseness
55 precomputation phase
56 primitives
57 properties
58 proposal
59 range
60 recovery attack
61 restriction
62 secret key bits
63 set
64 size
65 stream cipher
66 subset J
67 superpoly
68 symmetric-key primitives
69 table
70 technique
71 time
72 truth table
73 upper
74 whole truth table
75 schema:name Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly
76 schema:pagination 275-305
77 schema:productId N80bc639eaf714a75b5f8c74271944861
78 N9f50d6ab27bf417ab95d1b32fa614002
79 schema:publisher Nb0f1c725eb9f416f9ed1b6add7009b7d
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105813840
81 https://doi.org/10.1007/978-3-319-96884-1_10
82 schema:sdDatePublished 2022-05-20T07:45
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher N39c9258201c44c4bb1311b1bbdeb0ff8
85 schema:url https://doi.org/10.1007/978-3-319-96884-1_10
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N026e01680bab46b097d4e93026018686 rdf:first N83a2b6a87f284bdc8a02a1910aba843d
90 rdf:rest Na7a81dbc15864d3f9c6cd777cf619da3
91 N0bfc6eb790774c9aba807991d47ddac0 rdf:first sg:person.07653531142.18
92 rdf:rest rdf:nil
93 N10398877bd5f4bc3bbd32d52c9db667d rdf:first sg:person.011431743334.40
94 rdf:rest Nff38648f0f8f4d3582326c66a2c1b5e2
95 N31d3c19c59c9433da932d6e70ce7f220 rdf:first sg:person.012162474100.06
96 rdf:rest N73ccf7ab3851469a816bc745c70a0e0c
97 N364afdca19674f21851c1f04b0bc33fe schema:familyName Boldyreva
98 schema:givenName Alexandra
99 rdf:type schema:Person
100 N39c9258201c44c4bb1311b1bbdeb0ff8 schema:name Springer Nature - SN SciGraph project
101 rdf:type schema:Organization
102 N73ccf7ab3851469a816bc745c70a0e0c rdf:first sg:person.07676572757.38
103 rdf:rest N0bfc6eb790774c9aba807991d47ddac0
104 N80bc639eaf714a75b5f8c74271944861 schema:name doi
105 schema:value 10.1007/978-3-319-96884-1_10
106 rdf:type schema:PropertyValue
107 N83a2b6a87f284bdc8a02a1910aba843d schema:familyName Shacham
108 schema:givenName Hovav
109 rdf:type schema:Person
110 N890fa25ec4244d9998a2def6184a3ea7 schema:isbn 978-3-319-96883-4
111 978-3-319-96884-1
112 schema:name Advances in Cryptology – CRYPTO 2018
113 rdf:type schema:Book
114 N9f50d6ab27bf417ab95d1b32fa614002 schema:name dimensions_id
115 schema:value pub.1105813840
116 rdf:type schema:PropertyValue
117 Na7a81dbc15864d3f9c6cd777cf619da3 rdf:first N364afdca19674f21851c1f04b0bc33fe
118 rdf:rest rdf:nil
119 Nb0f1c725eb9f416f9ed1b6add7009b7d schema:name Springer Nature
120 rdf:type schema:Organisation
121 Nc2a1338c7d8b49e0b67780a26fea311c rdf:first sg:person.013247762751.78
122 rdf:rest N31d3c19c59c9433da932d6e70ce7f220
123 Nff38648f0f8f4d3582326c66a2c1b5e2 rdf:first sg:person.014270173173.47
124 rdf:rest Nc2a1338c7d8b49e0b67780a26fea311c
125 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
126 schema:name Information and Computing Sciences
127 rdf:type schema:DefinedTerm
128 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
129 schema:name Computation Theory and Mathematics
130 rdf:type schema:DefinedTerm
131 sg:person.011431743334.40 schema:affiliation grid-institutes:grid.16008.3f
132 schema:familyName Wang
133 schema:givenName Qingju
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40
135 rdf:type schema:Person
136 sg:person.012162474100.06 schema:affiliation grid-institutes:grid.5596.f
137 schema:familyName Li
138 schema:givenName Chaoyun
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162474100.06
140 rdf:type schema:Person
141 sg:person.013247762751.78 schema:affiliation grid-institutes:grid.419819.c
142 schema:familyName Todo
143 schema:givenName Yosuke
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78
145 rdf:type schema:Person
146 sg:person.014270173173.47 schema:affiliation grid-institutes:grid.496622.d
147 schema:familyName Hao
148 schema:givenName Yonglin
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47
150 rdf:type schema:Person
151 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
152 schema:familyName Meier
153 schema:givenName Willi
154 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
155 rdf:type schema:Person
156 sg:person.07676572757.38 schema:affiliation grid-institutes:grid.266453.0
157 schema:familyName Isobe
158 schema:givenName Takanori
159 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676572757.38
160 rdf:type schema:Person
161 grid-institutes:grid.16008.3f schema:alternateName SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
162 schema:name Shanghai Jiao Tong University, Shanghai, China
163 SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
164 Technical University of Denmark, Kongens Lyngby, Denmark
165 rdf:type schema:Organization
166 grid-institutes:grid.266453.0 schema:alternateName University of Hyogo, Kobe, Japan
167 schema:name University of Hyogo, Kobe, Japan
168 rdf:type schema:Organization
169 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
170 schema:name FHNW, Windisch, Switzerland
171 rdf:type schema:Organization
172 grid-institutes:grid.419819.c 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.496622.d schema:alternateName State Key Laboratory of Cryptology, Beijing, China
176 schema:name State Key Laboratory of Cryptology, Beijing, China
177 rdf:type schema:Organization
178 grid-institutes:grid.5596.f schema:alternateName imec-COSIC, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
179 schema:name imec-COSIC, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
180 rdf:type schema:Organization
 




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


...