Distinguisher and Related-Key Attack on the Full AES-256 View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Alex Biryukov , Dmitry Khovratovich , Ivica Nikolić

ABSTRACT

In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of differential q -multicollision and show that for AES-256 q-multicollisions can be constructed in time q·267 and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least \(O(q\cdot 2^{\frac{q-1}{q+1}128})\) time. Using similar approach and with the same complexity we can also construct q-pseudo collisions for AES-256 in Davies-Meyer mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial q-multicollisions in time q·237 on a PC to verify our results. These results show that AES-256 can not model an ideal cipher in theoretical constructions. Finally we extend our results to find the first publicly known attack on the full 14-round AES-256: a related-key distinguisher which works for one out of every 235 keys with 2120 data and time complexity and negligible memory. This distinguisher is translated into a key-recovery attack with total complexity of 2131 time and 265 memory. More... »

PAGES

231-249

Book

TITLE

Advances in Cryptology - CRYPTO 2009

ISBN

978-3-642-03355-1
978-3-642-03356-8

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03356-8_14

DOI

http://dx.doi.org/10.1007/978-3-642-03356-8_14

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Luxembourg", 
          "id": "https://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "University of Luxembourg,"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Biryukov", 
        "givenName": "Alex", 
        "id": "sg:person.07752327005.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07752327005.55"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Luxembourg", 
          "id": "https://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "University of Luxembourg,"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Khovratovich", 
        "givenName": "Dmitry", 
        "id": "sg:person.011601463101.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601463101.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Luxembourg", 
          "id": "https://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "University of Luxembourg,"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nikoli\u0107", 
        "givenName": "Ivica", 
        "id": "sg:person.013715004754.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013715004754.76"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-76900-2_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004683177", 
          "https://doi.org/10.1007/978-3-540-76900-2_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-76900-2_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004683177", 
          "https://doi.org/10.1007/978-3-540-76900-2_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-85093-9_22", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013401685", 
          "https://doi.org/10.1007/978-3-540-85093-9_22"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44706-7_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015721088", 
          "https://doi.org/10.1007/3-540-44706-7_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44706-7_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015721088", 
          "https://doi.org/10.1007/3-540-44706-7_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45708-9_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019344851", 
          "https://doi.org/10.1007/3-540-45708-9_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45708-9_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019344851", 
          "https://doi.org/10.1007/3-540-45708-9_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-74619-5_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020871863", 
          "https://doi.org/10.1007/978-3-540-74619-5_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-74619-5_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020871863", 
          "https://doi.org/10.1007/978-3-540-74619-5_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11799313_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030756500", 
          "https://doi.org/10.1007/11799313_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11799313_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030756500", 
          "https://doi.org/10.1007/11799313_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45661-9_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033628798", 
          "https://doi.org/10.1007/3-540-45661-9_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-28628-8_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033642671", 
          "https://doi.org/10.1007/978-3-540-28628-8_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-28628-8_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033642671", 
          "https://doi.org/10.1007/978-3-540-28628-8_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1008731.1008734", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037229512"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-00862-7_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037370925", 
          "https://doi.org/10.1007/978-3-642-00862-7_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-00862-7_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037370925", 
          "https://doi.org/10.1007/978-3-642-00862-7_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11426639_30", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037593715", 
          "https://doi.org/10.1007/11426639_30"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11426639_30", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037593715", 
          "https://doi.org/10.1007/11426639_30"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11927587_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042497960", 
          "https://doi.org/10.1007/11927587_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11927587_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042497960", 
          "https://doi.org/10.1007/11927587_5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of differential q -multicollision and show that for AES-256 q-multicollisions can be constructed in time q\u00b7267 and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least \\(O(q\\cdot 2^{\\frac{q-1}{q+1}128})\\) time. Using similar approach and with the same complexity we can also construct q-pseudo collisions for AES-256 in Davies-Meyer mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial q-multicollisions in time q\u00b7237 on a PC to verify our results. These results show that AES-256 can not model an ideal cipher in theoretical constructions. Finally we extend our results to find the first publicly known attack on the full 14-round AES-256: a related-key distinguisher which works for one out of every 235 keys with 2120 data and time complexity and negligible memory. This distinguisher is translated into a key-recovery attack with total complexity of 2131 time and 265 memory.", 
    "editor": [
      {
        "familyName": "Halevi", 
        "givenName": "Shai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03356-8_14", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03355-1", 
        "978-3-642-03356-8"
      ], 
      "name": "Advances in Cryptology - CRYPTO 2009", 
      "type": "Book"
    }, 
    "name": "Distinguisher and Related-Key Attack on the Full AES-256", 
    "pagination": "231-249", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03356-8_14"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4e8c2399bedc9ea41ff3617da9a1b34ff587b32e3db698af2480d99dace65b7f"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016485222"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03356-8_14", 
      "https://app.dimensions.ai/details/publication/pub.1016485222"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T10:32", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8659_00000253.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-03356-8_14"
  }
]
 

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-642-03356-8_14'

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-642-03356-8_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03356-8_14'

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-642-03356-8_14'


 

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

126 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03356-8_14 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N95d72fd394cc4edf9a1d50197b436a49
4 schema:citation sg:pub.10.1007/11426639_30
5 sg:pub.10.1007/11799313_21
6 sg:pub.10.1007/11927587_5
7 sg:pub.10.1007/3-540-44706-7_15
8 sg:pub.10.1007/3-540-45661-9_19
9 sg:pub.10.1007/3-540-45708-9_21
10 sg:pub.10.1007/978-3-540-28628-8_19
11 sg:pub.10.1007/978-3-540-74619-5_15
12 sg:pub.10.1007/978-3-540-76900-2_19
13 sg:pub.10.1007/978-3-540-85093-9_22
14 sg:pub.10.1007/978-3-642-00862-7_11
15 https://doi.org/10.1145/1008731.1008734
16 schema:datePublished 2009
17 schema:datePublishedReg 2009-01-01
18 schema:description In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of differential q -multicollision and show that for AES-256 q-multicollisions can be constructed in time q·267 and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least \(O(q\cdot 2^{\frac{q-1}{q+1}128})\) time. Using similar approach and with the same complexity we can also construct q-pseudo collisions for AES-256 in Davies-Meyer mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial q-multicollisions in time q·237 on a PC to verify our results. These results show that AES-256 can not model an ideal cipher in theoretical constructions. Finally we extend our results to find the first publicly known attack on the full 14-round AES-256: a related-key distinguisher which works for one out of every 235 keys with 2120 data and time complexity and negligible memory. This distinguisher is translated into a key-recovery attack with total complexity of 2131 time and 265 memory.
19 schema:editor Nc329bd30c828489a87d244ab525c572d
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf Nbbfac344f8534a00914f8cfa5329a325
24 schema:name Distinguisher and Related-Key Attack on the Full AES-256
25 schema:pagination 231-249
26 schema:productId N21d34a51c0724e168b893173b48e5eab
27 N2b2356449f354022a4ae700d8f902344
28 Na02e8b20bd3742cea6ee064efb667cf8
29 schema:publisher N230e30df1c63456280092239762383d1
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016485222
31 https://doi.org/10.1007/978-3-642-03356-8_14
32 schema:sdDatePublished 2019-04-15T10:32
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N9e9be4f86681492dae17692dd2109fbc
35 schema:url http://link.springer.com/10.1007/978-3-642-03356-8_14
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N21d34a51c0724e168b893173b48e5eab schema:name readcube_id
40 schema:value 4e8c2399bedc9ea41ff3617da9a1b34ff587b32e3db698af2480d99dace65b7f
41 rdf:type schema:PropertyValue
42 N230e30df1c63456280092239762383d1 schema:location Berlin, Heidelberg
43 schema:name Springer Berlin Heidelberg
44 rdf:type schema:Organisation
45 N2b2356449f354022a4ae700d8f902344 schema:name dimensions_id
46 schema:value pub.1016485222
47 rdf:type schema:PropertyValue
48 N5194777f61fc45e4816baaf6b54a284d rdf:first sg:person.013715004754.76
49 rdf:rest rdf:nil
50 N7de2c4ad70854b3c9c58037cdd2bca6e schema:familyName Halevi
51 schema:givenName Shai
52 rdf:type schema:Person
53 N95d72fd394cc4edf9a1d50197b436a49 rdf:first sg:person.07752327005.55
54 rdf:rest Nc53aaf7e0df044918e6e09696ab4e323
55 N9e9be4f86681492dae17692dd2109fbc schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 Na02e8b20bd3742cea6ee064efb667cf8 schema:name doi
58 schema:value 10.1007/978-3-642-03356-8_14
59 rdf:type schema:PropertyValue
60 Nbbfac344f8534a00914f8cfa5329a325 schema:isbn 978-3-642-03355-1
61 978-3-642-03356-8
62 schema:name Advances in Cryptology - CRYPTO 2009
63 rdf:type schema:Book
64 Nc329bd30c828489a87d244ab525c572d rdf:first N7de2c4ad70854b3c9c58037cdd2bca6e
65 rdf:rest rdf:nil
66 Nc53aaf7e0df044918e6e09696ab4e323 rdf:first sg:person.011601463101.27
67 rdf:rest N5194777f61fc45e4816baaf6b54a284d
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:person.011601463101.27 schema:affiliation https://www.grid.ac/institutes/grid.16008.3f
75 schema:familyName Khovratovich
76 schema:givenName Dmitry
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601463101.27
78 rdf:type schema:Person
79 sg:person.013715004754.76 schema:affiliation https://www.grid.ac/institutes/grid.16008.3f
80 schema:familyName Nikolić
81 schema:givenName Ivica
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013715004754.76
83 rdf:type schema:Person
84 sg:person.07752327005.55 schema:affiliation https://www.grid.ac/institutes/grid.16008.3f
85 schema:familyName Biryukov
86 schema:givenName Alex
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07752327005.55
88 rdf:type schema:Person
89 sg:pub.10.1007/11426639_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037593715
90 https://doi.org/10.1007/11426639_30
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/11799313_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030756500
93 https://doi.org/10.1007/11799313_21
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/11927587_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042497960
96 https://doi.org/10.1007/11927587_5
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/3-540-44706-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015721088
99 https://doi.org/10.1007/3-540-44706-7_15
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/3-540-45661-9_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033628798
102 https://doi.org/10.1007/3-540-45661-9_19
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/3-540-45708-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019344851
105 https://doi.org/10.1007/3-540-45708-9_21
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/978-3-540-28628-8_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033642671
108 https://doi.org/10.1007/978-3-540-28628-8_19
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/978-3-540-74619-5_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020871863
111 https://doi.org/10.1007/978-3-540-74619-5_15
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/978-3-540-76900-2_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004683177
114 https://doi.org/10.1007/978-3-540-76900-2_19
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/978-3-540-85093-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013401685
117 https://doi.org/10.1007/978-3-540-85093-9_22
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/978-3-642-00862-7_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037370925
120 https://doi.org/10.1007/978-3-642-00862-7_11
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/1008731.1008734 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037229512
123 rdf:type schema:CreativeWork
124 https://www.grid.ac/institutes/grid.16008.3f schema:alternateName University of Luxembourg
125 schema:name University of Luxembourg,
126 rdf:type schema:Organization
 




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


...