Modeling for Three-Subset Division Property Without Unknown Subset View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-05-01

AUTHORS

Yonglin Hao , Gregor Leander , Willi Meier , Yosuke Todo , Qingju Wang

ABSTRACT

A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the feature of the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 841-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 841-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to distinguishing attacks. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. More... »

PAGES

466-495

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-45721-1_17

DOI

http://dx.doi.org/10.1007/978-3-030-45721-1_17

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.496622.d", 
          "name": [
            "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, 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": "Horst G\u00f6rtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5570.7", 
          "name": [
            "Horst G\u00f6rtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Leander", 
        "givenName": "Gregor", 
        "id": "sg:person.016572560277.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016572560277.70"
        ], 
        "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"
      }, 
      {
        "affiliation": {
          "alternateName": "NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "NTT Secure Platform Laboratories, 180-8585, 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": "SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg", 
          "id": "http://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "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"
      }
    ], 
    "datePublished": "2020-05-01", 
    "datePublishedReg": "2020-05-01", 
    "description": "Abstract\nA division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the feature of the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 841-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 841-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to distinguishing attacks. Then, the distinguishing attacks are improved up\u00a0to 189 rounds, and we also show the best key-recovery attack against 190 rounds.", 
    "editor": [
      {
        "familyName": "Canteaut", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Ishai", 
        "givenName": "Yuval", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-45721-1_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-45720-4", 
        "978-3-030-45721-1"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2020", 
      "type": "Book"
    }, 
    "keywords": [
      "key recovery attack", 
      "automatic tool", 
      "best key-recovery attack", 
      "unknown subset", 
      "SAT/SMT", 
      "new efficient algorithm", 
      "division property", 
      "art algorithms", 
      "stream cipher", 
      "efficient algorithm", 
      "inaccuracy problem", 
      "generic tool", 
      "new algorithm", 
      "algorithm", 
      "attacks", 
      "cipher", 
      "integral distinguishers", 
      "cube attack", 
      "tool", 
      "applications", 
      "security", 
      "critical flaws", 
      "MILP", 
      "SMT", 
      "Trivium", 
      "distinguisher", 
      "flaws", 
      "subset", 
      "features", 
      "promising method", 
      "rounds", 
      "inaccuracy", 
      "method", 
      "state", 
      "results", 
      "propagation", 
      "properties", 
      "degenerate", 
      "problem", 
      "paper", 
      "division property degenerate", 
      "property degenerate", 
      "three-subset division property", 
      "Asiacrypt2019", 
      "CRYPTO2018", 
      "Grain-128AEAD", 
      "key-recovery attack degenerates", 
      "attack degenerates"
    ], 
    "name": "Modeling for Three-Subset Division Property Without Unknown Subset", 
    "pagination": "466-495", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1127314031"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-45721-1_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-45721-1_17", 
      "https://app.dimensions.ai/details/publication/pub.1127314031"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_217.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-45721-1_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/978-3-030-45721-1_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/978-3-030-45721-1_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-45721-1_17'

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-030-45721-1_17'


 

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

153 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-45721-1_17 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N44ca7aef2d214c728ce8eaed15c29a87
4 schema:datePublished 2020-05-01
5 schema:datePublishedReg 2020-05-01
6 schema:description Abstract A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the feature of the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 841-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 841-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to distinguishing attacks. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds.
7 schema:editor N20a793a2ae9249c696fb20cfd0f48f4c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N308a83d1c1d0475fa272ed5739cdf339
12 schema:keywords Asiacrypt2019
13 CRYPTO2018
14 Grain-128AEAD
15 MILP
16 SAT/SMT
17 SMT
18 Trivium
19 algorithm
20 applications
21 art algorithms
22 attack degenerates
23 attacks
24 automatic tool
25 best key-recovery attack
26 cipher
27 critical flaws
28 cube attack
29 degenerate
30 distinguisher
31 division property
32 division property degenerate
33 efficient algorithm
34 features
35 flaws
36 generic tool
37 inaccuracy
38 inaccuracy problem
39 integral distinguishers
40 key recovery attack
41 key-recovery attack degenerates
42 method
43 new algorithm
44 new efficient algorithm
45 paper
46 problem
47 promising method
48 propagation
49 properties
50 property degenerate
51 results
52 rounds
53 security
54 state
55 stream cipher
56 subset
57 three-subset division property
58 tool
59 unknown subset
60 schema:name Modeling for Three-Subset Division Property Without Unknown Subset
61 schema:pagination 466-495
62 schema:productId N1418db406808416d9f92caa91d135650
63 Nfce6e14950624306b1c353ad3571fb8b
64 schema:publisher Nb63d32d24c4e405fa5906d24a34b5305
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127314031
66 https://doi.org/10.1007/978-3-030-45721-1_17
67 schema:sdDatePublished 2022-01-01T19:12
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N322b3239d63a4932bd376896aedb00d1
70 schema:url https://doi.org/10.1007/978-3-030-45721-1_17
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N0ea4da56aa0c47a18f5782f32e2308a3 rdf:first sg:person.011431743334.40
75 rdf:rest rdf:nil
76 N1418db406808416d9f92caa91d135650 schema:name dimensions_id
77 schema:value pub.1127314031
78 rdf:type schema:PropertyValue
79 N1f7ac5ea639a432b8453f73c45ef08fb rdf:first sg:person.013247762751.78
80 rdf:rest N0ea4da56aa0c47a18f5782f32e2308a3
81 N20a793a2ae9249c696fb20cfd0f48f4c rdf:first N64fa924a966445609a3f995c0c0116c9
82 rdf:rest N9d348c04597a41bfa95cd8d7fade4a16
83 N308a83d1c1d0475fa272ed5739cdf339 schema:isbn 978-3-030-45720-4
84 978-3-030-45721-1
85 schema:name Advances in Cryptology – EUROCRYPT 2020
86 rdf:type schema:Book
87 N322b3239d63a4932bd376896aedb00d1 schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 N334356dce8a0417386f3a848fa5c1eca rdf:first sg:person.07653531142.18
90 rdf:rest N1f7ac5ea639a432b8453f73c45ef08fb
91 N44ca7aef2d214c728ce8eaed15c29a87 rdf:first sg:person.014270173173.47
92 rdf:rest Na8ede8ea33c74f5e98f6d5f14966ce97
93 N64fa924a966445609a3f995c0c0116c9 schema:familyName Canteaut
94 schema:givenName Anne
95 rdf:type schema:Person
96 N9d348c04597a41bfa95cd8d7fade4a16 rdf:first Na67d5f3b434f41c381af572d731cb74c
97 rdf:rest rdf:nil
98 Na67d5f3b434f41c381af572d731cb74c schema:familyName Ishai
99 schema:givenName Yuval
100 rdf:type schema:Person
101 Na8ede8ea33c74f5e98f6d5f14966ce97 rdf:first sg:person.016572560277.70
102 rdf:rest N334356dce8a0417386f3a848fa5c1eca
103 Nb63d32d24c4e405fa5906d24a34b5305 schema:name Springer Nature
104 rdf:type schema:Organisation
105 Nfce6e14950624306b1c353ad3571fb8b schema:name doi
106 schema:value 10.1007/978-3-030-45721-1_17
107 rdf:type schema:PropertyValue
108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information and Computing Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
112 schema:name Artificial Intelligence and Image Processing
113 rdf:type schema:DefinedTerm
114 sg:person.011431743334.40 schema:affiliation grid-institutes:grid.16008.3f
115 schema:familyName Wang
116 schema:givenName Qingju
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40
118 rdf:type schema:Person
119 sg:person.013247762751.78 schema:affiliation grid-institutes:None
120 schema:familyName Todo
121 schema:givenName Yosuke
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78
123 rdf:type schema:Person
124 sg:person.014270173173.47 schema:affiliation grid-institutes:grid.496622.d
125 schema:familyName Hao
126 schema:givenName Yonglin
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47
128 rdf:type schema:Person
129 sg:person.016572560277.70 schema:affiliation grid-institutes:grid.5570.7
130 schema:familyName Leander
131 schema:givenName Gregor
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016572560277.70
133 rdf:type schema:Person
134 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
135 schema:familyName Meier
136 schema:givenName Willi
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
138 rdf:type schema:Person
139 grid-institutes:None schema:alternateName NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
140 schema:name NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
141 rdf:type schema:Organization
142 grid-institutes:grid.16008.3f schema:alternateName SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
143 schema:name SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
144 rdf:type schema:Organization
145 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
146 schema:name FHNW, Windisch, Switzerland
147 rdf:type schema:Organization
148 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
149 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
150 rdf:type schema:Organization
151 grid-institutes:grid.5570.7 schema:alternateName Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany
152 schema:name Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany
153 rdf:type schema:Organization
 




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


...