On the Influence of Message Length in PMAC’s Security Bounds View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016-04-28

AUTHORS

Atul Luykx , Bart Preneel , Alan Szepieniec , Kan Yasuda

ABSTRACT

Many MAC (Message Authentication Code) algorithms have security bounds which degrade linearly with the message length. Often there are attacks that confirm the linear dependence on the message length, yet PMAC has remained without attacks. Our results show that PMAC’s message length dependence in security bounds is non-trivial. We start by studying a generalization of PMAC in order to focus on PMAC’s basic structure. By abstracting away details, we are able to show that there are two possibilities: either there are infinitely many instantiations of generic PMAC with security bounds independent of the message length, or finding an attack against generic PMAC which establishes message length dependence is computationally hard. The latter statement relies on a conjecture on the difficulty of finding subsets of a finite field summing to zero or satisfying a binary quadratic form. Using the insights gained from studying PMAC’s basic structure, we then shift our attention to the original instantiation of PMAC, namely, with Gray codes. Despite the initial results on generic PMAC, we show that PMAC with Gray codes is one of the more insecure instantiations of PMAC, by illustrating an attack which roughly establishes a linear dependence on the message length. More... »

PAGES

596-621

Book

TITLE

Advances in Cryptology – EUROCRYPT 2016

ISBN

978-3-662-49889-7
978-3-662-49890-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-49890-3_23

DOI

http://dx.doi.org/10.1007/978-3-662-49890-3_23

DIMENSIONS

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


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": "NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.419819.c", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium", 
            "iMinds, Ghent, Belgium", 
            "NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Luykx", 
        "givenName": "Atul", 
        "id": "sg:person.010234250021.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010234250021.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "iMinds, Ghent, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.56912.39", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium", 
            "iMinds, Ghent, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "id": "sg:person.011115044357.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "iMinds, Ghent, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.56912.39", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium", 
            "iMinds, Ghent, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szepieniec", 
        "givenName": "Alan", 
        "id": "sg:person.013013776035.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.419819.c", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium", 
            "NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yasuda", 
        "givenName": "Kan", 
        "id": "sg:person.016111147443.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016111147443.09"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-04-28", 
    "datePublishedReg": "2016-04-28", 
    "description": "Many MAC (Message Authentication Code) algorithms have security bounds which degrade linearly with the message length. Often there are attacks that confirm the linear dependence on the message length, yet PMAC has remained without attacks. Our results show that PMAC\u2019s message length dependence in security bounds is non-trivial. We start by studying a generalization of PMAC in order to focus on PMAC\u2019s basic structure. By abstracting away details, we are able to show that there are two possibilities: either there are infinitely many instantiations of generic PMAC with security bounds independent of the message length, or finding an attack against generic PMAC which establishes message length dependence is computationally hard. The latter statement relies on a conjecture on the difficulty of finding subsets of a finite field summing to zero or satisfying a binary quadratic form. Using the insights gained from studying PMAC\u2019s basic structure, we then shift our attention to the original instantiation of PMAC, namely, with Gray codes. Despite the initial results on generic PMAC, we show that PMAC with Gray codes is one of the more insecure instantiations of PMAC, by illustrating an attack which roughly establishes a linear dependence on the message length.", 
    "editor": [
      {
        "familyName": "Fischlin", 
        "givenName": "Marc", 
        "type": "Person"
      }, 
      {
        "familyName": "Coron", 
        "givenName": "Jean-S\u00e9bastien", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-49890-3_23", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-49889-7", 
        "978-3-662-49890-3"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "message length", 
      "security bounds", 
      "Gray code", 
      "MAC algorithm", 
      "original instantiation", 
      "instantiation", 
      "attacks", 
      "basic structure", 
      "PMAC", 
      "finite field", 
      "code", 
      "initial results", 
      "algorithm", 
      "bounds", 
      "generalization", 
      "order", 
      "results", 
      "subset", 
      "detail", 
      "difficulties", 
      "attention", 
      "field", 
      "structure", 
      "quadratic form", 
      "latter statement", 
      "statements", 
      "possibility", 
      "binary quadratic forms", 
      "insights", 
      "form", 
      "length", 
      "conjecture", 
      "influence", 
      "dependence", 
      "linear dependence", 
      "length dependence"
    ], 
    "name": "On the Influence of Message Length in PMAC\u2019s Security Bounds", 
    "pagination": "596-621", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025533121"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-49890-3_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-49890-3_23", 
      "https://app.dimensions.ai/details/publication/pub.1025533121"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_225.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-49890-3_23"
  }
]
 

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-49890-3_23'

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-49890-3_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-49890-3_23'

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-49890-3_23'


 

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

127 TRIPLES      22 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-49890-3_23 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nd6f86faa3e74457e8183d9dce5a811b0
4 schema:datePublished 2016-04-28
5 schema:datePublishedReg 2016-04-28
6 schema:description Many MAC (Message Authentication Code) algorithms have security bounds which degrade linearly with the message length. Often there are attacks that confirm the linear dependence on the message length, yet PMAC has remained without attacks. Our results show that PMAC’s message length dependence in security bounds is non-trivial. We start by studying a generalization of PMAC in order to focus on PMAC’s basic structure. By abstracting away details, we are able to show that there are two possibilities: either there are infinitely many instantiations of generic PMAC with security bounds independent of the message length, or finding an attack against generic PMAC which establishes message length dependence is computationally hard. The latter statement relies on a conjecture on the difficulty of finding subsets of a finite field summing to zero or satisfying a binary quadratic form. Using the insights gained from studying PMAC’s basic structure, we then shift our attention to the original instantiation of PMAC, namely, with Gray codes. Despite the initial results on generic PMAC, we show that PMAC with Gray codes is one of the more insecure instantiations of PMAC, by illustrating an attack which roughly establishes a linear dependence on the message length.
7 schema:editor N95601e50fb3f4a35b004909ff89cbc09
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nd8de111333ef4de6b1baef3f6b5cbd8f
11 schema:keywords Gray code
12 MAC algorithm
13 PMAC
14 algorithm
15 attacks
16 attention
17 basic structure
18 binary quadratic forms
19 bounds
20 code
21 conjecture
22 dependence
23 detail
24 difficulties
25 field
26 finite field
27 form
28 generalization
29 influence
30 initial results
31 insights
32 instantiation
33 latter statement
34 length
35 length dependence
36 linear dependence
37 message length
38 order
39 original instantiation
40 possibility
41 quadratic form
42 results
43 security bounds
44 statements
45 structure
46 subset
47 schema:name On the Influence of Message Length in PMAC’s Security Bounds
48 schema:pagination 596-621
49 schema:productId N148fe46fbec74fd6a73b4a0472cd36a3
50 Nf73e312f04854b0cb9a9612e3a60a1f3
51 schema:publisher N017d0197768e4047ba5e03f3e2588e79
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025533121
53 https://doi.org/10.1007/978-3-662-49890-3_23
54 schema:sdDatePublished 2022-09-02T16:12
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N79c54bba693e463ea53e3ed3713288f5
57 schema:url https://doi.org/10.1007/978-3-662-49890-3_23
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N017d0197768e4047ba5e03f3e2588e79 schema:name Springer Nature
62 rdf:type schema:Organisation
63 N148fe46fbec74fd6a73b4a0472cd36a3 schema:name dimensions_id
64 schema:value pub.1025533121
65 rdf:type schema:PropertyValue
66 N388ed291019d46b0aa51ab800e6397d1 rdf:first sg:person.016111147443.09
67 rdf:rest rdf:nil
68 N57073f23b1034fcaaa155defb232d1ee schema:familyName Coron
69 schema:givenName Jean-Sébastien
70 rdf:type schema:Person
71 N57e731b7624248d6b2996372e8e6e48e schema:familyName Fischlin
72 schema:givenName Marc
73 rdf:type schema:Person
74 N79c54bba693e463ea53e3ed3713288f5 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N85e354f8a073433090f654c638ea23ea rdf:first N57073f23b1034fcaaa155defb232d1ee
77 rdf:rest rdf:nil
78 N95601e50fb3f4a35b004909ff89cbc09 rdf:first N57e731b7624248d6b2996372e8e6e48e
79 rdf:rest N85e354f8a073433090f654c638ea23ea
80 N9ce70d4bec5a44f39e9a5c4d252d34b5 rdf:first sg:person.013013776035.00
81 rdf:rest N388ed291019d46b0aa51ab800e6397d1
82 Nd6f86faa3e74457e8183d9dce5a811b0 rdf:first sg:person.010234250021.33
83 rdf:rest Neebe56dcae2446fcba262fbd28834d13
84 Nd8de111333ef4de6b1baef3f6b5cbd8f schema:isbn 978-3-662-49889-7
85 978-3-662-49890-3
86 schema:name Advances in Cryptology – EUROCRYPT 2016
87 rdf:type schema:Book
88 Neebe56dcae2446fcba262fbd28834d13 rdf:first sg:person.011115044357.39
89 rdf:rest N9ce70d4bec5a44f39e9a5c4d252d34b5
90 Nf73e312f04854b0cb9a9612e3a60a1f3 schema:name doi
91 schema:value 10.1007/978-3-662-49890-3_23
92 rdf:type schema:PropertyValue
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
97 schema:name Data Format
98 rdf:type schema:DefinedTerm
99 sg:person.010234250021.33 schema:affiliation grid-institutes:grid.419819.c
100 schema:familyName Luykx
101 schema:givenName Atul
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010234250021.33
103 rdf:type schema:Person
104 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.56912.39
105 schema:familyName Preneel
106 schema:givenName Bart
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
108 rdf:type schema:Person
109 sg:person.013013776035.00 schema:affiliation grid-institutes:grid.56912.39
110 schema:familyName Szepieniec
111 schema:givenName Alan
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00
113 rdf:type schema:Person
114 sg:person.016111147443.09 schema:affiliation grid-institutes:grid.419819.c
115 schema:familyName Yasuda
116 schema:givenName Kan
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016111147443.09
118 rdf:type schema:Person
119 grid-institutes:grid.419819.c schema:alternateName NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan
120 schema:name Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium
121 NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan
122 iMinds, Ghent, Belgium
123 rdf:type schema:Organization
124 grid-institutes:grid.56912.39 schema:alternateName iMinds, Ghent, Belgium
125 schema:name Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium
126 iMinds, Ghent, Belgium
127 rdf:type schema:Organization
 




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


...