Optimal Forgeries Against Polynomial-Based MACs and GCM View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-03-31

AUTHORS

Atul Luykx , Bart Preneel

ABSTRACT

Polynomial-based authentication algorithms, such as GCM and Poly1305, have seen widespread adoption in practice. Due to their importance, a significant amount of attention has been given to understanding and improving both proofs and attacks against such schemes. At EUROCRYPT 2005, Bernstein published the best known analysis of the schemes when instantiated with PRPs, thereby establishing the most lenient limits on the amount of data the schemes can process per key. A long line of work, initiated by Handschuh and Preneel at CRYPTO 2008, finds the best known attacks, advancing our understanding of the fragility of the schemes. Yet surprisingly, no known attacks perform as well as the predicted worst-case attacks allowed by Bernstein’s analysis, nor has there been any advancement in proofs improving Bernstein’s bounds, and the gap between attacks and analysis is significant. We settle the issue by finding a novel attack against polynomial-based authentication algorithms using PRPs, and combine it with new analysis, to show that Bernstein’s bound, and our attacks, are optimal. More... »

PAGES

445-467

Book

TITLE

Advances in Cryptology – EUROCRYPT 2018

ISBN

978-3-319-78380-2
978-3-319-78381-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-78381-9_17

DOI

http://dx.doi.org/10.1007/978-3-319-78381-9_17

DIMENSIONS

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


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": "Visa Research, Palo Alto, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Visa Research, Palo Alto, USA"
          ], 
          "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": "imec-COSIC, KU Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC, KU Leuven, Leuven, 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"
      }
    ], 
    "datePublished": "2018-03-31", 
    "datePublishedReg": "2018-03-31", 
    "description": "Polynomial-based authentication algorithms, such as GCM and Poly1305, have seen widespread adoption in practice. Due to their importance, a significant amount of attention has been given to understanding and improving both proofs and attacks against such schemes. At EUROCRYPT 2005, Bernstein published the best known analysis of the schemes when instantiated with PRPs, thereby establishing the most lenient limits on the amount of data the schemes can process per key. A long line of work, initiated by Handschuh and Preneel at CRYPTO 2008, finds the best known attacks, advancing our understanding of the fragility of the schemes. Yet surprisingly, no known attacks perform as well as the predicted worst-case attacks allowed by Bernstein\u2019s analysis, nor has there been any advancement in proofs improving Bernstein\u2019s bounds, and the gap between attacks and analysis is significant. We settle the issue by finding a novel attack against polynomial-based authentication algorithms using PRPs, and combine it with new analysis, to show that Bernstein\u2019s bound, and our attacks, are optimal.", 
    "editor": [
      {
        "familyName": "Nielsen", 
        "givenName": "Jesper Buus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rijmen", 
        "givenName": "Vincent", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-78381-9_17", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-78380-2", 
        "978-3-319-78381-9"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "authentication algorithm", 
      "worst-case attack", 
      "amount of data", 
      "novel attacks", 
      "CRYPTO 2008", 
      "Bernstein bounds", 
      "Eurocrypt 2005", 
      "attacks", 
      "such schemes", 
      "widespread adoption", 
      "algorithm", 
      "scheme", 
      "Poly1305", 
      "forgery", 
      "Handschuh", 
      "Bernstein's analysis", 
      "Preneel", 
      "proof", 
      "bounds", 
      "key", 
      "adoption", 
      "advancement", 
      "significant amount", 
      "issues", 
      "work", 
      "polynomials", 
      "amount", 
      "data", 
      "long line", 
      "new analysis", 
      "MACS", 
      "analysis", 
      "attention", 
      "gap", 
      "practice", 
      "Bernstein", 
      "importance", 
      "understanding", 
      "lines", 
      "GCM", 
      "limit", 
      "fragility", 
      "PrP"
    ], 
    "name": "Optimal Forgeries Against Polynomial-Based MACs and GCM", 
    "pagination": "445-467", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1101874811"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-78381-9_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-78381-9_17", 
      "https://app.dimensions.ai/details/publication/pub.1101874811"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:59", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_449.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-78381-9_17"
  }
]
 

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-319-78381-9_17'

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-319-78381-9_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-78381-9_17'

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-319-78381-9_17'


 

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

117 TRIPLES      22 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-78381-9_17 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N0541665f88644eb8b32a0c7b44ffe3c8
4 schema:datePublished 2018-03-31
5 schema:datePublishedReg 2018-03-31
6 schema:description Polynomial-based authentication algorithms, such as GCM and Poly1305, have seen widespread adoption in practice. Due to their importance, a significant amount of attention has been given to understanding and improving both proofs and attacks against such schemes. At EUROCRYPT 2005, Bernstein published the best known analysis of the schemes when instantiated with PRPs, thereby establishing the most lenient limits on the amount of data the schemes can process per key. A long line of work, initiated by Handschuh and Preneel at CRYPTO 2008, finds the best known attacks, advancing our understanding of the fragility of the schemes. Yet surprisingly, no known attacks perform as well as the predicted worst-case attacks allowed by Bernstein’s analysis, nor has there been any advancement in proofs improving Bernstein’s bounds, and the gap between attacks and analysis is significant. We settle the issue by finding a novel attack against polynomial-based authentication algorithms using PRPs, and combine it with new analysis, to show that Bernstein’s bound, and our attacks, are optimal.
7 schema:editor Nada478ae729442449728c5b06eb2d6aa
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N70f690fca5454fdd95463496dfa52586
11 schema:keywords Bernstein
12 Bernstein bounds
13 Bernstein's analysis
14 CRYPTO 2008
15 Eurocrypt 2005
16 GCM
17 Handschuh
18 MACS
19 Poly1305
20 PrP
21 Preneel
22 adoption
23 advancement
24 algorithm
25 amount
26 amount of data
27 analysis
28 attacks
29 attention
30 authentication algorithm
31 bounds
32 data
33 forgery
34 fragility
35 gap
36 importance
37 issues
38 key
39 limit
40 lines
41 long line
42 new analysis
43 novel attacks
44 polynomials
45 practice
46 proof
47 scheme
48 significant amount
49 such schemes
50 understanding
51 widespread adoption
52 work
53 worst-case attack
54 schema:name Optimal Forgeries Against Polynomial-Based MACs and GCM
55 schema:pagination 445-467
56 schema:productId N284b03e492de4a64920348c9dba2813d
57 N37d09a086ca147cc8611db3f8acc6175
58 schema:publisher N4e3e7f8c52d4408a82b74ca9b6302e7f
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101874811
60 https://doi.org/10.1007/978-3-319-78381-9_17
61 schema:sdDatePublished 2022-10-01T06:59
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N2229107df7ea4a818a00ef63b25979e8
64 schema:url https://doi.org/10.1007/978-3-319-78381-9_17
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N0541665f88644eb8b32a0c7b44ffe3c8 rdf:first sg:person.010234250021.33
69 rdf:rest N77c5d9184a724cb18b127e2dd4ebe4f3
70 N2229107df7ea4a818a00ef63b25979e8 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N27d6fc6568da4dcb888b4674ae6d96ac schema:familyName Nielsen
73 schema:givenName Jesper Buus
74 rdf:type schema:Person
75 N284b03e492de4a64920348c9dba2813d schema:name doi
76 schema:value 10.1007/978-3-319-78381-9_17
77 rdf:type schema:PropertyValue
78 N37d09a086ca147cc8611db3f8acc6175 schema:name dimensions_id
79 schema:value pub.1101874811
80 rdf:type schema:PropertyValue
81 N4e3e7f8c52d4408a82b74ca9b6302e7f schema:name Springer Nature
82 rdf:type schema:Organisation
83 N70f690fca5454fdd95463496dfa52586 schema:isbn 978-3-319-78380-2
84 978-3-319-78381-9
85 schema:name Advances in Cryptology – EUROCRYPT 2018
86 rdf:type schema:Book
87 N77c5d9184a724cb18b127e2dd4ebe4f3 rdf:first sg:person.011115044357.39
88 rdf:rest rdf:nil
89 Nada478ae729442449728c5b06eb2d6aa rdf:first N27d6fc6568da4dcb888b4674ae6d96ac
90 rdf:rest Nc81e7efa9e204270ba8523be943a0c3d
91 Nc81e7efa9e204270ba8523be943a0c3d rdf:first Nd1e3e0b6f79f4f929b69417ab665a33f
92 rdf:rest rdf:nil
93 Nd1e3e0b6f79f4f929b69417ab665a33f schema:familyName Rijmen
94 schema:givenName Vincent
95 rdf:type schema:Person
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
100 schema:name Data Format
101 rdf:type schema:DefinedTerm
102 sg:person.010234250021.33 schema:affiliation grid-institutes:None
103 schema:familyName Luykx
104 schema:givenName Atul
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010234250021.33
106 rdf:type schema:Person
107 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.5596.f
108 schema:familyName Preneel
109 schema:givenName Bart
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
111 rdf:type schema:Person
112 grid-institutes:None schema:alternateName Visa Research, Palo Alto, USA
113 schema:name Visa Research, Palo Alto, USA
114 rdf:type schema:Organization
115 grid-institutes:grid.5596.f schema:alternateName imec-COSIC, KU Leuven, Leuven, Belgium
116 schema:name imec-COSIC, KU Leuven, Leuven, Belgium
117 rdf:type schema:Organization
 




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


...