Difference between revisions of "BLAKE"

From The ECRYPT Hash Function Website
(Added Guo/Matusiewicz results)
m (references updated)
 
(23 intermediate revisions by 4 users not shown)
Line 3: Line 3:
 
* Author(s): Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
 
* Author(s): Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
 
* Website: [http://131002.net/blake/ http://131002.net/blake/]
 
* Website: [http://131002.net/blake/ http://131002.net/blake/]
−
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKE.zip BLAKE.zip]
+
* NIST submission package:
 +
** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Blake_FinalRnd.zip Blake_FinalRnd.zip]
 +
** Round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/BLAKE_Round2.zip BLAKE_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKE.zip BLAKE.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKEUpdate.zip BLAKEUpdate.zip])
  
 +
 +
<bibtex>
 +
@misc{sha3AumassonHMP10,
 +
  author    = {Jean-Philippe Aumasson and Luca Henzen and Willi Meier and Raphael C.-W. Phan},
 +
  title    = {SHA-3 proposal BLAKE},
 +
  url        = {http://131002.net/blake/blake.pdf},
 +
  howpublished = {Submission to NIST (Round 3)},
 +
  year      = {2010},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 10: Line 22:
 
   author    = {Jean-Philippe Aumasson and Luca Henzen and Willi Meier and Raphael C.-W. Phan},
 
   author    = {Jean-Philippe Aumasson and Luca Henzen and Willi Meier and Raphael C.-W. Phan},
 
   title    = {SHA-3 proposal BLAKE},
 
   title    = {SHA-3 proposal BLAKE},
−
   url        = {http://131002.net/blake/blake.pdf},
+
   url        = {http://ehash.iaik.tugraz.at/uploads/0/06/Blake.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (Round 1/2)},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 +
== 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: '''14''' rounds (n=224,256); '''16''' rounds (n=384,512)
 +
 +
 +
=== 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
 +
|-                   
 +
| preimage || 224,256 || 2.5 rounds  || 2<sup>n-15</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
 +
|-
 +
| preimage || 384 || 2.5 rounds  || 2<sup>355</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
 +
|-
 +
| preimage ||  512 || 2.5 rounds  || 2<sup>481</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
 +
|-
 +
|}                   
 +
 +
 +
=== Building blocks ===
  
−
== Cryptanalysis ==
+
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  
−
|-                   
 
−
| 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]
+
| semi-free-start near-collisions || compression function || 256 || 2 rounds || 2<sup>26</sup> || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan]
 +
|-
 +
| collision || hash || all || toy version BLOKE || example  || - || [http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf Vidali,Nose,Pašalic]
 +
|-
 +
| semi-free-start collision || compression function || all || toy version BRAKE || example  || - || [http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf Vidali,Nose,Pašalic]
 +
|-
 +
| near-collision || compression function || 256 || 4 rounds (No. 4-7) || 2<sup>21</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
| near-collision || compression function || 512 || 4 rounds (No. 7-10) || 2<sup>16</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
| near-collision || compression function || 512 || 5 rounds (No. 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]
 
|-
 
|-
−
| preimage || hash || 224/256 || 2.5 rounds  || 2<sup>n-15</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]
 
|-
 
|-
−
| preimage || hash || 384 || 2.5 rounds  || 2<sup>355</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
+
| near-collision || compression function || 256 || 4 rounds (No. 3-6) || 2<sup>56</sup>  || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
 
|-
 
|-
−
| preimage || hash || 512 || 2.5 rounds  || 2<sup>481</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]
 
|-
 
|-
−
| near-collision || compression function || 256 || 4 rounds (nb. 6-9) || 2<sup>42</sup>  || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
+
| free-start collision || hash || 384,512 || 2.5 rounds  || 2<sup>n/2-32</sup>  || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
 
|-
 
|-
 
|}                     
 
|}                     
  
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
  
 +
<bibtex>
 +
@misc{blakeTU10,
 +
  author = {Meltem Sönmez Turan, Erdener Uyan},
 +
  title = {Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH},
 +
  howpublished = {Second SHA-3 Candidate Conference},
 +
  year = {2010},
 +
  url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf},
 +
  abstract = {A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. We also observed practical collisions and near-collisions for reduced versions of F-256 function used in Fugue.}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{iplVNP10,
 +
  author    = {Janoš Vidali, Peter Nose, Enes Pašalic},
 +
  title    = {Collisions for variants of the BLAKE hash function},
 +
  url = {http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf},
 +
  booktitle = {Information Processing Letters},
 +
  volume = {110},
 +
  issue = {14-15},
 +
  month = {July},
 +
  year = {2010},
 +
  pages = {585--590},
 +
  publisher = {Elsevier North-Holland, Inc.},
 +
  abstract = {In this paper we present an attack to the BLOKE and BRAKE hash functions, which are weakened versions of the SHA-3 candidate BLAKE. In difference to BLAKE, the BLOKE hash function does not permute the message words and constants in the round computation of the compression function, and BRAKE additionally removes feedforward and zeroes the constants used in each round of the compression function. We show that in these cases we can efficiently find, for any intermediate hash value, a fixed-point block giving us an internal collision, thus producing collisions for messages of equal length in case of BLOKE, and internal collisions for BRAKE.}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{skeinSuWWD10,
 +
  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},
 +
  booktitle = {CANS},
 +
  year      = {2010},
 +
  pages    = {124-139},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6467},
 +
  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>
 +
@misc{blakeGli10,
 +
  author    = {Danilo Gligoroski},
 +
  title    = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
 +
  url        = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf},
 +
  howpublished = {NIST hash function mailing list},
 +
  year      = {2010},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{cryptoeprint:2009:238,
+
@inproceedings{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},
−
     year = {2009},
+
  booktitle = {FSE},
−
    note = {\url{http://eprint.iacr.org/}},
+
  year      = {2010},
−
     url = {http://eprint.iacr.org/2009/238.pdf},
+
  pages     = {318-332},
−
     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. },
+
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6147},
 +
     url = {http://eprint.iacr.org/2010/043.pdf},
 +
     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 57: Line 176:
 
  author = {Jian Guo and Krystian Matusiewicz},
 
  author = {Jian Guo and Krystian Matusiewicz},
 
  title  = {Round-Reduced Near-Collisions of BLAKE-32},
 
  title  = {Round-Reduced Near-Collisions of BLAKE-32},
−
  url   = {http://www.jguo.org/docs/blake-col.pdf},
+
howpublished = {Accepted for presentation at WEWoRC 2009},
−
howpublished = {Available online},
+
  url = {http://www.jguo.org/docs/blake-col.pdf},
−
note = {Accepted for presentation at WEWoRC 2009},
 
 
  year  = {2009}
 
  year  = {2009}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2009:238,
 +
    author = {Li Ji and Xu Liangyu },
 +
    title = {Attacks on Round-Reduced BLAKE},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/238},
 +
    year = {2009},
 +
    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>

Latest revision as of 10:26, 22 April 2011

1 The algorithm


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

,2010
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 : 2010

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

,2008
http://ehash.iaik.tugraz.at/uploads/0/06/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: 14 rounds (n=224,256); 16 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
semi-free-start near-collisions compression function 256 2 rounds 226 - Turan,Uyan
collision hash all toy version BLOKE example - Vidali,Nose,Pašalic
semi-free-start collision compression function all toy version BRAKE example - Vidali,Nose,Pašalic
near-collision compression function 256 4 rounds (No. 4-7) 221 - Su,Wu,Wu,Dong
near-collision compression function 512 4 rounds (No. 7-10) 216 - Su,Wu,Wu,Dong
near-collision compression function 512 5 rounds (No. 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 (No. 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


Meltem Sönmez Turan, Erdener Uyan - Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH

,2010
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf
Bibtex
Author : Meltem Sönmez Turan, Erdener Uyan
Title : Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
In : -
Address :
Date : 2010

Janoš Vidali, Peter Nose, Enes Pašalic - Collisions for variants of the BLAKE hash function

Information Processing Letters 110:585--590, July 2010
http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf
Bibtex
Author : Janoš Vidali, Peter Nose, Enes Pašalic
Title : Collisions for variants of the BLAKE hash function
In : Information Processing Letters -
Address :
Date : July 2010

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

CANS 6467:124-139,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 : CANS -
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

FSE 6147:318-332,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
In : FSE -
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=3707"