Ontology type: schema:Chapter Open Access: True
2020-05-01
AUTHORSYonglin Hao , Gregor Leander , Willi Meier , Yosuke Todo , Qingju Wang
ABSTRACTA 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... »
PAGES466-495
Advances in Cryptology – EUROCRYPT 2020
ISBN
978-3-030-45720-4
978-3-030-45721-1
http://scigraph.springernature.com/pub.10.1007/978-3-030-45721-1_17
DOIhttp://dx.doi.org/10.1007/978-3-030-45721-1_17
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1127314031
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
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 |