Synthetic linear analysis with applications to CubeHash and Rabbit View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2012-07-31

AUTHORS

Yi Lu, Serge Vaudenay, Willi Meier

ABSTRACT

In linear cryptanalysis, it has been considered most important and difficult to analyze the bias and find a large bias. The demonstration of a large bias will usually imply that the target crypto-system is not strong. Regarding the bias analysis, researchers tend to look for a theoretical solution for a specific problem. In this paper, we take a first step towards the synthetic approach on bias analysis. We successfully apply our synthetic analysis to improve the most recent linear attacks on CubeHash and Rabbit respectively. CubeHash was selected to the second round of SHA-3 competition. The best linear attack on 11-round CubeHash with 2470 queries was proposed in Ashur and Dunkelman (2011). We present an improved attack for 11-round CubeHash with complexity 2414.2. Based on our 11-round attack, we give a new linear attack for 12-round CubeHash with complexity 2509. It is the first known attack on 12 rounds with complexity below the security parameter 2512 of CubeHash. Rabbit is a stream cipher among the finalists of ECRYPT Stream Cipher Project (eSTREAM). It has also been published as informational RFC 4503 with the Internet Engineering Task Force (IETF), which is the main standardization body for Internet technology. For Rabbit, the best linear attack with complexity 2141 was recently presented in [9]. Our synthetic bias analysis yields the improved attack with complexity 2136. More... »

PAGES

259-276

References to SciGraph publications

  • 2011. Linear Analysis of Reduced-Round CubeHash in APPLIED CRYPTOGRAPHY AND NETWORK SECURITY
  • 2007-01-01. Multiple Modular Additions and Crossword Puzzle Attack on NLSv2 in INFORMATION SECURITY
  • 2012. Synthetic Linear Analysis: Improved Attacks on CubeHash and Rabbit in INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2011
  • 2006. Improved Linear Distinguishers for SNOW 2.0 in FAST SOFTWARE ENCRYPTION
  • 2008-01-01. Cryptanalysis of Rabbit in INFORMATION SECURITY
  • 2011. Discovery and Exploitation of New Biases in RC4 in SELECTED AREAS IN CRYPTOGRAPHY
  • 1994. Linear Cryptanalysis Method for DES Cipher in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’93
  • 2011. Improved Distinguishing Attack on Rabbit in INFORMATION SECURITY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s12095-012-0064-8

    DOI

    http://dx.doi.org/10.1007/s12095-012-0064-8

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "National Engineering Research Center of Fundamental Software, Institute of Software, Chinese Academy of Sciences, Beijing, China", 
              "id": "http://www.grid.ac/institutes/grid.458446.f", 
              "name": [
                "National Engineering Research Center of Fundamental Software, Institute of Software, Chinese Academy of Sciences, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lu", 
            "givenName": "Yi", 
            "id": "sg:person.010630432145.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010630432145.10"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "EPFL, Lausanne, Switzerland", 
              "id": "http://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "EPFL, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vaudenay", 
            "givenName": "Serge", 
            "id": "sg:person.01353240467.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01353240467.39"
            ], 
            "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-19574-7_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022831806", 
              "https://doi.org/10.1007/978-3-642-19574-7_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75496-1_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000779144", 
              "https://doi.org/10.1007/978-3-540-75496-1_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48285-7_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038500879", 
              "https://doi.org/10.1007/3-540-48285-7_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-31912-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026686964", 
              "https://doi.org/10.1007/978-3-642-31912-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21554-4_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034071158", 
              "https://doi.org/10.1007/978-3-642-21554-4_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-18178-8_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037546787", 
              "https://doi.org/10.1007/978-3-642-18178-8_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11799313_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021327215", 
              "https://doi.org/10.1007/11799313_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-85886-7_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051744247", 
              "https://doi.org/10.1007/978-3-540-85886-7_14"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012-07-31", 
        "datePublishedReg": "2012-07-31", 
        "description": "In linear cryptanalysis, it has been considered most important and difficult to analyze the bias and find a large bias. The demonstration of a large bias will usually imply that the target crypto-system is not strong. Regarding the bias analysis, researchers tend to look for a theoretical solution for a specific problem. In this paper, we take a first step towards the synthetic approach on bias analysis. We successfully apply our synthetic analysis to improve the most recent linear attacks on CubeHash and Rabbit respectively. CubeHash was selected to the second round of SHA-3 competition. The best linear attack on 11-round CubeHash with 2470 queries was proposed in Ashur and Dunkelman (2011). We present an improved attack for 11-round CubeHash with complexity 2414.2. Based on our 11-round attack, we give a new linear attack for 12-round CubeHash with complexity 2509. It is the first known attack on 12 rounds with complexity below the security parameter 2512 of CubeHash. Rabbit is a stream cipher among the finalists of ECRYPT Stream Cipher Project (eSTREAM). It has also been published as informational RFC 4503 with the Internet Engineering Task Force (IETF), which is the main standardization body for Internet technology. For Rabbit, the best linear attack with complexity 2141 was recently presented in [9]. Our synthetic bias analysis yields the improved attack with complexity 2136.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s12095-012-0064-8", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.4929939", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136695", 
            "issn": [
              "1936-2447", 
              "1936-2455"
            ], 
            "name": "Cryptography and Communications", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "4"
          }
        ], 
        "keywords": [
          "Internet Engineering Task Force", 
          "Engineering Task Force", 
          "linear attack", 
          "improved attacks", 
          "ECRYPT Stream Cipher Project", 
          "Internet technology", 
          "stream cipher", 
          "standardization bodies", 
          "attacks", 
          "SHA-3 competition", 
          "linear cryptanalysis", 
          "specific problems", 
          "Cipher Project", 
          "main standardization bodies", 
          "CubeHash", 
          "queries", 
          "cryptanalysis", 
          "cipher", 
          "first step", 
          "complexity", 
          "Dunkelman", 
          "technology", 
          "finalists", 
          "applications", 
          "project", 
          "researchers", 
          "Task Force", 
          "solution", 
          "rounds", 
          "step", 
          "synthetic analysis", 
          "theoretical solution", 
          "large bias", 
          "analysis", 
          "synthetic approach", 
          "demonstration", 
          "paper", 
          "competition", 
          "target", 
          "second round", 
          "problem", 
          "approach", 
          "bias", 
          "bias analysis", 
          "body", 
          "force", 
          "linear analysis", 
          "best linear attack", 
          "rabbits", 
          "recent linear attacks", 
          "Ashur", 
          "complexity 2414.2", 
          "new linear attack", 
          "complexity 2509", 
          "security parameter 2512", 
          "parameter 2512", 
          "Stream Cipher Project", 
          "informational RFC 4503", 
          "RFC 4503", 
          "complexity 2141", 
          "synthetic bias analysis", 
          "complexity 2136", 
          "Synthetic linear analysis"
        ], 
        "name": "Synthetic linear analysis with applications to CubeHash and Rabbit", 
        "pagination": "259-276", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1032453864"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s12095-012-0064-8"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s12095-012-0064-8", 
          "https://app.dimensions.ai/details/publication/pub.1032453864"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:27", 
        "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/article/article_565.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s12095-012-0064-8"
      }
    ]
     

    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/s12095-012-0064-8'

    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/s12095-012-0064-8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12095-012-0064-8'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12095-012-0064-8'


     

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

    183 TRIPLES      22 PREDICATES      98 URIs      80 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s12095-012-0064-8 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author N538bb5b8769d41529dded6f4d9ab8e2d
    6 schema:citation sg:pub.10.1007/11799313_10
    7 sg:pub.10.1007/3-540-48285-7_33
    8 sg:pub.10.1007/978-3-540-75496-1_16
    9 sg:pub.10.1007/978-3-540-85886-7_14
    10 sg:pub.10.1007/978-3-642-18178-8_2
    11 sg:pub.10.1007/978-3-642-19574-7_5
    12 sg:pub.10.1007/978-3-642-21554-4_27
    13 sg:pub.10.1007/978-3-642-31912-9_17
    14 schema:datePublished 2012-07-31
    15 schema:datePublishedReg 2012-07-31
    16 schema:description In linear cryptanalysis, it has been considered most important and difficult to analyze the bias and find a large bias. The demonstration of a large bias will usually imply that the target crypto-system is not strong. Regarding the bias analysis, researchers tend to look for a theoretical solution for a specific problem. In this paper, we take a first step towards the synthetic approach on bias analysis. We successfully apply our synthetic analysis to improve the most recent linear attacks on CubeHash and Rabbit respectively. CubeHash was selected to the second round of SHA-3 competition. The best linear attack on 11-round CubeHash with 2470 queries was proposed in Ashur and Dunkelman (2011). We present an improved attack for 11-round CubeHash with complexity 2414.2. Based on our 11-round attack, we give a new linear attack for 12-round CubeHash with complexity 2509. It is the first known attack on 12 rounds with complexity below the security parameter 2512 of CubeHash. Rabbit is a stream cipher among the finalists of ECRYPT Stream Cipher Project (eSTREAM). It has also been published as informational RFC 4503 with the Internet Engineering Task Force (IETF), which is the main standardization body for Internet technology. For Rabbit, the best linear attack with complexity 2141 was recently presented in [9]. Our synthetic bias analysis yields the improved attack with complexity 2136.
    17 schema:genre article
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf Nd7c39244e8eb4cd08386a725c9289452
    21 Ne99af403a8e145619d52131c7ea4559a
    22 sg:journal.1136695
    23 schema:keywords Ashur
    24 Cipher Project
    25 CubeHash
    26 Dunkelman
    27 ECRYPT Stream Cipher Project
    28 Engineering Task Force
    29 Internet Engineering Task Force
    30 Internet technology
    31 RFC 4503
    32 SHA-3 competition
    33 Stream Cipher Project
    34 Synthetic linear analysis
    35 Task Force
    36 analysis
    37 applications
    38 approach
    39 attacks
    40 best linear attack
    41 bias
    42 bias analysis
    43 body
    44 cipher
    45 competition
    46 complexity
    47 complexity 2136
    48 complexity 2141
    49 complexity 2414.2
    50 complexity 2509
    51 cryptanalysis
    52 demonstration
    53 finalists
    54 first step
    55 force
    56 improved attacks
    57 informational RFC 4503
    58 large bias
    59 linear analysis
    60 linear attack
    61 linear cryptanalysis
    62 main standardization bodies
    63 new linear attack
    64 paper
    65 parameter 2512
    66 problem
    67 project
    68 queries
    69 rabbits
    70 recent linear attacks
    71 researchers
    72 rounds
    73 second round
    74 security parameter 2512
    75 solution
    76 specific problems
    77 standardization bodies
    78 step
    79 stream cipher
    80 synthetic analysis
    81 synthetic approach
    82 synthetic bias analysis
    83 target
    84 technology
    85 theoretical solution
    86 schema:name Synthetic linear analysis with applications to CubeHash and Rabbit
    87 schema:pagination 259-276
    88 schema:productId N9875d8ee25b5412ba1dba804101bab94
    89 Naf845fb79f864329839e06b54e7a67df
    90 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032453864
    91 https://doi.org/10.1007/s12095-012-0064-8
    92 schema:sdDatePublished 2022-01-01T18:27
    93 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    94 schema:sdPublisher Nc4f31050752347f4a85512b992ab2a45
    95 schema:url https://doi.org/10.1007/s12095-012-0064-8
    96 sgo:license sg:explorer/license/
    97 sgo:sdDataset articles
    98 rdf:type schema:ScholarlyArticle
    99 N1b498119f18e48dd9191ca816c531816 rdf:first sg:person.07653531142.18
    100 rdf:rest rdf:nil
    101 N538bb5b8769d41529dded6f4d9ab8e2d rdf:first sg:person.010630432145.10
    102 rdf:rest N6436516a06b84745b197e3629827f3bd
    103 N6436516a06b84745b197e3629827f3bd rdf:first sg:person.01353240467.39
    104 rdf:rest N1b498119f18e48dd9191ca816c531816
    105 N9875d8ee25b5412ba1dba804101bab94 schema:name dimensions_id
    106 schema:value pub.1032453864
    107 rdf:type schema:PropertyValue
    108 Naf845fb79f864329839e06b54e7a67df schema:name doi
    109 schema:value 10.1007/s12095-012-0064-8
    110 rdf:type schema:PropertyValue
    111 Nc4f31050752347f4a85512b992ab2a45 schema:name Springer Nature - SN SciGraph project
    112 rdf:type schema:Organization
    113 Nd7c39244e8eb4cd08386a725c9289452 schema:issueNumber 3-4
    114 rdf:type schema:PublicationIssue
    115 Ne99af403a8e145619d52131c7ea4559a schema:volumeNumber 4
    116 rdf:type schema:PublicationVolume
    117 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    118 schema:name Mathematical Sciences
    119 rdf:type schema:DefinedTerm
    120 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    121 schema:name Pure Mathematics
    122 rdf:type schema:DefinedTerm
    123 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    124 schema:name Applied Mathematics
    125 rdf:type schema:DefinedTerm
    126 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    127 schema:name Numerical and Computational Mathematics
    128 rdf:type schema:DefinedTerm
    129 sg:grant.4929939 http://pending.schema.org/fundedItem sg:pub.10.1007/s12095-012-0064-8
    130 rdf:type schema:MonetaryGrant
    131 sg:journal.1136695 schema:issn 1936-2447
    132 1936-2455
    133 schema:name Cryptography and Communications
    134 schema:publisher Springer Nature
    135 rdf:type schema:Periodical
    136 sg:person.010630432145.10 schema:affiliation grid-institutes:grid.458446.f
    137 schema:familyName Lu
    138 schema:givenName Yi
    139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010630432145.10
    140 rdf:type schema:Person
    141 sg:person.01353240467.39 schema:affiliation grid-institutes:grid.5333.6
    142 schema:familyName Vaudenay
    143 schema:givenName Serge
    144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01353240467.39
    145 rdf:type schema:Person
    146 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
    147 schema:familyName Meier
    148 schema:givenName Willi
    149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
    150 rdf:type schema:Person
    151 sg:pub.10.1007/11799313_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021327215
    152 https://doi.org/10.1007/11799313_10
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/3-540-48285-7_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038500879
    155 https://doi.org/10.1007/3-540-48285-7_33
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/978-3-540-75496-1_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000779144
    158 https://doi.org/10.1007/978-3-540-75496-1_16
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/978-3-540-85886-7_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051744247
    161 https://doi.org/10.1007/978-3-540-85886-7_14
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1007/978-3-642-18178-8_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037546787
    164 https://doi.org/10.1007/978-3-642-18178-8_2
    165 rdf:type schema:CreativeWork
    166 sg:pub.10.1007/978-3-642-19574-7_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022831806
    167 https://doi.org/10.1007/978-3-642-19574-7_5
    168 rdf:type schema:CreativeWork
    169 sg:pub.10.1007/978-3-642-21554-4_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034071158
    170 https://doi.org/10.1007/978-3-642-21554-4_27
    171 rdf:type schema:CreativeWork
    172 sg:pub.10.1007/978-3-642-31912-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026686964
    173 https://doi.org/10.1007/978-3-642-31912-9_17
    174 rdf:type schema:CreativeWork
    175 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
    176 schema:name FHNW, Windisch, Switzerland
    177 rdf:type schema:Organization
    178 grid-institutes:grid.458446.f schema:alternateName National Engineering Research Center of Fundamental Software, Institute of Software, Chinese Academy of Sciences, Beijing, China
    179 schema:name National Engineering Research Center of Fundamental Software, Institute of Software, Chinese Academy of Sciences, Beijing, China
    180 rdf:type schema:Organization
    181 grid-institutes:grid.5333.6 schema:alternateName EPFL, Lausanne, Switzerland
    182 schema:name EPFL, Lausanne, Switzerland
    183 rdf:type schema:Organization
     




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


    ...