Making the Impossible Possible View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-02-01

AUTHORS

Christina Boura, Virginie Lallemand, María Naya-Plasencia, Valentin Suder

ABSTRACT

This paper introduces new techniques and correct complexity analyses for impossible differential cryptanalysis, a powerful block cipher attack. We show how the key schedule of a cipher impacts an impossible differential attack, and we provide a new formula for the time complexity analysis that takes this parameter into account. Further, we show, for the first time, that the technique of multiple differentials can be applied to impossible differential attacks. Then, we demonstrate how this technique can be combined in practice with multiple impossible differentials or with the so-called state-test technique. To support our proposal, we implemented the above techniques on small-scale ciphers and verified their efficiency and accuracy in practice. We apply our techniques to the cryptanalysis of ciphers including AES-128, CRYPTON-128, ARIA-128, CLEFIA-128, Camellia-256 and LBlock. All of our attacks significantly improve previous impossible differential attacks and generally achieve the best memory complexity among all previous attacks against these ciphers. More... »

PAGES

101-133

References to SciGraph publications

  • 1999. A Revised Version of CRYPTON: CRYPTON V1.0 in FAST SOFTWARE ENCRYPTION
  • 2007-05-30. Impossible Differential Cryptanalysis of Reduced-Round ARIA and Camellia in JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
  • 2001-04-25. Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms — Design andAnalysis in SELECTED AREAS IN CRYPTOGRAPHY
  • 2004. Truncated Differential Attacks on 8-Round CRYPTON in INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2003
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00145-016-9251-7

    DOI

    http://dx.doi.org/10.1007/s00145-016-9251-7

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "UVSQ, Versailles, France", 
              "id": "http://www.grid.ac/institutes/grid.12832.3a", 
              "name": [
                "UVSQ, Versailles, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Boura", 
            "givenName": "Christina", 
            "id": "sg:person.015244215073.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015244215073.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Inria, Paris, France", 
              "id": "http://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "Inria, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lallemand", 
            "givenName": "Virginie", 
            "id": "sg:person.011135275143.03", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011135275143.03"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Inria, Paris, France", 
              "id": "http://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "Inria, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Naya-Plasencia", 
            "givenName": "Mar\u00eda", 
            "id": "sg:person.013206304341.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo, Waterloo, Canada", 
              "id": "http://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "University of Waterloo, Waterloo, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Suder", 
            "givenName": "Valentin", 
            "id": "sg:person.010107336631.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010107336631.95"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s11390-007-9056-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040099033", 
              "https://doi.org/10.1007/s11390-007-9056-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48519-8_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044235979", 
              "https://doi.org/10.1007/3-540-48519-8_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24691-6_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009335826", 
              "https://doi.org/10.1007/978-3-540-24691-6_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44983-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037539478", 
              "https://doi.org/10.1007/3-540-44983-3_4"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-02-01", 
        "datePublishedReg": "2017-02-01", 
        "description": "This paper introduces new techniques and correct complexity analyses for impossible differential cryptanalysis, a powerful block cipher attack. We show how the key schedule of a cipher impacts an impossible differential attack, and we provide a new formula for the time complexity analysis that takes this parameter into account. Further, we show, for the first time, that the technique of multiple differentials can be applied to impossible differential attacks. Then, we demonstrate how this technique can be combined in practice with multiple impossible differentials or with the so-called state-test technique. To support our proposal, we implemented the above techniques on small-scale ciphers and verified their efficiency and accuracy in practice. We apply our techniques to the cryptanalysis of ciphers including AES-128, CRYPTON-128, ARIA-128, CLEFIA-128, Camellia-256 and LBlock. All of our attacks significantly improve previous impossible differential attacks and generally achieve the best memory complexity among all previous attacks against these ciphers.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00145-016-9251-7", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136278", 
            "issn": [
              "0933-2790", 
              "1432-1378"
            ], 
            "name": "Journal of Cryptology", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "31"
          }
        ], 
        "keywords": [
          "differential attacks", 
          "complexity analysis", 
          "time complexity analysis", 
          "cryptanalysis of ciphers", 
          "cipher attacks", 
          "impossible differential attack", 
          "memory complexity", 
          "AES-128", 
          "cipher", 
          "impossible differential cryptanalysis", 
          "key schedule", 
          "attacks", 
          "previous attacks", 
          "previous impossible differential attacks", 
          "cryptanalysis", 
          "differential cryptanalysis", 
          "CLEFIA-128", 
          "Camellia-256", 
          "above techniques", 
          "impossible differentials", 
          "technique", 
          "LBlock", 
          "new technique", 
          "complexity", 
          "accuracy", 
          "proposal", 
          "multiple differentials", 
          "efficiency", 
          "schedule", 
          "time", 
          "practice", 
          "analysis", 
          "account", 
          "parameters", 
          "new formula", 
          "formula", 
          "first time", 
          "differential", 
          "paper"
        ], 
        "name": "Making the Impossible Possible", 
        "pagination": "101-133", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1083422229"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00145-016-9251-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00145-016-9251-7", 
          "https://app.dimensions.ai/details/publication/pub.1083422229"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:42", 
        "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/article/article_732.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00145-016-9251-7"
      }
    ]
     

    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/s00145-016-9251-7'

    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/s00145-016-9251-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-016-9251-7'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-016-9251-7'


     

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

    139 TRIPLES      21 PREDICATES      67 URIs      55 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00145-016-9251-7 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nc8d3b081a84947f587bbae157077dc21
    4 schema:citation sg:pub.10.1007/3-540-44983-3_4
    5 sg:pub.10.1007/3-540-48519-8_3
    6 sg:pub.10.1007/978-3-540-24691-6_33
    7 sg:pub.10.1007/s11390-007-9056-0
    8 schema:datePublished 2017-02-01
    9 schema:datePublishedReg 2017-02-01
    10 schema:description This paper introduces new techniques and correct complexity analyses for impossible differential cryptanalysis, a powerful block cipher attack. We show how the key schedule of a cipher impacts an impossible differential attack, and we provide a new formula for the time complexity analysis that takes this parameter into account. Further, we show, for the first time, that the technique of multiple differentials can be applied to impossible differential attacks. Then, we demonstrate how this technique can be combined in practice with multiple impossible differentials or with the so-called state-test technique. To support our proposal, we implemented the above techniques on small-scale ciphers and verified their efficiency and accuracy in practice. We apply our techniques to the cryptanalysis of ciphers including AES-128, CRYPTON-128, ARIA-128, CLEFIA-128, Camellia-256 and LBlock. All of our attacks significantly improve previous impossible differential attacks and generally achieve the best memory complexity among all previous attacks against these ciphers.
    11 schema:genre article
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N9317c57523d44753832f9e1825d0e882
    14 Nf8ad4d3a5ba94161bfa6ab61b5a7c0de
    15 sg:journal.1136278
    16 schema:keywords AES-128
    17 CLEFIA-128
    18 Camellia-256
    19 LBlock
    20 above techniques
    21 account
    22 accuracy
    23 analysis
    24 attacks
    25 cipher
    26 cipher attacks
    27 complexity
    28 complexity analysis
    29 cryptanalysis
    30 cryptanalysis of ciphers
    31 differential
    32 differential attacks
    33 differential cryptanalysis
    34 efficiency
    35 first time
    36 formula
    37 impossible differential attack
    38 impossible differential cryptanalysis
    39 impossible differentials
    40 key schedule
    41 memory complexity
    42 multiple differentials
    43 new formula
    44 new technique
    45 paper
    46 parameters
    47 practice
    48 previous attacks
    49 previous impossible differential attacks
    50 proposal
    51 schedule
    52 technique
    53 time
    54 time complexity analysis
    55 schema:name Making the Impossible Possible
    56 schema:pagination 101-133
    57 schema:productId N0171ea52ea1140cabb1bdf1b381bcd0f
    58 Ne9f3fabf3e8c469a8b1730103c386dba
    59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083422229
    60 https://doi.org/10.1007/s00145-016-9251-7
    61 schema:sdDatePublished 2022-10-01T06:42
    62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    63 schema:sdPublisher N4822dbd833734518a785c61d63ee069b
    64 schema:url https://doi.org/10.1007/s00145-016-9251-7
    65 sgo:license sg:explorer/license/
    66 sgo:sdDataset articles
    67 rdf:type schema:ScholarlyArticle
    68 N0171ea52ea1140cabb1bdf1b381bcd0f schema:name doi
    69 schema:value 10.1007/s00145-016-9251-7
    70 rdf:type schema:PropertyValue
    71 N4822dbd833734518a785c61d63ee069b schema:name Springer Nature - SN SciGraph project
    72 rdf:type schema:Organization
    73 N9317c57523d44753832f9e1825d0e882 schema:volumeNumber 31
    74 rdf:type schema:PublicationVolume
    75 Nac6f05123ffe4154961910c65bb2fe2d rdf:first sg:person.010107336631.95
    76 rdf:rest rdf:nil
    77 Nc8d3b081a84947f587bbae157077dc21 rdf:first sg:person.015244215073.45
    78 rdf:rest Neea2003a85d2495eb3982197f0fac188
    79 Ne416b4b2de48497794ee862beac0e383 rdf:first sg:person.013206304341.94
    80 rdf:rest Nac6f05123ffe4154961910c65bb2fe2d
    81 Ne9f3fabf3e8c469a8b1730103c386dba schema:name dimensions_id
    82 schema:value pub.1083422229
    83 rdf:type schema:PropertyValue
    84 Neea2003a85d2495eb3982197f0fac188 rdf:first sg:person.011135275143.03
    85 rdf:rest Ne416b4b2de48497794ee862beac0e383
    86 Nf8ad4d3a5ba94161bfa6ab61b5a7c0de schema:issueNumber 1
    87 rdf:type schema:PublicationIssue
    88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Information and Computing Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Computation Theory and Mathematics
    93 rdf:type schema:DefinedTerm
    94 sg:journal.1136278 schema:issn 0933-2790
    95 1432-1378
    96 schema:name Journal of Cryptology
    97 schema:publisher Springer Nature
    98 rdf:type schema:Periodical
    99 sg:person.010107336631.95 schema:affiliation grid-institutes:grid.46078.3d
    100 schema:familyName Suder
    101 schema:givenName Valentin
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010107336631.95
    103 rdf:type schema:Person
    104 sg:person.011135275143.03 schema:affiliation grid-institutes:grid.5328.c
    105 schema:familyName Lallemand
    106 schema:givenName Virginie
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011135275143.03
    108 rdf:type schema:Person
    109 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
    110 schema:familyName Naya-Plasencia
    111 schema:givenName María
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
    113 rdf:type schema:Person
    114 sg:person.015244215073.45 schema:affiliation grid-institutes:grid.12832.3a
    115 schema:familyName Boura
    116 schema:givenName Christina
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015244215073.45
    118 rdf:type schema:Person
    119 sg:pub.10.1007/3-540-44983-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037539478
    120 https://doi.org/10.1007/3-540-44983-3_4
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/3-540-48519-8_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044235979
    123 https://doi.org/10.1007/3-540-48519-8_3
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-24691-6_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009335826
    126 https://doi.org/10.1007/978-3-540-24691-6_33
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/s11390-007-9056-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040099033
    129 https://doi.org/10.1007/s11390-007-9056-0
    130 rdf:type schema:CreativeWork
    131 grid-institutes:grid.12832.3a schema:alternateName UVSQ, Versailles, France
    132 schema:name UVSQ, Versailles, France
    133 rdf:type schema:Organization
    134 grid-institutes:grid.46078.3d schema:alternateName University of Waterloo, Waterloo, Canada
    135 schema:name University of Waterloo, Waterloo, Canada
    136 rdf:type schema:Organization
    137 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
    138 schema:name Inria, Paris, France
    139 rdf:type schema:Organization
     




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


    ...