Fast Correlation Attacks over Extension Fields, Large-Unit Linear Approximation and Cryptanalysis of SNOW 2.0 View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-08-01

AUTHORS

Bin Zhang , Chao Xu , Willi Meier

ABSTRACT

Several improvements of fast correlation attacks have been proposed during the past two decades, with a regrettable lack of a better generalization and adaptation to the concrete involved primitives, especially to those modern stream ciphers based on word-based LFSRs. In this paper, we develop some necessary cryptanalytic tools to bridge this gap. First, a formal framework for fast correlation attacks over extension fields is constructed, under which the theoretical predictions of the computational complexities for both the offline and online/decoding phase can be reliably derived. Our decoding algorithm makes use of Fast Walsh Transform (FWT) to get a better performance. Second, an efficient algorithm to compute the large-unit distribution of a broad class of functions is proposed, which allows to find better linear approximations than the bitwise ones with low complexity in symmetric-key primitives. Last, we apply our methods to SNOW 2.0, an ISO/IEC 18033-4 standard stream cipher, which results in the significantly reduced complexities all below 2164.15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{164.15}$$\end{document}. This attack is more than 249\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{49}$$\end{document} times better than the best published result at Asiacrypt 2008. Our results have been verified by experiments on a small-scale version of SNOW 2.0. More... »

PAGES

643-662

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-47989-6_31

DOI

http://dx.doi.org/10.1007/978-3-662-47989-6_31

DIMENSIONS

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


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": "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"
      }, 
      {
        "affiliation": {
          "alternateName": "TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.458446.f", 
          "name": [
            "TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xu", 
        "givenName": "Chao", 
        "id": "sg:person.015403636457.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015403636457.52"
        ], 
        "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": "2015-08-01", 
    "datePublishedReg": "2015-08-01", 
    "description": "Several improvements of fast correlation attacks have been proposed during the past two decades, with a regrettable lack of a better generalization and adaptation to the concrete involved primitives, especially to those modern stream ciphers based on word-based LFSRs. In this paper, we develop some necessary cryptanalytic tools to bridge this gap. First, a formal framework for fast correlation attacks over extension fields is constructed, under which the theoretical predictions of the computational complexities for both the offline and online/decoding phase can be reliably derived. Our decoding algorithm makes use of Fast Walsh Transform (FWT) to get a better performance. Second, an efficient algorithm to compute the large-unit distribution of a broad class of functions is proposed, which allows to find better linear approximations than the bitwise ones with low complexity in symmetric-key primitives. Last, we apply our methods to SNOW 2.0, an ISO/IEC 18033-4 standard stream cipher, which results in the significantly reduced complexities all below 2164.15\\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^{164.15}$$\\end{document}. This attack is more than 249\\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^{49}$$\\end{document} times better than the best published result at Asiacrypt 2008. Our results have been verified by experiments on a small-scale version of SNOW 2.0.", 
    "editor": [
      {
        "familyName": "Gennaro", 
        "givenName": "Rosario", 
        "type": "Person"
      }, 
      {
        "familyName": "Robshaw", 
        "givenName": "Matthew", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-47989-6_31", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-47988-9", 
        "978-3-662-47989-6"
      ], 
      "name": "Advances in Cryptology -- CRYPTO 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "fast correlation attacks", 
      "fast Walsh transform", 
      "SNOW 2.0", 
      "correlation attacks", 
      "stream cipher", 
      "standard stream cipher", 
      "ISO/IEC 18033", 
      "symmetric-key primitives", 
      "modern stream ciphers", 
      "extension field", 
      "computational complexity", 
      "decoding phase", 
      "decoding algorithm", 
      "better generalization", 
      "formal framework", 
      "efficient algorithm", 
      "low complexity", 
      "cryptanalytic tool", 
      "ASIACRYPT 2008", 
      "Walsh transform", 
      "better performance", 
      "primitives", 
      "cipher", 
      "algorithm", 
      "complexity", 
      "attacks", 
      "linear approximation", 
      "broad class", 
      "cryptanalysis", 
      "LFSR", 
      "small-scale version", 
      "framework", 
      "transform", 
      "tool", 
      "performance", 
      "version", 
      "approximation", 
      "generalization", 
      "field", 
      "method", 
      "results", 
      "experiments", 
      "class", 
      "prediction", 
      "adaptation", 
      "improvement", 
      "regrettable lack", 
      "one", 
      "time", 
      "use", 
      "best linear approximation", 
      "gap", 
      "lack", 
      "function", 
      "decades", 
      "phase", 
      "distribution", 
      "theoretical predictions", 
      "concrete", 
      "paper", 
      "word-based LFSRs", 
      "necessary cryptanalytic tools", 
      "large-unit distribution", 
      "bitwise ones", 
      "IEC 18033", 
      "Unit Linear Approximation"
    ], 
    "name": "Fast Correlation Attacks over Extension Fields, Large-Unit Linear Approximation and Cryptanalysis of SNOW 2.0", 
    "pagination": "643-662", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084730231"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-47989-6_31"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-47989-6_31", 
      "https://app.dimensions.ai/details/publication/pub.1084730231"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:07", 
    "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_121.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-47989-6_31"
  }
]
 

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-662-47989-6_31'

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-662-47989-6_31'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-47989-6_31'

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-662-47989-6_31'


 

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

152 TRIPLES      23 PREDICATES      91 URIs      84 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-47989-6_31 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N139796ecb9584d07b72111fc83f334fd
4 schema:datePublished 2015-08-01
5 schema:datePublishedReg 2015-08-01
6 schema:description Several improvements of fast correlation attacks have been proposed during the past two decades, with a regrettable lack of a better generalization and adaptation to the concrete involved primitives, especially to those modern stream ciphers based on word-based LFSRs. In this paper, we develop some necessary cryptanalytic tools to bridge this gap. First, a formal framework for fast correlation attacks over extension fields is constructed, under which the theoretical predictions of the computational complexities for both the offline and online/decoding phase can be reliably derived. Our decoding algorithm makes use of Fast Walsh Transform (FWT) to get a better performance. Second, an efficient algorithm to compute the large-unit distribution of a broad class of functions is proposed, which allows to find better linear approximations than the bitwise ones with low complexity in symmetric-key primitives. Last, we apply our methods to SNOW 2.0, an ISO/IEC 18033-4 standard stream cipher, which results in the significantly reduced complexities all below 2164.15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{164.15}$$\end{document}. This attack is more than 249\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{49}$$\end{document} times better than the best published result at Asiacrypt 2008. Our results have been verified by experiments on a small-scale version of SNOW 2.0.
7 schema:editor N3223901654cd4f53ba44f7377e06ce9c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0c17f0b3e9e848ccb3ba3380cf2f0431
12 schema:keywords ASIACRYPT 2008
13 IEC 18033
14 ISO/IEC 18033
15 LFSR
16 SNOW 2.0
17 Unit Linear Approximation
18 Walsh transform
19 adaptation
20 algorithm
21 approximation
22 attacks
23 best linear approximation
24 better generalization
25 better performance
26 bitwise ones
27 broad class
28 cipher
29 class
30 complexity
31 computational complexity
32 concrete
33 correlation attacks
34 cryptanalysis
35 cryptanalytic tool
36 decades
37 decoding algorithm
38 decoding phase
39 distribution
40 efficient algorithm
41 experiments
42 extension field
43 fast Walsh transform
44 fast correlation attacks
45 field
46 formal framework
47 framework
48 function
49 gap
50 generalization
51 improvement
52 lack
53 large-unit distribution
54 linear approximation
55 low complexity
56 method
57 modern stream ciphers
58 necessary cryptanalytic tools
59 one
60 paper
61 performance
62 phase
63 prediction
64 primitives
65 regrettable lack
66 results
67 small-scale version
68 standard stream cipher
69 stream cipher
70 symmetric-key primitives
71 theoretical predictions
72 time
73 tool
74 transform
75 use
76 version
77 word-based LFSRs
78 schema:name Fast Correlation Attacks over Extension Fields, Large-Unit Linear Approximation and Cryptanalysis of SNOW 2.0
79 schema:pagination 643-662
80 schema:productId N9fa828d019ae49c58eade9ff53261614
81 Nc05fce7ff30842d9bdc03d7a2fb5b180
82 schema:publisher Nc865c297685b44a98900912d2aed95bc
83 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084730231
84 https://doi.org/10.1007/978-3-662-47989-6_31
85 schema:sdDatePublished 2022-01-01T19:07
86 schema:sdLicense https://scigraph.springernature.com/explorer/license/
87 schema:sdPublisher Nef0626c3be114ed0ad91a037bd22b5ff
88 schema:url https://doi.org/10.1007/978-3-662-47989-6_31
89 sgo:license sg:explorer/license/
90 sgo:sdDataset chapters
91 rdf:type schema:Chapter
92 N0c17f0b3e9e848ccb3ba3380cf2f0431 schema:isbn 978-3-662-47988-9
93 978-3-662-47989-6
94 schema:name Advances in Cryptology -- CRYPTO 2015
95 rdf:type schema:Book
96 N139796ecb9584d07b72111fc83f334fd rdf:first sg:person.014125113140.40
97 rdf:rest N57761672a9fb4bbc8f368f205a3de077
98 N3223901654cd4f53ba44f7377e06ce9c rdf:first N9409d2bdb37b4624b1524dc7a9550387
99 rdf:rest N38e63fbed5f5466884d462fd2ed0bee7
100 N38e63fbed5f5466884d462fd2ed0bee7 rdf:first Nb65fb7108591426782ee081754848fc6
101 rdf:rest rdf:nil
102 N57761672a9fb4bbc8f368f205a3de077 rdf:first sg:person.015403636457.52
103 rdf:rest Na54e4dede494457484b0f60088cb91ab
104 N9409d2bdb37b4624b1524dc7a9550387 schema:familyName Gennaro
105 schema:givenName Rosario
106 rdf:type schema:Person
107 N9fa828d019ae49c58eade9ff53261614 schema:name dimensions_id
108 schema:value pub.1084730231
109 rdf:type schema:PropertyValue
110 Na54e4dede494457484b0f60088cb91ab rdf:first sg:person.07653531142.18
111 rdf:rest rdf:nil
112 Nb65fb7108591426782ee081754848fc6 schema:familyName Robshaw
113 schema:givenName Matthew
114 rdf:type schema:Person
115 Nc05fce7ff30842d9bdc03d7a2fb5b180 schema:name doi
116 schema:value 10.1007/978-3-662-47989-6_31
117 rdf:type schema:PropertyValue
118 Nc865c297685b44a98900912d2aed95bc schema:name Springer Nature
119 rdf:type schema:Organisation
120 Nef0626c3be114ed0ad91a037bd22b5ff schema:name Springer Nature - SN SciGraph project
121 rdf:type schema:Organization
122 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
123 schema:name Information and Computing Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
126 schema:name Computation Theory and Mathematics
127 rdf:type schema:DefinedTerm
128 sg:person.014125113140.40 schema:affiliation grid-institutes:grid.496622.d
129 schema:familyName Zhang
130 schema:givenName Bin
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014125113140.40
132 rdf:type schema:Person
133 sg:person.015403636457.52 schema:affiliation grid-institutes:grid.458446.f
134 schema:familyName Xu
135 schema:givenName Chao
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015403636457.52
137 rdf:type schema:Person
138 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
139 schema:familyName Meier
140 schema:givenName Willi
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
142 rdf:type schema:Person
143 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
144 schema:name FHNW, Windisch, Switzerland
145 rdf:type schema:Organization
146 grid-institutes:grid.458446.f schema:alternateName TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
147 schema:name TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
148 rdf:type schema:Organization
149 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O.Box 5159, 100878, Beijing, China
150 schema:name State Key Laboratory of Cryptology, P.O.Box 5159, 100878, Beijing, China
151 TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
152 rdf:type schema:Organization
 




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


...