Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Johannes Buchmann , Stanislav Bulygin , Jintai Ding , Wael Said Abd Elmageed Mohamed , Fabian Werner

ABSTRACT

Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding’s concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma’s implementation of F4. More... »

PAGES

140-155

References to SciGraph publications

  • 2008. MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy in POST-QUANTUM CRYPTOGRAPHY
  • 2009. Multivariate Public Key Cryptography in POST-QUANTUM CRYPTOGRAPHY
  • 2009. Algebraic Attack on the MQQ Public Key Cryptosystem in CRYPTOLOGY AND NETWORK SECURITY
  • 2010. MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals in INFORMATION, SECURITY AND CRYPTOLOGY – ICISC 2009
  • 2009. Overview of Cryptanalysis Techniques in Multivariate Public Key Cryptography in GRÖBNER BASES, CODING, AND CRYPTOGRAPHY
  • 2009. Algebraic Cryptanalysis in NONE
  • 2000. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2000
  • Book

    TITLE

    Cryptology and Network Security

    ISBN

    978-3-642-17618-0
    978-3-642-17619-7

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-17619-7_11

    DOI

    http://dx.doi.org/10.1007/978-3-642-17619-7_11

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Technical University of Darmstadt", 
              "id": "https://www.grid.ac/institutes/grid.6546.1", 
              "name": [
                "FB Informatik, TU Darmstadt, Hochschulstrasse 10, 64289, Darmstadt, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Buchmann", 
            "givenName": "Johannes", 
            "id": "sg:person.016400723075.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Center for Advanced Security Research Darmstadt (CASED), Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bulygin", 
            "givenName": "Stanislav", 
            "id": "sg:person.010425774147.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425774147.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Cincinnati", 
              "id": "https://www.grid.ac/institutes/grid.24827.3b", 
              "name": [
                "Department of Mathematical Sciences, University of Cincinnati, 45220, Cincinnati, OH, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ding", 
            "givenName": "Jintai", 
            "id": "sg:person.010723403013.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technical University of Darmstadt", 
              "id": "https://www.grid.ac/institutes/grid.6546.1", 
              "name": [
                "FB Informatik, TU Darmstadt, Hochschulstrasse 10, 64289, Darmstadt, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mohamed", 
            "givenName": "Wael Said Abd Elmageed", 
            "id": "sg:person.013634073236.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013634073236.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technical University of Darmstadt", 
              "id": "https://www.grid.ac/institutes/grid.6546.1", 
              "name": [
                "TU Darmstadt, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Werner", 
            "givenName": "Fabian", 
            "id": "sg:person.010621103143.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010621103143.01"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45539-6_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000285811", 
              "https://doi.org/10.1007/3-540-45539-6_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000585614", 
              "https://doi.org/10.1007/978-3-540-88403-3_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000585614", 
              "https://doi.org/10.1007/978-3-540-88403-3_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-88757-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008607024", 
              "https://doi.org/10.1007/978-0-387-88757-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-88757-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008607024", 
              "https://doi.org/10.1007/978-0-387-88757-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-88702-7_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014471166", 
              "https://doi.org/10.1007/978-3-540-88702-7_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-88702-7_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014471166", 
              "https://doi.org/10.1007/978-3-540-88702-7_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10433-6_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030842749", 
              "https://doi.org/10.1007/978-3-642-10433-6_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041918753", 
              "https://doi.org/10.1007/978-3-642-14423-3_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041918753", 
              "https://doi.org/10.1007/978-3-642-14423-3_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-93806-4_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049368744", 
              "https://doi.org/10.1007/978-3-540-93806-4_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.5121/ijnsa.2010.2201", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072619522"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding\u2019s concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma\u2019s implementation of F4.", 
        "editor": [
          {
            "familyName": "Heng", 
            "givenName": "Swee-Huay", 
            "type": "Person"
          }, 
          {
            "familyName": "Wright", 
            "givenName": "Rebecca N.", 
            "type": "Person"
          }, 
          {
            "familyName": "Goi", 
            "givenName": "Bok-Min", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-17619-7_11", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-17618-0", 
            "978-3-642-17619-7"
          ], 
          "name": "Cryptology and Network Security", 
          "type": "Book"
        }, 
        "name": "Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems", 
        "pagination": "140-155", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1046045813"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-17619-7_11"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "db560b7636d04bf74a0680391b4e5665543c8ca079648651be30687ad500303f"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-17619-7_11", 
          "https://app.dimensions.ai/details/publication/pub.1046045813"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:30", 
        "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/0000000364_0000000364/records_72835_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-17619-7_11"
      }
    ]
     

    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-17619-7_11'

    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-17619-7_11'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17619-7_11'

    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-17619-7_11'


     

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

    140 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-17619-7_11 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author Nd531a3d087364fbaa90b4ce3e1c61c8e
    4 schema:citation sg:pub.10.1007/3-540-45539-6_27
    5 sg:pub.10.1007/978-0-387-88757-9
    6 sg:pub.10.1007/978-3-540-88403-3_14
    7 sg:pub.10.1007/978-3-540-88702-7_6
    8 sg:pub.10.1007/978-3-540-93806-4_15
    9 sg:pub.10.1007/978-3-642-10433-6_26
    10 sg:pub.10.1007/978-3-642-14423-3_7
    11 https://doi.org/10.5121/ijnsa.2010.2201
    12 schema:datePublished 2010
    13 schema:datePublishedReg 2010-01-01
    14 schema:description Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding’s concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma’s implementation of F4.
    15 schema:editor N737c5a6a7e6e4630bc1ad5791d75290a
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N538527d6e21a4d189500940b26950ba0
    20 schema:name Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems
    21 schema:pagination 140-155
    22 schema:productId N9001f4cd015c4f7882546ae9e0bbe0f1
    23 Ne56b7fa53ba64327a879f2cefef03fb9
    24 Ne6db10da2dda4141ba6ec4aeac4213e7
    25 schema:publisher Nd84d1b42f86840b684fe10c1db194aed
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046045813
    27 https://doi.org/10.1007/978-3-642-17619-7_11
    28 schema:sdDatePublished 2019-04-16T08:30
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N4301c7c4d45746e7acf70f4fc9076601
    31 schema:url https://link.springer.com/10.1007%2F978-3-642-17619-7_11
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N3afe3ddbde034bf0b6a007d41c592dd6 rdf:first sg:person.013634073236.45
    36 rdf:rest Na9f36de12f6b49c7b0b37f2ea93041ef
    37 N4301c7c4d45746e7acf70f4fc9076601 schema:name Springer Nature - SN SciGraph project
    38 rdf:type schema:Organization
    39 N538527d6e21a4d189500940b26950ba0 schema:isbn 978-3-642-17618-0
    40 978-3-642-17619-7
    41 schema:name Cryptology and Network Security
    42 rdf:type schema:Book
    43 N737c5a6a7e6e4630bc1ad5791d75290a rdf:first Nc66b91d582604f77948620d70465689a
    44 rdf:rest Na9dd0eabdfd44012921cc06b9025da29
    45 N805c04008f0449cfa4243fe1eeff15cf rdf:first sg:person.010723403013.04
    46 rdf:rest N3afe3ddbde034bf0b6a007d41c592dd6
    47 N8c9da8df2868499cbaa8a501b400d250 rdf:first sg:person.010425774147.54
    48 rdf:rest N805c04008f0449cfa4243fe1eeff15cf
    49 N8d88485b71bb46c7a5bd1708f86c3ed5 rdf:first Ne1f6e7ec259f4b929368d3f374a46a08
    50 rdf:rest rdf:nil
    51 N9001f4cd015c4f7882546ae9e0bbe0f1 schema:name dimensions_id
    52 schema:value pub.1046045813
    53 rdf:type schema:PropertyValue
    54 N90fa4eb3d717464781136584fdc7d693 schema:familyName Wright
    55 schema:givenName Rebecca N.
    56 rdf:type schema:Person
    57 Na9dd0eabdfd44012921cc06b9025da29 rdf:first N90fa4eb3d717464781136584fdc7d693
    58 rdf:rest N8d88485b71bb46c7a5bd1708f86c3ed5
    59 Na9f36de12f6b49c7b0b37f2ea93041ef rdf:first sg:person.010621103143.01
    60 rdf:rest rdf:nil
    61 Nc66b91d582604f77948620d70465689a schema:familyName Heng
    62 schema:givenName Swee-Huay
    63 rdf:type schema:Person
    64 Nd531a3d087364fbaa90b4ce3e1c61c8e rdf:first sg:person.016400723075.52
    65 rdf:rest N8c9da8df2868499cbaa8a501b400d250
    66 Nd84d1b42f86840b684fe10c1db194aed schema:location Berlin, Heidelberg
    67 schema:name Springer Berlin Heidelberg
    68 rdf:type schema:Organisation
    69 Ne1f6e7ec259f4b929368d3f374a46a08 schema:familyName Goi
    70 schema:givenName Bok-Min
    71 rdf:type schema:Person
    72 Ne510f3e0704441deb06344a1aed1135f schema:name Center for Advanced Security Research Darmstadt (CASED), Germany
    73 rdf:type schema:Organization
    74 Ne56b7fa53ba64327a879f2cefef03fb9 schema:name doi
    75 schema:value 10.1007/978-3-642-17619-7_11
    76 rdf:type schema:PropertyValue
    77 Ne6db10da2dda4141ba6ec4aeac4213e7 schema:name readcube_id
    78 schema:value db560b7636d04bf74a0680391b4e5665543c8ca079648651be30687ad500303f
    79 rdf:type schema:PropertyValue
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Data Format
    85 rdf:type schema:DefinedTerm
    86 sg:person.010425774147.54 schema:affiliation Ne510f3e0704441deb06344a1aed1135f
    87 schema:familyName Bulygin
    88 schema:givenName Stanislav
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425774147.54
    90 rdf:type schema:Person
    91 sg:person.010621103143.01 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
    92 schema:familyName Werner
    93 schema:givenName Fabian
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010621103143.01
    95 rdf:type schema:Person
    96 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
    97 schema:familyName Ding
    98 schema:givenName Jintai
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
    100 rdf:type schema:Person
    101 sg:person.013634073236.45 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
    102 schema:familyName Mohamed
    103 schema:givenName Wael Said Abd Elmageed
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013634073236.45
    105 rdf:type schema:Person
    106 sg:person.016400723075.52 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
    107 schema:familyName Buchmann
    108 schema:givenName Johannes
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52
    110 rdf:type schema:Person
    111 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
    112 https://doi.org/10.1007/3-540-45539-6_27
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-0-387-88757-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008607024
    115 https://doi.org/10.1007/978-0-387-88757-9
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-540-88403-3_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000585614
    118 https://doi.org/10.1007/978-3-540-88403-3_14
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-540-88702-7_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014471166
    121 https://doi.org/10.1007/978-3-540-88702-7_6
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-540-93806-4_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049368744
    124 https://doi.org/10.1007/978-3-540-93806-4_15
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-642-10433-6_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030842749
    127 https://doi.org/10.1007/978-3-642-10433-6_26
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-3-642-14423-3_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041918753
    130 https://doi.org/10.1007/978-3-642-14423-3_7
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.5121/ijnsa.2010.2201 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072619522
    133 rdf:type schema:CreativeWork
    134 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
    135 schema:name Department of Mathematical Sciences, University of Cincinnati, 45220, Cincinnati, OH, USA
    136 rdf:type schema:Organization
    137 https://www.grid.ac/institutes/grid.6546.1 schema:alternateName Technical University of Darmstadt
    138 schema:name FB Informatik, TU Darmstadt, Hochschulstrasse 10, 64289, Darmstadt, Germany
    139 TU Darmstadt, Germany
    140 rdf:type schema:Organization
     




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


    ...