Fast Correlation Attack Revisited View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-07-24

AUTHORS

Yosuke Todo , Takanori Isobe , Willi Meier , Kazumaro Aoki , Bin Zhang

ABSTRACT

A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time. More... »

PAGES

129-159

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-96881-0_5

DOI

http://dx.doi.org/10.1007/978-3-319-96881-0_5

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "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": "University of Hyogo, 650-0047, Hyogo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.266453.0", 
          "name": [
            "University of Hyogo, 650-0047, Hyogo, 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"
      }, 
      {
        "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": "Aoki", 
        "givenName": "Kazumaro", 
        "id": "sg:person.015040765627.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015040765627.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.496622.d", 
          "name": [
            "TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China", 
            "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Bin", 
        "id": "sg:person.014125113140.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014125113140.40"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-07-24", 
    "datePublishedReg": "2018-07-24", 
    "description": "A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.", 
    "editor": [
      {
        "familyName": "Shacham", 
        "givenName": "Hovav", 
        "type": "Person"
      }, 
      {
        "familyName": "Boldyreva", 
        "givenName": "Alexandra", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-96881-0_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-96880-3", 
        "978-3-319-96881-0"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "fast correlation attacks", 
      "stream cipher", 
      "correlation attacks", 
      "ISO/IEC", 
      "data complexity", 
      "key stream", 
      "cryptanalysis techniques", 
      "novel algorithm", 
      "multiple linear approximations", 
      "cipher", 
      "Grain-v1", 
      "finite field", 
      "LFSR", 
      "full version", 
      "attacks", 
      "algorithm", 
      "cryptanalysis", 
      "new point", 
      "complexity", 
      "initial state", 
      "Grain-128a", 
      "technique", 
      "new properties", 
      "linear approximation", 
      "streams", 
      "IEC", 
      "version", 
      "goal", 
      "Grain-128", 
      "time", 
      "view", 
      "class", 
      "grain families", 
      "state", 
      "point", 
      "approximation", 
      "field", 
      "results", 
      "portfolio", 
      "properties", 
      "first time", 
      "correlation", 
      "family", 
      "paper"
    ], 
    "name": "Fast Correlation Attack Revisited", 
    "pagination": "129-159", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105780991"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-96881-0_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-96881-0_5", 
      "https://app.dimensions.ai/details/publication/pub.1105780991"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:21", 
    "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_377.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-96881-0_5"
  }
]
 

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-96881-0_5'

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-96881-0_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-96881-0_5'

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-96881-0_5'


 

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

147 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-96881-0_5 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N5d1b736d0a7d498eb041f88faffc3e76
4 schema:datePublished 2018-07-24
5 schema:datePublishedReg 2018-07-24
6 schema:description A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.
7 schema:editor Neb866bb4f1e14beeb38585ecf37656c5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0ed364afe09e445080479246eadd7e05
12 schema:keywords Grain-128
13 Grain-128a
14 Grain-v1
15 IEC
16 ISO/IEC
17 LFSR
18 algorithm
19 approximation
20 attacks
21 cipher
22 class
23 complexity
24 correlation
25 correlation attacks
26 cryptanalysis
27 cryptanalysis techniques
28 data complexity
29 family
30 fast correlation attacks
31 field
32 finite field
33 first time
34 full version
35 goal
36 grain families
37 initial state
38 key stream
39 linear approximation
40 multiple linear approximations
41 new point
42 new properties
43 novel algorithm
44 paper
45 point
46 portfolio
47 properties
48 results
49 state
50 stream cipher
51 streams
52 technique
53 time
54 version
55 view
56 schema:name Fast Correlation Attack Revisited
57 schema:pagination 129-159
58 schema:productId N38e359102c744e06b9daecbf5439a6ff
59 N5314023a8429421cb6df6db943a94369
60 schema:publisher Nbf5ecaca77b641aba13210e0e1078637
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105780991
62 https://doi.org/10.1007/978-3-319-96881-0_5
63 schema:sdDatePublished 2022-01-01T19:21
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N0dc7547157cb4302b32f176788453941
66 schema:url https://doi.org/10.1007/978-3-319-96881-0_5
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N0dc7547157cb4302b32f176788453941 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N0ed364afe09e445080479246eadd7e05 schema:isbn 978-3-319-96880-3
73 978-3-319-96881-0
74 schema:name Advances in Cryptology – CRYPTO 2018
75 rdf:type schema:Book
76 N1a6f0f3e42c940419db94d1ab3d032b9 rdf:first sg:person.07676572757.38
77 rdf:rest Nfb1cfac704aa4feab970bbbd7c58037e
78 N38e359102c744e06b9daecbf5439a6ff schema:name doi
79 schema:value 10.1007/978-3-319-96881-0_5
80 rdf:type schema:PropertyValue
81 N5314023a8429421cb6df6db943a94369 schema:name dimensions_id
82 schema:value pub.1105780991
83 rdf:type schema:PropertyValue
84 N5d1b736d0a7d498eb041f88faffc3e76 rdf:first sg:person.013247762751.78
85 rdf:rest N1a6f0f3e42c940419db94d1ab3d032b9
86 N9030b7ea69c4438a9bb5d04173b89063 rdf:first sg:person.015040765627.38
87 rdf:rest Na189e3bdea40472999e9bec148d949af
88 Na189e3bdea40472999e9bec148d949af rdf:first sg:person.014125113140.40
89 rdf:rest rdf:nil
90 Na581966ad74e40649ea3b87b659d493a schema:familyName Boldyreva
91 schema:givenName Alexandra
92 rdf:type schema:Person
93 Na6252c2f856e40868610fdb1bd19755b schema:familyName Shacham
94 schema:givenName Hovav
95 rdf:type schema:Person
96 Nbb912573a1794e53b56fb8c13a794216 rdf:first Na581966ad74e40649ea3b87b659d493a
97 rdf:rest rdf:nil
98 Nbf5ecaca77b641aba13210e0e1078637 schema:name Springer Nature
99 rdf:type schema:Organisation
100 Neb866bb4f1e14beeb38585ecf37656c5 rdf:first Na6252c2f856e40868610fdb1bd19755b
101 rdf:rest Nbb912573a1794e53b56fb8c13a794216
102 Nfb1cfac704aa4feab970bbbd7c58037e rdf:first sg:person.07653531142.18
103 rdf:rest N9030b7ea69c4438a9bb5d04173b89063
104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information and Computing Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
108 schema:name Data Format
109 rdf:type schema:DefinedTerm
110 sg:person.013247762751.78 schema:affiliation grid-institutes:None
111 schema:familyName Todo
112 schema:givenName Yosuke
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78
114 rdf:type schema:Person
115 sg:person.014125113140.40 schema:affiliation grid-institutes:grid.496622.d
116 schema:familyName Zhang
117 schema:givenName Bin
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014125113140.40
119 rdf:type schema:Person
120 sg:person.015040765627.38 schema:affiliation grid-institutes:None
121 schema:familyName Aoki
122 schema:givenName Kazumaro
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015040765627.38
124 rdf:type schema:Person
125 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
126 schema:familyName Meier
127 schema:givenName Willi
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
129 rdf:type schema:Person
130 sg:person.07676572757.38 schema:affiliation grid-institutes:grid.266453.0
131 schema:familyName Isobe
132 schema:givenName Takanori
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676572757.38
134 rdf:type schema:Person
135 grid-institutes:None schema:alternateName NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
136 schema:name NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
137 rdf:type schema:Organization
138 grid-institutes:grid.266453.0 schema:alternateName University of Hyogo, 650-0047, Hyogo, Japan
139 schema:name University of Hyogo, 650-0047, Hyogo, Japan
140 rdf:type schema:Organization
141 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
142 schema:name FHNW, Windisch, Switzerland
143 rdf:type schema:Organization
144 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
145 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
146 TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
147 rdf:type schema:Organization
 




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


...