Difference between revisions of "Shabal"

From The ECRYPT Hash Function Website
(new nonrandomness observations on the Shabal permutation)
(added eprint 2010/434)
 
(20 intermediate revisions by 7 users not shown)
Line 3: Line 3:
 
* Author(s): Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
 
* Author(s): Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
 
* Website: http://www.shabal.com/
 
* Website: http://www.shabal.com/
−
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Shabal.zip Shabal.zip]
+
* NIST submission package:
 +
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Shabal_Round2.zip Shabal_Round2.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Shabal.zip Shabal.zip])
  
  
Line 13: Line 14:
 
   howpublished = {Submission to NIST},
 
   howpublished = {Submission to NIST},
 
   year      = {2008},
 
   year      = {2008},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2009:199,
 +
    author = {Emmanuel Bresson and Anne Canteaut and Benoît Chevallier-Mames and Christophe Clavier and Thomas Fuhr and Aline Gouget and Thomas Icart and Jean-François Misarsky and Marìa Naya-Plasencia and Pascal Paillier and Thomas Pornin and Jean-René Reinhard and Céline Thuillet and Marion Videau},
 +
    title = {Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/199},
 +
    year = {2009},
 +
    url = {http://eprint.iacr.org/2009/199.pdf},
 +
    abstract = {Shabal is based on a new provably secure mode of operation. Some related-key distinguishers for the underlying keyed permutation have been exhibited recently by Aumasson et al. and Knudsen et al., but with no visible impact on the security of Shabal. This paper then aims at extensively studying such distinguishers for the keyed permutation used in Shabal, and at clarifying the impact that they exert on the security of the full hash function. Most interestingly, a new security proof for Shabal's mode of operation is provided where the keyed permutation is not assumed to be an ideal cipher anymore, but observes a distinguishing property i.e., an explicit relation verified by all its inputs and outputs. As a consequence of this extended proof, all known distinguishers for the keyed permutation are proven not to weaken the security of Shabal. In our study, we provide the foundation of a generalization of the indifferentiability framework to biased random primitives, this part being of independent interest.},
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 19: Line 31:
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
 +
We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.
  
−
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
+
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
Recommended security parameters: (p,r)='''(3,12)'''
 +
 
 +
=== 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
 +
|-                   
 +
| || || || || ||
 +
|-                   
 +
|}
 +
 
 +
=== 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 function || all || 45-bit difference || 2<sup>84</sup> ||  || [http://eprint.iacr.org/2010/434.pdf Isobe,Shirai]
 +
|-                                     
 +
|  | preimage || hash || all || (2,12),no final loop || 2<sup>497</sup> || 2<sup>400</sup> || [http://eprint.iacr.org/2010/434.pdf Isobe,Shirai]
 +
|- 
 +
|  | preimage || hash || all || (1.5,8) || 2<sup>497</sup> || 2<sup>272</sup> || [http://eprint.iacr.org/2010/434.pdf Isobe,Shirai]
 +
|- 
 +
|  | non-randomness || compression function || all || || 1 || || [http://ehash.iaik.tugraz.at/uploads/4/4b/Aumasson_shabal.txt Aumasson]
 +
|-                                                                               
 +
|  | non-randomness || permutation || all || || 2<sup>21</sup> || || [http://eprint.iacr.org/2010/398.pdf Novotney]
 +
|- 
 +
|  | non-randomness || permutation || all || || 2<sup>159</sup> || || [http://gva.noekeon.org/papers/ShabalRotation.pdf Van Assche]
 +
|- 
 +
|  | non-randomness<sup>(1)</sup> || permutation || all || || 2 || || [http://131002.net/data/papers/AMM09.pdf Aumasson,Mashatan,Meier]
 
|-                                         
 
|-                                         
−
|  | non-randomness || permutation || all || || 2<sup>12</sup> || || [http://131002.net/data/papers/Aum09.pdf Aumasson]
+
|  | non-randomness<sup>(1)</sup> || permutation || all || || 1 || || [http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf Knudsen,Matusiewicz,Thomsen]
−
|-                                            
+
|-    
−
|  | non-randomness || permutation || all || || 1 || || [http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf Knudsen, Matusiewicz, Thomsen]
+
|  | non-randomness<sup>(1)</sup> || permutation || all || || 2<sup>12</sup> || || [http://131002.net/data/papers/Aum09.pdf Aumasson]
−
|-                                            
+
|-                                
 
|}                     
 
|}                     
 +
<sup>(1)</sup>The Shabal team commented on these analyses and provide an update of their security proofs in [http://eprint.iacr.org/2009/199.pdf this note].
  
  
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
+
<bibtex>
 +
@misc{shabalIS10,
 +
    author = {Takanori Isobe and Taizo Shirai},
 +
    title = {Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/434},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/434.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
  abstract = {This paper studies two types of attacks on the hash function Shabal. The first attack is a low-weight pseudo collision attack on Shabal. Since a pseudo collision attack is trivial for Shabal, we focus on a low-weight pseudo collision attack. It means that only low-weight difference in a chaining value is considered. By analyzing the difference propagation in the underlying permutation, we can construct a low-weight (45-bits) pseudo collision attack on the full compression function with complexity of 2^84. The second attack is a preimage attack on variants of Shabal-512. We utilize a guess-and-determine technique, which is originally developed for a cryptanalysis of stream ciphers, and customize the technique for a preimage attack on Shabal-512. As a result, for the weakened variant of Shabal-512 using security parameters (p; r) = (2; 12), a preimage can be found with complexity of 2^497 and memory of 2^400. Moreover, for the Shabal-512 using security parameters (p; r) = (1:5; 8), a preimage can be found with complexity of 2^497 and memory of 2^272. To the best of our knowledge, these are best preimage attacks on Shabal variants and the second result is a first preimage attack on Shabal-512 with reduced security parameters.},
 +
}
 +
</bibtex>
  
 +
<bibtex>
 +
@misc{shabalAum10,
 +
  author    = {Jean-Philippe Aumasson},
 +
  title    = {Observation on Shabal},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/4/4b/Aumasson_shabal.txt},
 +
  howpublished = {NIST mailing list (local link)},
 +
  year = {2010},
 +
}
 +
</bibtex>
  
 +
<bibtex>
 +
@misc{shabalNov10,
 +
    author = {Peter Novotney},
 +
    title = {Distinguisher for Shabal's Permutation Function},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/398},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/398.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
  abstract = {In this note we consider the Shabal permutation function $\mathcal{P}$ as a block cipher with input $A_p$,$B_p$ and key $C$,$M$ and describe a distinguisher with a data complexity of $2^{23}$ random inputs with a given difference. If the attacker can control one chosen bit of $B_p$, only $2^{21}$ inputs with a given difference are required on average. This distinguisher does not appear to lead directly to an attack on the full Shabal construction.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{shabalAum09,
+
@misc{shabalVA10,
−
   author    = {Jean-Philippe Aumasson},
+
   author    = {Gilles Van Assche},
−
   title    = {On the pseudorandomness of Shabal's keyed permutation},
+
   title    = {A rotational distinguisher on Shabal's keyed permutation and its impact on the security proofs},
−
   url        = {http://131002.net/data/papers/Aum09.pdf},
+
   url        = {http://gva.noekeon.org/papers/ShabalRotation.pdf},
 
   howpublished = {Available online},
 
   howpublished = {Available online},
 +
  year      = {2010},
 +
  abstract = {In this short note, we apply a rotational distinguisher to the keyed permutation of the SHA-3 candidate Shabal. We then discuss its applicability in the scope of Shabal's mode of operation and its impact on the security proofs.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{shabalAum09a,
 +
  author    = {Jean-Philippe Aumasson and Atefeh Mashatan and Willi Meier},
 +
  title    = {More on Shabal's permutation},
 +
  url        = {http://131002.net/data/papers/AMM09.pdf},
 +
  howpublished = {OFFICIAL COMMENT},
 
   year      = {2009},
 
   year      = {2009},
−
  abstract = {
 
−
  We report observations suggesting that the permutation used in
 
−
  Shabal does not behave pseudorandomly. This does not affect the
 
−
  security of Shabal as submitted to the NIST Hash Competition.},
 
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 54: Line 141:
 
   title    = {Observations on the Shabal keyed permutation},
 
   title    = {Observations on the Shabal keyed permutation},
 
   url        = {http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf },
 
   url        = {http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf },
−
   howpublished = {Available online},
+
   howpublished = {OFFICIAL COMMENT},
 
   year      = {2009},
 
   year      = {2009},
 
   abstract = {
 
   abstract = {
Line 64: Line 151:
 
choice of security parameters. Our observations, on the other hand, do not seem extensible
 
choice of security parameters. Our observations, on the other hand, do not seem extensible
 
to the full hash function.
 
to the full hash function.
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{shabalAum09,
 +
  author    = {Jean-Philippe Aumasson},
 +
  title    = {On the pseudorandomness of Shabal's keyed permutation},
 +
  url        = {http://131002.net/data/papers/Aum09.pdf},
 +
  howpublished = {Available online},
 +
  year      = {2009},
 +
  abstract = {
 +
  We report observations suggesting that the permutation used in
 +
  Shabal does not behave pseudorandomly. This does not affect the
 +
  security of Shabal as submitted to the NIST Hash Competition.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Latest revision as of 17:46, 8 November 2010

1 The algorithm

  • Author(s): Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
  • Website: http://www.shabal.com/
  • NIST submission package:


Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau - Shabal, a Submission to NIST’s Cryptographic Hash Algorithm Competition

,2008
http://ehash.iaik.tugraz.at/uploads/6/6c/Shabal.pdf
Bibtex
Author : Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
Title : Shabal, a Submission to NIST’s Cryptographic Hash Algorithm Competition
In : -
Address :
Date : 2008

Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau - Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers

,2009
http://eprint.iacr.org/2009/199.pdf
Bibtex
Author : Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
Title : Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers
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 parameters: (p,r)=(3,12)

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

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
pseudo collision compression function all 45-bit difference 284 Isobe,Shirai
preimage hash all (2,12),no final loop 2497 2400 Isobe,Shirai
preimage hash all (1.5,8) 2497 2272 Isobe,Shirai
non-randomness compression function all 1 Aumasson
non-randomness permutation all 221 Novotney
non-randomness permutation all 2159 Van Assche
non-randomness(1) permutation all 2 Aumasson,Mashatan,Meier
non-randomness(1) permutation all 1 Knudsen,Matusiewicz,Thomsen
non-randomness(1) permutation all 212 Aumasson

(1)The Shabal team commented on these analyses and provide an update of their security proofs in this note.


Takanori Isobe, Taizo Shirai - Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512

,2010
http://eprint.iacr.org/2010/434.pdf
Bibtex
Author : Takanori Isobe, Taizo Shirai
Title : Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512
In : -
Address :
Date : 2010

Jean-Philippe Aumasson - Observation on Shabal

,2010
http://ehash.iaik.tugraz.at/uploads/4/4b/Aumasson_shabal.txt
Bibtex
Author : Jean-Philippe Aumasson
Title : Observation on Shabal
In : -
Address :
Date : 2010

Peter Novotney - Distinguisher for Shabal's Permutation Function

,2010
http://eprint.iacr.org/2010/398.pdf
Bibtex
Author : Peter Novotney
Title : Distinguisher for Shabal's Permutation Function
In : -
Address :
Date : 2010

Gilles Van Assche - A rotational distinguisher on Shabal's keyed permutation and its impact on the security proofs

,2010
http://gva.noekeon.org/papers/ShabalRotation.pdf
Bibtex
Author : Gilles Van Assche
Title : A rotational distinguisher on Shabal's keyed permutation and its impact on the security proofs
In : -
Address :
Date : 2010

Jean-Philippe Aumasson, Atefeh Mashatan, Willi Meier - More on Shabal's permutation

,2009
http://131002.net/data/papers/AMM09.pdf
Bibtex
Author : Jean-Philippe Aumasson, Atefeh Mashatan, Willi Meier
Title : More on Shabal's permutation
In : -
Address :
Date : 2009

Lars R. Knudsen, Krystian Matusiewicz, Søren S. Thomsen - Observations on the Shabal keyed permutation

,2009
http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf
Bibtex
Author : Lars R. Knudsen, Krystian Matusiewicz, Søren S. Thomsen
Title : Observations on the Shabal keyed permutation
In : -
Address :
Date : 2009

Jean-Philippe Aumasson - On the pseudorandomness of Shabal's keyed permutation

,2009
http://131002.net/data/papers/Aum09.pdf
Bibtex
Author : Jean-Philippe Aumasson
Title : On the pseudorandomness of Shabal's keyed permutation
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Shabal&oldid=3624"