How to Break MD5 and Other Hash Functions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Xiaoyun Wang , Hongbo Yu

ABSTRACT

MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL. More... »

PAGES

19-35

References to SciGraph publications

  • 1996. Cryptanalysis of MD4 in FAST SOFTWARE ENCRYPTION
  • 1997-12. RIPEMD with two-round compress function is not collision-free in JOURNAL OF CRYPTOLOGY
  • 1996. RIPEMD-160: A strengthened version of RIPEMD in FAST SOFTWARE ENCRYPTION
  • 2001-07-06. One Way Hash Functions and DES in ADVANCES IN CRYPTOLOGY — CRYPTO’ 89 PROCEEDINGS
  • 1993. Differential Cryptanalysis of the Data Encryption Standard in NONE
  • 1998. Differential collisions in SHA-0 in ADVANCES IN CRYPTOLOGY — CRYPTO '98
  • 1993. HAVAL — A one-way hashing algorithm with variable length of output (extended abstract) in ADVANCES IN CRYPTOLOGY — AUSCRYPT '92
  • 1991. The MD4 Message Digest Algorithm in ADVANCES IN CRYPTOLOGY-CRYPT0’ 90
  • 2004. Near-Collisions of SHA-0 in ADVANCES IN CRYPTOLOGY – CRYPTO 2004
  • 2001-07-06. A Design Principle for Hash Functions in ADVANCES IN CRYPTOLOGY — CRYPTO’ 89 PROCEEDINGS
  • 1994. Collisions for the compression function of MD5 in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’93
  • Book

    TITLE

    Advances in Cryptology – EUROCRYPT 2005

    ISBN

    978-3-540-25910-7
    978-3-540-32055-5

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11426639_2

    DOI

    http://dx.doi.org/10.1007/11426639_2

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": "Shandong University", 
              "id": "https://www.grid.ac/institutes/grid.27255.37", 
              "name": [
                "Shandong University, 250100, Jinan, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wang", 
            "givenName": "Xiaoyun", 
            "id": "sg:person.014307113655.13", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014307113655.13"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Shandong University", 
              "id": "https://www.grid.ac/institutes/grid.27255.37", 
              "name": [
                "Shandong University, 250100, Jinan, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yu", 
            "givenName": "Hongbo", 
            "id": "sg:person.014370615764.25", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014370615764.25"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0055720", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005449369", 
              "https://doi.org/10.1007/bfb0055720"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008729969", 
              "https://doi.org/10.1007/0-387-34805-0_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008729969", 
              "https://doi.org/10.1007/0-387-34805-0_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60865-6_44", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021127547", 
              "https://doi.org/10.1007/3-540-60865-6_44"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026402674", 
              "https://doi.org/10.1007/0-387-34805-0_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026402674", 
              "https://doi.org/10.1007/0-387-34805-0_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57220-1_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028079858", 
              "https://doi.org/10.1007/3-540-57220-1_54"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48285-7_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036089264", 
              "https://doi.org/10.1007/3-540-48285-7_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s001459900019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036779009", 
              "https://doi.org/10.1007/s001459900019"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-38424-3_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042887644", 
              "https://doi.org/10.1007/3-540-38424-3_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1047747404", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-9314-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047747404", 
              "https://doi.org/10.1007/978-1-4613-9314-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-9314-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047747404", 
              "https://doi.org/10.1007/978-1-4613-9314-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28628-8_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050229654", 
              "https://doi.org/10.1007/978-3-540-28628-8_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28628-8_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050229654", 
              "https://doi.org/10.1007/978-3-540-28628-8_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60865-6_43", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050400281", 
              "https://doi.org/10.1007/3-540-60865-6_43"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.", 
        "editor": [
          {
            "familyName": "Cramer", 
            "givenName": "Ronald", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11426639_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-25910-7", 
            "978-3-540-32055-5"
          ], 
          "name": "Advances in Cryptology \u2013 EUROCRYPT 2005", 
          "type": "Book"
        }, 
        "name": "How to Break MD5 and Other Hash Functions", 
        "pagination": "19-35", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1043264875"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11426639_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "ce15da7e82c89d4a7f6d1cece030cd668967b2455aff7c5a9fe16ed8bb9ecef9"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11426639_2", 
          "https://app.dimensions.ai/details/publication/pub.1043264875"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:05", 
        "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/0000000359_0000000359/records_29219_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11426639_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/11426639_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/11426639_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11426639_2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11426639_2'


     

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

    118 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11426639_2 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N4762b5bf73e14a98b671a5ecc3404489
    4 schema:citation sg:pub.10.1007/0-387-34805-0_39
    5 sg:pub.10.1007/0-387-34805-0_40
    6 sg:pub.10.1007/3-540-38424-3_22
    7 sg:pub.10.1007/3-540-48285-7_26
    8 sg:pub.10.1007/3-540-57220-1_54
    9 sg:pub.10.1007/3-540-60865-6_43
    10 sg:pub.10.1007/3-540-60865-6_44
    11 sg:pub.10.1007/978-1-4613-9314-6
    12 sg:pub.10.1007/978-3-540-28628-8_18
    13 sg:pub.10.1007/bfb0055720
    14 sg:pub.10.1007/s001459900019
    15 https://app.dimensions.ai/details/publication/pub.1047747404
    16 schema:datePublished 2005
    17 schema:datePublishedReg 2005-01-01
    18 schema:description MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.
    19 schema:editor N11cf25801ae94d0b928172a0d5e302f9
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N4c4f517d9b6147e3af2c12cb11222c04
    24 schema:name How to Break MD5 and Other Hash Functions
    25 schema:pagination 19-35
    26 schema:productId N00cfc9aea4cb4a3c8360b82e5383ee78
    27 N39f3095fb805403cbd2728ce38cb4843
    28 N80df1b8ded5c4b4d86ea76ef8e8fd4bb
    29 schema:publisher N0bd9cb8b7df24f1d8186efb7f4a95bca
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043264875
    31 https://doi.org/10.1007/11426639_2
    32 schema:sdDatePublished 2019-04-16T08:05
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N74cb47d8ea3c438ab1a468e9db7764bc
    35 schema:url https://link.springer.com/10.1007%2F11426639_2
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N00cfc9aea4cb4a3c8360b82e5383ee78 schema:name readcube_id
    40 schema:value ce15da7e82c89d4a7f6d1cece030cd668967b2455aff7c5a9fe16ed8bb9ecef9
    41 rdf:type schema:PropertyValue
    42 N0bd9cb8b7df24f1d8186efb7f4a95bca schema:location Berlin, Heidelberg
    43 schema:name Springer Berlin Heidelberg
    44 rdf:type schema:Organisation
    45 N11cf25801ae94d0b928172a0d5e302f9 rdf:first N7810e618566b488285042f470a2212a0
    46 rdf:rest rdf:nil
    47 N39f3095fb805403cbd2728ce38cb4843 schema:name dimensions_id
    48 schema:value pub.1043264875
    49 rdf:type schema:PropertyValue
    50 N4330bfd939574f63a137f4a0113c7e94 rdf:first sg:person.014370615764.25
    51 rdf:rest rdf:nil
    52 N4762b5bf73e14a98b671a5ecc3404489 rdf:first sg:person.014307113655.13
    53 rdf:rest N4330bfd939574f63a137f4a0113c7e94
    54 N4c4f517d9b6147e3af2c12cb11222c04 schema:isbn 978-3-540-25910-7
    55 978-3-540-32055-5
    56 schema:name Advances in Cryptology – EUROCRYPT 2005
    57 rdf:type schema:Book
    58 N74cb47d8ea3c438ab1a468e9db7764bc schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 N7810e618566b488285042f470a2212a0 schema:familyName Cramer
    61 schema:givenName Ronald
    62 rdf:type schema:Person
    63 N80df1b8ded5c4b4d86ea76ef8e8fd4bb schema:name doi
    64 schema:value 10.1007/11426639_2
    65 rdf:type schema:PropertyValue
    66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Information and Computing Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Computation Theory and Mathematics
    71 rdf:type schema:DefinedTerm
    72 sg:person.014307113655.13 schema:affiliation https://www.grid.ac/institutes/grid.27255.37
    73 schema:familyName Wang
    74 schema:givenName Xiaoyun
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014307113655.13
    76 rdf:type schema:Person
    77 sg:person.014370615764.25 schema:affiliation https://www.grid.ac/institutes/grid.27255.37
    78 schema:familyName Yu
    79 schema:givenName Hongbo
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014370615764.25
    81 rdf:type schema:Person
    82 sg:pub.10.1007/0-387-34805-0_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026402674
    83 https://doi.org/10.1007/0-387-34805-0_39
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/0-387-34805-0_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008729969
    86 https://doi.org/10.1007/0-387-34805-0_40
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/3-540-38424-3_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042887644
    89 https://doi.org/10.1007/3-540-38424-3_22
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/3-540-48285-7_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036089264
    92 https://doi.org/10.1007/3-540-48285-7_26
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/3-540-57220-1_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028079858
    95 https://doi.org/10.1007/3-540-57220-1_54
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/3-540-60865-6_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050400281
    98 https://doi.org/10.1007/3-540-60865-6_43
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/3-540-60865-6_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021127547
    101 https://doi.org/10.1007/3-540-60865-6_44
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/978-1-4613-9314-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047747404
    104 https://doi.org/10.1007/978-1-4613-9314-6
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/978-3-540-28628-8_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050229654
    107 https://doi.org/10.1007/978-3-540-28628-8_18
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/bfb0055720 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005449369
    110 https://doi.org/10.1007/bfb0055720
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/s001459900019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036779009
    113 https://doi.org/10.1007/s001459900019
    114 rdf:type schema:CreativeWork
    115 https://app.dimensions.ai/details/publication/pub.1047747404 schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.27255.37 schema:alternateName Shandong University
    117 schema:name Shandong University, 250100, Jinan, China
    118 rdf:type schema:Organization
     




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


    ...