Modeling for Three-Subset Division Property without Unknown Subset View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2021-05-20

AUTHORS

Yonglin Hao, Gregor Leander, Willi Meier, Yosuke Todo, Qingju Wang

ABSTRACT

A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 842-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 842-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to a distinguishing attack. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. In the application to ACORN, we prove that the 772-round key-recovery attack at ISC2019 is in fact a constant-sum distinguisher. We then give new key-recovery attacks mounting to 773-, 774- and 775-round ACORN. We verify the current best key-recovery attack on 892-round Kreyvium and recover the exact superpoly. We further propose a new attack mounting to 893 rounds. More... »

PAGES

22

References to SciGraph publications

  • 1997. The block cipher Square in FAST SOFTWARE ENCRYPTION
  • 2017-03-30. New Integral Characteristics of KASUMI Derived by Division Property in INFORMATION SECURITY APPLICATIONS
  • 2019-11-22. MILP-aided Method of Searching Division Property Using Three Subsets and Applications in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2019
  • 2017-08-02. Cube Attacks on Non-Blackbox Polynomials Based on Division Property in ADVANCES IN CRYPTOLOGY – CRYPTO 2017
  • 2016-07-21. Another View of the Division Property in ADVANCES IN CRYPTOLOGY – CRYPTO 2016
  • 2016-07-20. Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression in FAST SOFTWARE ENCRYPTION
  • 2019-02-03. Automatic Search for a Variant of Division Property Using Three Subsets in TOPICS IN CRYPTOLOGY – CT-RSA 2019
  • 2020-05-01. Modeling for Three-Subset Division Property Without Unknown Subset in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2020
  • 2020-12-06. Lower Bounds on the Degree of Block Ciphers in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2020
  • 2017-11-30. Automatic Search of Bit-Based Division Property for ARX Ciphers and Word-Based Division Property in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2017
  • 2016-07-20. Bit-Based Division Property and Application to Simon Family in FAST SOFTWARE ENCRYPTION
  • 2018-07-25. Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly in ADVANCES IN CRYPTOLOGY – CRYPTO 2018
  • 2015-04-14. Structural Evaluation by Generalized Integral Property in ADVANCES IN CRYPTOLOGY -- EUROCRYPT 2015
  • 2016-11-09. Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2016
  • 2017-08-25. Gimli : A Cross-Platform Permutation in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS – CHES 2017
  • 2017-08-25. GIFT: A Small Present in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS – CHES 2017
  • 2002-07-12. Integral Cryptanalysis in FAST SOFTWARE ENCRYPTION
  • 2015-08-01. Integral Cryptanalysis on Full MISTY1 in ADVANCES IN CRYPTOLOGY -- CRYPTO 2015
  • 2014-10-25. Cryptanalysis of Reduced-Round SIMON32 and SIMON48 in PROGRESS IN CRYPTOLOGY -- INDOCRYPT 2014
  • 2018-07-24. Fast Correlation Attack Revisited in ADVANCES IN CRYPTOLOGY – CRYPTO 2018
  • 2018-07-24. A Key-Recovery Attack on 855-round Trivium in ADVANCES IN CRYPTOLOGY – CRYPTO 2018
  • 2019-09-02. Cube Cryptanalysis of Round-Reduced ACORN in INFORMATION SECURITY
  • 2009. Cube Attacks on Tweakable Black Box Polynomials in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2009
  • 2018-05-08. On stream ciphers with provable beyond-the-birthday-bound security against time-memory-data tradeoff attacks in CRYPTOGRAPHY AND COMMUNICATIONS
  • 2017-10-20. New Differential Bounds and Division Property of Lilliput: Block Cipher with Extended Generalized Feistel Network in SELECTED AREAS IN CRYPTOGRAPHY – SAC 2016
  • 1994. Higher Order Derivatives and Differential Cryptanalysis in COMMUNICATIONS AND CRYPTOGRAPHY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00145-021-09383-2

    DOI

    http://dx.doi.org/10.1007/s00145-021-09383-2

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China", 
              "id": "http://www.grid.ac/institutes/grid.496622.d", 
              "name": [
                "State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hao", 
            "givenName": "Yonglin", 
            "id": "sg:person.014270173173.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Horst G\u00f6rtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany", 
              "id": "http://www.grid.ac/institutes/grid.5570.7", 
              "name": [
                "Horst G\u00f6rtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Leander", 
            "givenName": "Gregor", 
            "id": "sg:person.016572560277.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016572560277.70"
            ], 
            "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": "NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan", 
              "id": "http://www.grid.ac/institutes/None", 
              "name": [
                "NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Todo", 
            "givenName": "Yosuke", 
            "id": "sg:person.013247762751.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "SnT, University of Luxembourg, EschsurAlzette, Luxembourg", 
              "id": "http://www.grid.ac/institutes/grid.16008.3f", 
              "name": [
                "SnT, University of Luxembourg, EschsurAlzette, Luxembourg"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wang", 
            "givenName": "Qingju", 
            "id": "sg:person.011431743334.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-96881-0_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105780992", 
              "https://doi.org/10.1007/978-3-319-96881-0_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0052343", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018616072", 
              "https://doi.org/10.1007/bfb0052343"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-66787-4_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091344107", 
              "https://doi.org/10.1007/978-3-319-66787-4_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-47989-6_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047706904", 
              "https://doi.org/10.1007/978-3-662-47989-6_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-64837-4_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1133275468", 
              "https://doi.org/10.1007/978-3-030-64837-4_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-96884-1_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105813840", 
              "https://doi.org/10.1007/978-3-319-96884-1_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-70694-8_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093079621", 
              "https://doi.org/10.1007/978-3-319-70694-8_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-12612-4_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1111894775", 
              "https://doi.org/10.1007/978-3-030-12612-4_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-2694-0_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010308889", 
              "https://doi.org/10.1007/978-1-4615-2694-0_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-66787-4_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091344108", 
              "https://doi.org/10.1007/978-3-319-66787-4_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-53018-4_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035525395", 
              "https://doi.org/10.1007/978-3-662-53018-4_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-52993-5_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010467891", 
              "https://doi.org/10.1007/978-3-662-52993-5_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-69453-5_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092291531", 
              "https://doi.org/10.1007/978-3-319-69453-5_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-63697-9_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091024677", 
              "https://doi.org/10.1007/978-3-319-63697-9_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45661-9_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009882418", 
              "https://doi.org/10.1007/3-540-45661-9_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-96881-0_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105780991", 
              "https://doi.org/10.1007/978-3-319-96881-0_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-52993-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052565510", 
              "https://doi.org/10.1007/978-3-662-52993-5_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-34618-8_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1122795186", 
              "https://doi.org/10.1007/978-3-030-34618-8_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-30215-3_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1120756874", 
              "https://doi.org/10.1007/978-3-030-30215-3_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-56549-1_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084723155", 
              "https://doi.org/10.1007/978-3-319-56549-1_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-46800-5_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000291591", 
              "https://doi.org/10.1007/978-3-662-46800-5_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-53887-6_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084897406", 
              "https://doi.org/10.1007/978-3-662-53887-6_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-45721-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1127314031", 
              "https://doi.org/10.1007/978-3-030-45721-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01001-9_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052713322", 
              "https://doi.org/10.1007/978-3-642-01001-9_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s12095-018-0294-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1103887204", 
              "https://doi.org/10.1007/s12095-018-0294-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-13039-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000317005", 
              "https://doi.org/10.1007/978-3-319-13039-2_9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-05-20", 
        "datePublishedReg": "2021-05-20", 
        "description": "A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 842-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 842-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to a distinguishing attack. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. In the application to ACORN, we prove that the 772-round key-recovery attack at ISC2019 is in fact a constant-sum distinguisher. We then give new key-recovery attacks mounting to 773-, 774- and 775-round ACORN. We verify the current best key-recovery attack on 892-round Kreyvium and recover the exact superpoly. We further propose a new attack mounting to 893 rounds.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00145-021-09383-2", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.8454748", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136278", 
            "issn": [
              "0933-2790", 
              "1432-1378"
            ], 
            "name": "Journal of Cryptology", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "34"
          }
        ], 
        "keywords": [
          "key recovery attack", 
          "automatic tool", 
          "best key-recovery attack", 
          "unknown subset", 
          "SAT/SMT", 
          "new key recovery attack", 
          "new efficient algorithm", 
          "division property", 
          "art algorithms", 
          "new attacks", 
          "stream cipher", 
          "efficient algorithm", 
          "generic tool", 
          "inaccuracy problem", 
          "new algorithm", 
          "algorithm", 
          "attacks", 
          "cipher", 
          "integral distinguishers", 
          "cube attack", 
          "distinguishing attack", 
          "tool", 
          "applications", 
          "security", 
          "critical flaws", 
          "distinguisher", 
          "MILP", 
          "SMT", 
          "Kreyvium", 
          "Trivium", 
          "superpoly", 
          "flaws", 
          "rounds", 
          "subset", 
          "promising method", 
          "inaccuracy", 
          "method", 
          "state", 
          "results", 
          "fact", 
          "propagation", 
          "properties", 
          "acorns", 
          "problem", 
          "degenerate", 
          "paper", 
          "division property degenerate", 
          "property degenerate", 
          "three-subset division property", 
          "Asiacrypt2019", 
          "CRYPTO2018", 
          "Grain-128AEAD", 
          "ISC2019", 
          "constant-sum distinguisher", 
          "current best key-recovery attack", 
          "exact superpoly"
        ], 
        "name": "Modeling for Three-Subset Division Property without Unknown Subset", 
        "pagination": "22", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1139034530"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00145-021-09383-2"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00145-021-09383-2", 
          "https://app.dimensions.ai/details/publication/pub.1139034530"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T19:00", 
        "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_904.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00145-021-09383-2"
      }
    ]
     

    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-021-09383-2'

    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-021-09383-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-021-09383-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-021-09383-2'


     

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

    260 TRIPLES      22 PREDICATES      107 URIs      73 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00145-021-09383-2 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nde462484777049a5a45a862f07ebe722
    4 schema:citation sg:pub.10.1007/3-540-45661-9_9
    5 sg:pub.10.1007/978-1-4615-2694-0_23
    6 sg:pub.10.1007/978-3-030-12612-4_21
    7 sg:pub.10.1007/978-3-030-30215-3_3
    8 sg:pub.10.1007/978-3-030-34618-8_14
    9 sg:pub.10.1007/978-3-030-45721-1_17
    10 sg:pub.10.1007/978-3-030-64837-4_18
    11 sg:pub.10.1007/978-3-319-13039-2_9
    12 sg:pub.10.1007/978-3-319-56549-1_23
    13 sg:pub.10.1007/978-3-319-63697-9_9
    14 sg:pub.10.1007/978-3-319-66787-4_15
    15 sg:pub.10.1007/978-3-319-66787-4_16
    16 sg:pub.10.1007/978-3-319-69453-5_15
    17 sg:pub.10.1007/978-3-319-70694-8_5
    18 sg:pub.10.1007/978-3-319-96881-0_5
    19 sg:pub.10.1007/978-3-319-96881-0_6
    20 sg:pub.10.1007/978-3-319-96884-1_10
    21 sg:pub.10.1007/978-3-642-01001-9_16
    22 sg:pub.10.1007/978-3-662-46800-5_12
    23 sg:pub.10.1007/978-3-662-47989-6_20
    24 sg:pub.10.1007/978-3-662-52993-5_16
    25 sg:pub.10.1007/978-3-662-52993-5_18
    26 sg:pub.10.1007/978-3-662-53018-4_24
    27 sg:pub.10.1007/978-3-662-53887-6_24
    28 sg:pub.10.1007/bfb0052343
    29 sg:pub.10.1007/s12095-018-0294-5
    30 schema:datePublished 2021-05-20
    31 schema:datePublishedReg 2021-05-20
    32 schema:description A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 842-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 842-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to a distinguishing attack. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. In the application to ACORN, we prove that the 772-round key-recovery attack at ISC2019 is in fact a constant-sum distinguisher. We then give new key-recovery attacks mounting to 773-, 774- and 775-round ACORN. We verify the current best key-recovery attack on 892-round Kreyvium and recover the exact superpoly. We further propose a new attack mounting to 893 rounds.
    33 schema:genre article
    34 schema:inLanguage en
    35 schema:isAccessibleForFree false
    36 schema:isPartOf Nafff36792bfd4d8fbf570913b64e7916
    37 Nec098622fb9d4bbfbf91feb43ac96517
    38 sg:journal.1136278
    39 schema:keywords Asiacrypt2019
    40 CRYPTO2018
    41 Grain-128AEAD
    42 ISC2019
    43 Kreyvium
    44 MILP
    45 SAT/SMT
    46 SMT
    47 Trivium
    48 acorns
    49 algorithm
    50 applications
    51 art algorithms
    52 attacks
    53 automatic tool
    54 best key-recovery attack
    55 cipher
    56 constant-sum distinguisher
    57 critical flaws
    58 cube attack
    59 current best key-recovery attack
    60 degenerate
    61 distinguisher
    62 distinguishing attack
    63 division property
    64 division property degenerate
    65 efficient algorithm
    66 exact superpoly
    67 fact
    68 flaws
    69 generic tool
    70 inaccuracy
    71 inaccuracy problem
    72 integral distinguishers
    73 key recovery attack
    74 method
    75 new algorithm
    76 new attacks
    77 new efficient algorithm
    78 new key recovery attack
    79 paper
    80 problem
    81 promising method
    82 propagation
    83 properties
    84 property degenerate
    85 results
    86 rounds
    87 security
    88 state
    89 stream cipher
    90 subset
    91 superpoly
    92 three-subset division property
    93 tool
    94 unknown subset
    95 schema:name Modeling for Three-Subset Division Property without Unknown Subset
    96 schema:pagination 22
    97 schema:productId N2cbd6f0eea5042d4a7944a03cfd2764f
    98 Nf6bca3cc122e4f0fa4ab134ce96e3a16
    99 schema:sameAs https://app.dimensions.ai/details/publication/pub.1139034530
    100 https://doi.org/10.1007/s00145-021-09383-2
    101 schema:sdDatePublished 2022-01-01T19:00
    102 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    103 schema:sdPublisher N6602fb4430404369970a58aa229145cc
    104 schema:url https://doi.org/10.1007/s00145-021-09383-2
    105 sgo:license sg:explorer/license/
    106 sgo:sdDataset articles
    107 rdf:type schema:ScholarlyArticle
    108 N205aadcde5614f3eb15f13d78a5ed249 rdf:first sg:person.013247762751.78
    109 rdf:rest N6bf4c3e4b5834344926e7fd32e882876
    110 N2cbd6f0eea5042d4a7944a03cfd2764f schema:name doi
    111 schema:value 10.1007/s00145-021-09383-2
    112 rdf:type schema:PropertyValue
    113 N6602fb4430404369970a58aa229145cc schema:name Springer Nature - SN SciGraph project
    114 rdf:type schema:Organization
    115 N6bf4c3e4b5834344926e7fd32e882876 rdf:first sg:person.011431743334.40
    116 rdf:rest rdf:nil
    117 N83195d2b57034897a0a4fc83df045d35 rdf:first sg:person.016572560277.70
    118 rdf:rest N935205d42e4443e0bcf8e89aa37fa5e7
    119 N935205d42e4443e0bcf8e89aa37fa5e7 rdf:first sg:person.07653531142.18
    120 rdf:rest N205aadcde5614f3eb15f13d78a5ed249
    121 Nafff36792bfd4d8fbf570913b64e7916 schema:volumeNumber 34
    122 rdf:type schema:PublicationVolume
    123 Nde462484777049a5a45a862f07ebe722 rdf:first sg:person.014270173173.47
    124 rdf:rest N83195d2b57034897a0a4fc83df045d35
    125 Nec098622fb9d4bbfbf91feb43ac96517 schema:issueNumber 3
    126 rdf:type schema:PublicationIssue
    127 Nf6bca3cc122e4f0fa4ab134ce96e3a16 schema:name dimensions_id
    128 schema:value pub.1139034530
    129 rdf:type schema:PropertyValue
    130 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    131 schema:name Information and Computing Sciences
    132 rdf:type schema:DefinedTerm
    133 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    134 schema:name Artificial Intelligence and Image Processing
    135 rdf:type schema:DefinedTerm
    136 sg:grant.8454748 http://pending.schema.org/fundedItem sg:pub.10.1007/s00145-021-09383-2
    137 rdf:type schema:MonetaryGrant
    138 sg:journal.1136278 schema:issn 0933-2790
    139 1432-1378
    140 schema:name Journal of Cryptology
    141 schema:publisher Springer Nature
    142 rdf:type schema:Periodical
    143 sg:person.011431743334.40 schema:affiliation grid-institutes:grid.16008.3f
    144 schema:familyName Wang
    145 schema:givenName Qingju
    146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40
    147 rdf:type schema:Person
    148 sg:person.013247762751.78 schema:affiliation grid-institutes:None
    149 schema:familyName Todo
    150 schema:givenName Yosuke
    151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013247762751.78
    152 rdf:type schema:Person
    153 sg:person.014270173173.47 schema:affiliation grid-institutes:grid.496622.d
    154 schema:familyName Hao
    155 schema:givenName Yonglin
    156 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270173173.47
    157 rdf:type schema:Person
    158 sg:person.016572560277.70 schema:affiliation grid-institutes:grid.5570.7
    159 schema:familyName Leander
    160 schema:givenName Gregor
    161 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016572560277.70
    162 rdf:type schema:Person
    163 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
    164 schema:familyName Meier
    165 schema:givenName Willi
    166 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
    167 rdf:type schema:Person
    168 sg:pub.10.1007/3-540-45661-9_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009882418
    169 https://doi.org/10.1007/3-540-45661-9_9
    170 rdf:type schema:CreativeWork
    171 sg:pub.10.1007/978-1-4615-2694-0_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010308889
    172 https://doi.org/10.1007/978-1-4615-2694-0_23
    173 rdf:type schema:CreativeWork
    174 sg:pub.10.1007/978-3-030-12612-4_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111894775
    175 https://doi.org/10.1007/978-3-030-12612-4_21
    176 rdf:type schema:CreativeWork
    177 sg:pub.10.1007/978-3-030-30215-3_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1120756874
    178 https://doi.org/10.1007/978-3-030-30215-3_3
    179 rdf:type schema:CreativeWork
    180 sg:pub.10.1007/978-3-030-34618-8_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1122795186
    181 https://doi.org/10.1007/978-3-030-34618-8_14
    182 rdf:type schema:CreativeWork
    183 sg:pub.10.1007/978-3-030-45721-1_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127314031
    184 https://doi.org/10.1007/978-3-030-45721-1_17
    185 rdf:type schema:CreativeWork
    186 sg:pub.10.1007/978-3-030-64837-4_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1133275468
    187 https://doi.org/10.1007/978-3-030-64837-4_18
    188 rdf:type schema:CreativeWork
    189 sg:pub.10.1007/978-3-319-13039-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000317005
    190 https://doi.org/10.1007/978-3-319-13039-2_9
    191 rdf:type schema:CreativeWork
    192 sg:pub.10.1007/978-3-319-56549-1_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084723155
    193 https://doi.org/10.1007/978-3-319-56549-1_23
    194 rdf:type schema:CreativeWork
    195 sg:pub.10.1007/978-3-319-63697-9_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091024677
    196 https://doi.org/10.1007/978-3-319-63697-9_9
    197 rdf:type schema:CreativeWork
    198 sg:pub.10.1007/978-3-319-66787-4_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091344107
    199 https://doi.org/10.1007/978-3-319-66787-4_15
    200 rdf:type schema:CreativeWork
    201 sg:pub.10.1007/978-3-319-66787-4_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091344108
    202 https://doi.org/10.1007/978-3-319-66787-4_16
    203 rdf:type schema:CreativeWork
    204 sg:pub.10.1007/978-3-319-69453-5_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092291531
    205 https://doi.org/10.1007/978-3-319-69453-5_15
    206 rdf:type schema:CreativeWork
    207 sg:pub.10.1007/978-3-319-70694-8_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093079621
    208 https://doi.org/10.1007/978-3-319-70694-8_5
    209 rdf:type schema:CreativeWork
    210 sg:pub.10.1007/978-3-319-96881-0_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105780991
    211 https://doi.org/10.1007/978-3-319-96881-0_5
    212 rdf:type schema:CreativeWork
    213 sg:pub.10.1007/978-3-319-96881-0_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105780992
    214 https://doi.org/10.1007/978-3-319-96881-0_6
    215 rdf:type schema:CreativeWork
    216 sg:pub.10.1007/978-3-319-96884-1_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105813840
    217 https://doi.org/10.1007/978-3-319-96884-1_10
    218 rdf:type schema:CreativeWork
    219 sg:pub.10.1007/978-3-642-01001-9_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052713322
    220 https://doi.org/10.1007/978-3-642-01001-9_16
    221 rdf:type schema:CreativeWork
    222 sg:pub.10.1007/978-3-662-46800-5_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000291591
    223 https://doi.org/10.1007/978-3-662-46800-5_12
    224 rdf:type schema:CreativeWork
    225 sg:pub.10.1007/978-3-662-47989-6_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047706904
    226 https://doi.org/10.1007/978-3-662-47989-6_20
    227 rdf:type schema:CreativeWork
    228 sg:pub.10.1007/978-3-662-52993-5_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052565510
    229 https://doi.org/10.1007/978-3-662-52993-5_16
    230 rdf:type schema:CreativeWork
    231 sg:pub.10.1007/978-3-662-52993-5_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010467891
    232 https://doi.org/10.1007/978-3-662-52993-5_18
    233 rdf:type schema:CreativeWork
    234 sg:pub.10.1007/978-3-662-53018-4_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035525395
    235 https://doi.org/10.1007/978-3-662-53018-4_24
    236 rdf:type schema:CreativeWork
    237 sg:pub.10.1007/978-3-662-53887-6_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084897406
    238 https://doi.org/10.1007/978-3-662-53887-6_24
    239 rdf:type schema:CreativeWork
    240 sg:pub.10.1007/bfb0052343 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018616072
    241 https://doi.org/10.1007/bfb0052343
    242 rdf:type schema:CreativeWork
    243 sg:pub.10.1007/s12095-018-0294-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103887204
    244 https://doi.org/10.1007/s12095-018-0294-5
    245 rdf:type schema:CreativeWork
    246 grid-institutes:None schema:alternateName NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
    247 schema:name NTT Secure Platform Laboratories, 180-8585, Tokyo, Japan
    248 rdf:type schema:Organization
    249 grid-institutes:grid.16008.3f schema:alternateName SnT, University of Luxembourg, EschsurAlzette, Luxembourg
    250 schema:name SnT, University of Luxembourg, EschsurAlzette, Luxembourg
    251 rdf:type schema:Organization
    252 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
    253 schema:name FHNW, Windisch, Switzerland
    254 rdf:type schema:Organization
    255 grid-institutes:grid.496622.d schema:alternateName State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
    256 schema:name State Key Laboratory of Cryptology, P.O. Box 5159, 100878, Beijing, China
    257 rdf:type schema:Organization
    258 grid-institutes:grid.5570.7 schema:alternateName Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany
    259 schema:name Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany
    260 rdf:type schema:Organization
     




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


    ...