Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1 View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2021-10-18

AUTHORS

Mingxing Wang , Yonglin Hao

ABSTRACT

At ASIACRYPT 2019, Zhang proposes a near collision attack on A5/1. He claims that such an attack method can recover the 64-bit A5/1 state with a time complexity around 232\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{32}$$\end{document} cipher ticks and requires negligible memory complexities. Soon after its proposal, Zhang’s near collision attack is severely challenged by Derbez et al. who claim that Zhang’s attack cannot have a time complexity lower than Golic’s memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. In order to make a fair comparison, we recover the state s0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{s}^0$$\end{document} using both methods. We propose a new guessing technique that can construct linear equation filters in a more efficient manner. When evaluating time complexities, we take the filtering strength of the linear equation systems into account making the complexities more convincing. According to our detailed analysis, the new guess-and-determine attack can recover the state s0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{s}^0$$\end{document} with a time complexity of 243.91\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{43.91}$$\end{document} simple operations. The time complexity for the near collision attack is 250.57\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{50.57}$$\end{document} simple operations. More... »

PAGES

191-211

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-88323-2_10

DOI

http://dx.doi.org/10.1007/978-3-030-88323-2_10

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "The 6th Research Institute of China Electronics Corporation, 100083, Beijing, China", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China", 
            "The 6th Research Institute of China Electronics Corporation, 100083, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Mingxing", 
        "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": [
            "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"
      }
    ], 
    "datePublished": "2021-10-18", 
    "datePublishedReg": "2021-10-18", 
    "description": "At ASIACRYPT 2019, Zhang proposes a near collision attack on A5/1. He claims that such an attack method can recover the 64-bit A5/1 state with a time complexity around 232\\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^{32}$$\\end{document} cipher ticks and requires negligible memory complexities. Soon after its proposal, Zhang\u2019s near collision attack is severely challenged by Derbez et al. who claim that Zhang\u2019s attack cannot have a time complexity lower than Golic\u2019s memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. In order to make a fair comparison, we recover the state s0\\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}$$\\boldsymbol{s}^0$$\\end{document} using both methods. We propose a new guessing technique that can construct linear equation filters in a more efficient manner. When evaluating time complexities, we take the filtering strength of the linear equation systems into account making the complexities more convincing. According to our detailed analysis, the new guess-and-determine attack can recover the state s0\\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}$$\\boldsymbol{s}^0$$\\end{document} with a time complexity of 243.91\\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^{43.91}$$\\end{document} simple operations. The time complexity for the near collision attack is 250.57\\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^{50.57}$$\\end{document} simple operations.", 
    "editor": [
      {
        "familyName": "Yu", 
        "givenName": "Yu", 
        "type": "Person"
      }, 
      {
        "familyName": "Yung", 
        "givenName": "Moti", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-88323-2_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-88322-5", 
        "978-3-030-88323-2"
      ], 
      "name": "Information Security and Cryptology", 
      "type": "Book"
    }, 
    "keywords": [
      "time complexity", 
      "linear equation system", 
      "memory complexity", 
      "equation system", 
      "new guess", 
      "determine attack", 
      "guess", 
      "cryptanalysis methods", 
      "efficient manner", 
      "filtering strength", 
      "complexity", 
      "fair comparison", 
      "Zhang", 
      "et al", 
      "attack methods", 
      "simple operation", 
      "detailed analysis", 
      "state", 
      "filter", 
      "operation", 
      "account", 
      "system", 
      "collision attack", 
      "order", 
      "technique", 
      "al", 
      "comparison", 
      "attacks", 
      "proposal", 
      "determine", 
      "analysis", 
      "strength", 
      "manner", 
      "ticks", 
      "method", 
      "paper", 
      "ASIACRYPT 2019", 
      "near-collision attack", 
      "cipher ticks"
    ], 
    "name": "Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1", 
    "pagination": "191-211", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1141950821"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-88323-2_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-88323-2_10", 
      "https://app.dimensions.ai/details/publication/pub.1141950821"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:34", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_417.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-88323-2_10"
  }
]
 

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-88323-2_10'

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-88323-2_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-88323-2_10'

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-88323-2_10'


 

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

114 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-88323-2_10 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Nb203bb8b71be4455985143420aefe9dc
4 schema:datePublished 2021-10-18
5 schema:datePublishedReg 2021-10-18
6 schema:description At ASIACRYPT 2019, Zhang proposes a near collision attack on A5/1. He claims that such an attack method can recover the 64-bit A5/1 state with a time complexity around 232\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{32}$$\end{document} cipher ticks and requires negligible memory complexities. Soon after its proposal, Zhang’s near collision attack is severely challenged by Derbez et al. who claim that Zhang’s attack cannot have a time complexity lower than Golic’s memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. In order to make a fair comparison, we recover the state s0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{s}^0$$\end{document} using both methods. We propose a new guessing technique that can construct linear equation filters in a more efficient manner. When evaluating time complexities, we take the filtering strength of the linear equation systems into account making the complexities more convincing. According to our detailed analysis, the new guess-and-determine attack can recover the state s0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{s}^0$$\end{document} with a time complexity of 243.91\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{43.91}$$\end{document} simple operations. The time complexity for the near collision attack is 250.57\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{50.57}$$\end{document} simple operations.
7 schema:editor N815fc605196341ecaa56525ae191adfd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc571da262b29434b9ff675f2afb291d4
12 schema:keywords ASIACRYPT 2019
13 Zhang
14 account
15 al
16 analysis
17 attack methods
18 attacks
19 cipher ticks
20 collision attack
21 comparison
22 complexity
23 cryptanalysis methods
24 detailed analysis
25 determine
26 determine attack
27 efficient manner
28 equation system
29 et al
30 fair comparison
31 filter
32 filtering strength
33 guess
34 linear equation system
35 manner
36 memory complexity
37 method
38 near-collision attack
39 new guess
40 operation
41 order
42 paper
43 proposal
44 simple operation
45 state
46 strength
47 system
48 technique
49 ticks
50 time complexity
51 schema:name Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1
52 schema:pagination 191-211
53 schema:productId N37cfd815595d4494aefda90cdb873918
54 N5baff1b5061e47809633b36051087c53
55 schema:publisher Na9d0b8428a2049969e609cd92041f8fe
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1141950821
57 https://doi.org/10.1007/978-3-030-88323-2_10
58 schema:sdDatePublished 2022-06-01T22:34
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N8d741cad1cb346f29fba33fc798d80e3
61 schema:url https://doi.org/10.1007/978-3-030-88323-2_10
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N24f4974a3ca24835a75f192080cae393 schema:familyName Yu
66 schema:givenName Yu
67 rdf:type schema:Person
68 N37cfd815595d4494aefda90cdb873918 schema:name dimensions_id
69 schema:value pub.1141950821
70 rdf:type schema:PropertyValue
71 N58785144c8c74b6c91a37a4d64626bef schema:familyName Yung
72 schema:givenName Moti
73 rdf:type schema:Person
74 N5b70f73ac9304204a4bc9870997d288a rdf:first N58785144c8c74b6c91a37a4d64626bef
75 rdf:rest rdf:nil
76 N5baff1b5061e47809633b36051087c53 schema:name doi
77 schema:value 10.1007/978-3-030-88323-2_10
78 rdf:type schema:PropertyValue
79 N722cbbd4980b446283a21c9f9e32d267 rdf:first sg:person.014270173173.47
80 rdf:rest rdf:nil
81 N815fc605196341ecaa56525ae191adfd rdf:first N24f4974a3ca24835a75f192080cae393
82 rdf:rest N5b70f73ac9304204a4bc9870997d288a
83 N8d741cad1cb346f29fba33fc798d80e3 schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 Na9d0b8428a2049969e609cd92041f8fe schema:name Springer Nature
86 rdf:type schema:Organisation
87 Nb203bb8b71be4455985143420aefe9dc rdf:first Nef6faa129be14761be9a2ef0d8bdcef2
88 rdf:rest N722cbbd4980b446283a21c9f9e32d267
89 Nc571da262b29434b9ff675f2afb291d4 schema:isbn 978-3-030-88322-5
90 978-3-030-88323-2
91 schema:name Information Security and Cryptology
92 rdf:type schema:Book
93 Nef6faa129be14761be9a2ef0d8bdcef2 schema:affiliation grid-institutes:None
94 schema:familyName Wang
95 schema:givenName Mingxing
96 rdf:type schema:Person
97 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
98 schema:name Mathematical Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
101 schema:name Statistics
102 rdf:type schema:DefinedTerm
103 sg:person.014270173173.47 schema:affiliation grid-institutes:grid.496622.d
104 schema:familyName Hao
105 schema:givenName Yonglin
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47
107 rdf:type schema:Person
108 grid-institutes:None schema:alternateName The 6th Research Institute of China Electronics Corporation, 100083, Beijing, China
109 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
110 The 6th Research Institute of China Electronics Corporation, 100083, Beijing, China
111 rdf:type schema:Organization
112 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
113 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
114 rdf:type schema:Organization
 




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


...