Improved Linear Differential Attacks on CubeHash View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Shahram Khazaei , Simon Knellwolf , Willi Meier , Deian Stefan

ABSTRACT

This paper presents improved collision attacks on round-reduced variants of the hash function CubeHash, one of the SHA-3 second round candidates. We apply two methods for finding linear differential trails that lead to lower estimated attack complexities when used within the framework introduced by Brier, Khazaei, Meier and Peyrin at ASIACRYPT 2009. The first method yields trails that are relatively dense at the beginning and sparse towards the end. In combination with the condition function concept, such trails lead to much faster collision attacks. We demonstrate this by providing a real collision for CubeHash-5/96. The second method randomizes the search for highly probable linear differential trails and leads to significantly better attacks for up to eight rounds. More... »

PAGES

407-418

References to SciGraph publications

  • 2005. Update on SHA-1 in TOPICS IN CRYPTOLOGY – CT-RSA 2005
  • 2005. How to Break MD5 and Other Hash Functions in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2005
  • 2009. Linearization Framework for Collision Attacks: Application to CubeHash and MD6 in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2009
  • 1998. Differential collisions in SHA-0 in ADVANCES IN CRYPTOLOGY — CRYPTO '98
  • 2006. Improved Collision Search for SHA-0 in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2006
  • 2004. Near-Collisions of SHA-0 in ADVANCES IN CRYPTOLOGY – CRYPTO 2004
  • 2009. Practical Collisions for EnRUPT in FAST SOFTWARE ENCRYPTION
  • 2005. Exploiting Coding Theory for Collision Attacks on SHA-1 in CRYPTOGRAPHY AND CODING
  • 2009. Cryptanalysis of CubeHash in ROBOCUP 2001: ROBOT SOCCER WORLD CUP V
  • Book

    TITLE

    Progress in Cryptology – AFRICACRYPT 2010

    ISBN

    978-3-642-12677-2
    978-3-642-12678-9

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-12678-9_24

    DOI

    http://dx.doi.org/10.1007/978-3-642-12678-9_24

    DIMENSIONS

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


    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/1103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Clinical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Medical and Health Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "EPFL, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Khazaei", 
            "givenName": "Shahram", 
            "id": "sg:person.016542062647.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016542062647.95"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Applied Sciences and Arts Northwestern Switzerland", 
              "id": "https://www.grid.ac/institutes/grid.410380.e", 
              "name": [
                "FHNW, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Knellwolf", 
            "givenName": "Simon", 
            "id": "sg:person.016510524306.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016510524306.72"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Applied Sciences and Arts Northwestern Switzerland", 
              "id": "https://www.grid.ac/institutes/grid.410380.e", 
              "name": [
                "FHNW, 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": "Cooper Union", 
              "id": "https://www.grid.ac/institutes/grid.254672.0", 
              "name": [
                "The Cooper Union, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Stefan", 
            "givenName": "Deian", 
            "id": "sg:person.012620432773.74", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620432773.74"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0055720", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005449369", 
              "https://doi.org/10.1007/bfb0055720"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01957-9_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012371707", 
              "https://doi.org/10.1007/978-3-642-01957-9_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01957-9_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012371707", 
              "https://doi.org/10.1007/978-3-642-01957-9_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01957-9_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012371707", 
              "https://doi.org/10.1007/978-3-642-01957-9_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30574-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013139660", 
              "https://doi.org/10.1007/978-3-540-30574-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30574-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013139660", 
              "https://doi.org/10.1007/978-3-540-30574-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11935230_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027885647", 
              "https://doi.org/10.1007/11935230_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11935230_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027885647", 
              "https://doi.org/10.1007/11935230_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10366-7_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028984015", 
              "https://doi.org/10.1007/978-3-642-10366-7_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10366-7_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028984015", 
              "https://doi.org/10.1007/978-3-642-10366-7_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043264875", 
              "https://doi.org/10.1007/11426639_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043264875", 
              "https://doi.org/10.1007/11426639_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03317-9_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049730712", 
              "https://doi.org/10.1007/978-3-642-03317-9_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03317-9_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049730712", 
              "https://doi.org/10.1007/978-3-642-03317-9_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28628-8_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050229654", 
              "https://doi.org/10.1007/978-3-540-28628-8_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28628-8_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050229654", 
              "https://doi.org/10.1007/978-3-540-28628-8_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11586821_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052080704", 
              "https://doi.org/10.1007/11586821_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11586821_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052080704", 
              "https://doi.org/10.1007/11586821_7"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "This paper presents improved collision attacks on round-reduced variants of the hash function CubeHash, one of the SHA-3 second round candidates. We apply two methods for finding linear differential trails that lead to lower estimated attack complexities when used within the framework introduced by Brier, Khazaei, Meier and Peyrin at ASIACRYPT 2009. The first method yields trails that are relatively dense at the beginning and sparse towards the end. In combination with the condition function concept, such trails lead to much faster collision attacks. We demonstrate this by providing a real collision for CubeHash-5/96. The second method randomizes the search for highly probable linear differential trails and leads to significantly better attacks for up to eight rounds.", 
        "editor": [
          {
            "familyName": "Bernstein", 
            "givenName": "Daniel J.", 
            "type": "Person"
          }, 
          {
            "familyName": "Lange", 
            "givenName": "Tanja", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-12678-9_24", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-12677-2", 
            "978-3-642-12678-9"
          ], 
          "name": "Progress in Cryptology \u2013 AFRICACRYPT 2010", 
          "type": "Book"
        }, 
        "name": "Improved Linear Differential Attacks on CubeHash", 
        "pagination": "407-418", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045413866"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-12678-9_24"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d853ad80d523a8994f20b3604e6c71ddc42cff3cfbf4aaadd5b0710b3cf91f4d"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-12678-9_24", 
          "https://app.dimensions.ai/details/publication/pub.1045413866"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:39", 
        "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/0000000357_0000000357/records_99330_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-12678-9_24"
      }
    ]
     

    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-12678-9_24'

    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-12678-9_24'

    Turtle is a human-readable linked data format.

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

    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-12678-9_24'


     

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

    133 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-12678-9_24 schema:about anzsrc-for:11
    2 anzsrc-for:1103
    3 schema:author Nb95670c07850414798a89287948dffb1
    4 schema:citation sg:pub.10.1007/11426639_2
    5 sg:pub.10.1007/11586821_7
    6 sg:pub.10.1007/11935230_2
    7 sg:pub.10.1007/978-3-540-28628-8_18
    8 sg:pub.10.1007/978-3-540-30574-3_6
    9 sg:pub.10.1007/978-3-642-01957-9_22
    10 sg:pub.10.1007/978-3-642-03317-9_15
    11 sg:pub.10.1007/978-3-642-10366-7_33
    12 sg:pub.10.1007/bfb0055720
    13 schema:datePublished 2010
    14 schema:datePublishedReg 2010-01-01
    15 schema:description This paper presents improved collision attacks on round-reduced variants of the hash function CubeHash, one of the SHA-3 second round candidates. We apply two methods for finding linear differential trails that lead to lower estimated attack complexities when used within the framework introduced by Brier, Khazaei, Meier and Peyrin at ASIACRYPT 2009. The first method yields trails that are relatively dense at the beginning and sparse towards the end. In combination with the condition function concept, such trails lead to much faster collision attacks. We demonstrate this by providing a real collision for CubeHash-5/96. The second method randomizes the search for highly probable linear differential trails and leads to significantly better attacks for up to eight rounds.
    16 schema:editor Na932a66d2ce24608a3e3864eefd0b48d
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf Nf1438c38edcf47419afbb501d4befa31
    21 schema:name Improved Linear Differential Attacks on CubeHash
    22 schema:pagination 407-418
    23 schema:productId N49be84baed584480bb8d6aeee18c9d04
    24 N6778039ae50347a9a5128fde23c3b1a7
    25 Na9ab8ee05051463da23be30f4d23f6d5
    26 schema:publisher N4dc047f319114b0aa4aa02f8d5f39a1c
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045413866
    28 https://doi.org/10.1007/978-3-642-12678-9_24
    29 schema:sdDatePublished 2019-04-16T07:39
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher Nc320fa8246eb44b58f7f172dae5d9922
    32 schema:url https://link.springer.com/10.1007%2F978-3-642-12678-9_24
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N4029f65335b545bc896fb59c6583a7b7 rdf:first N8d5d185a91b74cbdad8982cc48673428
    37 rdf:rest rdf:nil
    38 N49be84baed584480bb8d6aeee18c9d04 schema:name doi
    39 schema:value 10.1007/978-3-642-12678-9_24
    40 rdf:type schema:PropertyValue
    41 N4dc047f319114b0aa4aa02f8d5f39a1c schema:location Berlin, Heidelberg
    42 schema:name Springer Berlin Heidelberg
    43 rdf:type schema:Organisation
    44 N556a44d3fd6d467e96c6830b9a87620a rdf:first sg:person.016510524306.72
    45 rdf:rest Na3c3263e816b48229f490b3e784409b0
    46 N6778039ae50347a9a5128fde23c3b1a7 schema:name readcube_id
    47 schema:value d853ad80d523a8994f20b3604e6c71ddc42cff3cfbf4aaadd5b0710b3cf91f4d
    48 rdf:type schema:PropertyValue
    49 N8d5d185a91b74cbdad8982cc48673428 schema:familyName Lange
    50 schema:givenName Tanja
    51 rdf:type schema:Person
    52 N8ea6e0e460284c55ae63ad4bda731a88 rdf:first sg:person.012620432773.74
    53 rdf:rest rdf:nil
    54 Na3c3263e816b48229f490b3e784409b0 rdf:first sg:person.07653531142.18
    55 rdf:rest N8ea6e0e460284c55ae63ad4bda731a88
    56 Na932a66d2ce24608a3e3864eefd0b48d rdf:first Nedadbaada9ee400385d766af1a3cbced
    57 rdf:rest N4029f65335b545bc896fb59c6583a7b7
    58 Na9ab8ee05051463da23be30f4d23f6d5 schema:name dimensions_id
    59 schema:value pub.1045413866
    60 rdf:type schema:PropertyValue
    61 Nb95670c07850414798a89287948dffb1 rdf:first sg:person.016542062647.95
    62 rdf:rest N556a44d3fd6d467e96c6830b9a87620a
    63 Nc320fa8246eb44b58f7f172dae5d9922 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Nedadbaada9ee400385d766af1a3cbced schema:familyName Bernstein
    66 schema:givenName Daniel J.
    67 rdf:type schema:Person
    68 Nf1438c38edcf47419afbb501d4befa31 schema:isbn 978-3-642-12677-2
    69 978-3-642-12678-9
    70 schema:name Progress in Cryptology – AFRICACRYPT 2010
    71 rdf:type schema:Book
    72 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Medical and Health Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:1103 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Clinical Sciences
    77 rdf:type schema:DefinedTerm
    78 sg:person.012620432773.74 schema:affiliation https://www.grid.ac/institutes/grid.254672.0
    79 schema:familyName Stefan
    80 schema:givenName Deian
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620432773.74
    82 rdf:type schema:Person
    83 sg:person.016510524306.72 schema:affiliation https://www.grid.ac/institutes/grid.410380.e
    84 schema:familyName Knellwolf
    85 schema:givenName Simon
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016510524306.72
    87 rdf:type schema:Person
    88 sg:person.016542062647.95 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    89 schema:familyName Khazaei
    90 schema:givenName Shahram
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016542062647.95
    92 rdf:type schema:Person
    93 sg:person.07653531142.18 schema:affiliation https://www.grid.ac/institutes/grid.410380.e
    94 schema:familyName Meier
    95 schema:givenName Willi
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
    97 rdf:type schema:Person
    98 sg:pub.10.1007/11426639_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043264875
    99 https://doi.org/10.1007/11426639_2
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/11586821_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052080704
    102 https://doi.org/10.1007/11586821_7
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/11935230_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027885647
    105 https://doi.org/10.1007/11935230_2
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/978-3-540-28628-8_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050229654
    108 https://doi.org/10.1007/978-3-540-28628-8_18
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/978-3-540-30574-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013139660
    111 https://doi.org/10.1007/978-3-540-30574-3_6
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/978-3-642-01957-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012371707
    114 https://doi.org/10.1007/978-3-642-01957-9_22
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/978-3-642-03317-9_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049730712
    117 https://doi.org/10.1007/978-3-642-03317-9_15
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-3-642-10366-7_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028984015
    120 https://doi.org/10.1007/978-3-642-10366-7_33
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/bfb0055720 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005449369
    123 https://doi.org/10.1007/bfb0055720
    124 rdf:type schema:CreativeWork
    125 https://www.grid.ac/institutes/grid.254672.0 schema:alternateName Cooper Union
    126 schema:name The Cooper Union, USA
    127 rdf:type schema:Organization
    128 https://www.grid.ac/institutes/grid.410380.e schema:alternateName University of Applied Sciences and Arts Northwestern Switzerland
    129 schema:name FHNW, Switzerland
    130 rdf:type schema:Organization
    131 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
    132 schema:name EPFL, Switzerland
    133 rdf:type schema:Organization
     




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


    ...