sg:pub.10.1007/978-3-030-88323-2_10 - Springer Nature SciGraph

Chapter Info

DATE

2021-10-18

AUTHORS

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

Book

TITLE

Information Security and Cryptology

ISBN

978-3-030-88322-5
978-3-030-88323-2

Subjects

FOR: Mathematical Sciences

FOR: Statistics

Author Affiliations

The 6th Research Institute of China Electronics Corporation, 100083, Beijing, China

State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China

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

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

Chapter Info

Book

Subjects

Author Affiliations

Identifiers