Difference between revisions of "BLAKE"
From The ECRYPT Hash Function Website
Mschlaeffer (talk | contribs) m |
Mschlaeffer (talk | contribs) m (references updated) |
||
| Line 97: | Line 97: | ||
howpublished = {Second SHA-3 Candidate Conference}, | howpublished = {Second SHA-3 Candidate Conference}, | ||
year = {2010}, | year = {2010}, | ||
| − | + | note = {Available online: 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.} | 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.} | ||
} | } | ||
| Line 106: | Line 106: | ||
author = {Janoš Vidali, Peter Nose, Enes Pašalic}, | author = {Janoš Vidali, Peter Nose, Enes Pašalic}, | ||
title = {Collisions for variants of the BLAKE hash function}, | title = {Collisions for variants of the BLAKE hash function}, | ||
| − | + | note = {Available online: http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf}, | |
| − | booktitle | + | booktitle = {Information Processing Letters}, |
| − | year | + | 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.} | 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> | ||
| Line 118: | Line 123: | ||
howpublished = {Cryptology ePrint Archive, Report 2010/355}, | howpublished = {Cryptology ePrint Archive, Report 2010/355}, | ||
year = {2010}, | year = {2010}, | ||
| − | + | note = {Available online: 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.} | 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.} | ||
} | } | ||
| Line 127: | Line 132: | ||
author = {Danilo Gligoroski}, | author = {Danilo Gligoroski}, | ||
title = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains}, | title = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains}, | ||
| − | + | note = {Available online: http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf}, | |
| − | howpublished = {NIST mailing list}, | + | howpublished = {NIST hash function mailing list}, |
year = {2010}, | year = {2010}, | ||
} | } | ||
| Line 140: | Line 145: | ||
howpublished = {Cryptology ePrint Archive, Report 2010/043}, | howpublished = {Cryptology ePrint Archive, Report 2010/043}, | ||
year = {2010}, | year = {2010}, | ||
| − | + | note = {Available online: http://eprint.iacr.org/2010/043.pdf}, | |
abstract = {BLAKE is a hash function selected by NIST as one of | abstract = {BLAKE is a hash function selected by NIST as one of | ||
the 14 second round candidates for the SHA-3 Competition. In this | the 14 second round candidates for the SHA-3 Competition. In this | ||
| Line 163: | Line 168: | ||
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}, | ||
| − | + | howpublished = {Accepted for presentation at WEWoRC 2009}, | |
| − | + | note = {Available online: http://www.jguo.org/docs/blake-col.pdf}, | |
| − | |||
year = {2009} | year = {2009} | ||
} | } | ||
| Line 176: | Line 180: | ||
howpublished = {Cryptology ePrint Archive, Report 2009/238}, | howpublished = {Cryptology ePrint Archive, Report 2009/238}, | ||
year = {2009}, | year = {2009}, | ||
| − | note = {\url | + | note = {Available online: \url{http://eprint.iacr.org/2009/238.pdf}}, |
| − | |||
abstract = {BLAKE is a new hash family proposed for SHA-3. The | abstract = {BLAKE is a new hash family proposed for SHA-3. The | ||
core of compression function reuses the core function of ChaCha. A | core of compression function reuses the core function of ChaCha. A | ||
Revision as of 09:32, 22 April 2011
1 The algorithm
- Author(s): Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
- Website: http://131002.net/blake/
- NIST submission package:
- Round 3: Blake_FinalRnd.zip
- Round 1/2: BLAKE_Round2.zip (old versions: BLAKE.zip, BLAKEUpdate.zip)
Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan - SHA-3 proposal BLAKE
- ,2010
- http://131002.net/blake/blake.pdf
BibtexAuthor : 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
BibtexAuthor : 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
Janoš Vidali, Peter Nose, Enes Pašalic - Collisions for variants of the BLAKE hash function
- Information Processing Letters 110:585--590, July 2010
- BibtexAuthor : 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
Danilo Gligoroski - Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains
Jean-Philippe Aumasson, Jian Guo, Simon Knellwolf, Krystian Matusiewicz, Willi Meier - Differential and invertibility properties of BLAKE (full version)
Jian Guo, Krystian Matusiewicz - Round-Reduced Near-Collisions of BLAKE-32
Li Ji, Xu Liangyu - Attacks on Round-Reduced BLAKE
