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 Nbac033b3640840e1b545656b40aa31d5
    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 N8393f8de349b435885441d11b480c704
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N3400fed074b14d3594c6b5b06207e1cd
    20 schema:name Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems
    21 schema:pagination 140-155
    22 schema:productId N90711e650b104d1d92769442dd5fa5fa
    23 Ncc7dc2cccf184b56b88a5f336cef6534
    24 Nef3b717d71f640bdb1d57a59bd1fbca4
    25 schema:publisher Nfcb96352f7cd413a84862a42033bd9d6
    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 N19ea2688b640479783d66bfd93f590cc
    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 N011eb3e7359e486ca2857262f2f4d6e9 schema:familyName Wright
    36 schema:givenName Rebecca N.
    37 rdf:type schema:Person
    38 N0dff50bc53fa471c8fe5f43886364c80 rdf:first N227d16758da44c0cab8e0e32c0840c44
    39 rdf:rest rdf:nil
    40 N19ea2688b640479783d66bfd93f590cc schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N227d16758da44c0cab8e0e32c0840c44 schema:familyName Goi
    43 schema:givenName Bok-Min
    44 rdf:type schema:Person
    45 N3400fed074b14d3594c6b5b06207e1cd schema:isbn 978-3-642-17618-0
    46 978-3-642-17619-7
    47 schema:name Cryptology and Network Security
    48 rdf:type schema:Book
    49 N8393f8de349b435885441d11b480c704 rdf:first Nafc2fd218b1846a38b19726be5e42250
    50 rdf:rest Nd92681a6952540289d472fd193496842
    51 N8cab9ad1a7d749e19c7bdf844d5e8c70 rdf:first sg:person.010425774147.54
    52 rdf:rest Nf8a8bb4a351246729227facfc3debaee
    53 N90711e650b104d1d92769442dd5fa5fa schema:name doi
    54 schema:value 10.1007/978-3-642-17619-7_11
    55 rdf:type schema:PropertyValue
    56 Nafc2fd218b1846a38b19726be5e42250 schema:familyName Heng
    57 schema:givenName Swee-Huay
    58 rdf:type schema:Person
    59 Nb2fe728ec9b44731b344482415920946 schema:name Center for Advanced Security Research Darmstadt (CASED), Germany
    60 rdf:type schema:Organization
    61 Nbac033b3640840e1b545656b40aa31d5 rdf:first sg:person.016400723075.52
    62 rdf:rest N8cab9ad1a7d749e19c7bdf844d5e8c70
    63 Nbcb504fca8e9432fa4c490a7edca9046 rdf:first sg:person.013634073236.45
    64 rdf:rest Nc72e83e3895a4ab48a0a224cb49779e7
    65 Nc72e83e3895a4ab48a0a224cb49779e7 rdf:first sg:person.010621103143.01
    66 rdf:rest rdf:nil
    67 Ncc7dc2cccf184b56b88a5f336cef6534 schema:name dimensions_id
    68 schema:value pub.1046045813
    69 rdf:type schema:PropertyValue
    70 Nd92681a6952540289d472fd193496842 rdf:first N011eb3e7359e486ca2857262f2f4d6e9
    71 rdf:rest N0dff50bc53fa471c8fe5f43886364c80
    72 Nef3b717d71f640bdb1d57a59bd1fbca4 schema:name readcube_id
    73 schema:value db560b7636d04bf74a0680391b4e5665543c8ca079648651be30687ad500303f
    74 rdf:type schema:PropertyValue
    75 Nf8a8bb4a351246729227facfc3debaee rdf:first sg:person.010723403013.04
    76 rdf:rest Nbcb504fca8e9432fa4c490a7edca9046
    77 Nfcb96352f7cd413a84862a42033bd9d6 schema:location Berlin, Heidelberg
    78 schema:name Springer Berlin Heidelberg
    79 rdf:type schema:Organisation
    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 Nb2fe728ec9b44731b344482415920946
    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)


    ...