Difference between revisions of "Groestl"

From The ECRYPT Hash Function Website
(→‎Building blocks: added Sasaki et al.)
m
 
(11 intermediate revisions by 4 users not shown)
Line 4: Line 4:
 
* Website: [http://www.groestl.info http://www.groestl.info]
 
* Website: [http://www.groestl.info http://www.groestl.info]
 
* NIST submission package:  
 
* NIST submission package:  
−
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Grostl_Round2.zip Grostl_Round2.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Grostl.zip Grostl.zip])
+
** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Groestl_FinalRnd.zip Groestl_FinalRnd.zip]
 +
** Round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Grostl_Round2.zip Grostl_Round2.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Grostl.zip Grostl.zip])
  
  
Line 12: Line 13:
 
   title    = {Grøstl -- a SHA-3 candidate},
 
   title    = {Grøstl -- a SHA-3 candidate},
 
   url        = {http://www.groestl.info/Groestl.pdf},
 
   url        = {http://www.groestl.info/Groestl.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (Round 3)},
−
   year      = {2008},
+
   year      = {2011},
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 22: Line 23:
 
   title    = {Grøstl Addendum},
 
   title    = {Grøstl Addendum},
 
   url        = {http://groestl.info/Groestl-addendum.pdf},
 
   url        = {http://groestl.info/Groestl-addendum.pdf},
−
   howpublished = {Available online},
+
   howpublished = {Submission to NIST (Round 2)},
 
   year      = {2009},
 
   year      = {2009},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{sha3groestl,
 +
  author    = {Praveen Gauravaram and Lars R. Knudsen and Krystian Matusiewicz and Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
 +
  title    = {Grøstl -- a SHA-3 candidate},
 +
  url        = {http://groestl.info/Groestl-0.pdf},
 +
  howpublished = {Submission to NIST (Round 1/2)},
 +
  year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 34: Line 45:
  
 
Recommended security parameter: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
 
Recommended security parameter: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
 +
  
 
=== Hash function ===
 
=== Hash function ===
Line 43: Line 55:
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
|-
 
|-
−
| collision || 224,256 || 5 rounds || 2<sup>48</sup> || 2<sup>32</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
+
| collision || 224,256 || 3 rounds || 2<sup>64</sup> || - || [http://groestl.info/groestl-analysis.pdf Schläffer]
 
|-
 
|-
−
| collision || 256 || 6 rounds || 2<sup>112</sup> || 2<sup>32</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
+
| collision || 512 || 3 rounds || 2<sup>192</sup> || - || [http://groestl.info/groestl-analysis.pdf Schläffer]
 
|-
 
|-
−
| collision || 224,256 || 4 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
+
|}
−
|-                   
 
−
| collision || 224,256 || 3 rounds || 2<sup>64</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 
−
|-                   
 
−
| collision || 384,512 || 5 rounds || 2<sup>176</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 
−
|-                   
 
−
| collision || 384,512 || 4 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 
−
|-                   
 
−
|}                  
 
  
  
Line 68: Line 72:
 
| 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  
 
|-           
 
|-           
−
| distinguisher || compression function || 256 || 10 rounds || 2<sup>175</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
+
| distinguisher || permutation || 256 || 9 rounds || 2<sup>368</sup> || 2<sup>64</sup> || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
 +
|-       
 +
| distinguisher || permutation || 512 || 8 rounds || 2<sup>280</sup> || 2<sup>64</sup> || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
 +
|-
 +
| distinguisher || permutation || 512 || 9 rounds || 2<sup>328</sup> || 2<sup>64</sup> || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
 +
|-
 +
| distinguisher || permutation || 512 || 10 rounds || 2<sup>392</sup> || 2<sup>64</sup> || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
 +
|-
 +
| preimage|| output transformation || 256 || 5 rounds || 2<sup>206</sup> || 2<sup>48</sup> || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
 +
|-
 +
| pseudo preimage|| hash function || 256 || 5 rounds || 2<sup>244.85</sup> || 2<sup>230.13</sup> || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
 +
|-
 +
| preimage|| output transformation || 512 || 8 rounds || 2<sup>495</sup> || 2<sup>16</sup> || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
 +
|-
 +
| pseudo preimage|| hash function || 512 || 8 rounds || 2<sup>507.32</sup> || 2<sup>507</sup> || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
 +
|-
 +
| preimage || output transformation || 256 || 6 rounds || 2<sup>251</sup> ||  || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
 +
|-
 +
| preimage || compression function || 256 || 6 rounds || 2<sup>128</sup> ||  || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || compression function || 256 || 6 rounds / 2<sup>64</sup> targets || 2<sup>64</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 
|-
 
|-
−
| distinguisher || compression function || 512 || 11 rounds || 2<sup>630</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
+
| chosen multitarget preimage || compression function || 256 || 6 rounds / 2<sup>8</sup> targets || 2<sup>120</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 
|-
 
|-
−
| semi-free-start collision || compression function || 224,256 || 7 rounds || 2<sup>80</sup> || 2<sup>32</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
+
| chosen multitarget preimage || compression function || 256 || 7 rounds / 2<sup>80</sup> targets || 2<sup>64</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 
|-
 
|-
−
| semi-free-start collision || compression function || 224,256 || 8 rounds || 2<sup>192</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
+
| chosen multitarget preimage || compression function || 256 || 7 rounds / 2<sup>24</sup> targets || 2<sup>120</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || compression function || 256 || 8 rounds / 2<sup>192</sup> targets || 2<sup>64</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || compression function || 256 || 8 rounds / 2<sup>136</sup> targets || 2<sup>120</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || compression function || 256 || 9 rounds / 2<sup>192</sup> targets || 2<sup>120</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || hash function || 256 || 5 rounds / 2<sup>64</sup> targets || 2<sup>80</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || hash function || 256 || 6 rounds / 2<sup>16</sup> targets || 2<sup>136</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || hash function || 256 || 6 rounds / 2<sup>64</sup> targets || 2<sup>64</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || hash function || 256 || 6 rounds / 2<sup>8</sup> targets || 2<sup>120</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || hash function || 256 || 7 rounds / 2<sup>80</sup> targets || 2<sup>64</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| chosen multitarget preimage || hash function || 256 || 7 rounds / 2<sup>24</sup> targets || 2<sup>120</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| preimage || hash function || 256 || 5 rounds || 2<sup>144</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| preimage || hash function || 256 || 6 rounds || 2<sup>144</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|-
 +
| pseudo preimage || hash function || 256 || 6 rounds || 2<sup>128</sup> || 2<sup>64</sup> || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
 +
|- 
 +
| distinguisher  || permutation || 256 || 10 rounds || 2<sup>509</sup> || || [http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf Boura,Canteaut,DeCannière]
 +
|-         
 +
| semi-free-start collision || compression function || 256 || 6 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://groestl.info/groestl-analysis.pdf Schläffer]
 +
|-
 +
| semi-free-start collision || compression function || 384,512 || 6 rounds || 2<sup>180</sup> || 2<sup>64</sup> || [http://groestl.info/groestl-analysis.pdf Schläffer]
 +
|-
 +
| collision || hash function || 224,256 || 5 rounds (Round 1/2) || 2<sup>48</sup> || 2<sup>32</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 +
|-
 +
| collision || hash function || 256 || 6 rounds (Round 1/2) || 2<sup>112</sup> || 2<sup>32</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 +
|-
 +
| collision || hash function || 224,256 || 4 rounds (Round 1/2) || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| collision || hash function || 224,256 || 3 rounds (Round 1/2) || 2<sup>64</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| collision || hash function || 384,512 || 5 rounds (Round 1/2) || 2<sup>176</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| collision || hash function || 384,512 || 4 rounds (Round 1/2) || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| distinguisher || compression function || 256 || 10 rounds (Round 1/2) || 2<sup>175</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 +
|-
 +
| distinguisher || compression function || 512 || 11 rounds (Round 1/2) || 2<sup>630</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 +
|-
 +
| distinguisher || permutation || 256 || 8 rounds || 2<sup>48</sup> || 2<sup>8</sup> || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
 +
|-
 +
| semi-free-start collision || compression function || 512 || 7 rounds || 2<sup>152</sup> || 2<sup>56</sup> || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
 +
|-
 +
| semi-free-start collision || compression function || 224,256 || 7 rounds (Round 1/2) || 2<sup>80</sup> || 2<sup>32</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 +
|-
 +
| semi-free-start collision || compression function || 224,256 || 8 rounds (Round 1/2) || 2<sup>192</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 
|-
 
|-
 
| distinguisher || permutation || 224,256 || 7 rounds || 2<sup>19</sup> || - || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 
| distinguisher || permutation || 224,256 || 7 rounds || 2<sup>19</sup> || - || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
Line 80: Line 158:
 
| distinguisher || permutation || 224,256 || 8 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 
| distinguisher || permutation || 224,256 || 8 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
 
|-
 
|-
−
| distinguisher || compression function || 256 || 10 rounds || 2<sup>192</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
+
| distinguisher || compression function || 256 || 10 rounds (Round 1/2) || 2<sup>192</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
|-                     
 
|-                     
−
| distinguisher || compression function || 256 || 9 rounds || 2<sup>80</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
+
| distinguisher || compression function || 256 || 9 rounds (Round 1/2) || 2<sup>80</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
|-                     
 
|-                     
−
| distinguisher || compression function || 512 || 11 rounds || 2<sup>640</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
+
| distinguisher || compression function || 512 || 11 rounds (Round 1/2) || 2<sup>640</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
|-   
 
|-   
−
| semi-free-start collision || compression function || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
+
| semi-free-start collision || compression function || 256 || 7 rounds (Round 1/2) || 2<sup>120</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
|-                     
 
|-                     
−
| distinguisher || compression function || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
+
| distinguisher || compression function || 256 || 8 rounds (Round 1/2) || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
|-                     
 
|-                     
 
| distinguisher || permutation || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
| distinguisher || permutation || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression function || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
+
| semi-free-start collision || compression function || 256 || 7 rounds (Round 1/2) || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression function|| 384,512 || 7 rounds || 2<sup>152</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
+
| semi-free-start collision || compression function|| 384,512 || 7 rounds (Round 1/2) || 2<sup>152</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression function || 224,256 || 6 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
+
| semi-free-start collision || compression function || 224,256 || 6 rounds (Round 1/2) || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 
|-                     
 
|-                     
 
| distinguisher || output transformation || 224,256 || 7 rounds || 2<sup>56</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 
| distinguisher || output transformation || 224,256 || 7 rounds || 2<sup>56</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
Line 102: Line 180:
 
| distinguisher || permutation || 224,256 || 7 rounds || 2<sup>55</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 
| distinguisher || permutation || 224,256 || 7 rounds || 2<sup>55</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression function || 256 || 6 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
+
| semi-free-start collision || compression function || 256 || 6 rounds (Round 1/2) || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression function || 224,256 || 5 rounds || 2<sup>64</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
+
| semi-free-start collision || compression function || 224,256 || 5 rounds (Round 1/2) || 2<sup>64</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
 
| observation || hash  || all  ||  ||  ||  || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
 
| observation || hash  || all  ||  ||  ||  || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
Line 117: Line 195:
  
  
−
== Cryptanalysis ==
+
<bibtex>
 +
@inproceedings{DBLP:dblp_conf/fse/JeanNP12,
 +
  author              = {Jérémy Jean and
 +
                          María Naya-Plasencia and
 +
                          Thomas Peyrin and
 +
                          Thomas Peyrin},
 +
  title              = {Improved Rebound Attack on the Finalist Grøstl.},
 +
  booktitle          = {FSE},
 +
  year                = {2012},
 +
  pages              = {110-126},
 +
  url                = {http://dx.doi.org/10.1007/978-3-642-34047-5_7},
 +
  crossref            = {2012},
 +
  abstract = {Grøstl is one of the five finalist hash functions of the SHA-3 competition. For entering this final phase, the designers have tweaked the submitted versions. This tweak renders inapplicable the best known distinguishers on the compression function presented by Peyrin [18] that exploited the internal permutation properties. Since the beginning of the final round, very few analysis have been published on Grøstl. Currently, the best known rebound-based results on the permutation and the compression function for the 256-bit version work up to 8 rounds, and up to 7 rounds for the 512-bit version. In this paper, we present new rebound distinguishers that work on a higher number of rounds for the permutations of both 256 and 512-bit versions of this finalist, that is 9 and 10 respectively. Our distinguishers make use of an algorithm that we propose for solving three fully active states in the middle of the differential characteristic, while the Super-Sbox technique only handles two.}
 +
}
 +
</bibtex>
  
−
We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.
+
<bibtex>
 +
@misc{cryptoeprint:2012:206,
 +
    author = {Shuang Wu and Dengguo Feng and Wenling Wu and Jian Guo and Le Dong and Jian Zou},
 +
    title = {(Pseudo) Preimage Attack on Round-Reduced Gr{\o}stl Hash Function and Others (Extended Version)},
 +
    howpublished = {Cryptology ePrint Archive, Report 2012/206},
 +
    year = {2012},
 +
    url = {http://eprint.iacr.org/2012/206.pdf},
 +
    abstract = {The Gr{\o}stl hash function is one of the 5 final round candidates of the SHA-3 competition hosted by NIST. In this paper, we study the preimage resistance of the Gr{\o}stl hash function. We propose pseudo preimage attacks on Gr{\o}stl hash function for both 256-bit and 512-bit versions, i.e. we need to choose the initial value in order to invert the hash function. Pseudo preimage attack on 5(out of 10)-round Gr{\o}stl-256 has a complexity of $(2^{244.85},2^{230.13})$ (in time and memory) and pseudo preimage attack on 8(out of 14)-round Gr{\o}stl-512 has a complexity of $(2^{507.32},2^{507.00})$. To the best of our knowledge, our attacks are the first (pseudo) preimage attacks on round-reduced Gr{\o}stl hash function, including its compression function and output transformation. These results are obtained by a variant of meet-in-the-middle preimage attack framework by Aoki and Sasaki. We also improve the time complexities of the preimage attacks against 5-round Whirlpool and 7-round AES hashes by Sasaki in FSE~2011.}
 +
}
 +
</bibtex>
  
−
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
+
<bibtex>
 +
@misc{emami-multitarget,
 +
  author = {Sareh Emami and Praveen Gauravaram and Josef Pieprzyk and Ron Steinfeld},
 +
  title = {(Chosen-multi-target) preimage attacks on reduced Grøstl-0},
 +
  url = {http://web.science.mq.edu.au/~rons/preimageattack-final.pdf},
 +
  abstract = {The cryptographic hash function Grøstl is a finalist in the NIST’s SHA-3 hash function
 +
competition and it is a tweaked variant of its predecessor called Grøstl-0, a second round SHA-3 candidate.
 +
In this article, we consider 256-bit Grøstl-0 and its 512-bit compression function. We show that
 +
internal differential trails built between the two almost similar looking permutations of the compression
 +
function can be coverted to chosen-multi-target-preimage attacks, a variant of multi-target preimage
 +
attacks. Consequently, we show chosen-multi-target-preimage attacks for up to 9 out of 10 rounds of
 +
the compression function and up to 7 rounds of the hash function. Finally, we use these attacks as a
 +
tool to find preimages and pseudo preimages for 6 rounds of the 256-bit Grøstl-0 hash function.}
 +
}
 +
</bibtex>
  
−
Recommended security parameter: '''8''' rounds (n=224,256); '''10''' rounds (n=384,512)
+
<bibtex>
 +
@misc{cryptoeprint:2012:141,
 +
    author = {Dmitry Khovratovich},
 +
    title = {Bicliques for permutations: collision and preimage attacks in stronger settings},
 +
    howpublished = {Cryptology ePrint Archive, Report 2012/141},
 +
    year = {2012},
 +
    url = {http://eprint.iacr.org/2012/141.pdf},
 +
    abstract = {We extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, we show how to mount attacks on the primitives with these parameters fixed, i.e. on permutations. We introduce the concept of sliced bicliques, which is a translation of regular bicliques to the framework with permutations.
  
−
=== Hash function ===
+
The new framework allows to convert preimage attacks into collision attacks and derive the first collision attacks on the reduced SHA-3 finalist Skein in the hash function setting up to 11 rounds. We also demonstrate new preimage attacks on the reduced Skein and the output transformation of the reduced Gr{\o}stl. Finally, the sophisticated technique of message compensation gets a simple explanation with bicliques.}
 +
}
 +
</bibtex>
  
−
Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.
+
<bibtex>
−
 
+
@inproceedings{fseBCD11,
−
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"                 
+
  author = {Christina Boura and Anne Canteaut and Christophe De Cannière},
−
|- style="background:#efefef;"                 
+
   title = {Higher-order differential properties of Keccak and Luffa},
−
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||   Reference
+
  url = {http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf},
−
|-                  
+
  booktitle  = {FSE},
−
| collision<sup>(1)</sup> || 256 || 5 rounds || 2<sup>112</sup> || 2<sup>85.3</sup> || [http://eprint.iacr.org/2010/588.pdf Schläffer]
+
  year      = {2011},
−
|-                   
+
  series    = {LNCS},
−
|}                  
+
  pages    = {252-269},
−
 
+
  publisher = {Springer},
−
<sup>(1)</sup> In this attack some problems in the [http://eprint.iacr.org/2010/321.pdf previous attacks] (pointed out by [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]) have been corrected.
+
  volume    = {6733},
−
 
+
   abstract = {In this paper, we identify higher-order differential and zero-sum properties in the full Keccak-f permutation, in the Luffa v1 hash function, and in components of the Luffa v2 algorithm. These structural properties rely on a new bound on the degree of iterated permutations with a nonlinear layer composed of parallel applications of smaller balanced Sboxes. These techniques yield zero-sum partitions of size $2^{1590}$ for the full Keccak-f permutation and several observations on the Luffa hash family. We first show that Luffa v1 applied to one-block messages is a function of 255 variables with degree at most 251. This observation leads to the construction of a higher-order differential distinguisher for the full Luffa v1 hash function, similar to the one presented by Watanabe et al. on a reduced version. We show that similar techniques can be used to find all-zero higher-order differentials in the Luffa v2 compression function, but the additional blank round destroys this property in the hash function.},
−
 
+
</bibtex>
−
=== 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;"                 
 
−
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 
−
|-
 
−
| distinguisher || permutation || 256 || 8 rounds || 2<sup>151</sup> || 2<sup>67</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 
−
|-  
 
−
| distinguisher || permutation || 256 || 8 rounds || 2<sup>48</sup> || 2<sup>8</sup> || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
 
−
|-
 
−
| semi-free-start collision || compression function || 512 || 7 rounds || 2<sup>152</sup> || 2<sup>56</sup> || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
 
−
|-
 
−
| distinguisher<sup>(1)</sup> (chosen salt) || compression function || 256 || 7 rounds || 2<sup>160</sup> || 2<sup>128</sup> || [http://eprint.iacr.org/2010/588.pdf Schläffer]
 
−
|-                  
 
−
| free-start collision<sup>(1)</sup> (chosen salt) || compression function || 256 || 6 rounds || 2<sup>160</sup> || 2<sup>128</sup> || [http://eprint.iacr.org/2010/588.pdf Schläffer]
 
−
|-
 
−
| semi-free-start collision || compression function || 256 || 4 rounds || 2<sup>52</sup> || 2<sup>16</sup> || [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]
 
−
|-  
 
−
| semi-free-start collision || compression function || 256 || 3 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
−
|-                  
 
−
| distinguisher || compression function || 256 || 4 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
−
|-      
 
−
| semi-free-start collision || compression function || 512 || 3 rounds || 2<sup>96</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
−
|-                 
 
−
| distinguisher || compression function || 512 || 6 rounds || 2<sup>96</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
−
|-               
 
−
| distinguisher || permutation || all || 8 rounds || 2<sup>768</sup> || 2<sup>512</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
−
|-                   
 
−
| distinguisher || permutation || all || 7 rounds || 2<sup>384</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=110408 Mendel,Peyrin,Rechberger,Schläffer]
 
−
|-                   
 
−
| distinguisher || permutation || all || 7 rounds || 2<sup>896</sup> || - || [http://crypto.rd.francetelecom.com/echo/doc/echo_description_1-5.pdf submission document]
 
−
|-                   
 
−
|} 
 
−
 
 
−
<sup>(1)</sup> In this attack some problems in the [http://eprint.iacr.org/2010/321.pdf previous attacks] (pointed out by [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]) have been corrected.
 
  
 +
<bibtex>
 +
@misc{groestlSchlaeffer11,
 +
    author = {Martin Schläffer},
 +
    title = {Updated Differential Analysis of Grøstl},
 +
    howpublished = {Grøstl website},
 +
    month = {January},
 +
    year = {2011},
 +
    url = {http://groestl.info/groestl-analysis.pdf},
 +
    abstract = {Grøstl is a SHA-3 finalist with clear proofs against a large class of differential attacks, similar to those of MD6. Furthermore, in this note we provide an update also regarding more advanced types of differential attacks that have been developed in recent years. We apply the rebound attacks on the initial submission to the tweaked version of Grøstl. We have analyzed the round-reduced hash function and compression function of Grøstl-256 (10 rounds) and Grøstl-512 (14 rounds). For both versions, we get collisions for 3 rounds of the hash function and collisions for 6 rounds of the compression function. We hope that our own efforts on improving the cryptanalysis will continue to motivate and accelerate external cryptanalysis.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 187: Line 283:
 
     howpublished = {Cryptology ePrint Archive, Report 2010/607},
 
     howpublished = {Cryptology ePrint Archive, Report 2010/607},
 
     year = {2010},
 
     year = {2010},
−
    note = {\url{http://eprint.iacr.org/}},
 
 
     url = {http://eprint.iacr.org/2010/607.pdf},
 
     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).},
 
     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).},
Line 194: Line 289:
  
 
<bibtex>
 
<bibtex>
−
@misc{groestlechoSLWSO10,
+
@inproceedings{groestlechoSLWSO10,
 
   author = {Yu Sasaki and Yang Li and Lei Wang and Kazuo Sakiyama and Kazuo Ohta},
 
   author = {Yu Sasaki and Yang Li and Lei Wang and Kazuo Sakiyama and Kazuo Ohta},
−
   title = {New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl
+
   title = {New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl},
−
},
+
  booktitle = {ASIACRYPT},
−
   howpublished = {Second SHA-3 Candidate Conference},
+
  year      = {2010},
−
   year = {2010},
+
   pages    = {38-55},
 +
   publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6477},
 
   url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf},
 
   url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf},
 
   abstract = {In this paper, we present non-full-active Super-Sbox analysis which can detect non-ideal
 
   abstract = {In this paper, we present non-full-active Super-Sbox analysis which can detect non-ideal
Line 216: Line 314:
  
 
<bibtex>
 
<bibtex>
−
@misc{ITP10,
+
@inproceedings{ITP10,
 
     author = {Kota Ideguchi and Elmar Tischhauser and Bart Preneel},
 
     author = {Kota Ideguchi and Elmar Tischhauser and Bart Preneel},
 
     title = {Improved Collision Attacks on the Reduced-Round Grøstl Hash Function},
 
     title = {Improved Collision Attacks on the Reduced-Round Grøstl Hash Function},
 
     howpublished = {Cryptology ePrint Archive, Report 2010/375},
 
     howpublished = {Cryptology ePrint Archive, Report 2010/375},
−
    year = {2010},
+
  booktitle = {ISC},
−
     note = {\url{http://eprint.iacr.org/}},
+
  year     = {2010},
 +
  pages     = {1-16},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6531},
 
     url = {http://eprint.iacr.org/2010/375.pdf},
 
     url = {http://eprint.iacr.org/2010/375.pdf},
 
     abstract = {We analyze the Gr{\o}stl hash function, which is a 2nd-round candidate of the SHA-3 competition. Using the start-from-the-middle variant of the rebound technique, we show collision attacks on the Gr{\o}stl-256 hash function reduced to 5 and 6 out of 10 rounds with time complexities $2^{48}$ and $2^{112}$, respectively. Furthermore, we demonstrate semi-free-start collision attacks on the Gr{\o}stl-224 and -256 hash functions reduced to 7 rounds and the Gr{\o}stl-224 and -256 compression functions reduced to 8 rounds. Our attacks are based on differential paths between the two permutations $P$ and $Q$ of Gr{\o}stl, a strategy introduced by Peyrin to construct distinguishers for the compression function. In this paper, we extend this approach to construct collision and semi-free-start collision attacks for both the hash and the compression function. Finally, we present improved distinguishers for reduced-round versions of the Gr{\o}stl-224 and -256 permutations.},
 
     abstract = {We analyze the Gr{\o}stl hash function, which is a 2nd-round candidate of the SHA-3 competition. Using the start-from-the-middle variant of the rebound technique, we show collision attacks on the Gr{\o}stl-256 hash function reduced to 5 and 6 out of 10 rounds with time complexities $2^{48}$ and $2^{112}$, respectively. Furthermore, we demonstrate semi-free-start collision attacks on the Gr{\o}stl-224 and -256 hash functions reduced to 7 rounds and the Gr{\o}stl-224 and -256 compression functions reduced to 8 rounds. Our attacks are based on differential paths between the two permutations $P$ and $Q$ of Gr{\o}stl, a strategy introduced by Peyrin to construct distinguishers for the compression function. In this paper, we extend this approach to construct collision and semi-free-start collision attacks for both the hash and the compression function. Finally, we present improved distinguishers for reduced-round versions of the Gr{\o}stl-224 and -256 permutations.},
Line 228: Line 330:
  
 
<bibtex>           
 
<bibtex>           
−
@misc{Pey10,
+
@inproceedings{Pey10,
 
     author = {Thomas Peyrin},
 
     author = {Thomas Peyrin},
 
     title = {Improved Differential Attacks for ECHO and Grostl},
 
     title = {Improved Differential Attacks for ECHO and Grostl},
−
    howpublished = {Cryptology ePrint Archive, Report 2010/223},
+
  booktitle = {CRYPTO},
−
    year = {2010},
+
  year     = {2010},
−
     note = {\url{http://eprint.iacr.org/}},
+
  pages     = {370-392},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6223},
 
     url = {http://eprint.iacr.org/2010/223.pdf},
 
     url = {http://eprint.iacr.org/2010/223.pdf},
 
     abstract = {We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and Grostl. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of Grostl, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and Grostl. In particular, we are able to mount a distinguishing attack for the full Grostl-256 compression function.},
 
     abstract = {We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and Grostl. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of Grostl, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and Grostl. In particular, we are able to mount a distinguishing attack for the full Grostl-256 compression function.},
Line 243: Line 348:
 
   author    = {Henri Gilbert and Thomas Peyrin},
 
   author    = {Henri Gilbert and Thomas Peyrin},
 
   title    = {Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations},
 
   title    = {Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations},
−
  url = {http://eprint.iacr.org/2009/531.pdf},
 
 
   booktitle  = {FSE},
 
   booktitle  = {FSE},
 
   year      = {2010},
 
   year      = {2010},
 
   series    = {LNCS},
 
   series    = {LNCS},
 +
  volume    = {6147},
 
   publisher  = {Springer},
 
   publisher  = {Springer},
−
   note = {To appear}
+
   pages    = {365-383},
 +
  url = {http://eprint.iacr.org/2009/531.pdf},
 
   abstract = {In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.}
 
   abstract = {In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.}
 
</bibtex>
 
</bibtex>
Line 339: Line 445:
 
   title    = {Some notes on Grøstl},
 
   title    = {Some notes on Grøstl},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf},
−
   howpublished = {Available online},
+
   howpublished = {NIST hash function mailing list},
 +
  month    = {April},
 
   year      = {2009},
 
   year      = {2009},
 
   abstract  = {These are some quick notes on some properties and
 
   abstract  = {These are some quick notes on some properties and
Line 354: Line 461:
 
   title    = {An observation on Grøstl},
 
   title    = {An observation on Grøstl},
 
   url        = {http://www.larc.usp.br/~pbarreto/Grizzly.pdf},
 
   url        = {http://www.larc.usp.br/~pbarreto/Grizzly.pdf},
−
   howpublished = {Available online},
+
   howpublished = {NIST hash function mailing list},
 +
  month    = {November},
 
   year      = {2008},
 
   year      = {2008},
 
   abstract  = {An alternative view of the Groestl SHA-3 submission is
 
   abstract  = {An alternative view of the Groestl SHA-3 submission is

Latest revision as of 11:12, 1 August 2013

1 The algorithm


Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate

,2011
http://www.groestl.info/Groestl.pdf
Bibtex
Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl -- a SHA-3 candidate
In : -
Address :
Date : 2011

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl Addendum

,2009
http://groestl.info/Groestl-addendum.pdf
Bibtex
Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl Addendum
In : -
Address :
Date : 2009

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate

,2008
http://groestl.info/Groestl-0.pdf
Bibtex
Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl -- a SHA-3 candidate
In : -
Address :
Date : 2008

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: 10 rounds (n=224,256); 14 rounds (n=384,512)


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
collision 224,256 3 rounds 264 - Schläffer
collision 512 3 rounds 2192 - Schläffer


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
distinguisher permutation 256 9 rounds 2368 264 Jean,Naya-Plasencia,Peyrin
distinguisher permutation 512 8 rounds 2280 264 Jean,Naya-Plasencia,Peyrin
distinguisher permutation 512 9 rounds 2328 264 Jean,Naya-Plasencia,Peyrin
distinguisher permutation 512 10 rounds 2392 264 Jean,Naya-Plasencia,Peyrin
preimage output transformation 256 5 rounds 2206 248 Wu,Feng,Wu,Guo,Dong,Zou
pseudo preimage hash function 256 5 rounds 2244.85 2230.13 Wu,Feng,Wu,Guo,Dong,Zou
preimage output transformation 512 8 rounds 2495 216 Wu,Feng,Wu,Guo,Dong,Zou
pseudo preimage hash function 512 8 rounds 2507.32 2507 Wu,Feng,Wu,Guo,Dong,Zou
preimage output transformation 256 6 rounds 2251 Khovratovich
preimage compression function 256 6 rounds 2128 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 6 rounds / 264 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 6 rounds / 28 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 7 rounds / 280 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 7 rounds / 224 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 8 rounds / 2192 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 8 rounds / 2136 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 9 rounds / 2192 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 5 rounds / 264 targets 280 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 6 rounds / 216 targets 2136 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 6 rounds / 264 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 6 rounds / 28 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 7 rounds / 280 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 7 rounds / 224 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
preimage hash function 256 5 rounds 2144 264 Emami,Guaravaram,Pieprzyk,Steinfeld
preimage hash function 256 6 rounds 2144 264 Emami,Guaravaram,Pieprzyk,Steinfeld
pseudo preimage hash function 256 6 rounds 2128 264 Emami,Guaravaram,Pieprzyk,Steinfeld
distinguisher permutation 256 10 rounds 2509 Boura,Canteaut,DeCannière
semi-free-start collision compression function 256 6 rounds 2120 264 Schläffer
semi-free-start collision compression function 384,512 6 rounds 2180 264 Schläffer
collision hash function 224,256 5 rounds (Round 1/2) 248 232 Ideguchi,Tischhauser,Preneel
collision hash function 256 6 rounds (Round 1/2) 2112 232 Ideguchi,Tischhauser,Preneel
collision hash function 224,256 4 rounds (Round 1/2) 264 264 Mendel,Rechberger,Schläffer,Thomsen
collision hash function 224,256 3 rounds (Round 1/2) 264 - Mendel,Rechberger,Schläffer,Thomsen
collision hash function 384,512 5 rounds (Round 1/2) 2176 264 Mendel,Rechberger,Schläffer,Thomsen
collision hash function 384,512 4 rounds (Round 1/2) 264 264 Mendel,Rechberger,Schläffer,Thomsen
distinguisher compression function 256 10 rounds (Round 1/2) 2175 264 Naya-Plasencia
distinguisher compression function 512 11 rounds (Round 1/2) 2630 264 Naya-Plasencia
distinguisher permutation 256 8 rounds 248 28 Sasaki,Li,Wang,Sakiyama,Ohta
semi-free-start collision compression function 512 7 rounds 2152 256 Sasaki,Li,Wang,Sakiyama,Ohta
semi-free-start collision compression function 224,256 7 rounds (Round 1/2) 280 232 Ideguchi,Tischhauser,Preneel
semi-free-start collision compression function 224,256 8 rounds (Round 1/2) 2192 264 Ideguchi,Tischhauser,Preneel
distinguisher permutation 224,256 7 rounds 219 - Ideguchi,Tischhauser,Preneel
distinguisher permutation 224,256 8 rounds 264 264 Ideguchi,Tischhauser,Preneel
distinguisher compression function 256 10 rounds (Round 1/2) 2192 264 Peyrin
distinguisher compression function 256 9 rounds (Round 1/2) 280 264 Peyrin
distinguisher compression function 512 11 rounds (Round 1/2) 2640 264 Peyrin
semi-free-start collision compression function 256 7 rounds (Round 1/2) 2120 264 Gilbert,Peyrin
distinguisher compression function 256 8 rounds (Round 1/2) 2112 264 Gilbert,Peyrin
distinguisher permutation 256 8 rounds 2112 264 Gilbert,Peyrin
semi-free-start collision compression function 256 7 rounds (Round 1/2) 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 384,512 7 rounds (Round 1/2) 2152 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 224,256 6 rounds (Round 1/2) 264 264 Mendel,Peyrin,Rechberger,Schläffer
distinguisher output transformation 224,256 7 rounds 256 - Mendel,Peyrin,Rechberger,Schläffer
distinguisher permutation 224,256 7 rounds 255 - Mendel,Peyrin,Rechberger,Schläffer
semi-free-start collision compression function 256 6 rounds (Round 1/2) 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 224,256 5 rounds (Round 1/2) 264 - Mendel,Rechberger,Schläffer,Thomsen
observation hash all Kelsey
observation block cipher all Barreto
free-start collision compression function all any 22n/3 22n/3 submission document
pseudo-preimage compression function all any 2n - submission document


Jérémy Jean, María Naya-Plasencia, Thomas Peyrin, Thomas Peyrin - Improved Rebound Attack on the Finalist Grøstl.

FSE pp. 110-126,2012
http://dx.doi.org/10.1007/978-3-642-34047-5_7
Bibtex
Author : Jérémy Jean, María Naya-Plasencia, Thomas Peyrin, Thomas Peyrin
Title : Improved Rebound Attack on the Finalist Grøstl.
In : FSE -
Address :
Date : 2012

Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou - (Pseudo) Preimage Attack on Round-Reduced Gr{\o}stl Hash Function and Others (Extended Version)

,2012
http://eprint.iacr.org/2012/206.pdf
Bibtex
Author : Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou
Title : (Pseudo) Preimage Attack on Round-Reduced Gr{\o}stl Hash Function and Others (Extended Version)
In : -
Address :
Date : 2012

Sareh Emami, Praveen Gauravaram, Josef Pieprzyk, Ron Steinfeld - (Chosen-multi-target) preimage attacks on reduced Grøstl-0

http://web.science.mq.edu.au/~rons/preimageattack-final.pdf
Bibtex
Author : Sareh Emami, Praveen Gauravaram, Josef Pieprzyk, Ron Steinfeld
Title : (Chosen-multi-target) preimage attacks on reduced Grøstl-0
In : -
Address :
Date :

Dmitry Khovratovich - Bicliques for permutations: collision and preimage attacks in stronger settings

,2012
http://eprint.iacr.org/2012/141.pdf
Bibtex
Author : Dmitry Khovratovich
Title : Bicliques for permutations: collision and preimage attacks in stronger settings
In : -
Address :
Date : 2012

Christina Boura, Anne Canteaut, Christophe De Cannière - Higher-order differential properties of Keccak and Luffa

FSE 6733:252-269,2011
http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf
Bibtex
Author : Christina Boura, Anne Canteaut, Christophe De Cannière
Title : Higher-order differential properties of Keccak and Luffa
In : FSE -
Address :
Date : 2011

Martin Schläffer - Updated Differential Analysis of Grøstl

, January 2011
http://groestl.info/groestl-analysis.pdf
Bibtex
Author : Martin Schläffer
Title : Updated Differential Analysis of Grøstl
In : -
Address :
Date : January 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

Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta - New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl

ASIACRYPT 6477:38-55,2010
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf
Bibtex
Author : Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta
Title : New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl
In : ASIACRYPT -
Address :
Date : 2010

Kota Ideguchi, Elmar Tischhauser, Bart Preneel - Improved Collision Attacks on the Reduced-Round Grøstl Hash Function

ISC 6531:1-16,2010
http://eprint.iacr.org/2010/375.pdf
Bibtex
Author : Kota Ideguchi, Elmar Tischhauser, Bart Preneel
Title : Improved Collision Attacks on the Reduced-Round Grøstl Hash Function
In : ISC -
Address :
Date : 2010

Thomas Peyrin - Improved Differential Attacks for ECHO and Grostl

CRYPTO 6223:370-392,2010
http://eprint.iacr.org/2010/223.pdf
Bibtex
Author : Thomas Peyrin
Title : Improved Differential Attacks for ECHO and Grostl
In : CRYPTO -
Address :
Date : 2010

Henri Gilbert, Thomas Peyrin - Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations

FSE 6147:365-383,2010
http://eprint.iacr.org/2009/531.pdf
Bibtex
Author : Henri Gilbert, Thomas Peyrin
Title : Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations
In : FSE -
Address :
Date : 2010

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Rebound Attacks on the Reduced Grøstl Hash Function

CT-RSA 5985:350-365,2010
http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053
Bibtex
Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Rebound Attacks on the Reduced Grøstl Hash Function
In : CT-RSA -
Address :
Date : 2010

Florian Mendel, Thomas Peyrin, Christian Rechberger, Martin Schläffer - Improved Cryptanalysis of the Reduced Grøstl

Compression Function, ECHO Permutation and AES Block Cipher

SAC 5867:16-35,2009
http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420
Bibtex
Author : Florian Mendel, Thomas Peyrin, Christian

Rechberger, Martin Schläffer
Title : Improved Cryptanalysis of the Reduced Grøstl

Compression Function, ECHO Permutation and AES Block Cipher
In : SAC -
Address :
Date : 2009

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl

FSE 5665:260-276,2009
http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943
Bibtex
Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl
In : FSE -
Address :
Date : 2009

John Kelsey - Some notes on Grøstl

, April 2009
http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf
Bibtex
Author : John Kelsey
Title : Some notes on Grøstl
In : -
Address :
Date : April 2009

Paulo S. L. M. Barreto - An observation on Grøstl

, November 2008
http://www.larc.usp.br/~pbarreto/Grizzly.pdf
Bibtex
Author : Paulo S. L. M. Barreto
Title : An observation on Grøstl
In : -
Address :
Date : November 2008
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Groestl&oldid=3770"