Difference between revisions of "BLAKE"

From The ECRYPT Hash Function Website
m (fixed bibtex entry)
(results updated)
Line 27: Line 27:
 
=== Hash function ===
 
=== Hash function ===
  
−
Here we list results on the actual hash function. The only allowed modification is to change the security parameter.
+
Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.
  
 
Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
 
Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
Line 49: Line 49:
  
 
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).  
 
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).  
 +
 +
Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
  
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" 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  
−
|-                   
 
−
| 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 || 384,512 || 2.5 rounds  || 2<sup>n/2-32</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
+
| impossible differential || permutation || 224,256 || 5 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. 6-9) || 2<sup>42</sup>  || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
+
| near-collision || compression function || 256 || 4 rounds (nb. 6-9) || 2<sup>42</sup>  || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
 
|-
 
|-
−
| impossible differential || permutation || 224,256 || 5 rounds  || -  || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
+
| 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 || 384,512 || 2.5 rounds  || 2<sup>n/2-32</sup> || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
−
| impossible differential || permutation || 384,512 || 6 rounds  || -  || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
 
 
|-
 
|-
 
|}                     
 
|}                     
Line 71: Line 72:
  
 
<bibtex>
 
<bibtex>
−
@misc{cryptoeprint:2009:238,
+
@misc{cryptoeprint:2010:043,
−
     author = {Li Ji and Xu Liangyu },
+
     author = {Jean-Philippe Aumasson and Jian Guo and Simon Knellwolf
−
     title = {Attacks on Round-Reduced BLAKE},
+
and Krystian Matusiewicz and Willi Meier},
−
     howpublished = {Cryptology ePrint Archive, Report 2009/238},
+
     title = {Differential and invertibility properties of BLAKE (full version)},
−
     year = {2009},
+
     howpublished = {Cryptology ePrint Archive, Report 2010/043},
−
    note = {\url{http://eprint.iacr.org/}},
+
     year = {2010},
−
     url = {http://eprint.iacr.org/2009/238.pdf},
+
     url = {http://eprint.iacr.org/2010/043.pdf},
−
     abstract = {BLAKE is a new hash family proposed for SHA-3. The core of compression function reuses the core function of ChaCha. A round-dependent permutation is used as message schedule. BLAKE is claimed to achieve full diffusion after 2 rounds. However, message words can be controlled on the first several founds. By exploiting properties of message permutation, we can attack 2.5 reduced rounds. The results do not threat the security claimed in the specification. },
+
     abstract = {BLAKE is a hash function selected by NIST as one of
 +
the 14 second round candidates for the SHA-3 Competition. In this
 +
paper, we follow a bottom-up approach to exhibit properties of BLAKE
 +
and of its building blocks: based on differential properties of the
 +
internal function G, we show that a round of BLAKE is a permutation on
 +
the message space, and present an efficient inversion algorithm. For
 +
1.5 rounds we present an algorithm that finds preimages faster than in
 +
previous attacks. Discovered properties lead us to describe large
 +
classes of impossible differentials for two rounds of BLAKE’s internal
 +
permutation, and particular impossible differentials for five and six
 +
rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear
 +
and rotation-free model, we describe near-collisions for four rounds
 +
of the compression function. Finally, we discuss the problem of
 +
establishing upper bounds on the probability of differential
 +
characteristics for BLAKE.},
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 94: Line 109:
  
 
<bibtex>
 
<bibtex>
−
@misc{cryptoeprint:2010:043,
+
@misc{cryptoeprint:2009:238,
−
     author = {Jean-Philippe Aumasson and Jian Guo and Simon Knellwolf and Krystian Matusiewicz and Willi Meier},
+
     author = {Li Ji and Xu Liangyu },
−
     title = {Differential and invertibility properties of BLAKE (full version)},
+
     title = {Attacks on Round-Reduced BLAKE},
−
     howpublished = {Cryptology ePrint Archive, Report 2010/043},
+
     howpublished = {Cryptology ePrint Archive, Report 2009/238},
−
     year = {2010},
+
     year = {2009},
−
     url = {http://eprint.iacr.org/2010/043.pdf},
+
    note = {\url{http://eprint.iacr.org/}},
−
     abstract = {BLAKE is a hash function selected by NIST as one of the 14 second round candidates for the SHA-3 Competition. In this paper, we follow a bottom-up approach to exhibit properties of BLAKE and of its building blocks: based on differential properties of the internal function G, we show that a round of BLAKE is a permutation on the message space, and present an efficient inversion algorithm. For 1.5 rounds we present an algorithm that finds preimages faster than in previous attacks. Discovered properties lead us to describe large classes of impossible differentials for two rounds of BLAKE’s internal permutation, and particular impossible differentials for five and six rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear and rotation-free model, we describe near-collisions for four rounds of the compression function. Finally, we discuss the problem of establishing upper bounds on the probability of differential characteristics for BLAKE.},
+
     url = {http://eprint.iacr.org/2009/238.pdf},
 +
     abstract = {BLAKE is a new hash family proposed for SHA-3. The
 +
core of compression function reuses the core function of ChaCha. A
 +
round-dependent permutation is used as message schedule. BLAKE is
 +
claimed to achieve full diffusion after 2 rounds. However, message
 +
words can be controlled on the first several founds. By exploiting
 +
properties of message permutation, we can attack 2.5 reduced rounds.
 +
The results do not threat the security claimed in the specification.
 +
},
 
}
 
}
 
</bibtex>
 
</bibtex>

Revision as of 15:55, 15 February 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.


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.

Recommended security parameters: 10 rounds (n=224,256); 14 rounds (n=384,512)

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).

Recommended security parameters: 10 rounds (n=224,256); 14 rounds (n=384,512)

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
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 (nb. 6-9) 242 - 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



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=3377"