Difference between revisions of "Luffa"

From The ECRYPT Hash Function Website
m (analysis update)
(Cryptanalysis updated)
 
(8 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
* Author(s): Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
 
* Author(s): Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
 
* Website: [http://www.sdl.hitachi.co.jp/crypto/luffa/ http://www.sdl.hitachi.co.jp/crypto/luffa/]
 
* Website: [http://www.sdl.hitachi.co.jp/crypto/luffa/ http://www.sdl.hitachi.co.jp/crypto/luffa/]
−
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Luffa.zip Luffa.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LuffaUpdate.zip LuffaUpdate.zip]
+
* NIST submission package:
 +
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LuffaUpdate.zip LuffaUpdate.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Luffa.zip Luffa.zip])
 +
**round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Luffa_Round2_Update.zip Luffa_Round2_Update.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Luffa_Round2.zip Luffa_Round2.zip])
  
 +
 +
<bibtex>
 +
@misc{sha3CHSW09,
 +
  author    = {Christophe De Canniere and Hisayoshi Sato and Dai Watanabe},
 +
  title    = {Hash Function Luffa: Specification},
 +
  url        = {http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_Specification_20091002.pdf},
 +
  howpublished = {Submission to NIST (Round 2)},
 +
  year      = {2009},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{sha3CHSW09a,
 +
  author    = {Christophe De Canniere and Hisayoshi Sato and Dai Watanabe},
 +
  title    = {Hash Function Luffa: Supporting Document},
 +
  url        = {http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_SupportingDocument_20090915.pdf},
 +
  howpublished = {Submission to NIST (Round 2)},
 +
  year      = {2009},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 11: Line 33:
 
   title    = {Hash Function Luffa: Specification},
 
   title    = {Hash Function Luffa: Specification},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/e/ea/Luffa_Specification.pdf},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/e/ea/Luffa_Specification.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (Round 1)},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
  
 
<bibtex>
 
<bibtex>
Line 22: Line 43:
 
   title    = {Hash Function Luffa: Supporting Document},
 
   title    = {Hash Function Luffa: Supporting Document},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/f/fe/Luffa_SupportingDocument.pdf},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/f/fe/Luffa_SupportingDocument.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (Round 1)},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
  
 
== Cryptanalysis ==
 
== 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 [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 +
Recommended security parameter: '''8''' 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
 +
|-                   
 +
| collision || 256 || 4 rounds || 2<sup>90</sup> || - || [http://www.sdl.hitachi.co.jp/crypto/luffa/FindingCollisionsForReducedLuffa-256v2_20101108.pdf Preneel,Yoshida,Watanabe]
 +
|-                   
 +
|}                   
 +
 +
 +
=== 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" style="text-align:center"                   
+
{| 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-2nd preimage || hash || all ||  || 1 || - || [http://eprint.iacr.org/2009/224.pdf Jia]
+
| distinguisher || hash || 256 || Round 1 || 2<sup>251</sup> || - || [http://eprint.iacr.org/2010/589.pdf Boura,Canteaut,DeCanniere]
 +
|-
 +
| distinguisher || permutation ||  || 8 rounds || 2<sup>252</sup> || - || [http://eprint.iacr.org/2010/589.pdf Boura,Canteaut,DeCanniere]
 +
|-
 +
| semi-free-start collision || hash || 256 || 7 rounds || 2<sup>104</sup> || 2<sup>102</sup> || [http://online.tugraz.at/tug_online/voe_main2.getVollText?pDocumentNr=163671&pCurrPk=52053 Khovratovich,Naya-Plasencia,Röck,Schläffer]
 
|-
 
|-
−
| pseudo-preimage || hash || 256 || || 2<sup>127</sup> || - || [http://eprint.iacr.org/2009/224.pdf Jia]
+
| distinguisher || round function || 256 || 8 rounds || 2<sup>104</sup> || 2<sup>102</sup> || [http://online.tugraz.at/tug_online/voe_main2.getVollText?pDocumentNr=163671&pCurrPk=52053  Khovratovich,Naya-Plasencia,Röck,Schläffer]
 
|-
 
|-
−
| pseudo-preimage || hash || 512 || || 2<sup>171</sup> || - || [http://eprint.iacr.org/2009/224.pdf Jia]
+
| distinguisher || permutation || || 8 rounds || 2<sup>116.3</sup> || ? || [http://online.tugraz.at/tug_online/voe_main2.getVollText?pDocumentNr=163671&pCurrPk=52053  Khovratovich,Naya-Plasencia,Röck,Schläffer]
 
|-
 
|-
−
| distinguisher || permutation ||  || 4 rounds || ? || - || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
+
| distinguisher || permutation ||  || 8 rounds || 2<sup>82</sup> || - || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
 +
|-
 +
| free-start 2nd preimage || hash || all ||  || 1 || - || [http://eprint.iacr.org/2009/224.pdf Jia]
 +
|-
 +
| free-start preimage || hash || 256 ||  || 2<sup>127</sup> || - || [http://eprint.iacr.org/2009/224.pdf Jia]
 +
|-
 +
| free-start preimage || hash || 512 ||  || 2<sup>171</sup> || - || [http://eprint.iacr.org/2009/224.pdf Jia]
 +
|-
 +
| semi-free-start collision || hash || all || any || 2<sup>256*(w-1)/w</sup> || - || [http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_SupportingDocument_20090915.pdf submission document]
 +
|-
 +
| semi-free-start collision || hash || 512 || any || 2<sup>204.8</sup> || - || [http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_SupportingDocument_20090915.pdf submission document]
 +
|-
 +
| non-randomness || permutation ||  || 8 rounds || 2<sup>224</sup> || - || [http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_SupportingDocument_20090915.pdf submission document]
 
|-
 
|-
 
|}                     
 
|}                     
−
 
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
  
  
 
<bibtex>
 
<bibtex>
 
@misc{cryptoeprint:2009:224,
 
@misc{cryptoeprint:2009:224,
−
     author = {Keting Jia},
+
     author = {Christina Boura and Anne Canteaut and Christophe De Canni\`ere},
−
     title = {Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa},
+
     title = {Higher-order differential properties of Keccak and Luffa},
−
     howpublished = {Cryptology ePrint Archive, Report 2009/224},
+
     howpublished = {Cryptology ePrint Archive, Report 2010/589},
−
     year = {2009},
+
     year = {2010},
 
     note = {\url{http://eprint.iacr.org/}},
 
     note = {\url{http://eprint.iacr.org/}},
−
     url = {http://eprint.iacr.org/2009/224.pdf},
+
     url = {http://eprint.iacr.org/2010/589.pdf},
−
     abstract = {In this paper, we show some pseudo-collision and pseudo-second-preimage examples for the SHA-3 candidate algorithm Luffa. The pseudo-collision and pseudo-second-preimage can be obtained easily by the message injection function. At the same time, the pseudo-preimage attacks are shown in this paper. For Luffa-224/256, only two iteration functions is needed to get the pseudo-preimage. We need $2^{127}$ and $2^{171}$ to get the pseudo-preimage for Luffa-384 and Luffa-512 respectively. },
+
     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>
 +
 +
<bibtex>
 +
@misc{luffaPYW10,
 +
  author    = {Bart Preneel, Hirotaka Yoshida, Dai Watanabe},
 +
  title    = {Finding Collisions for Reduced Luffa-256 v2},
 +
  url        = {http://www.sdl.hitachi.co.jp/crypto/luffa/FindingCollisionsForReducedLuffa-256v2_20101108.pdf},
 +
  howpublished = {NIST mailing list}
 +
  year      = {2010},
 +
  abstract  = {Luffa is a family of cryptographic hash functions that has been selected as a second round SHA-3 candidate. This paper presents the first collision finding analysis of Luffa-256 v2 which is the 256-bit hash function in the Luffa family. We show that collisions for 4 out of 8 steps of Luffa can be found with complexity $2^{90}$ using sophisticated message modification techniques. Furthermore, we present a security analysis which shows how difficult it is to apply the same approach to Luffa-256 v2 reduced to 5 steps: the resulting attack would require a complexity of $2^{224}$. This analysis can be seen as an indication that the full 8 steps of the Luffa-256 v2 hash function has a large security margin against differential collision search with message modification technique.},
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{sacKNRS10,
 +
  author = {Dmitry Khovratovich, Maria Naya-Plasencia, Andrea Röck, Martin Schläffer},
 +
  title = {Cryptanalysis of Luffa v2 Components},
 +
  url = {http://online.tugraz.at/tug_online/voe_main2.getVollText?pDocumentNr=163671&pCurrPk=52053},
 +
  booktitle  = {SAC},
 +
  year      = {2010},
 +
  series    = {LNCS},
 +
  publisher  = {Springer},
 +
  note = {To appear}
 +
  abstract = {We develop a number of techniques for the cryptanalysis of the SHA-3 candidate Luffa, and apply them to various Luffa components. These techniques include a new variant of the rebound approach taking into account the specifics of Luffa. The main improvements include the construction of good truncated differential paths, the search for differences using multiple inbound phases and a fast final solution search via linear systems. Using these techniques, we are able to construct non-trivial semi-free-start collisions for 7 (out of 8 rounds) of Luffa-256 with a complexity of $2^{104}$ in time and $2^{102}$ in memory. This is the first analysis of a Luffa component other that the permutation of Luffa v1. Additionally, we provide new and more efficient distinguishers also for the full permutation of Luffa v2. For this permutation distinguisher, we use a new model which applies first a short test on all samples and then a longer test on a smaller subset of the inputs. We demonstrate that a set of right pairs for the given differential path can be found significantly faster than for a random permutation.}
 
</bibtex>
 
</bibtex>
  
Line 67: Line 150:
 
   year      = {2009},
 
   year      = {2009},
 
   abstract  = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
 
   abstract  = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2009:224,
 +
    author = {Keting Jia},
 +
    title = {Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/224},
 +
    year = {2009},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2009/224.pdf},
 +
    abstract = {In this paper, we show some pseudo-collision and pseudo-second-preimage examples for the SHA-3 candidate algorithm Luffa. The pseudo-collision and pseudo-second-preimage can be obtained easily by the message injection function. At the same time, the pseudo-preimage attacks are shown in this paper. For Luffa-224/256, only two iteration functions is needed to get the pseudo-preimage. We need $2^{127}$ and $2^{171}$ to get the pseudo-preimage for Luffa-384 and Luffa-512 respectively. },
 +
}
 
</bibtex>
 
</bibtex>

Latest revision as of 16:08, 6 December 2010

1 The algorithm


Christophe De Canniere, Hisayoshi Sato, Dai Watanabe - Hash Function Luffa: Specification

,2009
http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_Specification_20091002.pdf
Bibtex
Author : Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
Title : Hash Function Luffa: Specification
In : -
Address :
Date : 2009

Christophe De Canniere, Hisayoshi Sato, Dai Watanabe - Hash Function Luffa: Supporting Document

,2009
http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_SupportingDocument_20090915.pdf
Bibtex
Author : Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
Title : Hash Function Luffa: Supporting Document
In : -
Address :
Date : 2009

Christophe De Canniere, Hisayoshi Sato, Dai Watanabe - Hash Function Luffa: Specification

,2008
http://ehash.iaik.tugraz.at/uploads/e/ea/Luffa_Specification.pdf
Bibtex
Author : Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
Title : Hash Function Luffa: Specification
In : -
Address :
Date : 2008

Christophe De Canniere, Hisayoshi Sato, Dai Watanabe - Hash Function Luffa: Supporting Document

,2008
http://ehash.iaik.tugraz.at/uploads/f/fe/Luffa_SupportingDocument.pdf
Bibtex
Author : Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
Title : Hash Function Luffa: Supporting Document
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: 8 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
collision 256 4 rounds 290 - Preneel,Yoshida,Watanabe


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 hash 256 Round 1 2251 - Boura,Canteaut,DeCanniere
distinguisher permutation 8 rounds 2252 - Boura,Canteaut,DeCanniere
semi-free-start collision hash 256 7 rounds 2104 2102 Khovratovich,Naya-Plasencia,Röck,Schläffer
distinguisher round function 256 8 rounds 2104 2102 Khovratovich,Naya-Plasencia,Röck,Schläffer
distinguisher permutation 8 rounds 2116.3 ? Khovratovich,Naya-Plasencia,Röck,Schläffer
distinguisher permutation 8 rounds 282 - Aumasson,Meier
free-start 2nd preimage hash all 1 - Jia
free-start preimage hash 256 2127 - Jia
free-start preimage hash 512 2171 - Jia
semi-free-start collision hash all any 2256*(w-1)/w - submission document
semi-free-start collision hash 512 any 2204.8 - submission document
non-randomness permutation 8 rounds 2224 - submission document


Christina Boura, Anne Canteaut, Christophe De Canni\`ere - Higher-order differential properties of Keccak and Luffa

,2010
http://eprint.iacr.org/2010/589.pdf
Bibtex
Author : Christina Boura, Anne Canteaut, Christophe De Canni\`ere
Title : Higher-order differential properties of Keccak and Luffa
In : -
Address :
Date : 2010

Bart Preneel, Hirotaka Yoshida, Dai Watanabe - Finding Collisions for Reduced Luffa-256 v2

,2010
http://www.sdl.hitachi.co.jp/crypto/luffa/FindingCollisionsForReducedLuffa-256v2_20101108.pdf
Bibtex
Author : Bart Preneel, Hirotaka Yoshida, Dai Watanabe
Title : Finding Collisions for Reduced Luffa-256 v2
In : -
Address :
Date : 2010

Dmitry Khovratovich, Maria Naya-Plasencia, Andrea Röck, Martin Schläffer - Cryptanalysis of Luffa v2 Components

SAC ,2010
http://online.tugraz.at/tug_online/voe_main2.getVollText?pDocumentNr=163671&pCurrPk=52053
Bibtex
Author : Dmitry Khovratovich, Maria Naya-Plasencia, Andrea Röck, Martin Schläffer
Title : Cryptanalysis of Luffa v2 Components
In : SAC -
Address :
Date : 2010

Jean-Philippe Aumasson, Willi Meier - Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi

,2009
http://www.131002.net/data/papers/AM09.pdf
Bibtex
Author : Jean-Philippe Aumasson, Willi Meier
Title : Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi
In : -
Address :
Date : 2009

Keting Jia - Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa

,2009
http://eprint.iacr.org/2009/224.pdf
Bibtex
Author : Keting Jia
Title : Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Luffa&oldid=3639"