BLAKE (hash function)

BLAKE
General
Designers	Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
Successors	BLAKE2
Certification	SHA-3 finalist
Detail
Digest sizes	224, 256, 384 or 512 bits
Structure	HAIFA construction
Rounds	14 or 16
Speed	8.4 cpb on Core 2 for BLAKE-256; 7.8 cpb for BLAKE-512

BLAKE and BLAKE2 are cryptographic hash functions based on Dan Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with some round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and those output digest size are 256 bits and 224 bits, while BLAKE-512 and BLAKE-384 use 64-bit words and those output digest size are 512 bits and 384 bits.^[1]

History

BLAKE was submitted to the NIST hash function competition by Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and Raphael C.-W. Phan. In 2008, there were 51 entries. BLAKE made it to the final round consisting of five candidate but lost to Keccak in 2012, which was selected for the SHA-3 algorithm.

Algorithm

Like SHA-2, BLAKE comes in two variants: one that uses 32-bit words, used for computing hashes up to 256 bits long, and one that uses 64-bit words, used for computing hashes up to 512 bits long. The core block transformation combines 16 words of input with 16 working variables, but only 8 words (256 or 512 bits) are preserved between blocks.

It uses a table of 16 constant words (the leading 512 or 1024 bits of the fractional part of π), and a table of 10 16-element permutations:

σ[0] =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
σ[1] = 14 10  4  8  9 15 13  6  1 12  0  2 11  7  5  3
σ[2] = 11  8 12  0  5  2 15 13 10 14  3  6  7  1  9  4
σ[3] =  7  9  3  1 13 12 11 14  2  6  5 10  4  0 15  8
σ[4] =  9  0  5  7  2  4 10 15 14  1 11 12  6  8  3 13
σ[5] =  2 12  6 10  0 11  8  3  4 13  7  5 15 14  1  9
σ[6] = 12  5  1 15 14 13  4 10  0  7  6  3  9  2  8 11
σ[7] = 13 11  7 14 12  1  3  9  5  0 15  4  8  6  2 10
σ[8] =  6 15 14  9 11  3  0  8 12  2 13  7  1  4 10  5
σ[9] = 10  2  8  4  7  6  1  5 15 11  9 14  3 12 13  0

The core operation, equivalent to ChaCha's quarter round, operates on a 4-word column or diagonal combines with 2 words of message m[] and two constant words c[]. It is performed 8 times per full round:

j ← σ[r%10][2×i]            // Index computations
k ← σ[r%10][2×i+1]
a ← a + b + (m[j] ⊕ c[k])   // Step 1 (with input)
d ← (d ⊕ a) >>> 16
c ← c + d                   // Step 2 (no input)
b ← (b ⊕ c) >>> 12
a ← a + b + (m[k] ⊕ c[j])   // Step 3 (with input)
d ← (d ⊕ a) >>> 8
c ← c + d                   // Step 4 (no input)
b ← (b ⊕ c) >>> 7

In the above, r is the round number (0–13), and i varies from 0 to 7.

The differences from the ChaCha quarter-round function are:

The addition of the message words has been added.
The rotation directions have been reversed.

The 64-bit version (which does not exist in ChaCha) is identical, but the rotation amounts are 32, 25, 16 and 11, respectively, and the number of rounds is increased to 16.

Blake2b Algorithm

Pseudocode for the Blake2b algorithm. The Blake2b algorithm uses 8-byte (UInt64) words, and 128-byte chunks.

Algorithm Blake2b
   Input:
      M                               Message to be hashed
      cbMessageLen: Number, (0..2¹²⁸)  Length of the message in bytes
      Key                             Optional 0..64 byte key
      cbKeyLen: Number, (0..64)       Length of optional key in bytes
      cbHashLen: Number, (1..64)      Desired hash length in bytes
   Output:
      Hash                            Hash of cbHashLen bytes

   Initialize State vector h with IV
   h₀ ← 0xcbbb9d5dc1059ed8
   h₁ ← 0x629a292a367cd507
   h₂ ← 0x9159015a3070dd17
   h₃ ← 0x152fecd8f70e5939
   h₄ ← 0x67332667ffc00b31
   h₅ ← 0x8eb44a8768581511
   h₆ ← 0xdb0c2e0d64f98fa7
   h₇ ← 0x47b5481dbefa4fa4

   Mix key size (cbKeyLen) and desired hash length (cbHashLen) into h₀
   h₀ ← h₀ xor 0x0101kknn
         where kk is Key Length (in bytes)
               nn is Desired Hash Length (in bytes)

   Each time we Compress we record how many bytes have been compressed
   cBytesCompressed ← 0
   cBytesRemaining  ← cbMessageLen

   If there was a key supplied (i.e. cbKeyLen > 0) 
   then pad with zeros to make it 128-bytes (i.e. 16 words) 
   and prepend it to the message M
   if (cbKeyLen > 0) then
      M ← Pad(Key, 128) || M
      cBytesRemaining ← cBytesRemaining + 128
   end if

   Compress whole 128-byte chunks of the message, except the last chunk
   while (cbBytesRemaining > 128) do
      chunk ← get next 128 bytes of message M
      cBytesCompressed ← cBytesCompressed + 128  increase count of bytes that have been compressed
      cBytesRemaining  ← cBytesRemaining  - 128  decrease count of bytes in M remaining to be processed

      Compress(h, chunk, cBytesCompressed, false)  false ⇒ this is not the last chunk
   end while

   Compress the final bytes from M
   chunk ← get next 128 bytes of message M  We will get cBytesRemaining bytes (i.e. 0..128 bytes)
   cBytesCompressed ← cBytesCompressed+cBytesRemaining  The actual number of bytes leftover in M
   chunk ← Pad(chunk, 128)  If M was empty, then we will still compress a final chunk of zeros

   Compress(h, chunk, cBytesCompressed, true)  true ⇒ this is the last chunk

   Result ← first cbHashLen bytes of little endian state vector h
End Algorithm Blake2b

Compress

The Compress function takes a full 128-byte chunk of the input message and mixes it into the ongoing state array:

Function Compress
   Input:
      h                      Persistent state vector
      chunk                  128-byte (16 word) chunk of message to compress
      t: Number, 0..2¹²⁸     Count of bytes that have been fed into the Compression
      IsLastBlock: Boolean   Indicates if this is the final round of compression
   Output:
      h                      Updated persistent state vector

   Setup local work vector V
   V_0..7 ← h_0..7
   V_8..15 ← IV_0..7

   Mix offset 128-bit counter t into V₁₂:V₁₃
   v₁₂ ← V₁₂ xor Lo(t)    Lo 64-bits of UInt128 t
   V₁₃ ← V₁₃ xor Hi(t)    Hi 64-bits of UInt128 t
  
   If this is the last block then invert all the bits in V₁₄
   if IsLastBlock then
      V₁₄ ← V₁₄ xor 0xFFFFFFFFFFFFFFFF

   Treat each 128-byte message chunk as sixteen 8-byte (64-bit) words m
   m_0..15 ← chunk

   Twelve rounds of cryptographic message mixing
   for i from 0 to 11 do
      Select message mixing schedule for this round.
      Blake2b uses 12 rounds, while SIGMA has only 10 entries.
      S_0..15 ← SIGMA[i mod 10]   Rounds 10 and 11 use SIGMA[0] and SIGMA[1] respectively

      Mix(V₀, V₄, V₈,  V₁₂, m[S₀], m[S₁])
      Mix(V₁, V₅, V₉,  V₁₃, m[S₂], m[S₃])
      Mix(V₂, V₆, V₁₀, V₁₄, m[S₄], m[S₅])
      Mix(V₃, V₇, V₁₁, V₁₅, m[S₆], m[S₇])

      Mix(V₀, V₅, V₁₀, V₁₅, m[S₈],  m[S₉])
      Mix(V₁, V₆, V₁₁, V₁₂, m[S₁₀], m[S₁₁])
      Mix(V₂, V₇, V₈,  V₁₃, m[S₁₂], m[S₁₃])
      Mix(V₃, V₄, V₉,  V₁₄, m[S₁₄], m[S₁₅])
   end for

   Mix the upper and lower halves of V into ongoing state vector h
   h_0..7 ← h_0..7 xor V_0..7
   h_0..7 ← h_0..7 xor V_8..15

   Result ← h
End Function Compress

Mix

The Mix function is called by the Compress function, and mixes two 8-byte words from the message into the hash state. In most implementations this function would be written inline, or as an inlined function.

Function Mix
   Inputs:
        V_a, V_b, V_c, V_d       four 8-byte word entries from the work vector V
        x, y                two 8-byte word entries from padded message m
   Output:
        V_a, V_b, V_c, V_d       the modified versions of V_a, V_b, V_c, V_d

   V_a ← V_a + V_b + x          with input
   V_d ← (V_d xor V_a) rotateright 32

   V_c ← V_c + V_d              no input
   V_b ← (V_b xor V_c) rotateright 24

   V_a ← V_a + V_b + y          with input
   V_d ← (V_d xor V_a) rotateright 16

   V_c ← V_c + V_d              no input
   V_b ← (V_b xor V_c) rotateright 63

   Result ← V_a, V_b, V_c, V_d
End Algorithm Mix

Tweaks

Throughout the NIST hash function competition, entrants are permitted to "tweak" their algorithms to address issues that are discovered. Changes that have been made to BLAKE are:

The number of rounds was increased from 10/14 to 14/16. This is to be more conservative about security while still being fast.

BLAKE hashes

BLAKE-512("")
 = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B
   628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8

BLAKE-512("The quick brown fox jumps over the lazy dog")
 = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD
   2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451

BLAKE2

BLAKE2
General
Designers	Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, Christian Winnerlein
Derived from	BLAKE
Detail
Digest sizes	arbitrary
Rounds	10 or 12

An improved version of BLAKE called BLAKE2 was announced in December 21, 2012. It was created by Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, and Christian Winnerlein with the goal to replace widely used, but broken MD5 and SHA-1 algorithms.^[2] The reference implementation code was released under CC0.^[3]

BLAKE2 removes addition of constants to message words from BLAKE round function, changes two rotation constants, simplifies padding, adds parameter block that is XOR'ed with initialization vectors, and reduces the number of rounds from 16 to 12 for BLAKE2b (successor of BLAKE-512), and from 14 to 10 for BLAKE2s (successor of BLAKE-256).

BLAKE2 supports keying, salting, personalization, and hash tree modes, and can output digests from 1 up to 64 bytes for BLAKE2b or up to 32 bytes for BLAKE2s. There are also parallel versions designed for increased performance on multi-core processors; BLAKE2bp (4-way parallel) and BLAKE2sp (8-way parallel).

BLAKE2 hashes

BLAKE2b-512("")
 = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419
   D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE

BLAKE2b-512("The quick brown fox jumps over the lazy dog")
 = A8ADD4BDDDFD93E4877D2746E62817B116364A1FA7BC148D95090BC7333B3673
   F82401CF7AA2E4CB1ECD90296E3F14CB5413F8ED77BE73045B13914CDCD6A918

BLAKE2 uses

Argon2, the winner of the Password Hashing Competition uses BLAKE2.

Noise (crypto protocol), which is now used in WhatsApp includes BLAKE2 as an option.

RAR file archive format version 5 supports an optional 256-bit BLAKE2sp file checksum instead of the default 32-bit CRC32. It was implemented in WinRAR v5+.^[4]

NeoScrypt, a password based key derivation function, employs BLAKE2s within its FastKDF component. ^[5]

librsync uses BLAKE2.

Chef's Habitat deployment system uses BLAKE2 for package signing.

Several crypto libraries, including OpenSSL, Crypto++, libsodium, Botan, and Bouncy Castle include BLAKE2.

References

↑ Saarinen, M-J; Aumasson, J-P (November 2015). The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC). IETF. RFC 7693. https://tools.ietf.org/html/rfc7693. Retrieved 4 December 2015.
↑ http://lists.randombit.net/pipermail/cryptography/2012-December/003562.html
↑ BLAKE2 — fast secure hashing
↑ WinRAR Version Change List; RARsoft.
↑ Doering, John NeoScrypt, a Strong Memory Intensive Key Derivation Function, 2014, p. 3

External links

The BLAKE web site
The BLAKE2 web site
VHDL source code developed by the Cryptographic Engineering Research Group (CERG) at George Mason University

Cryptographic hash functions & message authentication codes

List Comparison Known attacks

Common functions	MD5 SHA-1 SHA-2 SHA-3 BLAKE2

SHA-3 finalists	BLAKE Grøstl JH Skein Keccak (winner)

Other functions	ECOH FSB GOST HAS-160 HAVAL Kupyna LM hash MD2 MD4 MD5 MD6 MDC-2 N-Hash RIPEMD RadioGatún SWIFFT SipHash Snefru Streebog Tiger VSH WHIRLPOOL

Key derivation functions	bcrypt crypt PBKDF2 scrypt Argon2

MAC functions	DAA CBC-MAC HMAC OMAC/CMAC PMAC VMAC UMAC Poly1305

Authenticated encryption modes	CCM CWC EAX GCM IAPM OCB

Attacks	Collision attack Preimage attack Birthday attack Brute force attack Rainbow table Side-channel attack Length extension attack

Design	Avalanche effect Hash collision Merkle–Damgård construction

Standardization	CRYPTREC NESSIE NIST hash function competition

Utilization	Hash-based cryptography Key stretching Merkle tree Message authentication Proof of work Salt

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Category Portal WikiProject

This article is issued from Wikipedia - version of the 10/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.