SHA-3 proposal BLAKE

BLAKE is our submission to the NIST Hash Competition. It is one of the simplest designs in the competition, and it entirely relies on previously analyzed components: the HAIFA structure and the ChaCha core function. BLAKE is one of the 14 submissions selected for the second round of the competition.

BLAKE is a family of four functions: BLAKE-28 and BLAKE-32 work on 32-bit words and produce 28- and 32-byte digests, respectively. BLAKE-48 and BLAKE-64 work on 64-bit words and produce 48- and 64-byte digests.

On an Intel Core 2 Duo, BLAKE-32 can hash at 6.97 cycles/byte, and BLAKE-64 can hash at 9.61 cycles/byte (see matsui on eBASH). On an Intel Core i7 920, BLAKE-32 can hash at 7.67 cycles/byte, and BLAKE-64 can hash at 9.52 cycles/byte (see odin on eBASH).

In hardware, the BLAKE-32 compression fits in about 10 kGE and can reach a throughput of 5.3 Gbps (respectively, 20 kGE gates and 5.9 Gbps for BLAKE-64). We implemented a compact architecture of the full BLAKE-32 in a UMC 180 nm 1P6M technology ASIC using 13.5 kGE, and achieving a througput of 125 Mbps (see a picture of the hardware layout).

BLAKE was designed by

Jean-Philippe Aumasson (Nagravision SA, Cheseaux, Switzerland)
Luca Henzen (ETHZ, Zürich, Switzerland)
Willi Meier (FHNW, Windisch, Switzerland)
Raphael C.-W. Phan (Loughborough University, UK)

Contact: jeanphilippe.aumasson@gmail.com

Downloads

The following files are available for download:

Submission document, including specification, implementation report, preliminary analysis
Slides of the presentation of BLAKE at the First SHA-3 Conference
Toy versions of BLAKE for cryptanalysis: BLOKE, FLAKE, BLAZE, and BRAKE
C implementations:

blake_ref.c, blake_ref.h: reference code for NIST's API
blake_opt.c, blake_opt.h: optimized code for NIST's API
blake28_light.c: light portable implementation of BLAKE-28
blake32_light.c: light portable implementation of BLAKE-32
blake48_light.c: light portable implementation of BLAKE-48
blake64_light.c: light portable implementation of BLAKE-64
blake-ref-0.3.tar.gz: eBASH "ref" submission
blake-sse2-0.5.tar.gz: eBASH "sse2" submission written with Peter Schwabe

Hardware implementations:
- blake_vhdl_v1.tar.gz: VHDL hardware implementation of BLAKE-32 and BLAKE-64, with four different architectures
- blakechip.jpg: picture of the chip containing our 13.5 kGE implementation of the full BLAKE-32

Third-party performance analysis

2010 May 11: Thomas Pornin. sphlib 2.0.
Main result(s): optimized portable C implementation of BLAKE-32 and BLAKE-64 in the sphlib library (see also the benchmark report in sphlib-2.0.zip)
2010 May 10: Christopher Drost. sha3-js.
Main result(s): implementation of BLAKE-32 in Javascript (see also the online demo)
2010 Apr 1: Jean-Luc Beuchat, Eiji Okamoto, Teppei Yamazaki. Compact Implementations of BLAKE-32 and BLAKE-64 on FPGA. IACR ePrint archive, report 2010/173.
Main result(s): compact implementations of BLAKE-32 and BLAKE-64 on Spartan 3, Virtex 4, Virtex 5, and Cyclone III FPGA devices; for example on Virtex 5, BLAKE-32 (resp. BLAKE-64) is implemented with 56 (resp 108) slices, and achieves a throughput of 225 (resp. 314) Mbps
2010 Jan 10: Kazuyuki Kobayashi, Jun Ikegami, Shin’ichiro Matsuo, Kazuo Sakiyama, Kazuo Ohta. Evaluation of Hardware Performance for the SHA-3 Candidates Using SASEBO-GII. IACR ePrint archive, report 2010/010.
Main result(s): implementation of BLAKE-32 on the SASEBO-GII FPGA platform with 1660 slices, 1393 slice registers, and 5154 slice LUTs, and achieving a throughput of 487 Mbps
2009 Oct 21: Stefan Tillich, Martin Feldhofer, Mario Kirschbaum, Thomas Plos, Jörn-Marc Schmidt, Alexander Szekely. High-Speed Hardware Implementations of BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. IACR ePrint archive, report 2009/510.
Main result(s): implementation of BLAKE-32 on 0.18 µm technology in 45.6 kGE, and achieving a throughput of 4 Gbps
2009 Oct 7: Samuel Neves. ChaCha implementation.
Main result(s): implementations optimized for Intel Core 2 and i7 processors using SSSE3 extensions; on a Core 2 E8400, measured speed-up from 10.34 to 9.05 cycles/byte for BLAKE-32, and from 13.65 to 11.80 for BLAKE-64
2009 Jul 28: Ashkan Hosseinzadeh Namin, M. Anwar Hasan. Hardware Implementation of the Compression Function for Selected SHA-3 Candidates.
Main result(s): synthesis of our VHDL code of BLAKE-32 into STM 90 nm technology maximizing frequency (47 MHz); implementation on Altera Stratix FPGA with 5435 ALUTs, and achieving a throughput of 2.2 Gbps
2009 Jul 14: Stefan Tillich, Martin Feldhofer, Wolfgang Issovits, Thomas Kern, Hermann Kureck, Michael Mühlberghuber, Georg Neubauer, Andreas Reiter, Armin Köfler, Mathias Mayrhofer. Compact Hardware Implementations of the SHA-3 Candidates ARIRANG, BLAKE, Grøstl, and Skein. IACR ePrint archive, report 2009/349.
Main result(s): Verilog implementation of BLAKE-32 on 0.35 µm technology in 25 kGE, and achieving a throughput of 15.4 Mbps
2009 May 29: Kota Ideguchi, Toru Owada, Hirotaka Yoshida. A study on RAM requirements of various SHA-3 candidates on low-cost 8-bit CPUs. Official comment on the NIST Hash Competition
Main result(s): estimates RAM requirements of BLAKE-32 on "low-bit 8-bit CPUs" to 96 bytes
2009 May 25: Daniel Otte. AVR-Crypto-Lib/en.
Main result(s): reports on C implementations of BLAKE on AVR microcontroller, including speed measurements of 109.41 cycles/byte for BLAKE-28 and -32, and 234.27 cycles/byte for BLAKE-48 and -64

Third-party security analysis

2010 Jul 1: Janoš Vidali, Peter Nose, Enes Pašalic. Collisions for variants of the BLAKE hash function . Information Processing Letters, volume 110, issues 14-15
Main result(s): efficient collision attacks for the toy version BLOKE, and for the compression function of the toy version BRAKE
2010 Jun 18: Bozhan Su, Wenling Wu, Shuang Wu, Le Dong. Near collisions on the reduced-round compression functions of Skein and BLAKE. IACR ePrint archive, report 2010/355
Main result(s): near-collision attacks on resp. 152, 396, and 306 bits for the compression function of BLAKE-32, -64, -64 reduced to 4, 4, 5 middle rounds (rounds 7 to 10, and rounds 6 to 10), with complexity 2²¹, 2¹⁶, and 2²¹⁶
2010 Jan 29: Jean-Philippe Aumasson, Jian Guo, Simon Knellwolf, Krystian Matusiewicz, Willi Meier. Differential and invertibility properties of BLAKE. FSE 2010. IACR ePrint archive, report 2010/043.
Main result(s): proof that one round is a permutation of the message, for a fixed state; improved preimage attack on 1.5 rounds; impossible differentials for the permutation with 5 (resp. 6) rounds for BLAKE-32 (resp. BLAKE-64)
2009 Dec 7: Lei Wang, Kazuo Ohta, Kazuo Sakiyama. Free-start preimages of step-reduced Blake compression function. Rump session of ASIACRYPT 2009.
Main result(s): preimage attacks for the permutation of BLAKE-32 reduced to 4.5 rounds and followed by the finalization, with complexity 2²⁵² and memory 2⁸
2009 Jun 23: Jian Guo, Krystian Matusiewicz. Round-reduced near-collisions of BLAKE-32. WEWoRC 2009.
Main result(s): near-collision attack on 232 bits for the compression of BLAKE-32 reduced to 4 middle rounds (rounds 3 to 6), with complexity 2⁵⁶; uses differences in the chaining value, the salt, the counter, and the message
2009 May 26: Li Ji, Xu Liangyu. Attacks on round-reduced BLAKE. IACR ePrint archive, report 2009/238
Main result(s): collision and preimage attacks for BLAKE with compression function reduced to 2.5 rounds. Respectively for BLAKE-28, -32, -48, and -64, collision attacks have complexities 2⁹⁶, 2¹¹², 2¹⁶⁰, and 2²²⁴; preimage attacks have complexities 2²⁰⁹, 2²⁴¹, 2³⁵⁵, and 2⁴⁸¹

Index