Security Analysis of the Mode of JH Hash Function View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Rishiraj Bhattacharyya , Avradip Mandal , Mridul Nandi

ABSTRACT

Recently, NIST has selected 14 second round candidates of SHA3 competition. One of these candidates will win the competition and eventually become the new hash function standard. In TCC’04, Maurer et al introduced the notion of indifferentiability as a generalization of the concept of the indistinguishability of two systems. Indifferentiability is the appropriate notion of modeling a random oracle as well as a strong security criteria for a hash-design. In this paper we analyze the indifferentiability and preimage resistance of JH hash function which is one of the SHA3 second round candidates. JH uses a 2n bit fixed permutation based compression function and applies chopMD domain extension with specific padding.We show under the assumption that the underlying permutations is a 2n-bit random permutation, JH mode of operation with output length 2n − s bits, is indifferentiable from a random oracle with distinguisher’s advantage bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\frac{q^2\sigma}{2^s} + \frac{q^3}{2^n})$\end{document} where σ is the total number of blocks queried by distinguisher.We show that the padding rule used in JH is essential as there is a simple indifferentiablity distinguisher (with constant query complexity) against JH mode of operation without length padding outputting n bit digest.We prove that a little modification (namely chopping different bits) of JH mode of operation enables us to construct a hash function based on random permutation (without any length padding) with similar bound of sponge constructions (with fixed output size) and with same efficiency.On the other hand, we improve the preimage attack of query complexity 2510.3 due to Mendel and Thompson. Using multicollisions in both forward and reverse direction, we show a preimage attack on JH with n = 512,s = 512 in 2507 queries to the permutation. More... »

PAGES

168-191

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13858-4_10

DOI

http://dx.doi.org/10.1007/978-3-642-13858-4_10

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Indian Statistical Institute, Kolkata, India", 
          "id": "http://www.grid.ac/institutes/grid.39953.35", 
          "name": [
            "Indian Statistical Institute, Kolkata, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhattacharyya", 
        "givenName": "Rishiraj", 
        "id": "sg:person.013060533545.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013060533545.97"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 du Luxembourg, Luxembourg", 
          "id": "http://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "Universit\u00e9 du Luxembourg, Luxembourg"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mandal", 
        "givenName": "Avradip", 
        "id": "sg:person.010716613427.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010716613427.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NIST, USA and Computer Science Department, The George Washington University", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "NIST, USA and Computer Science Department, The George Washington University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nandi", 
        "givenName": "Mridul", 
        "id": "sg:person.010452652471.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010452652471.74"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Recently, NIST has selected 14 second round candidates of SHA3 competition. One of these candidates will win the competition and eventually become the new hash function standard. In TCC\u201904, Maurer et al introduced the notion of indifferentiability as a generalization of the concept of the indistinguishability of two systems. Indifferentiability is the appropriate notion of modeling a random oracle as well as a strong security criteria for a hash-design. In this paper we analyze the indifferentiability and preimage resistance of JH hash function which is one of the SHA3 second round candidates. JH uses a 2n bit fixed permutation based compression function and applies chopMD domain extension with specific padding.We show under the assumption that the underlying permutations is a 2n-bit random permutation, JH mode of operation with output length 2n\u2009\u2212\u2009s bits, is indifferentiable from a random oracle with distinguisher\u2019s advantage bounded by \\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}$O(\\frac{q^2\\sigma}{2^s} + \\frac{q^3}{2^n})$\\end{document} where \u03c3 is the total number of blocks queried by distinguisher.We show that the padding rule used in JH is essential as there is a simple indifferentiablity distinguisher (with constant query complexity) against JH mode of operation without length padding outputting n bit digest.We prove that a little modification (namely chopping different bits) of JH mode of operation enables us to construct a hash function based on random permutation (without any length padding) with similar bound of sponge constructions (with fixed output size) and with same efficiency.On the other hand, we improve the preimage attack of query complexity 2510.3 due to Mendel and Thompson. Using multicollisions in both forward and reverse direction, we show a preimage attack on JH with n\u2009=\u2009512,s\u2009=\u2009512 in 2507 queries to the permutation.", 
    "editor": [
      {
        "familyName": "Hong", 
        "givenName": "Seokhie", 
        "type": "Person"
      }, 
      {
        "familyName": "Iwata", 
        "givenName": "Tetsu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13858-4_10", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13857-7", 
        "978-3-642-13858-4"
      ], 
      "name": "Fast Software Encryption", 
      "type": "Book"
    }, 
    "keywords": [
      "hash function", 
      "random oracles", 
      "second round candidates", 
      "strong security criterion", 
      "preimage attack", 
      "security criteria", 
      "random permutation", 
      "sponge construction", 
      "security analysis", 
      "SHA3 competition", 
      "notion of indifferentiability", 
      "preimage resistance", 
      "compression function", 
      "domain extension", 
      "s bits", 
      "indifferentiability", 
      "oracle", 
      "attacks", 
      "Maurer et al", 
      "appropriate notion", 
      "bits", 
      "permutations", 
      "little modification", 
      "queries", 
      "indistinguishability", 
      "operation", 
      "distinguisher", 
      "NIST", 
      "padding", 
      "advantages", 
      "notion", 
      "concept", 
      "system", 
      "rules", 
      "same efficiency", 
      "standards", 
      "generalization", 
      "extension", 
      "block", 
      "construction", 
      "efficiency", 
      "candidates", 
      "competition", 
      "et al", 
      "function", 
      "assumption", 
      "mode", 
      "total number", 
      "number", 
      "hand", 
      "Mendel", 
      "direction", 
      "criteria", 
      "analysis", 
      "digests", 
      "modification", 
      "al", 
      "length 2n", 
      "Thompson", 
      "multicollisions", 
      "JH", 
      "paper", 
      "resistance", 
      "JH hash function"
    ], 
    "name": "Security Analysis of the Mode of JH Hash Function", 
    "pagination": "168-191", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042043203"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13858-4_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13858-4_10", 
      "https://app.dimensions.ai/details/publication/pub.1042043203"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_327.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13858-4_10"
  }
]
 

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-13858-4_10'

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-13858-4_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13858-4_10'

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-13858-4_10'


 

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

148 TRIPLES      22 PREDICATES      89 URIs      82 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13858-4_10 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N64ab4bde669c45a1bb1190c7292907c5
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Recently, NIST has selected 14 second round candidates of SHA3 competition. One of these candidates will win the competition and eventually become the new hash function standard. In TCC’04, Maurer et al introduced the notion of indifferentiability as a generalization of the concept of the indistinguishability of two systems. Indifferentiability is the appropriate notion of modeling a random oracle as well as a strong security criteria for a hash-design. In this paper we analyze the indifferentiability and preimage resistance of JH hash function which is one of the SHA3 second round candidates. JH uses a 2n bit fixed permutation based compression function and applies chopMD domain extension with specific padding.We show under the assumption that the underlying permutations is a 2n-bit random permutation, JH mode of operation with output length 2n − s bits, is indifferentiable from a random oracle with distinguisher’s advantage bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\frac{q^2\sigma}{2^s} + \frac{q^3}{2^n})$\end{document} where σ is the total number of blocks queried by distinguisher.We show that the padding rule used in JH is essential as there is a simple indifferentiablity distinguisher (with constant query complexity) against JH mode of operation without length padding outputting n bit digest.We prove that a little modification (namely chopping different bits) of JH mode of operation enables us to construct a hash function based on random permutation (without any length padding) with similar bound of sponge constructions (with fixed output size) and with same efficiency.On the other hand, we improve the preimage attack of query complexity 2510.3 due to Mendel and Thompson. Using multicollisions in both forward and reverse direction, we show a preimage attack on JH with n = 512,s = 512 in 2507 queries to the permutation.
7 schema:editor N5a3446021db144e2867c3f8dcbef7f24
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N46909b08506a4bf1971724f65f15dab7
11 schema:keywords JH
12 JH hash function
13 Maurer et al
14 Mendel
15 NIST
16 SHA3 competition
17 Thompson
18 advantages
19 al
20 analysis
21 appropriate notion
22 assumption
23 attacks
24 bits
25 block
26 candidates
27 competition
28 compression function
29 concept
30 construction
31 criteria
32 digests
33 direction
34 distinguisher
35 domain extension
36 efficiency
37 et al
38 extension
39 function
40 generalization
41 hand
42 hash function
43 indifferentiability
44 indistinguishability
45 length 2n
46 little modification
47 mode
48 modification
49 multicollisions
50 notion
51 notion of indifferentiability
52 number
53 operation
54 oracle
55 padding
56 paper
57 permutations
58 preimage attack
59 preimage resistance
60 queries
61 random oracles
62 random permutation
63 resistance
64 rules
65 s bits
66 same efficiency
67 second round candidates
68 security analysis
69 security criteria
70 sponge construction
71 standards
72 strong security criterion
73 system
74 total number
75 schema:name Security Analysis of the Mode of JH Hash Function
76 schema:pagination 168-191
77 schema:productId Ndeef0bd71f43440daaa4b2d19a5e9480
78 Ne5eb3e4589c04983bc49e4bce6dc5fdc
79 schema:publisher Nc623ed3c53894645a7768c9b75843384
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042043203
81 https://doi.org/10.1007/978-3-642-13858-4_10
82 schema:sdDatePublished 2022-11-24T21:16
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher N400cbf4a70954dccb48458a0af551a43
85 schema:url https://doi.org/10.1007/978-3-642-13858-4_10
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N400cbf4a70954dccb48458a0af551a43 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 N46909b08506a4bf1971724f65f15dab7 schema:isbn 978-3-642-13857-7
92 978-3-642-13858-4
93 schema:name Fast Software Encryption
94 rdf:type schema:Book
95 N47cf40260ae14a6f94007bbbf333d089 rdf:first sg:person.010716613427.52
96 rdf:rest Nade281bf4071437498a4092679f507ae
97 N5a3446021db144e2867c3f8dcbef7f24 rdf:first N8b28223bcf0a4cc0a2a69453d3ef335f
98 rdf:rest Nb4ff03ca6e7e404ca90f727be7e5af6b
99 N64ab4bde669c45a1bb1190c7292907c5 rdf:first sg:person.013060533545.97
100 rdf:rest N47cf40260ae14a6f94007bbbf333d089
101 N8b28223bcf0a4cc0a2a69453d3ef335f schema:familyName Hong
102 schema:givenName Seokhie
103 rdf:type schema:Person
104 Nade281bf4071437498a4092679f507ae rdf:first sg:person.010452652471.74
105 rdf:rest rdf:nil
106 Nb4ff03ca6e7e404ca90f727be7e5af6b rdf:first Nd8e96a6890ac4f81aeb7e70df22a3d96
107 rdf:rest rdf:nil
108 Nc623ed3c53894645a7768c9b75843384 schema:name Springer Nature
109 rdf:type schema:Organisation
110 Nd8e96a6890ac4f81aeb7e70df22a3d96 schema:familyName Iwata
111 schema:givenName Tetsu
112 rdf:type schema:Person
113 Ndeef0bd71f43440daaa4b2d19a5e9480 schema:name dimensions_id
114 schema:value pub.1042043203
115 rdf:type schema:PropertyValue
116 Ne5eb3e4589c04983bc49e4bce6dc5fdc schema:name doi
117 schema:value 10.1007/978-3-642-13858-4_10
118 rdf:type schema:PropertyValue
119 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
120 schema:name Information and Computing Sciences
121 rdf:type schema:DefinedTerm
122 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
123 schema:name Data Format
124 rdf:type schema:DefinedTerm
125 sg:person.010452652471.74 schema:affiliation grid-institutes:None
126 schema:familyName Nandi
127 schema:givenName Mridul
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010452652471.74
129 rdf:type schema:Person
130 sg:person.010716613427.52 schema:affiliation grid-institutes:grid.16008.3f
131 schema:familyName Mandal
132 schema:givenName Avradip
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010716613427.52
134 rdf:type schema:Person
135 sg:person.013060533545.97 schema:affiliation grid-institutes:grid.39953.35
136 schema:familyName Bhattacharyya
137 schema:givenName Rishiraj
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013060533545.97
139 rdf:type schema:Person
140 grid-institutes:None schema:alternateName NIST, USA and Computer Science Department, The George Washington University
141 schema:name NIST, USA and Computer Science Department, The George Washington University
142 rdf:type schema:Organization
143 grid-institutes:grid.16008.3f schema:alternateName Université du Luxembourg, Luxembourg
144 schema:name Université du Luxembourg, Luxembourg
145 rdf:type schema:Organization
146 grid-institutes:grid.39953.35 schema:alternateName Indian Statistical Institute, Kolkata, India
147 schema:name Indian Statistical Institute, Kolkata, India
148 rdf:type schema:Organization
 




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


...