Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2021-08-11

AUTHORS

Fukang Liu , Takanori Isobe , Willi Meier

ABSTRACT

In this paper, we revisit the difference enumeration technique for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks. In the original difference enumeration attack framework, an inevitable step is to precompute and store a set of intermediate state differences for efficient checking via the binary search. Our first observation is that Bar-On et al.’s general algebraic technique developed for SPNs with partial nonlinear layers can be utilized to fulfill the same task, which can make the memory complexity negligible as there is no need to store a huge set of state differences any more. Benefiting from this technique, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. at ToSC 2018. Combining both techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative third-round candidate in NIST’s Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a concrete LowMC instance. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor cipher LowMC-M as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed 264\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{64}$$\end{document} data. The above mentioned attacks are all achieved with negligible memory. More... »

PAGES

368-401

Book

TITLE

Advances in Cryptology – CRYPTO 2021

ISBN

978-3-030-84251-2
978-3-030-84252-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-84252-9_13

DOI

http://dx.doi.org/10.1007/978-3-030-84252-9_13

DIMENSIONS

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


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": "University of Hyogo, Hyogo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.266453.0", 
          "name": [
            "East China Normal University, Shanghai, China", 
            "University of Hyogo, Hyogo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Fukang", 
        "id": "sg:person.07532571712.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07532571712.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "PRESTO, Japan Science and Technology Agency, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.419082.6", 
          "name": [
            "University of Hyogo, Hyogo, Japan", 
            "National Institute of Information and Communications Technology, Tokyo, Japan", 
            "PRESTO, Japan Science and Technology Agency, Tokyo, 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"
      }
    ], 
    "datePublished": "2021-08-11", 
    "datePublishedReg": "2021-08-11", 
    "description": "In this paper, we revisit the difference enumeration technique for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks. In the original difference enumeration attack framework, an inevitable step is to precompute and store a set of intermediate state differences for efficient checking via the binary search. Our first observation is that Bar-On et al.\u2019s general algebraic technique developed for SPNs with partial nonlinear layers can be utilized to fulfill the same task, which can make the memory complexity negligible as there is no need to store a huge set of state differences any more. Benefiting from this technique, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. at ToSC 2018. Combining both techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative third-round candidate in NIST\u2019s Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a concrete LowMC instance. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor cipher LowMC-M as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed 264\\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^{64}$$\\end{document} data. The above mentioned attacks are all achieved with negligible memory.", 
    "editor": [
      {
        "familyName": "Malkin", 
        "givenName": "Tal", 
        "type": "Person"
      }, 
      {
        "familyName": "Peikert", 
        "givenName": "Chris", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-84252-9_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-84251-2", 
        "978-3-030-84252-9"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2021", 
      "type": "Book"
    }, 
    "keywords": [
      "NIST post-quantum cryptography competition", 
      "block size", 
      "algebraic techniques", 
      "third-round candidate", 
      "efficient key-recovery attack", 
      "key recovery techniques", 
      "efficient checking", 
      "attack framework", 
      "key size", 
      "huge set", 
      "memory complexity", 
      "key recovery attack", 
      "binary search", 
      "output messages", 
      "LowMC", 
      "negligible memory", 
      "full key", 
      "full use", 
      "kinds of parameters", 
      "plaintext", 
      "attacks", 
      "enumeration technique", 
      "same task", 
      "inevitable step", 
      "encrypt", 
      "attacker", 
      "more rounds", 
      "backdoor", 
      "checking", 
      "set", 
      "cryptanalysis", 
      "instances", 
      "technique", 
      "task", 
      "messages", 
      "complexity", 
      "bits", 
      "framework", 
      "nonlinear layer", 
      "key", 
      "search", 
      "such parameters", 
      "input", 
      "BOX layer", 
      "memory", 
      "rounds", 
      "kind", 
      "interesting questions", 
      "et al", 
      "new algebraic technique", 
      "step", 
      "need", 
      "single pair", 
      "data", 
      "parameters", 
      "hand", 
      "time", 
      "layer", 
      "use", 
      "size", 
      "SPN", 
      "Wang", 
      "trails", 
      "pairs", 
      "competition", 
      "Peyrin", 
      "state differences", 
      "questions", 
      "candidates", 
      "picnic", 
      "al", 
      "observations", 
      "differences", 
      "bar", 
      "first observation", 
      "paper", 
      "general algebraic technique", 
      "difference enumeration technique", 
      "original difference enumeration attack framework", 
      "difference enumeration attack framework", 
      "enumeration attack framework", 
      "intermediate state differences", 
      "partial nonlinear layers", 
      "new key-recovery technique", 
      "difference trail", 
      "Rechberger et al", 
      "ToSC 2018", 
      "rounds of LowMC", 
      "Picnic3", 
      "alternative third-round candidate", 
      "\u2019s Post-Quantum Cryptography competition", 
      "Cryptography competition", 
      "concrete LowMC instance", 
      "LowMC instance", 
      "latest LowMC", 
      "backdoor cipher LowMC", 
      "cipher LowMC", 
      "CRYPTO 2020", 
      "Full LowMC"
    ], 
    "name": "Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques", 
    "pagination": "368-401", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1140318669"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-84252-9_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-84252-9_13", 
      "https://app.dimensions.ai/details/publication/pub.1140318669"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:25", 
    "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_437.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-84252-9_13"
  }
]
 

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-84252-9_13'

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-84252-9_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-84252-9_13'

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-84252-9_13'


 

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

187 TRIPLES      23 PREDICATES      124 URIs      117 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-84252-9_13 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nfa07d5d9b85a47a6af02c33d16ec229d
4 schema:datePublished 2021-08-11
5 schema:datePublishedReg 2021-08-11
6 schema:description In this paper, we revisit the difference enumeration technique for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks. In the original difference enumeration attack framework, an inevitable step is to precompute and store a set of intermediate state differences for efficient checking via the binary search. Our first observation is that Bar-On et al.’s general algebraic technique developed for SPNs with partial nonlinear layers can be utilized to fulfill the same task, which can make the memory complexity negligible as there is no need to store a huge set of state differences any more. Benefiting from this technique, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. at ToSC 2018. Combining both techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative third-round candidate in NIST’s Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a concrete LowMC instance. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor cipher LowMC-M as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed 264\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{64}$$\end{document} data. The above mentioned attacks are all achieved with negligible memory.
7 schema:editor Ncc20fd665f1c49f6ba52b7f1104d7540
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc4368ab459944653873eac5412b45c8f
12 schema:keywords BOX layer
13 CRYPTO 2020
14 Cryptography competition
15 Full LowMC
16 LowMC
17 LowMC instance
18 NIST post-quantum cryptography competition
19 Peyrin
20 Picnic3
21 Rechberger et al
22 SPN
23 ToSC 2018
24 Wang
25 al
26 algebraic techniques
27 alternative third-round candidate
28 attack framework
29 attacker
30 attacks
31 backdoor
32 backdoor cipher LowMC
33 bar
34 binary search
35 bits
36 block size
37 candidates
38 checking
39 cipher LowMC
40 competition
41 complexity
42 concrete LowMC instance
43 cryptanalysis
44 data
45 difference enumeration attack framework
46 difference enumeration technique
47 difference trail
48 differences
49 efficient checking
50 efficient key-recovery attack
51 encrypt
52 enumeration attack framework
53 enumeration technique
54 et al
55 first observation
56 framework
57 full key
58 full use
59 general algebraic technique
60 hand
61 huge set
62 inevitable step
63 input
64 instances
65 interesting questions
66 intermediate state differences
67 key
68 key recovery attack
69 key recovery techniques
70 key size
71 kind
72 kinds of parameters
73 latest LowMC
74 layer
75 memory
76 memory complexity
77 messages
78 more rounds
79 need
80 negligible memory
81 new algebraic technique
82 new key-recovery technique
83 nonlinear layer
84 observations
85 original difference enumeration attack framework
86 output messages
87 pairs
88 paper
89 parameters
90 partial nonlinear layers
91 picnic
92 plaintext
93 questions
94 rounds
95 rounds of LowMC
96 same task
97 search
98 set
99 single pair
100 size
101 state differences
102 step
103 such parameters
104 task
105 technique
106 third-round candidate
107 time
108 trails
109 use
110 ’s Post-Quantum Cryptography competition
111 schema:name Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques
112 schema:pagination 368-401
113 schema:productId Nc50f5df577c44f87b1b02d93f906cf0b
114 Ne490763ec12e4e4aa5da82467a4aa87f
115 schema:publisher N8a29ac54268f49faab94cf541661b469
116 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140318669
117 https://doi.org/10.1007/978-3-030-84252-9_13
118 schema:sdDatePublished 2022-01-01T19:25
119 schema:sdLicense https://scigraph.springernature.com/explorer/license/
120 schema:sdPublisher N9a8e5098c71e4c389d6c96fb56ba2027
121 schema:url https://doi.org/10.1007/978-3-030-84252-9_13
122 sgo:license sg:explorer/license/
123 sgo:sdDataset chapters
124 rdf:type schema:Chapter
125 N0c10eb5c985948ea97c425ce9719dd88 rdf:first sg:person.07676572757.38
126 rdf:rest Nde8f91ad44254445b49e3d3d64910f6a
127 N20266937ae8a40938776c1765c37e03e rdf:first N9eef8ad5b532417b83ec5da3731e0282
128 rdf:rest rdf:nil
129 N8a29ac54268f49faab94cf541661b469 schema:name Springer Nature
130 rdf:type schema:Organisation
131 N9a8e5098c71e4c389d6c96fb56ba2027 schema:name Springer Nature - SN SciGraph project
132 rdf:type schema:Organization
133 N9eef8ad5b532417b83ec5da3731e0282 schema:familyName Peikert
134 schema:givenName Chris
135 rdf:type schema:Person
136 Nb30a5131d54a4f0da0838c0be47a7379 schema:familyName Malkin
137 schema:givenName Tal
138 rdf:type schema:Person
139 Nc4368ab459944653873eac5412b45c8f schema:isbn 978-3-030-84251-2
140 978-3-030-84252-9
141 schema:name Advances in Cryptology – CRYPTO 2021
142 rdf:type schema:Book
143 Nc50f5df577c44f87b1b02d93f906cf0b schema:name doi
144 schema:value 10.1007/978-3-030-84252-9_13
145 rdf:type schema:PropertyValue
146 Ncc20fd665f1c49f6ba52b7f1104d7540 rdf:first Nb30a5131d54a4f0da0838c0be47a7379
147 rdf:rest N20266937ae8a40938776c1765c37e03e
148 Nde8f91ad44254445b49e3d3d64910f6a rdf:first sg:person.07653531142.18
149 rdf:rest rdf:nil
150 Ne490763ec12e4e4aa5da82467a4aa87f schema:name dimensions_id
151 schema:value pub.1140318669
152 rdf:type schema:PropertyValue
153 Nfa07d5d9b85a47a6af02c33d16ec229d rdf:first sg:person.07532571712.87
154 rdf:rest N0c10eb5c985948ea97c425ce9719dd88
155 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
156 schema:name Information and Computing Sciences
157 rdf:type schema:DefinedTerm
158 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
159 schema:name Data Format
160 rdf:type schema:DefinedTerm
161 sg:person.07532571712.87 schema:affiliation grid-institutes:grid.266453.0
162 schema:familyName Liu
163 schema:givenName Fukang
164 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07532571712.87
165 rdf:type schema:Person
166 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
167 schema:familyName Meier
168 schema:givenName Willi
169 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
170 rdf:type schema:Person
171 sg:person.07676572757.38 schema:affiliation grid-institutes:grid.419082.6
172 schema:familyName Isobe
173 schema:givenName Takanori
174 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07676572757.38
175 rdf:type schema:Person
176 grid-institutes:grid.266453.0 schema:alternateName University of Hyogo, Hyogo, Japan
177 schema:name East China Normal University, Shanghai, China
178 University of Hyogo, Hyogo, Japan
179 rdf:type schema:Organization
180 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
181 schema:name FHNW, Windisch, Switzerland
182 rdf:type schema:Organization
183 grid-institutes:grid.419082.6 schema:alternateName PRESTO, Japan Science and Technology Agency, Tokyo, Japan
184 schema:name National Institute of Information and Communications Technology, Tokyo, Japan
185 PRESTO, Japan Science and Technology Agency, Tokyo, Japan
186 University of Hyogo, Hyogo, Japan
187 rdf:type schema:Organization
 




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


...