Faster Multicollisions View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Jean-Philippe Aumasson

ABSTRACT

Joux’s multicollision attack is one of the most striking results on hash functions and also one of the simplest: it computes a k-collision on iterated hashes in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \log_2 k\rceil\cdot 2^{n/2}$\end{document}, whereas k!1/k·2n(k − 1)/k was thought to be optimal. Kelsey and Schneier improved this to 3·2n/2 if storage 2n/2 is available and if the compression functions admits easily found fixed-points. This paper presents a simple technique that reduces this cost to 2n/2 and negligible memory, when the IV can be chosen by the attacker. Additional benefits are shorter messages than the Kelsey/Schneier attack and cost-optimality. More... »

PAGES

67-77

Book

TITLE

Progress in Cryptology - INDOCRYPT 2008

ISBN

978-3-540-89753-8
978-3-540-89754-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-89754-5_6

DOI

http://dx.doi.org/10.1007/978-3-540-89754-5_6

DIMENSIONS

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


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": "FHNW, Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aumasson", 
        "givenName": "Jean-Philippe", 
        "id": "sg:person.012606440341.66", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "Joux\u2019s multicollision attack is one of the most striking results on hash functions and also one of the simplest: it computes a k-collision on iterated hashes in time \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\lceil \\log_2 k\\rceil\\cdot 2^{n/2}$\\end{document}, whereas k!1/k\u00b72n(k\u2009\u2212\u20091)/k was thought to be optimal. Kelsey and Schneier improved this to 3\u00b72n/2 if storage 2n/2 is available and if the compression functions admits easily found fixed-points. This paper presents a simple technique that reduces this cost to 2n/2 and negligible memory, when the IV can be chosen by the attacker. Additional benefits are shorter messages than the Kelsey/Schneier attack and cost-optimality.", 
    "editor": [
      {
        "familyName": "Chowdhury", 
        "givenName": "Dipanwita Roy", 
        "type": "Person"
      }, 
      {
        "familyName": "Rijmen", 
        "givenName": "Vincent", 
        "type": "Person"
      }, 
      {
        "familyName": "Das", 
        "givenName": "Abhijit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-89754-5_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-89753-8", 
        "978-3-540-89754-5"
      ], 
      "name": "Progress in Cryptology - INDOCRYPT 2008", 
      "type": "Book"
    }, 
    "keywords": [
      "simple technique", 
      "cost", 
      "technique", 
      "additional benefit", 
      "multicollision attack", 
      "results", 
      "simplest", 
      "collisions", 
      "time", 
      "striking result", 
      "function", 
      "attacks", 
      "compression function", 
      "short messages", 
      "benefits", 
      "hash", 
      "memory", 
      "attacker", 
      "hash function", 
      "multicollisions", 
      "messages", 
      "negligible memory", 
      "Schneier", 
      "Kelsey", 
      "paper"
    ], 
    "name": "Faster Multicollisions", 
    "pagination": "67-77", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045662003"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-89754-5_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-89754-5_6", 
      "https://app.dimensions.ai/details/publication/pub.1045662003"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:27", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_110.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-89754-5_6"
  }
]
 

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-540-89754-5_6'

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-540-89754-5_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-89754-5_6'

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-540-89754-5_6'


 

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

95 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-89754-5_6 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Ndf98f21da46147c9a0c490ed71e293d3
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema:description Joux’s multicollision attack is one of the most striking results on hash functions and also one of the simplest: it computes a k-collision on iterated hashes in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \log_2 k\rceil\cdot 2^{n/2}$\end{document}, whereas k!1/k·2n(k − 1)/k was thought to be optimal. Kelsey and Schneier improved this to 3·2n/2 if storage 2n/2 is available and if the compression functions admits easily found fixed-points. This paper presents a simple technique that reduces this cost to 2n/2 and negligible memory, when the IV can be chosen by the attacker. Additional benefits are shorter messages than the Kelsey/Schneier attack and cost-optimality.
7 schema:editor N7987ba90bffa44b5861d666e96749fcd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N41704547aca94a46826ebd712f4ed16c
12 schema:keywords Kelsey
13 Schneier
14 additional benefit
15 attacker
16 attacks
17 benefits
18 collisions
19 compression function
20 cost
21 function
22 hash
23 hash function
24 memory
25 messages
26 multicollision attack
27 multicollisions
28 negligible memory
29 paper
30 results
31 short messages
32 simple technique
33 simplest
34 striking result
35 technique
36 time
37 schema:name Faster Multicollisions
38 schema:pagination 67-77
39 schema:productId N6c323d5a4ef1480d8f2eb5010b65c778
40 Nb5d3bafc2c9f4668ba55594568b1d2df
41 schema:publisher N54ca227756d04991be9aad41f4ba9c94
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045662003
43 https://doi.org/10.1007/978-3-540-89754-5_6
44 schema:sdDatePublished 2022-06-01T22:27
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N4bba1deef4544f148d6219696ffdc52d
47 schema:url https://doi.org/10.1007/978-3-540-89754-5_6
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N1e28645a94d246548134fecde2ae8b6b schema:familyName Rijmen
52 schema:givenName Vincent
53 rdf:type schema:Person
54 N41704547aca94a46826ebd712f4ed16c schema:isbn 978-3-540-89753-8
55 978-3-540-89754-5
56 schema:name Progress in Cryptology - INDOCRYPT 2008
57 rdf:type schema:Book
58 N4bba1deef4544f148d6219696ffdc52d schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N54ca227756d04991be9aad41f4ba9c94 schema:name Springer Nature
61 rdf:type schema:Organisation
62 N62523ea38e4f49debe9e2c7a230842b2 rdf:first N7eb1910286d84c4dae1dc667f778e838
63 rdf:rest rdf:nil
64 N6c323d5a4ef1480d8f2eb5010b65c778 schema:name dimensions_id
65 schema:value pub.1045662003
66 rdf:type schema:PropertyValue
67 N6e6e590cbb984ee3ab9840411d43d977 rdf:first N1e28645a94d246548134fecde2ae8b6b
68 rdf:rest N62523ea38e4f49debe9e2c7a230842b2
69 N7987ba90bffa44b5861d666e96749fcd rdf:first N79ffa3da8d4243a9bd3dd2f380b00912
70 rdf:rest N6e6e590cbb984ee3ab9840411d43d977
71 N79ffa3da8d4243a9bd3dd2f380b00912 schema:familyName Chowdhury
72 schema:givenName Dipanwita Roy
73 rdf:type schema:Person
74 N7eb1910286d84c4dae1dc667f778e838 schema:familyName Das
75 schema:givenName Abhijit
76 rdf:type schema:Person
77 Nb5d3bafc2c9f4668ba55594568b1d2df schema:name doi
78 schema:value 10.1007/978-3-540-89754-5_6
79 rdf:type schema:PropertyValue
80 Ndf98f21da46147c9a0c490ed71e293d3 rdf:first sg:person.012606440341.66
81 rdf:rest rdf:nil
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
86 schema:name Artificial Intelligence and Image Processing
87 rdf:type schema:DefinedTerm
88 sg:person.012606440341.66 schema:affiliation grid-institutes:grid.410380.e
89 schema:familyName Aumasson
90 schema:givenName Jean-Philippe
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66
92 rdf:type schema:Person
93 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
94 schema:name FHNW, Windisch, Switzerland
95 rdf:type schema:Organization
 




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


...