Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Jean-Philippe Aumasson , Itai Dinur , Willi Meier , Adi Shamir

ABSTRACT

CRYPTO 2008 saw the introduction of the hash function MD6 and of cube attacks, a type of algebraic attack applicable to cryptographic functions having a low-degree algebraic normal form over GF(2). This paper applies cube attacks to reduced round MD6, finding the full 128-bit key of a 14-round MD6 with complexity 222 (which takes less than a minute on a single PC). This is the best key recovery attack announced so far for MD6. We then introduce a new class of attacks called cube testers, based on efficient property-testing algorithms, and apply them to MD6 and to the stream cipher Trivium. Unlike the standard cube attacks, cube testers detect nonrandom behavior rather than performing key extraction, but they can also attack cryptographic schemes described by nonrandom polynomials of relatively high degree. Applied to MD6, cube testers detect nonrandomness over 18 rounds in 217 complexity; applied to a slightly modified version of the MD6 compression function, they can distinguish 66 rounds from random in 224 complexity. Cube testers give distinguishers on Trivium reduced to 790 rounds from random with 230 complexity and detect nonrandomness over 885 rounds in 227, improving on the original 767-round cube attack. More... »

PAGES

1-22

Book

TITLE

Fast Software Encryption

ISBN

978-3-642-03316-2
978-3-642-03317-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03317-9_1

DOI

http://dx.doi.org/10.1007/978-3-642-03317-9_1

DIMENSIONS

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


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": "FHNW, Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aumasson", 
        "givenName": "Jean-Philippe", 
        "id": "sg:person.012606440341.66", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, The Weizmann Institute, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Computer Science Department, The Weizmann Institute, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dinur", 
        "givenName": "Itai", 
        "id": "sg:person.012046016703.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012046016703.69"
        ], 
        "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, The Weizmann Institute, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Computer Science Department, The Weizmann Institute, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shamir", 
        "givenName": "Adi", 
        "id": "sg:person.013052746407.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "CRYPTO\u00a02008 saw the introduction of the hash function MD6 and of cube attacks, a type of algebraic attack applicable to cryptographic functions having a low-degree algebraic normal form over GF(2). This paper applies cube attacks to reduced round MD6, finding the full 128-bit key of a 14-round MD6 with complexity 222 (which takes less than a minute on a single PC). This is the best key recovery attack announced so far for MD6. We then introduce a new class of attacks called cube testers, based on efficient property-testing algorithms, and apply them to MD6 and to the stream cipher Trivium. Unlike the standard cube attacks, cube testers detect nonrandom behavior rather than performing key extraction, but they can also attack cryptographic schemes described by nonrandom polynomials of relatively high degree. Applied to MD6, cube testers detect nonrandomness over 18 rounds in 217 complexity; applied to a slightly modified version of the MD6 compression function, they can distinguish 66 rounds from random in 224 complexity. Cube testers give distinguishers on Trivium reduced to 790 rounds from random with 230 complexity and detect nonrandomness over 885 rounds in 227, improving on the original 767-round cube attack.", 
    "editor": [
      {
        "familyName": "Dunkelman", 
        "givenName": "Orr", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03317-9_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03316-2", 
        "978-3-642-03317-9"
      ], 
      "name": "Fast Software Encryption", 
      "type": "Book"
    }, 
    "keywords": [
      "key recovery attack", 
      "best key recovery attack", 
      "recovery attack", 
      "stream cipher Trivium", 
      "cube testers", 
      "cryptographic schemes", 
      "cube attack", 
      "cryptographic functions", 
      "key extraction", 
      "algebraic attacks", 
      "algebraic normal form", 
      "compression function", 
      "attacks", 
      "complexity", 
      "MD6", 
      "Trivium", 
      "algorithm", 
      "crypto", 
      "nonrandom behavior", 
      "normal form", 
      "scheme", 
      "key", 
      "distinguisher", 
      "tester", 
      "extraction", 
      "version", 
      "rounds", 
      "new class", 
      "high degree", 
      "class", 
      "polynomials", 
      "function", 
      "introduction", 
      "types", 
      "behavior", 
      "form", 
      "degree", 
      "nonrandomness", 
      "paper", 
      "hash function MD6", 
      "function MD6", 
      "low-degree algebraic normal form", 
      "round MD6", 
      "complexity 222", 
      "efficient property-testing algorithms", 
      "property-testing algorithms", 
      "cipher Trivium", 
      "standard cube attacks", 
      "nonrandom polynomials", 
      "MD6 compression function"
    ], 
    "name": "Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium", 
    "pagination": "1-22", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041320003"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03317-9_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03317-9_1", 
      "https://app.dimensions.ai/details/publication/pub.1041320003"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:07", 
    "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_126.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03317-9_1"
  }
]
 

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-03317-9_1'

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-03317-9_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03317-9_1'

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-03317-9_1'


 

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

134 TRIPLES      23 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03317-9_1 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N8ac218cb29d941639e3727562252ebbc
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description CRYPTO 2008 saw the introduction of the hash function MD6 and of cube attacks, a type of algebraic attack applicable to cryptographic functions having a low-degree algebraic normal form over GF(2). This paper applies cube attacks to reduced round MD6, finding the full 128-bit key of a 14-round MD6 with complexity 222 (which takes less than a minute on a single PC). This is the best key recovery attack announced so far for MD6. We then introduce a new class of attacks called cube testers, based on efficient property-testing algorithms, and apply them to MD6 and to the stream cipher Trivium. Unlike the standard cube attacks, cube testers detect nonrandom behavior rather than performing key extraction, but they can also attack cryptographic schemes described by nonrandom polynomials of relatively high degree. Applied to MD6, cube testers detect nonrandomness over 18 rounds in 217 complexity; applied to a slightly modified version of the MD6 compression function, they can distinguish 66 rounds from random in 224 complexity. Cube testers give distinguishers on Trivium reduced to 790 rounds from random with 230 complexity and detect nonrandomness over 885 rounds in 227, improving on the original 767-round cube attack.
7 schema:editor Ncba4392d563a4835b757f191058be9eb
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ndb06a07ed1364a6989459d493692da65
12 schema:keywords MD6
13 MD6 compression function
14 Trivium
15 algebraic attacks
16 algebraic normal form
17 algorithm
18 attacks
19 behavior
20 best key recovery attack
21 cipher Trivium
22 class
23 complexity
24 complexity 222
25 compression function
26 crypto
27 cryptographic functions
28 cryptographic schemes
29 cube attack
30 cube testers
31 degree
32 distinguisher
33 efficient property-testing algorithms
34 extraction
35 form
36 function
37 function MD6
38 hash function MD6
39 high degree
40 introduction
41 key
42 key extraction
43 key recovery attack
44 low-degree algebraic normal form
45 new class
46 nonrandom behavior
47 nonrandom polynomials
48 nonrandomness
49 normal form
50 paper
51 polynomials
52 property-testing algorithms
53 recovery attack
54 round MD6
55 rounds
56 scheme
57 standard cube attacks
58 stream cipher Trivium
59 tester
60 types
61 version
62 schema:name Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium
63 schema:pagination 1-22
64 schema:productId Nd322212c42854ee783436420648cc8c4
65 Ne53bd8d49cac47fe980069bd07d9ceea
66 schema:publisher N3b21258479054ce0ba1da0b65e96958a
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041320003
68 https://doi.org/10.1007/978-3-642-03317-9_1
69 schema:sdDatePublished 2022-01-01T19:07
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N350459083c2741deb1daa4164a5d17d1
72 schema:url https://doi.org/10.1007/978-3-642-03317-9_1
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N166d899db8c44e2f8da9fcd9780381d5 rdf:first sg:person.07653531142.18
77 rdf:rest N69e63306065647f09086c6a75c8bd3f6
78 N350459083c2741deb1daa4164a5d17d1 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N3b21258479054ce0ba1da0b65e96958a schema:name Springer Nature
81 rdf:type schema:Organisation
82 N41e410e9574a45c392f784915fb6ca8c schema:familyName Dunkelman
83 schema:givenName Orr
84 rdf:type schema:Person
85 N69e63306065647f09086c6a75c8bd3f6 rdf:first sg:person.013052746407.28
86 rdf:rest rdf:nil
87 N8ac218cb29d941639e3727562252ebbc rdf:first sg:person.012606440341.66
88 rdf:rest Nf0867d34051844dbbdbbe1dbf38933e5
89 Ncba4392d563a4835b757f191058be9eb rdf:first N41e410e9574a45c392f784915fb6ca8c
90 rdf:rest rdf:nil
91 Nd322212c42854ee783436420648cc8c4 schema:name doi
92 schema:value 10.1007/978-3-642-03317-9_1
93 rdf:type schema:PropertyValue
94 Ndb06a07ed1364a6989459d493692da65 schema:isbn 978-3-642-03316-2
95 978-3-642-03317-9
96 schema:name Fast Software Encryption
97 rdf:type schema:Book
98 Ne53bd8d49cac47fe980069bd07d9ceea schema:name dimensions_id
99 schema:value pub.1041320003
100 rdf:type schema:PropertyValue
101 Nf0867d34051844dbbdbbe1dbf38933e5 rdf:first sg:person.012046016703.69
102 rdf:rest N166d899db8c44e2f8da9fcd9780381d5
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
107 schema:name Data Format
108 rdf:type schema:DefinedTerm
109 sg:person.012046016703.69 schema:affiliation grid-institutes:grid.13992.30
110 schema:familyName Dinur
111 schema:givenName Itai
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012046016703.69
113 rdf:type schema:Person
114 sg:person.012606440341.66 schema:affiliation grid-institutes:grid.410380.e
115 schema:familyName Aumasson
116 schema:givenName Jean-Philippe
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66
118 rdf:type schema:Person
119 sg:person.013052746407.28 schema:affiliation grid-institutes:grid.13992.30
120 schema:familyName Shamir
121 schema:givenName Adi
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28
123 rdf:type schema:Person
124 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
125 schema:familyName Meier
126 schema:givenName Willi
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
128 rdf:type schema:Person
129 grid-institutes:grid.13992.30 schema:alternateName Computer Science Department, The Weizmann Institute, Rehovot, Israel
130 schema:name Computer Science Department, The Weizmann Institute, Rehovot, Israel
131 rdf:type schema:Organization
132 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
133 schema:name FHNW, Windisch, Switzerland
134 rdf:type schema:Organization
 




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


...