Fast Near Collision Attack on the Grain v1 Stream Cipher View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-03-31

AUTHORS

Bin Zhang , Chao Xu , Willi Meier

ABSTRACT

Modern stream ciphers often adopt a large internal state to resist various attacks, where the cryptanalysts have to deal with a large number of variables when mounting state recovery attacks. In this paper, we propose a general new cryptanalytic method on stream ciphers, called fast near collision attack, to address this situation. It combines a near collision property with the divide-and-conquer strategy so that only subsets of the internal state, associated with different keystream vectors, are recovered first and merged carefully later to retrieve the full large internal state. A self-contained method is introduced and improved to derive the target subset of the internal state from the partial state difference efficiently. As an application, we propose a new key recovery attack on Grain v1, one of the 7 finalists selected by the eSTREAM project, in the single-key setting. Both the pre-computation and the online phases are tailored according to its internal structure, to provide an attack for any fixed IV in 275.7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{75.7}$$\end{document} cipher ticks after the pre-computation of 28.1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{8.1}$$\end{document} cipher ticks, given 228\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{28}$$\end{document}-bit memory and about 219\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{19}$$\end{document} keystream bits. Practical experiments on Grain v1 itself whenever possible and on a 80-bit reduced version confirmed our results. More... »

PAGES

771-802

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-78375-8_25

DOI

http://dx.doi.org/10.1007/978-3-319-78375-8_25

DIMENSIONS

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


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 Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.458480.5", 
          "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", 
            "University of Chinese Academy of Sciences, 100049, Beijing, China", 
            "State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, 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": "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": "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": "2018-03-31", 
    "datePublishedReg": "2018-03-31", 
    "description": "Modern stream ciphers often adopt a large internal state to resist various attacks, where the cryptanalysts have to deal with a large number of variables when mounting state recovery attacks. In this paper, we propose a general new cryptanalytic method on stream ciphers, called fast near collision attack, to address this situation. It combines a near collision property with the divide-and-conquer strategy so that only subsets of the internal state, associated with different keystream vectors, are recovered first and merged carefully later to retrieve the full large internal state. A self-contained method is introduced and improved to derive the target subset of the internal state from the partial state difference efficiently. As an application, we propose a new key recovery attack on Grain v1, one of the 7 finalists selected by the eSTREAM project, in the single-key setting. Both the pre-computation and the online phases are tailored according to its internal structure, to provide an attack for any fixed IV in 275.7\\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^{75.7}$$\\end{document} cipher ticks after the pre-computation of 28.1\\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^{8.1}$$\\end{document} cipher ticks, given 228\\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^{28}$$\\end{document}-bit memory and about 219\\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^{19}$$\\end{document} keystream bits. Practical experiments on Grain v1 itself whenever possible and on a 80-bit reduced version confirmed our results.", 
    "editor": [
      {
        "familyName": "Nielsen", 
        "givenName": "Jesper Buus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rijmen", 
        "givenName": "Vincent", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-78375-8_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-78374-1", 
        "978-3-319-78375-8"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "V1", 
      "attacks", 
      "large number", 
      "only subsets", 
      "subset", 
      "target subset", 
      "state differences", 
      "differences", 
      "setting", 
      "internal structure", 
      "ticks", 
      "fast", 
      "modern stream ciphers", 
      "stream cipher", 
      "internal states", 
      "state", 
      "number", 
      "variables", 
      "recovery attack", 
      "method", 
      "collision attack", 
      "situation", 
      "properties", 
      "divide", 
      "strategies", 
      "vector", 
      "new key recovery attack", 
      "key recovery attack", 
      "project", 
      "single-key setting", 
      "online phase", 
      "phase", 
      "memory", 
      "experiments", 
      "version", 
      "results", 
      "cipher", 
      "large internal state", 
      "cryptanalyst", 
      "state recovery attack", 
      "paper", 
      "new cryptanalytic method", 
      "cryptanalytic methods", 
      "collision properties", 
      "conquer strategy", 
      "self-contained method", 
      "applications", 
      "Grain v1", 
      "finalists", 
      "structure", 
      "cipher ticks", 
      "keystream bits", 
      "bits", 
      "practical experiments", 
      "general new cryptanalytic method", 
      "near collision property", 
      "full large internal state", 
      "partial state difference", 
      "Grain v1 stream cipher", 
      "v1 Stream Cipher"
    ], 
    "name": "Fast Near Collision Attack on the Grain v1 Stream Cipher", 
    "pagination": "771-802", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1101874795"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-78375-8_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-78375-8_25", 
      "https://app.dimensions.ai/details/publication/pub.1101874795"
    ], 
    "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_203.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-78375-8_25"
  }
]
 

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-78375-8_25'

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-78375-8_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-78375-8_25'

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-78375-8_25'


 

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

149 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-78375-8_25 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N953021f354164a6b8d0bbe944d9fb30c
4 schema:datePublished 2018-03-31
5 schema:datePublishedReg 2018-03-31
6 schema:description Modern stream ciphers often adopt a large internal state to resist various attacks, where the cryptanalysts have to deal with a large number of variables when mounting state recovery attacks. In this paper, we propose a general new cryptanalytic method on stream ciphers, called fast near collision attack, to address this situation. It combines a near collision property with the divide-and-conquer strategy so that only subsets of the internal state, associated with different keystream vectors, are recovered first and merged carefully later to retrieve the full large internal state. A self-contained method is introduced and improved to derive the target subset of the internal state from the partial state difference efficiently. As an application, we propose a new key recovery attack on Grain v1, one of the 7 finalists selected by the eSTREAM project, in the single-key setting. Both the pre-computation and the online phases are tailored according to its internal structure, to provide an attack for any fixed IV in 275.7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{75.7}$$\end{document} cipher ticks after the pre-computation of 28.1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{8.1}$$\end{document} cipher ticks, given 228\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{28}$$\end{document}-bit memory and about 219\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{19}$$\end{document} keystream bits. Practical experiments on Grain v1 itself whenever possible and on a 80-bit reduced version confirmed our results.
7 schema:editor Nde9f3a0a46c2477995b0bf8b647486dd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8ce68632cce1403a98d68c83ea2513d6
12 schema:keywords Grain v1
13 Grain v1 stream cipher
14 V1
15 applications
16 attacks
17 bits
18 cipher
19 cipher ticks
20 collision attack
21 collision properties
22 conquer strategy
23 cryptanalyst
24 cryptanalytic methods
25 differences
26 divide
27 experiments
28 fast
29 finalists
30 full large internal state
31 general new cryptanalytic method
32 internal states
33 internal structure
34 key recovery attack
35 keystream bits
36 large internal state
37 large number
38 memory
39 method
40 modern stream ciphers
41 near collision property
42 new cryptanalytic method
43 new key recovery attack
44 number
45 online phase
46 only subsets
47 paper
48 partial state difference
49 phase
50 practical experiments
51 project
52 properties
53 recovery attack
54 results
55 self-contained method
56 setting
57 single-key setting
58 situation
59 state
60 state differences
61 state recovery attack
62 strategies
63 stream cipher
64 structure
65 subset
66 target subset
67 ticks
68 v1 Stream Cipher
69 variables
70 vector
71 version
72 schema:name Fast Near Collision Attack on the Grain v1 Stream Cipher
73 schema:pagination 771-802
74 schema:productId Nb39c6aba8cd545458f4aaa7244f2ee31
75 Nba6d9d3236c142a7b6b9cb77bc33f860
76 schema:publisher N66af3821c38c43128cb2c040f3f44b82
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101874795
78 https://doi.org/10.1007/978-3-319-78375-8_25
79 schema:sdDatePublished 2022-01-01T19:12
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher N788018bd56ad473383bce074e98d0e5c
82 schema:url https://doi.org/10.1007/978-3-319-78375-8_25
83 sgo:license sg:explorer/license/
84 sgo:sdDataset chapters
85 rdf:type schema:Chapter
86 N1eec7752bae44bfab842a2914456b0c3 schema:familyName Nielsen
87 schema:givenName Jesper Buus
88 rdf:type schema:Person
89 N34b6dffa1ec841ca9c8a76910be2b9e5 rdf:first sg:person.015403636457.52
90 rdf:rest N379bfffd92154a3cbc3bf42195e65862
91 N379bfffd92154a3cbc3bf42195e65862 rdf:first sg:person.07653531142.18
92 rdf:rest rdf:nil
93 N66af3821c38c43128cb2c040f3f44b82 schema:name Springer Nature
94 rdf:type schema:Organisation
95 N788018bd56ad473383bce074e98d0e5c schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 N8ce68632cce1403a98d68c83ea2513d6 schema:isbn 978-3-319-78374-1
98 978-3-319-78375-8
99 schema:name Advances in Cryptology – EUROCRYPT 2018
100 rdf:type schema:Book
101 N8fc4497f27f9422b8ed1abcf5290442f schema:familyName Rijmen
102 schema:givenName Vincent
103 rdf:type schema:Person
104 N953021f354164a6b8d0bbe944d9fb30c rdf:first sg:person.014125113140.40
105 rdf:rest N34b6dffa1ec841ca9c8a76910be2b9e5
106 Nb39c6aba8cd545458f4aaa7244f2ee31 schema:name dimensions_id
107 schema:value pub.1101874795
108 rdf:type schema:PropertyValue
109 Nba6d9d3236c142a7b6b9cb77bc33f860 schema:name doi
110 schema:value 10.1007/978-3-319-78375-8_25
111 rdf:type schema:PropertyValue
112 Nd5e3adc8532d496f89f50a5292e98458 rdf:first N8fc4497f27f9422b8ed1abcf5290442f
113 rdf:rest rdf:nil
114 Nde9f3a0a46c2477995b0bf8b647486dd rdf:first N1eec7752bae44bfab842a2914456b0c3
115 rdf:rest Nd5e3adc8532d496f89f50a5292e98458
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
120 schema:name Computation Theory and Mathematics
121 rdf:type schema:DefinedTerm
122 sg:person.014125113140.40 schema:affiliation grid-institutes:grid.458480.5
123 schema:familyName Zhang
124 schema:givenName Bin
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014125113140.40
126 rdf:type schema:Person
127 sg:person.015403636457.52 schema:affiliation grid-institutes:grid.496622.d
128 schema:familyName Xu
129 schema:givenName Chao
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015403636457.52
131 rdf:type schema:Person
132 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
133 schema:familyName Meier
134 schema:givenName Willi
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
136 rdf:type schema:Person
137 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
138 schema:name FHNW, Windisch, Switzerland
139 rdf:type schema:Organization
140 grid-institutes:grid.458480.5 schema:alternateName State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
141 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
142 State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
143 TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
144 University of Chinese Academy of Sciences, 100049, Beijing, China
145 rdf:type schema:Organization
146 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
147 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
148 TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
149 rdf:type schema:Organization
 




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


...