Difference between revisions of "LANE"

From The ECRYPT Hash Function Website
(→‎Cryptanalysis: added Naya-Plasencia results)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== The algorithm ==
 
== The algorithm ==
  
−
* Author(s): Sebastiaan Indesteege, Bart Preneel
+
* Author(s): Sebastiaan Indesteege, Elena Andreeva, Christophe De Cannière, Orr Dunkelman, Emilia Käsper, Svetla Nikova, Bart Preneel, Elmar Tischhauser
 
* Website: [http://www.cosic.esat.kuleuven.be/lane/ http://www.cosic.esat.kuleuven.be/lane/]
 
* Website: [http://www.cosic.esat.kuleuven.be/lane/ http://www.cosic.esat.kuleuven.be/lane/]
−
* Specification:
+
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LANE.zip LANE.zip]
 +
 
  
 
<bibtex>
 
<bibtex>
 
@misc{sha3IP08,
 
@misc{sha3IP08,
−
   author    = {Sebastiaan Indesteege and Bart Preneel},
+
   author    = {Sebastiaan Indesteege},
 
   title    = {The LANE hash function},
 
   title    = {The LANE hash function},
 
   url        = {http://www.cosic.esat.kuleuven.be/publications/article-1181.pdf},
 
   url        = {http://www.cosic.esat.kuleuven.be/publications/article-1181.pdf},
Line 14: Line 15:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
−
* None yet
+
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|-             
 +
| semi-free-start collision || compression || 224,256 || 6 P-rounds || 2<sup>80</sup> || 2<sup>66</sup> || [http://eprint.iacr.org/20010/607.pdf Naya-Plasencia]
 +
|-
 +
| semi-free-start collision || compression || 512 || 8 P-rounds || 2<sup>224</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 +
|-     
 +
| collision || hash || 384,512 || 3 P-rounds || 2<sup>94</sup> || 2<sup>133</sup> || [http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf Wu,Feng,Wu]
 +
|-
 +
| semi-free-start collision || compression || 224,256 || 3 P-rounds || 2<sup>62</sup> || 2<sup>69</sup> || [http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf Wu,Feng,Wu]
 +
|-
 +
| semi-free-start collision || compression || 384,512 || 3 P-rounds || 2<sup>62</sup> || 2<sup>69</sup> || [http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf Wu,Feng,Wu]
 +
|-
 +
| semi-free-start collision || compression || 224,256 || 6 P-rounds || 2<sup>96</sup> || 2<sup>88</sup> || [http://eprint.iacr.org/2009/443.pdf Matusiewicz,Naya-Plasencia,Nikolic,Sasaki,Schläffer]
 +
|-
 +
| semi-free-start collision || compression || 512 || 8 P-rounds || 2<sup>224</sup> || 2<sup>128</sup> || [http://eprint.iacr.org/2009/443.pdf Matusiewicz,Naya-Plasencia,Nikolic,Sasaki,Schläffer]
 +
|-
 +
|}
 +
 
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
 
 +
<bibtex>
 +
@misc{cryptoeprint:2010:607,
 +
    author = {María Naya-Plasencia},
 +
    title = {Scrutinizing rebound attacks: new algorithms for improving the complexities},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/607},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2010/607.pdf},
 +
    abstract = {Rebound attacks are a state-of-the-art analysis method for hash functions. These cryptanalysis methods are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this paper we study rebound attacks in detail and find for a great number of cases, that complexities of existing attacks can be improved. This is done by determining problems that adapt optimally to the cryptanalytic situation, and by using better algorithms to follow the differential path. These improvements are essentially based on merging big lists in a more efficient way, as well as on new ideas on how to reduce the complexities. As a result, we introduce general purpose new algorithms for enabling further rebound analysis to be as performant as possible. We illustrate our new algorithms for real hash functions and demonstrate how to reduce the complexities of the best known analysis on five hash functions: JH, Grøstl, ECHO, Luffa and Lane (the first four are round two SHA-3 candidates).},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{laneWFW09,
 +
  author    = {Shuang Wu and Dengguo Feng and Wenling Wu},
 +
  title    = {Cryptanalysis of the LANE Hash Function},
 +
  url      = {http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf},
 +
  howpublished = {Presentation, SAC},
 +
  year      = {2009},
 +
  abstract  = {The LANE hash function is designed by Sebastiaan Indesteege and Bart Preneel. It is now a first round candidate of NIST's SHA-3 competition. The LANE hash function contains four concrete designs with different digest length of 224, 256, 384 and 512.
 +
The LANE hash function uses two permutations P and Q, which consist of different number of AES-like rounds. LANE-224/256 uses 6-round P and 3-round Q. LANE-384/512 uses 8-round P and 4-round Q. We will use LANE-n-(a,b) to denote a variant of LANE with a-round P, b-round Q and a digest length n.
 +
We have found a semi-free start collision attack on reduced-round LANE-256-(3,3) with complexity of 2^62 compression function evaluations and 2^69 memory. This technique can be applied to LANE-512-(3,4) to get a semi-free start collision attack with the same complexity of 2^62 and 2^69 memory. We also propose a collision attack on LANE-512-(3,4) with complexity of 2^94 and 2^133 memory.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{laneMNNSS09,
 +
  author    = {Krystian Matusiewicz and Maria Naya-Plasencia and Ivica Nikolic and Yu Sasaki and Martin Schläffer},
 +
  title    = {Rebound Attack on the Full LANE Compression Function},
 +
  url      = {http://eprint.iacr.org/2009/443.pdf},
 +
  howpublished = {Cryptology ePrint Archive, Report 2009/443},
 +
  year      = {2009},
 +
  abstract  = {In this work, we apply the rebound attack to the AES based SHA-3 candidate LANE. The hash function LANE uses a permutation based compression function, consisting of a linear message expansion and 6 parallel lanes. In the rebound attack on LANE, we apply several new techniques to construct a collision for the full compression function of LANE-256 and LANE-512. Using a relatively sparse truncated differential path, we are able to solve for a valid message expansion and colliding lanes independently. Additionally, we are able to apply the inbound phase more than once by exploiting the degrees of freedom in the parallel AES states. This allows us to construct semi-free-start collisions for full LANE-256 with $2^{96}$ compression function evaluations and $2^{88}$ memory, and for full LANE-512 with $2^{224}$ compression function evaluations and $2^{128}$ memory.},
 +
}
 +
</bibtex>

Latest revision as of 16:17, 7 December 2010

1 The algorithm

  • Author(s): Sebastiaan Indesteege, Elena Andreeva, Christophe De Cannière, Orr Dunkelman, Emilia Käsper, Svetla Nikova, Bart Preneel, Elmar Tischhauser
  • Website: http://www.cosic.esat.kuleuven.be/lane/
  • NIST submission package: LANE.zip


Sebastiaan Indesteege - The LANE hash function

,2008
http://www.cosic.esat.kuleuven.be/publications/article-1181.pdf
Bibtex
Author : Sebastiaan Indesteege
Title : The LANE hash function
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
semi-free-start collision compression 224,256 6 P-rounds 280 266 Naya-Plasencia
semi-free-start collision compression 512 8 P-rounds 2224 264 Naya-Plasencia
collision hash 384,512 3 P-rounds 294 2133 Wu,Feng,Wu
semi-free-start collision compression 224,256 3 P-rounds 262 269 Wu,Feng,Wu
semi-free-start collision compression 384,512 3 P-rounds 262 269 Wu,Feng,Wu
semi-free-start collision compression 224,256 6 P-rounds 296 288 Matusiewicz,Naya-Plasencia,Nikolic,Sasaki,Schläffer
semi-free-start collision compression 512 8 P-rounds 2224 2128 Matusiewicz,Naya-Plasencia,Nikolic,Sasaki,Schläffer

A description of this table is given here.


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

Shuang Wu, Dengguo Feng, Wenling Wu - Cryptanalysis of the LANE Hash Function

,2009
http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf
Bibtex
Author : Shuang Wu, Dengguo Feng, Wenling Wu
Title : Cryptanalysis of the LANE Hash Function
In : -
Address :
Date : 2009

Krystian Matusiewicz, Maria Naya-Plasencia, Ivica Nikolic, Yu Sasaki, Martin Schläffer - Rebound Attack on the Full LANE Compression Function

,2009
http://eprint.iacr.org/2009/443.pdf
Bibtex
Author : Krystian Matusiewicz, Maria Naya-Plasencia, Ivica Nikolic, Yu Sasaki, Martin Schläffer
Title : Rebound Attack on the Full LANE Compression Function
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=LANE&oldid=3658"