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-12-01T06:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_310.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 Nb811a73be06a40c79bd3bc940dae66ff
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 N05074d46325a4ef085020a536e5fd9c5
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N2d7659beecdd4765966b07bfc1a6eff3
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 Na43c5b6b40424e7d9aa927bd284354cf
50 Nc37061e869864400b1143fd397170fe4
51 schema:publisher Ndff2d2a34def48a5a5743b6ce14025af
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-12-01T06:51
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N0aaabe13b5374ea4994f3fbe33bf2b72
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 N05074d46325a4ef085020a536e5fd9c5 rdf:first N17f0c6c60d9e4df59c6383d011b574ba
62 rdf:rest N6805a18cef3049938c8d6e4dfc47b149
63 N0aaabe13b5374ea4994f3fbe33bf2b72 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N17f0c6c60d9e4df59c6383d011b574ba schema:familyName Fischlin
66 schema:givenName Marc
67 rdf:type schema:Person
68 N2d7659beecdd4765966b07bfc1a6eff3 schema:isbn 978-3-662-49889-7
69 978-3-662-49890-3
70 schema:name Advances in Cryptology – EUROCRYPT 2016
71 rdf:type schema:Book
72 N6805a18cef3049938c8d6e4dfc47b149 rdf:first N9a2ecfe8fa1b414ea1a87ec3dcead696
73 rdf:rest rdf:nil
74 N6dce67f73b344eb7a716cf090a77d4d5 rdf:first sg:person.013013776035.00
75 rdf:rest N8b0a6929c6f049549937c24da5e9b604
76 N8b0a6929c6f049549937c24da5e9b604 rdf:first sg:person.016111147443.09
77 rdf:rest rdf:nil
78 N9a2ecfe8fa1b414ea1a87ec3dcead696 schema:familyName Coron
79 schema:givenName Jean-Sébastien
80 rdf:type schema:Person
81 Na43c5b6b40424e7d9aa927bd284354cf schema:name dimensions_id
82 schema:value pub.1025533121
83 rdf:type schema:PropertyValue
84 Nb811a73be06a40c79bd3bc940dae66ff rdf:first sg:person.010234250021.33
85 rdf:rest Nc227fc764ec8442ebd23396921c240e3
86 Nc227fc764ec8442ebd23396921c240e3 rdf:first sg:person.011115044357.39
87 rdf:rest N6dce67f73b344eb7a716cf090a77d4d5
88 Nc37061e869864400b1143fd397170fe4 schema:name doi
89 schema:value 10.1007/978-3-662-49890-3_23
90 rdf:type schema:PropertyValue
91 Ndff2d2a34def48a5a5743b6ce14025af schema:name Springer Nature
92 rdf:type schema:Organisation
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)


...