Difference between revisions of "BLAKE"

From The ECRYPT Hash Function Website
(added Gligoroski's paper)
(http://eprint.iacr.org/2010/355 added)
Line 53: Line 53:
 
| 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  
 
|-
 
|-
−
|  observations || hash || all || ||  ||  || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
+
| near-collision || compression function || 256 || 4 rounds (round 4-7) || 2<sup>21</sup> || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
| near-collision || compression function || 512 || 4 rounds (round 7-10) || 2<sup>16</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
| near-collision || compression function || 512 || 5 rounds (round 7-11) || 2<sup>216</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
| observations || hash || all || ||  ||  || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
 
|-
 
|-
 
| impossible differential || permutation || 224,256 || 5 rounds  || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
 
| impossible differential || permutation || 224,256 || 5 rounds  || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
Line 59: Line 65:
 
| impossible differential || permutation || 384,512 || 6 rounds  || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
 
| impossible differential || permutation || 384,512 || 6 rounds  || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
 
|-
 
|-
−
| near-collision || compression function || 256 || 4 rounds (nb. 3-6) || 2<sup>56</sup>  || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
+
| near-collision || compression function || 256 || 4 rounds (round 3-6) || 2<sup>56</sup>  || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
 
|-
 
|-
 
| free-start collision || hash || 224,256 || 2.5 rounds  || 2<sup>n/2-16</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
 
| free-start collision || hash || 224,256 || 2.5 rounds  || 2<sup>n/2-16</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
Line 67: Line 73:
 
|}                     
 
|}                     
  
 +
 +
<bibtex>
 +
@misc{blakeSuWWD10,
 +
  author = {Bozhan Su and Wenling Wu and Shuang Wu and Le Dong},
 +
  title = {Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE},
 +
  howpublished = {Cryptology ePrint Archive, Report 2010/355},
 +
  year = {2010},
 +
  url = {http://eprint.iacr.org/2010/355.pdf},
 +
  abstract = {The SHA-3 competition organized by NIST aims to find a new hash standard as a replacement of SHA-2. Till now, 14 submissions have been selected as the second round candidates, including Skein and BLAKE, both of which have components based on modular addition, rotation and bitwise XOR (ARX). In this paper, we propose improved near-collision attacks on the reduced-round compression functions of Skein and a variant of BLAKE. The attacks are based on linear differentials of the modular additions. The computational complexity of near-collision attacks on a 4-round compression function of BLAKE-32, 4-round and 5-round compression functions of BLAKE-64 are 2^{21}, 2^{16} and 2^{216} respectively, and the attacks on a 24-round compression functions of Skein-256, Skein-512 and Skein-1024 have a complexity of 2^{60}, 2^{230} and 2^{395} respectively.}
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Revision as of 13:43, 5 July 2010

1 The algorithm


Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan - SHA-3 proposal BLAKE

,2008
http://131002.net/blake/blake.pdf
Bibtex
Author : Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
Title : SHA-3 proposal BLAKE
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
preimage 224,256 2.5 rounds 2n-15 - Ji,Liangyu
preimage 384 2.5 rounds 2355 - Ji,Liangyu
preimage 512 2.5 rounds 2481 - Ji,Liangyu


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
near-collision compression function 256 4 rounds (round 4-7) 221 - Su,Wu,Wu,Dong
near-collision compression function 512 4 rounds (round 7-10) 216 - Su,Wu,Wu,Dong
near-collision compression function 512 5 rounds (round 7-11) 2216 - Su,Wu,Wu,Dong
observations hash all Gligoroski
impossible differential permutation 224,256 5 rounds - - Aumasson,Guo,Knellwolf,Matusiewicz,Meier
impossible differential permutation 384,512 6 rounds - - Aumasson,Guo,Knellwolf,Matusiewicz,Meier
near-collision compression function 256 4 rounds (round 3-6) 256 - Guo,Matusiewicz
free-start collision hash 224,256 2.5 rounds 2n/2-16 - Ji,Liangyu
free-start collision hash 384,512 2.5 rounds 2n/2-32 - Ji,Liangyu


Bozhan Su, Wenling Wu, Shuang Wu, Le Dong - Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE

,2010
http://eprint.iacr.org/2010/355.pdf
Bibtex
Author : Bozhan Su, Wenling Wu, Shuang Wu, Le Dong
Title : Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE
In : -
Address :
Date : 2010

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

Jean-Philippe Aumasson, Jian Guo, Simon Knellwolf, Krystian Matusiewicz, Willi Meier - Differential and invertibility properties of BLAKE (full version)

,2010
http://eprint.iacr.org/2010/043.pdf
Bibtex
Author : Jean-Philippe Aumasson, Jian Guo, Simon Knellwolf, Krystian Matusiewicz, Willi Meier
Title : Differential and invertibility properties of BLAKE (full version)
In : -
Address :
Date : 2010

Jian Guo, Krystian Matusiewicz - Round-Reduced Near-Collisions of BLAKE-32

,2009
http://www.jguo.org/docs/blake-col.pdf
Bibtex
Author : Jian Guo, Krystian Matusiewicz
Title : Round-Reduced Near-Collisions of BLAKE-32
In : -
Address :
Date : 2009

Li Ji, Xu Liangyu - Attacks on Round-Reduced BLAKE

,2009
http://eprint.iacr.org/2009/238.pdf
Bibtex
Author : Li Ji, Xu Liangyu
Title : Attacks on Round-Reduced BLAKE
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=BLAKE&oldid=3517"