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", 
      "recovery attack", 
      "cube attack", 
      "cryptographic schemes", 
      "stream cipher Trivium", 
      "cryptographic functions", 
      "property testing algorithm", 
      "key extraction", 
      "cube testers", 
      "cipher Trivium", 
      "compression function", 
      "algebraic attacks", 
      "algebraic normal form", 
      "best key-recovery attack", 
      "attacks", 
      "MD6", 
      "complexity", 
      "Trivium", 
      "crypto", 
      "algorithm", 
      "normal form", 
      "nonrandom behavior", 
      "scheme", 
      "key", 
      "tester", 
      "distinguisher", 
      "rounds", 
      "extraction", 
      "version", 
      "new class", 
      "high degree", 
      "class", 
      "polynomials", 
      "function", 
      "introduction", 
      "types", 
      "behavior", 
      "form", 
      "degree", 
      "nonrandomness", 
      "paper"
    ], 
    "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-05-10T10:43", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_244.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.

125 TRIPLES      23 PREDICATES      67 URIs      60 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 N2bf7e95e64b64700bebcac4f14f3c051
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 Naa440ad3fd9849739773b82ff0b1ec8c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N1f71d211d2df498ca56f04edc9c6311c
12 schema:keywords MD6
13 Trivium
14 algebraic attacks
15 algebraic normal form
16 algorithm
17 attacks
18 behavior
19 best key-recovery attack
20 cipher Trivium
21 class
22 complexity
23 compression function
24 crypto
25 cryptographic functions
26 cryptographic schemes
27 cube attack
28 cube testers
29 degree
30 distinguisher
31 extraction
32 form
33 function
34 high degree
35 introduction
36 key
37 key extraction
38 key recovery attack
39 new class
40 nonrandom behavior
41 nonrandomness
42 normal form
43 paper
44 polynomials
45 property testing algorithm
46 recovery attack
47 rounds
48 scheme
49 stream cipher Trivium
50 tester
51 types
52 version
53 schema:name Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium
54 schema:pagination 1-22
55 schema:productId N878704f407e544b1947759b7cfaeca51
56 Nd1f563deccc445948e284ddce66e8cf3
57 schema:publisher N3222fd3d0d554969bdc2ec84ff8ae0ef
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041320003
59 https://doi.org/10.1007/978-3-642-03317-9_1
60 schema:sdDatePublished 2022-05-10T10:43
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N5b338563e99240688e46a9fecf3efd1c
63 schema:url https://doi.org/10.1007/978-3-642-03317-9_1
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N1f71d211d2df498ca56f04edc9c6311c schema:isbn 978-3-642-03316-2
68 978-3-642-03317-9
69 schema:name Fast Software Encryption
70 rdf:type schema:Book
71 N2bf7e95e64b64700bebcac4f14f3c051 rdf:first sg:person.012606440341.66
72 rdf:rest Nc575210c30e04339aeb368bf700f4832
73 N3222fd3d0d554969bdc2ec84ff8ae0ef schema:name Springer Nature
74 rdf:type schema:Organisation
75 N5b338563e99240688e46a9fecf3efd1c schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N64bf0563b6164d7c89bea475ee627ca6 rdf:first sg:person.07653531142.18
78 rdf:rest N9aeb688e939943dbb24c8d6b7c34e46d
79 N878704f407e544b1947759b7cfaeca51 schema:name doi
80 schema:value 10.1007/978-3-642-03317-9_1
81 rdf:type schema:PropertyValue
82 N9aeb688e939943dbb24c8d6b7c34e46d rdf:first sg:person.013052746407.28
83 rdf:rest rdf:nil
84 Naa440ad3fd9849739773b82ff0b1ec8c rdf:first Nb24a15c2fe15486aaddfd1a0a02262f9
85 rdf:rest rdf:nil
86 Nb24a15c2fe15486aaddfd1a0a02262f9 schema:familyName Dunkelman
87 schema:givenName Orr
88 rdf:type schema:Person
89 Nc575210c30e04339aeb368bf700f4832 rdf:first sg:person.012046016703.69
90 rdf:rest N64bf0563b6164d7c89bea475ee627ca6
91 Nd1f563deccc445948e284ddce66e8cf3 schema:name dimensions_id
92 schema:value pub.1041320003
93 rdf:type schema:PropertyValue
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
98 schema:name Data Format
99 rdf:type schema:DefinedTerm
100 sg:person.012046016703.69 schema:affiliation grid-institutes:grid.13992.30
101 schema:familyName Dinur
102 schema:givenName Itai
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012046016703.69
104 rdf:type schema:Person
105 sg:person.012606440341.66 schema:affiliation grid-institutes:grid.410380.e
106 schema:familyName Aumasson
107 schema:givenName Jean-Philippe
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66
109 rdf:type schema:Person
110 sg:person.013052746407.28 schema:affiliation grid-institutes:grid.13992.30
111 schema:familyName Shamir
112 schema:givenName Adi
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28
114 rdf:type schema:Person
115 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
116 schema:familyName Meier
117 schema:givenName Willi
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
119 rdf:type schema:Person
120 grid-institutes:grid.13992.30 schema:alternateName Computer Science Department, The Weizmann Institute, Rehovot, Israel
121 schema:name Computer Science Department, The Weizmann Institute, Rehovot, Israel
122 rdf:type schema:Organization
123 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
124 schema:name FHNW, Windisch, Switzerland
125 rdf:type schema:Organization
 




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


...