Difference between revisions of "SHAvite-3"

From The ECRYPT Hash Function Website
(Added Nandi and Paul's new fixed points in the SHAvite-3-256 block cipher)
m
 
(12 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
* Author(s): Eli Biham and Orr Dunkelman
 
* Author(s): Eli Biham and Orr Dunkelman
−
<!--
+
* Website: [http://www.cs.technion.ac.il/~orrd/SHAvite-3/ http://www.cs.technion.ac.il/~orrd/SHAvite-3/]
−
* Website:
+
* NIST submission package:
−
-->
+
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite3Update.zip SHAvite3Update.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite-3.zip SHAvite-3.zip])
−
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite-3.zip SHAvite-3.zip]
+
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/SHAvite-3_Round2.zip SHAvite-3_Round2.zip]
  
 +
 +
<bibtex>
 +
@misc{sha3BihamD09,
 +
  author    = {Eli Biham and Orr Dunkelman},
 +
  title    = {The SHAvite-3 Hash Function},
 +
  url        = {http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf},
 +
  howpublished = {Submission to NIST (Round 2)},
 +
  year      = {2009},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 13: Line 23:
 
   title    = {The SHAvite-3 Hash Function},
 
   title    = {The SHAvite-3 Hash Function},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/f/f5/Shavite.pdf},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/f/f5/Shavite.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (Round 1)},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</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: '''12''' rounds (n=224,256); '''14''' rounds (n=384,512)
 +
 
 +
=== 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
 +
|-                   
 +
| second preimage || 512 || 10 rounds || 2<sup>497</sup> || 2<sup>16</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pCurrPk=49974 Gauravaram et al.]
 +
|-                   
 +
| second preimage || 512 || 9 rounds || 2<sup>496</sup> || 2<sup>16</sup> || [http://eprint.iacr.org/2009/634.pdf Bouillaguet et al.]
 +
|-                   
 +
|}                   
 +
 
 +
 
 +
=== 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/e/ea/Peyrin-SHAvite-3.txt Peyrin]
+
| observations || hash || all || ||  ||  || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
 +
|-
 +
| pseudo-preimage || compression || 512 || 14 rounds || 2<sup>384+s</sup> || 2<sup>128-s</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pCurrPk=49974 Gauravaram et al.]
 +
|-                                             
 +
| pseudo-collision || compression || 512 || 14 rounds || 2<sup>192</sup> || 2<sup>128</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pCurrPk=49974 Gauravaram et al.]
 
|-                                               
 
|-                                               
−
|  | pseudo-collision || compression || 256 || ||  ||  || [http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt Nandi,Paul]
+
| pseudo-collision || compression || all || full (Round 1) ||  ||  || [http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt Peyrin]
 
|-                                               
 
|-                                               
 +
| pseudo-collision || compression || 256 || full (Round 1) ||  ||  || [http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt Nandi,Paul]
 +
|-
 +
| impossible differential || block cipher || 224,256 || 5 rounds  || -  || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
 +
|-
 +
| impossible differential || block cipher || 384,512 || 9 rounds  || -  || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
 +
|-
 
|}                     
 
|}                     
  
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
  
 +
<bibtex>
 +
@misc{shaviteGli10,
 +
  author    = {Danilo Gligoroski},
 +
  title    = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
 +
  url        = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf},
 +
  howpublished = {NIST mailing list},
 +
  year      = {2010},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{africacryptGauravaramLMNPRS10,
 +
author = {Praveen Gauravaram and Gaëtan Leurent and Florian Mendel and Maria Naya-Plasencia and Thomas Peyrin and Christian Rechberger and Martin Schläffer},
 +
title = {Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512},
 +
booktitle = {Africacrypt},
 +
year = {2010},
 +
editor = {Daniel J. Bernstein and Tanja Lange},
 +
volume = {6055},
 +
series = {LNCS},
 +
pages = {419 - 436},
 +
publisher = {Springer},
 +
url= {http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pCurrPk=49974},
 +
abstract = {In this paper, we analyze the SHAvite-3-512 hash function, as proposed and tweaked for round 2 of the SHA-3 competition. We present cryptanalytic results on 10 out of 14 rounds of the hash function SHAvite-3-512, and on the full 14 round compression function of SHAvite-3-512. We show a second preimage attack on the hash function reduced to 10 rounds with a complexity of $2^{497}$ compression function evaluations and $2^{16}$ memory. For the full 14-round compression function, we give a chosen counter, chosen salt preimage attack with $2^{384}$ compression function evaluations and $2^{128}$ memory (or complexity $2^{448}$ without memory), and a collision attack with $2^{192}$ compression function evaluations and $2^{128}$ memory.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2009:634,
 +
    author = {Charles Bouillaguet and Orr Dunkelman and Gaëtan Leurent and Pierre-Alain Fouque},
 +
    title = {Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3_{512}},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/634},
 +
    year = {2009},
 +
    url= {http://eprint.iacr.org/2009/634.pdf},
 +
    abstract = {In this paper we study the strength of two hash functions which are based on Generalized Feistels. Our proposed attacks themselves are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions.
 +
 +
We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta. We then show a generic integral attack on 20-round Lesamnta (which can be used against the block cipher itself). We follow with an attack on 9-round SHAvite-3_{512} which is the first cryptanalytic result on the hash function (which also works for the tweaked version of SHAvite-3_{512}).},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Latest revision as of 14:54, 5 July 2010

1 The algorithm


Eli Biham, Orr Dunkelman - The SHAvite-3 Hash Function

,2009
http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf
Bibtex
Author : Eli Biham, Orr Dunkelman
Title : The SHAvite-3 Hash Function
In : -
Address :
Date : 2009

Eli Biham, Orr Dunkelman - The SHAvite-3 Hash Function

,2008
http://ehash.iaik.tugraz.at/uploads/f/f5/Shavite.pdf
Bibtex
Author : Eli Biham, Orr Dunkelman
Title : The SHAvite-3 Hash Function
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: 12 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
second preimage 512 10 rounds 2497 216 Gauravaram et al.
second preimage 512 9 rounds 2496 216 Bouillaguet et al.


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
observations hash all Gligoroski
pseudo-preimage compression 512 14 rounds 2384+s 2128-s Gauravaram et al.
pseudo-collision compression 512 14 rounds 2192 2128 Gauravaram et al.
pseudo-collision compression all full (Round 1) Peyrin
pseudo-collision compression 256 full (Round 1) Nandi,Paul
impossible differential block cipher 224,256 5 rounds - - submission document
impossible differential block cipher 384,512 9 rounds - - submission document


Danilo Gligoroski - Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains

,2010
http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf
Bibtex
Author : Danilo Gligoroski
Title : Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains
In : -
Address :
Date : 2010

Praveen Gauravaram, Gaëtan Leurent, Florian Mendel, Maria Naya-Plasencia, Thomas Peyrin, Christian Rechberger, Martin Schläffer - Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512

Africacrypt 6055:419 - 436,2010
http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pCurrPk=49974
Bibtex
Author : Praveen Gauravaram, Gaëtan Leurent, Florian Mendel, Maria Naya-Plasencia, Thomas Peyrin, Christian Rechberger, Martin Schläffer
Title : Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512
In : Africacrypt -
Address :
Date : 2010

Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent, Pierre-Alain Fouque - Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3_{512}

,2009
http://eprint.iacr.org/2009/634.pdf
Bibtex
Author : Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent, Pierre-Alain Fouque
Title : Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3_{512}
In : -
Address :
Date : 2009

Thomas Peyrin - Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function

,2009
http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt
Bibtex
Author : Thomas Peyrin
Title : Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function
In : -
Address :
Date : 2009

Mridul Nandi, Souradyuti Paul - OFFICIAL COMMENT: SHAvite-3

,2009
http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt
Bibtex
Author : Mridul Nandi, Souradyuti Paul
Title : OFFICIAL COMMENT: SHAvite-3
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=SHAvite-3&oldid=3527"