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


Ontology type: schema:Chapter      Open Access: True


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/grid.419819.c", 
          "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": true, 
    "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", 
      "division property", 
      "new efficient algorithm", 
      "art algorithms", 
      "stream cipher", 
      "efficient algorithm", 
      "Grain-128AEAD", 
      "generic tool", 
      "inaccuracy problem", 
      "new algorithm", 
      "algorithm", 
      "attacks", 
      "cipher", 
      "integral distinguishers", 
      "cube attack", 
      "tool", 
      "applications", 
      "critical flaws", 
      "security", 
      "MILP", 
      "SMT", 
      "distinguisher", 
      "Trivium", 
      "flaws", 
      "subset", 
      "features", 
      "promising method", 
      "rounds", 
      "inaccuracy", 
      "method", 
      "state", 
      "results", 
      "propagation", 
      "properties", 
      "degenerate", 
      "problem", 
      "paper"
    ], 
    "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-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_166.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.

146 TRIPLES      23 PREDICATES      66 URIs      59 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 N71a1cce700ff4994bb1fc3ce46f101b5
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 N7231908c04984c2f8aba28a02bef467f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N373b1ff3a0294bcbb9a4e28d19fdabc3
12 schema:keywords Grain-128AEAD
13 MILP
14 SAT/SMT
15 SMT
16 Trivium
17 algorithm
18 applications
19 art algorithms
20 attacks
21 automatic tool
22 best key-recovery attack
23 cipher
24 critical flaws
25 cube attack
26 degenerate
27 distinguisher
28 division property
29 efficient algorithm
30 features
31 flaws
32 generic tool
33 inaccuracy
34 inaccuracy problem
35 integral distinguishers
36 key recovery attack
37 method
38 new algorithm
39 new efficient algorithm
40 paper
41 problem
42 promising method
43 propagation
44 properties
45 results
46 rounds
47 security
48 state
49 stream cipher
50 subset
51 tool
52 unknown subset
53 schema:name Modeling for Three-Subset Division Property Without Unknown Subset
54 schema:pagination 466-495
55 schema:productId N45e6eb4837e34b4e96c82f0fb727f03d
56 N477b81aabd47433085eb1cf2472a2a15
57 schema:publisher N5222063eb8f14bb5a134be5ecdedff58
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127314031
59 https://doi.org/10.1007/978-3-030-45721-1_17
60 schema:sdDatePublished 2022-05-20T07:42
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher Nff8c94b718a44dd5bdbfc907d3218cf0
63 schema:url https://doi.org/10.1007/978-3-030-45721-1_17
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N0f4c85dc5be540e89d5560228d38a1cd rdf:first sg:person.016572560277.70
68 rdf:rest N275bc8376778463d971dcb8a93640ddf
69 N275bc8376778463d971dcb8a93640ddf rdf:first sg:person.07653531142.18
70 rdf:rest N838f53e5e5ac4317a98b90143aec28f3
71 N373b1ff3a0294bcbb9a4e28d19fdabc3 schema:isbn 978-3-030-45720-4
72 978-3-030-45721-1
73 schema:name Advances in Cryptology – EUROCRYPT 2020
74 rdf:type schema:Book
75 N45e6eb4837e34b4e96c82f0fb727f03d schema:name doi
76 schema:value 10.1007/978-3-030-45721-1_17
77 rdf:type schema:PropertyValue
78 N477b81aabd47433085eb1cf2472a2a15 schema:name dimensions_id
79 schema:value pub.1127314031
80 rdf:type schema:PropertyValue
81 N5222063eb8f14bb5a134be5ecdedff58 schema:name Springer Nature
82 rdf:type schema:Organisation
83 N588b8c57d8de451ca17e70b1a86c999a schema:familyName Canteaut
84 schema:givenName Anne
85 rdf:type schema:Person
86 N71a1cce700ff4994bb1fc3ce46f101b5 rdf:first sg:person.014270173173.47
87 rdf:rest N0f4c85dc5be540e89d5560228d38a1cd
88 N7231908c04984c2f8aba28a02bef467f rdf:first N588b8c57d8de451ca17e70b1a86c999a
89 rdf:rest Nec8aa2be725047efa1d46d054548e122
90 N7ff1e18f2cca4ecd9e056cf4b41017b5 schema:familyName Ishai
91 schema:givenName Yuval
92 rdf:type schema:Person
93 N838f53e5e5ac4317a98b90143aec28f3 rdf:first sg:person.013247762751.78
94 rdf:rest Nab40cd6595894324b2a7af7c25fc7854
95 Nab40cd6595894324b2a7af7c25fc7854 rdf:first sg:person.011431743334.40
96 rdf:rest rdf:nil
97 Nec8aa2be725047efa1d46d054548e122 rdf:first N7ff1e18f2cca4ecd9e056cf4b41017b5
98 rdf:rest rdf:nil
99 Nff8c94b718a44dd5bdbfc907d3218cf0 schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
102 schema:name Information and Computing Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
105 schema:name Artificial Intelligence and Image Processing
106 rdf:type schema:DefinedTerm
107 sg:person.011431743334.40 schema:affiliation grid-institutes:grid.16008.3f
108 schema:familyName Wang
109 schema:givenName Qingju
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40
111 rdf:type schema:Person
112 sg:person.013247762751.78 schema:affiliation grid-institutes:grid.419819.c
113 schema:familyName Todo
114 schema:givenName Yosuke
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78
116 rdf:type schema:Person
117 sg:person.014270173173.47 schema:affiliation grid-institutes:grid.496622.d
118 schema:familyName Hao
119 schema:givenName Yonglin
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47
121 rdf:type schema:Person
122 sg:person.016572560277.70 schema:affiliation grid-institutes:grid.5570.7
123 schema:familyName Leander
124 schema:givenName Gregor
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016572560277.70
126 rdf:type schema:Person
127 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
128 schema:familyName Meier
129 schema:givenName Willi
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
131 rdf:type schema:Person
132 grid-institutes:grid.16008.3f schema:alternateName SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
133 schema:name SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
134 rdf:type schema:Organization
135 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
136 schema:name FHNW, Windisch, Switzerland
137 rdf:type schema:Organization
138 grid-institutes:grid.419819.c schema:alternateName NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
139 schema:name NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
140 rdf:type schema:Organization
141 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
142 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
143 rdf:type schema:Organization
144 grid-institutes:grid.5570.7 schema:alternateName Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany
145 schema:name Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany
146 rdf:type schema:Organization
 




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


...