Difference between revisions of "JH"

From The ECRYPT Hash Function Website
m (→‎Cryptanalysis)
m (Fixed some minor syntax in the table.)
 
(26 intermediate revisions by 5 users not shown)
Line 2: Line 2:
  
 
* Author(s): Hongjun Wu
 
* Author(s): Hongjun Wu
−
* Website: [http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/ http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/]
+
* Website: [http://www3.ntu.edu.sg/home/wuhj/research/jh/ http://www3.ntu.edu.sg/home/wuhj/research/jh/]
−
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/JH.zip JH.zip]
+
* NIST submission package:
 +
** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/JH_FinalRnd.zip JH_FinalRnd.zip]
 +
** Round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/JH_Round2.zip JH_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/JH.zip JH.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/JHUpdate.zip JHUpdate.zip])
  
  
 
<bibtex>
 
<bibtex>
−
@misc{sha3W08,
+
@misc{sha3W09,
 
   author    = {Hongjun Wu},
 
   author    = {Hongjun Wu},
 
   title    = {The Hash Function JH},
 
   title    = {The Hash Function JH},
−
   url        = {http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/jh.pdf},
+
   url        = {http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (round 3)},
−
   year      = {2008},
+
   year      = {2011},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 +
<bibtex>
 +
@misc{sha3W09a,
 +
  author    = {Hongjun Wu},
 +
  title    = {The Hash Function JH},
 +
  url        = {http://ehash.iaik.tugraz.at/uploads/1/1d/Jh20090915.pdf},
 +
  howpublished = {Submission to NIST (Round 1/2)},
 +
  year      = {2009},
 +
}
 +
</bibtex>
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
−
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
+
We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.
 +
 
 +
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
Recommended security parameter: '''42''' rounds
 +
 
 +
 
 +
=== Hash function ===
 +
 
 +
Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.
 +
 
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
|  Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference
 +
|-
 +
|  style="background:greenyellow" | preimage || 512 ||  || 2<sup>507</sup> || 2<sup>507</sup> || [http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf Bhattacharyya et al.]
 +
|-                                   
 +
|  style="background:greenyellow" | preimage<sup>(1)</sup> || 512 ||  || 2<sup>510.3</sup> (+ 2<sup>524</sup> MA + 2<sup>524</sup> CMP) || 2<sup>510.3</sup> (Wu: 2<sup>510.6</sup>) || [http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf Mendel,Thomsen], [http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf Wu]
 +
|-                                     
 +
|}                   
 +
 
 +
<sup>(1)</sup> Wu has analyzed the exact memory requirements, additional memory accesses (MA) and comparisons (CMP) of the attack by Mendel and Thomsen.
 +
 
 +
 
 +
=== Building blocks ===
 +
 
 +
Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.
 +
 
 +
Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).
 +
 
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"                   
 
|- style="background:#efefef;"                   
 
|- style="background:#efefef;"                   
 
|  Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
|  Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
|-                                     
 
|-                                     
−
|  | pseudo-collision || compression || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
+
|  semi-free-start collision || compression function || 256 || 26 rounds  || 2<sup>112</sup> || 2<sup>57.6</sup> || [http://dx.doi.org/10.1007/978-3-642-25385-0_14 Naya-Plasencia,Toz,Varici]
 +
|-                                   
 +
|  semi-free-start collision || compression function || 256 || 32 rounds  || 2<sup>304</sup> || 2<sup>57.6</sup> || [http://dx.doi.org/10.1007/978-3-642-25385-0_14 Naya-Plasencia,Toz,Varici]
 +
|-                                 
 +
|  semi-free-start collision || compression function || 256 || 36 rounds  || 2<sup>352</sup> || 2<sup>57.6</sup> || [http://dx.doi.org/10.1007/978-3-642-25385-0_14 Naya-Plasencia,Toz,Varici]
 +
|-                                 
 +
|  semi-free-start collision || compression function || 256 || 37 rounds  || 2<sup>352</sup> || 2<sup>57.6</sup> || [http://dx.doi.org/10.1007/978-3-642-25385-0_14 Naya-Plasencia,Toz,Varici]
 +
|-                               
 +
|  distinguisher || internal permutation || 256 || 42 rounds  || 2<sup>304</sup> || 2<sup>57.6</sup> || [http://dx.doi.org/10.1007/978-3-642-25385-0_14 Naya-Plasencia,Toz,Varici]
 +
|-                                 
 +
|  distinguisher || internal permutation || 256 || 42 rounds  || 2<sup>352</sup> || 2<sup>57.6</sup> || [http://dx.doi.org/10.1007/978-3-642-25385-0_14 Naya-Plasencia,Toz,Varici]
 +
|-                                   
 +
|  semi-free-start collision || compression function || 256 || 16 rounds  || 2<sup>96.12</sup> || 2<sup>96.12</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 +
|-
 +
|  semi-free-start near collision || compression function || 256 || 22 rounds  || 2<sup>95.63</sup> || 2<sup>95.63</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 +
|-
 +
|  semi-free-start near collision || compression function || all || 10 rounds  || 2<sup>23.24</sup> || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan]
 +
|-                                   
 +
|  semi-free-start collision || hash || 256 || 16 rounds  || 2<sup>178.24</sup> || 2<sup>101.12</sup> || [http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf Rijmen,Toz,Varıcı]
 +
|-                                   
 +
|  semi-free-start near collision || compression function || 256 || 22 rounds  || 2<sup>156.77</sup> || 2<sup>143.70</sup> || [http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf Rijmen,Toz,Varıcı]
 +
|-
 +
|  semi-free-start near collision || compression function || 256 || 22 rounds  || 2<sup>156.56</sup> || 2<sup>143.70</sup> || [http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf Rijmen,Toz,Varıcı]
 +
|-
 +
|  | pseudo-collision || compression function || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
 
|-                     
 
|-                     
 
|  | pseudo-2nd preimage || compression || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
 
|  | pseudo-2nd preimage || compression || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
 
|-                     
 
|-                     
−
|  style="background:greenyellow" | preimage || hash || 512 ||  || 2<sup>510.3</sup> || 2<sup>510.3</sup> || [http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf Mendel,Thomsen]
 
−
|-                                     
 
 
|}                     
 
|}                     
  
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
  
 +
<bibtex>
 +
@inproceedings{DBLP:dblp_conf/asiacrypt/Naya-PlasenciaTV11,
 +
  author              = {María Naya-Plasencia and
 +
                          Deniz Toz and
 +
                          Kerem Varici and
 +
                          Kerem Varici},
 +
  title              = {Rebound Attack on JH42.},
 +
  booktitle          = {ASIACRYPT},
 +
  year                = {2011},
 +
  pages              = {252-269},
 +
  url                = {http://dx.doi.org/10.1007/978-3-642-25385-0_14},
 +
  crossref            = {2011},
 +
  abstract = {The hash function JH [20] is one of the five finalists of the NIST SHA-3 hash competition. It has been recently tweaked for the final by increasing its number of rounds from 35.5 to 42. The previously best known results on JH were semi-free-start near-collisions up to 22 rounds using multi-inbound rebound attacks. In this paper we provide a new differential path on 32 rounds. Using this path, we are able to build various semi-free-start internal-state near-collisions and the maximum number of rounds that we achieved is up to 37 rounds on 986 bits. Moreover, we build distinguishers in the full 42-round internal permutation. These are, to our knowledge, the first results faster than generic attack on the full internal permutation of JH42, the finalist version. These distinguishers also apply to the compression function.}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2010:607,
 +
    author = {María Naya-Plasencia},
 +
    title = {Scrutinizing rebound attacks: new algorithms for improving the complexities},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/607},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/607.pdf},
 +
    abstract = {Rebound attacks are a state-of-the-art analysis method for hash functions. These cryptanalysis methods are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this paper we study rebound attacks in detail and find for a great number of cases, that complexities of existing attacks can be improved. This is done by determining problems that adapt optimally to the cryptanalytic situation, and by using better algorithms to follow the differential path. These improvements are essentially based on merging big lists in a more efficient way, as well as on new ideas on how to reduce the complexities. As a result, we introduce general purpose new algorithms for enabling further rebound analysis to be as performant as possible. We illustrate our new algorithms for real hash functions and demonstrate how to reduce the complexities of the best known analysis on five hash functions: JH, Grøstl, ECHO, Luffa and Lane (the first four are round two SHA-3 candidates).},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{blakeTU10,
 +
  author = {Meltem Sönmez Turan, Erdener Uyan},
 +
  title = {Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH},
 +
  howpublished = {Second SHA-3 Candidate Conference},
 +
  year = {2010},
 +
  url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf},
 +
  abstract = {A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. We also observed practical collisions and near-collisions for reduced versions of F-256 function used in Fugue.}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{BMN10,
 +
  author    = {Rishiraj Bhattacharyya and Avradip Mandal and Mridul Nandi},
 +
  title    = {Security Analysis of the Mode of JH Hash Function},
 +
  url = {http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf},
 +
  booktitle = {FSE},
 +
  year      = {2010},
 +
  pages    = {168-191},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6147},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{RTV10,
 +
  author    = {Vincent Rijmen and Denis Toz and Kerem Varıcı},
 +
  title    = {Rebound Attack on Reduced-Round Versions of JH},
 +
  url = {http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf},
 +
  booktitle  = {FSE},
 +
  year      = {2010},
 +
  pages    = {286-303},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6147},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 39: Line 166:
 
   title    = {Pseudo-collision and pseudo-second preimage on JH},
 
   title    = {Pseudo-collision and pseudo-second preimage on JH},
 
   url = {http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt},  
 
   url = {http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt},  
−
   howpublished = {NIST mailing list (local link)},
+
   howpublished = {NIST mailing list},
 
   year = {2008},
 
   year = {2008},
−
 
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 56: Line 182:
 
properties in the design principles of JH-512 which do not exist in other hash functions, e.g., the
 
properties in the design principles of JH-512 which do not exist in other hash functions, e.g., the
 
SHA-2 family.},
 
SHA-2 family.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{MT08,
 +
  author    = {Hongjun Wu},
 +
  title    = {The Complexity of Mendel and Thomsen's Preimage Attack on JH-512},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf},
 +
  howpublished = {Available online},
 +
  year = {2009},
 +
  abstract  = {Mendel and Thomsen gave a preimage attack on JH-512 by finding a preimage through the collision search over the space of $2^{1024} elements. However, they did not estimate the cost of the collision search which is the most expensive part in their attack. Our analysis shows that their attack requires at least $2^{510.3}$ compression function computations, $2^{510.6}$ memory ($2^{516.6}$ bytes), $2^{524}$ memory accesses and $2^{524}$ comparisons. Such complexity is far more expensive than brute force
 +
attack which requires $2^{512}$ compression function computations and almost no memory.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Latest revision as of 14:35, 14 February 2013

1 The algorithm


Hongjun Wu - The Hash Function JH

,2011
http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf
Bibtex
Author : Hongjun Wu
Title : The Hash Function JH
In : -
Address :
Date : 2011

Hongjun Wu - The Hash Function JH

,2009
http://ehash.iaik.tugraz.at/uploads/1/1d/Jh20090915.pdf
Bibtex
Author : Hongjun Wu
Title : The Hash Function JH
In : -
Address :
Date : 2009

2 Cryptanalysis

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given here.

Recommended security parameter: 42 rounds


2.1 Hash function

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

Type of Analysis Hash Size (n) Parameters Compression Function Calls Memory Requirements Reference
preimage 512 2507 2507 Bhattacharyya et al.
preimage(1) 512 2510.3 (+ 2524 MA + 2524 CMP) 2510.3 (Wu: 2510.6) Mendel,Thomsen, Wu

(1) Wu has analyzed the exact memory requirements, additional memory accesses (MA) and comparisons (CMP) of the attack by Mendel and Thomsen.


2.2 Building blocks

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
semi-free-start collision compression function 256 26 rounds 2112 257.6 Naya-Plasencia,Toz,Varici
semi-free-start collision compression function 256 32 rounds 2304 257.6 Naya-Plasencia,Toz,Varici
semi-free-start collision compression function 256 36 rounds 2352 257.6 Naya-Plasencia,Toz,Varici
semi-free-start collision compression function 256 37 rounds 2352 257.6 Naya-Plasencia,Toz,Varici
distinguisher internal permutation 256 42 rounds 2304 257.6 Naya-Plasencia,Toz,Varici
distinguisher internal permutation 256 42 rounds 2352 257.6 Naya-Plasencia,Toz,Varici
semi-free-start collision compression function 256 16 rounds 296.12 296.12 Naya-Plasencia
semi-free-start near collision compression function 256 22 rounds 295.63 295.63 Naya-Plasencia
semi-free-start near collision compression function all 10 rounds 223.24 - Turan,Uyan
semi-free-start collision hash 256 16 rounds 2178.24 2101.12 Rijmen,Toz,Varıcı
semi-free-start near collision compression function 256 22 rounds 2156.77 2143.70 Rijmen,Toz,Varıcı
semi-free-start near collision compression function 256 22 rounds 2156.56 2143.70 Rijmen,Toz,Varıcı
pseudo-collision compression function all - - Bagheri
pseudo-2nd preimage compression all - - Bagheri


María Naya-Plasencia, Deniz Toz, Kerem Varici, Kerem Varici - Rebound Attack on JH42.

ASIACRYPT pp. 252-269,2011
http://dx.doi.org/10.1007/978-3-642-25385-0_14
Bibtex
Author : María Naya-Plasencia, Deniz Toz, Kerem Varici, Kerem Varici
Title : Rebound Attack on JH42.
In : ASIACRYPT -
Address :
Date : 2011

María Naya-Plasencia - Scrutinizing rebound attacks: new algorithms for improving the complexities

,2010
http://eprint.iacr.org/2010/607.pdf
Bibtex
Author : María Naya-Plasencia
Title : Scrutinizing rebound attacks: new algorithms for improving the complexities
In : -
Address :
Date : 2010

Meltem Sönmez Turan, Erdener Uyan - Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH

,2010
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf
Bibtex
Author : Meltem Sönmez Turan, Erdener Uyan
Title : Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
In : -
Address :
Date : 2010

Rishiraj Bhattacharyya, Avradip Mandal, Mridul Nandi - Security Analysis of the Mode of JH Hash Function

FSE 6147:168-191,2010
http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf
Bibtex
Author : Rishiraj Bhattacharyya, Avradip Mandal, Mridul Nandi
Title : Security Analysis of the Mode of JH Hash Function
In : FSE -
Address :
Date : 2010

Vincent Rijmen, Denis Toz, Kerem Varıcı - Rebound Attack on Reduced-Round Versions of JH

FSE 6147:286-303,2010
http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf
Bibtex
Author : Vincent Rijmen, Denis Toz, Kerem Varıcı
Title : Rebound Attack on Reduced-Round Versions of JH
In : FSE -
Address :
Date : 2010

Nasour Bagheri - Pseudo-collision and pseudo-second preimage on JH

,2008
http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt
Bibtex
Author : Nasour Bagheri
Title : Pseudo-collision and pseudo-second preimage on JH
In : -
Address :
Date : 2008

Florian Mendel, Søren S. Thomsen - An Observation on JH-512

,2008
http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf
Bibtex
Author : Florian Mendel, Søren S. Thomsen
Title : An Observation on JH-512
In : -
Address :
Date : 2008

Hongjun Wu - The Complexity of Mendel and Thomsen's Preimage Attack on JH-512

,2009
http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf
Bibtex
Author : Hongjun Wu
Title : The Complexity of Mendel and Thomsen's Preimage Attack on JH-512
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=JH&oldid=3769"