BLAKE (hash function)

BLAKE is a cryptographic hash function in the development of which was attended by Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan.

There are two options for the hash function: BLAKE-256 and BLAKE-512.

Content

1 History
2 Cryptographic strength
3 Performance and implementation
4 Algorithm
- 4.1 Constants
- 4.2 Compression Functions
- 4.3 Initialization
- 4.4 Round function
- 4.5 Last step
- 4.6 Message Hashing
- 4.7 Differences from the quarterround ChaCha algorithm
5 BLAKE Hash
6 BLAKE2
- 6.1 Differences from BLAKE
- 6.2 BLAKE2 Hashes
7 Comments
8 Sources
9 Literature
10 Links

History

For the first time, BLAKE was presented at a cryptographic algorithms contest held by the US National Institute of Standards and Technology ( NIST hash function competition , SHA-3 (competition) ). BLAKE has become one of the five finalists of the competition ( English finalists ).

Cryptographic Strength

The BLAKE hash function is built from three previously learned components:

HAIFA iteration mode provides resistance to type II attacks
internal structure of local wide-pipe provides protection against collisions
the compression algorithm for BLAKE is a modified version of the highly parallelizable stream cipher ChaCha , whose security has been carefully analyzed ^[1]

Performance and implementation

Performance on two different processors:

CPU	Speed (Beats / Bytes)
CPU	BLAKE-256	BLAKE-512
Intel Core i5-2400M (Sandy Bridge)	7.49	5.64
AMD FX-8120 (Bulldozer)	11.83	6.88

Possibility of implementation on various microcontrollers:

Microcontroller	BLAKE-256		BLAKE-512
Microcontroller	RAM (bytes)	ROM (byte)	RAM (bytes)	ROM (byte)
Cortex-M3 based microcontroller (32-bit processor)	280	1320	516	1776
ATmega1284P microcontroller (8-bit processor)	267	3434	525	6350

Performance on PPVM ( English FPGA ):

On the Xilinx Virtex 5 FPGA , BLAKE-256 is implemented on 56 cells and can reach a throughput of more than 160 Mbit / s, and BLAKE-512 on 108 cells and at speeds of up to 270 Mbit / s.

Performance on ASIC :

At 180nm ASIC , the BLAKE-256 can be implemented at 13.5 kGE. At 90nm ASIC , BLAKE-256 is implemented at 38 kGE and can achieve a performance of 10 Gb / s, and BLAKE-512 at 79 kGE and at a speed of 15 Gb / s ^[2] .

Algorithm

As mentioned earlier, the BLAKE hash function is built from three previously learned components:

HAIFA iteration mode
internal structure of local wide-pipe
BLAKE's compression algorithm is a modified version of the highly parallelizable stream cipher ChaCha , whose security has been carefully analyzed. ^[one]

Consider the BLAKE-256 algorithm ^[3]

BLAKE-256 operates with 32-bit words and returns a 32-byte hash.

Constants

There are initial constants, the so-called INITIAL VALUES (IV):

  IV0 = 6A09E667 IV1 = BB67AE85
 IV2 = 3C6EF372 IV3 = A54FF53A
 IV4 = 510E527F IV5 = 9B05688C
 IV6 = 1F83D9AB IV7 = 5BE0CD19

16 constants (First digits of pi):

  c ₀ = 243F6A88 c ₁ = 85A308D3
 c ₂ = 13198A2E c ₃ = 03707344
 c ₄ = A4093822 c ₅ = 299F31D0
 c ₆ = 082EFA98 c ₇ = EC4E6C89
 c ₈ = 452821E6 c ₉ = 38D01377
 c ₁₀ = BE5466CF c ₁₁ = 34E90C6C
 c ₁₂ = C0AC29B7 c ₁₃ = C97C50DD
 c ₁₄ = 3F84D5B5 c ₁₅ = B5470917

permutations {0, ..., 15} (used in all BLAKE functions):

  σ ₀ = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
 σ ₁ = 14 10 4 8 9 15 13 6 1 12 0 2 11 7 5 3
 σ ₂ = 11 8 12 0 5 2 15 13 10 14 3 6 7 1 9 4
 σ ₃ = 7 9 3 1 13 12 11 14 2 6 5 10 4 0 15 8
 σ ₄ = 9 0 5 7 2 4 10 15 14 1 11 12 6 8 3 13
 σ ₅ = 2 12 6 10 0 11 8 3 4 13 7 5 15 14 1 9
 σ ₆ = 12 5 1 15 14 13 4 10 0 7 6 3 9 2 8 11
 σ ₇ = 13 11 7 14 12 1 3 9 5 0 15 4 8 6 2 10
 σ ₈ = 6 15 14 9 11 3 0 8 12 2 13 7 1 4 10 5
 σ ₉ = 10 2 8 4 7 6 1 5 15 11 9 14 3 12 13 0

Compression Functions

The BLAKE-256 algorithm compression function accepts:

Variable chains h = h ₀ , ..., h ₇ (8 words);
Message block m = m ₀ , ..., m ₁₅ ;
The value of the salt is s = s ₀ , ..., s ₃ ;
Counter value t = t ₀ , t ₁ .

Thus, 30 words are fed to the input (8 + 16 + 4 + 2 = 30, 30 * 4 = 120 bytes = 960 bits). The compression function returns only the new value of the chain variables: h '= h' ₀ , ..., h ' ₇ . In what follows, we denote h '= compress (h, m, s, t).

Initialization

16 variables, v ₀ , ..., v ₁₅ , describing the current state of v , are initialized with initial values depending on the input data and are presented in the form of a 4 × 4 matrix:

${\begin{pmatrix}v_{0}&v_{1}&v_{2}&v_{3}\\v_{4}&v_{5}&v_{6}&v_{7}\\v_{8}&v_{9}&v_{10}&v_{11}\\v_{12}&v_{13}&v_{14}&v_{15}\\\end{pmatrix}}$ ${\ displaystyle {\ begin {pmatrix} v_ {0} & v_ {1} & v_ {2} & v_ {3} \\ v_ {4} & v_ {5} & v_ {6} & v_ {7} \\ v_ {8} & v_ {9} & v_ {10} & v_ {11} \\ v_ {12} & v_ {13} & v_ {14} & v_ {15} \\\ end {pmatrix}}}$ ← ${\begin{pmatrix}h_{0}&h_{1}&h_{2}&h_{3}\\h_{4}&h_{5}&h_{6}&h_{7}\\s_{0}\oplus c_{0}&s_{1}\oplus c_{1}&s_{2}\oplus c_{2}&s_{3}\oplus c_{3}\\t_{0}\oplus c_{4}&t_{0}\oplus c_{5}&t_{1}\oplus c_{6}&t_{1}\oplus c_{7}\\\end{pmatrix}}$ ${\ displaystyle {\ begin {pmatrix} h_ {0} & h_ {1} & h_ {2} & h_ {3} \\ h_ {4} & h_ {5} & h_ {6} & h_ {7} \\ s_ {0} \ oplus c_ {0} & s_ {1} \ oplus c_ {1} & s_ {2} \ oplus c_ {2} & s_ {3} \ oplus c_ {3} \\ t_ {0} \ oplus c_ {4} & t_ {0 } \ oplus c_ {5} & t_ {1} \ oplus c_ {6} & t_ {1} \ oplus c_ {7} \\\ end {pmatrix}}}$

Round function

After state v is initialized, a series of 14 rounds starts. A round is a state operation $v$ ${\ displaystyle v}$ , which performs calculations divided into the following blocks:

  G ₀ (v ₀ , v ₄ , v ₈ , v ₁₂ ) G ₁ (v ₁ , v ₅ , v ₉ , v ₁₃ ) G ₂ (v ₂ , v ₆ , v ₁₀ , v ₁₄ ) G ₃ (v ₃ , v ₇ , v ₁₁ , v ₁₅ ) 
 G ₄ (v ₀ , v ₅ , v ₁₀ , v ₁₅ ) G ₅ (v ₁ , v ₆ , v ₁₁ , v ₁₂ ) G ₆ (v ₂ , v ₇ , v ₈ , v ₁₃ ) G ₇ (v ₃ , v ₄ , v ₉ , v ₁₄ )

on the rth round, the calculation block $G_{i}(a,b,c,d)$ ${\ displaystyle G_ {i} (a, b, c, d)}$ works as follows:

Graphic illustration of the operation of the computing unit Gi

  j ← σ _{r% 10} [2 × i]
 k ← σ _{r% 10} [2 × i + 1]
 a ← a + b + (m _j ⊕ c _k )  
 d ← (d ⊕ a) >>> 16
 c ← c + db ← (b ⊕ c) >>> 12
 a ← a + b + (m _k ⊕ c _j )  
 d ← (d ⊕ a) >>> 8
 c ← c + db ← (b ⊕ c) >>> 7

Column step and diagonal step of BLAKE-256 hash function algorythm

The first four blocks G ₀ , ..., G ₃ can be calculated in parallel, since each changes its own specific column of variables of the state matrix. We call the calculation procedure G ₀ , ..., G ₃ column step . In the same way, G ₄ , ..., G ₇ can be computed in parallel, but they in turn change each diagonal of their state matrix v . Therefore, we call the calculation procedure G ₄ , ..., G ₇ diagonal step . The possibility of parallel computation of G _i is represented graphically.

In rounds whose numbers r are greater than 9, the permutation σ _{r% 10 is used} , for example, in the 13th round, σ _{3 is used} .

Last Step

After all rounds, the new value of the variables of the chain h ' ₀ , ..., h' _{7 is} calculated from the variables $v_{0},...,v_{15}$ ${\ displaystyle v_ {0}, ..., v_ {15}}$ state matrices, input variables $h$ ${\ displaystyle h}$ and from salt $s$ ${\ displaystyle s}$ :

  h ' ₀ ← h ₀ ⊕ s ₀ ⊕ v ₈
 h ' ₁ ← h ₁ ⊕ s ₁ ⊕ v ₉
 h ' ₂ ← h ₂ ⊕ s ₂ ⊕ v ₁₀
 h ' ₃ ← h ₃ ⊕ s ₃ ⊕ v ₁₁
 h ' ₄ ← h ₄ ⊕ s ₄ ⊕ v ₁₂
 h ' ₅ ← h ₅ ⊕ s ₅ ⊕ v ₁₃
 h ' ₆ ← h ₆ ⊕ s ₆ ⊕ v ₁₄
 h ' ₇ ← h ₇ ⊕ s ₇ ⊕ v ₁₅

Message Hashing

Let us describe the process of hashing a message m of length l <2 ^ 64 bits. First, the message is supplemented with a padding function for 512 bits (64 bytes), then, block by block, it is processed by the compression function compression function .

In the padding function, the message is first supplemented with bits, so that its length becomes modulo 512 equal to 447: first 1 is added, then the required number of zeros. After that, another 1 and 64-bit representation of the message length l from the most significant bit to the least is added. Thus, the message length becomes a multiple of 512 ^[Comm. ^1] . Padding ensures that the message length becomes a multiple of 512 bits.

To calculate the message hash, the result of the padding function is divided into blocks of 16 words m ₀ , ..., m _N-1 . Let L _i be the number of bits of the initial message in blocks m ₀ , ..., m _i , that is, excluding those bits that were added in the padding procedure. For example, if a message has a length of 600 bits, then after the padding procedure it will have a length of 1024 bits and will be divided into two blocks: m ₀ and m ₁ . Moreover, L ₀ = 512, L ₁ = 600. In some cases, the last block does not contain the bit of the original message. For example, if there are 1020 bits in the original message, then as a result of the padding procedure it will have a length of 1536 bits and in m _{0 there} will be 512 bits of the original message, in m ₁ - 508, and in m ₂ - 0. Set L ₀ = 512, L ₁ = 1020, and L ₂ = 0. That is, the rule is as follows: if there is no bit of the original message in the last block, then set the counter L _N-1 to 0. This ensures that if i ≠ j , then L _i ≠ L _j . The salt value is user-defined or set to 0 if it does not need to be used ( s ₀ = s ₁ = s ₂ = s ₃ = 0 ). The message hash is thus computed:

  h ⁰ ← IV
 for i = 0, ..., N-1
    h ^{i + 1} ← compress (h ⁱ , m ⁱ , s, l ⁱ )
 return h ^N.

The hashing process is presented graphically in a flowchart:

The algorithm of the 64-bit version of the function is identical: the shift values are 32, 25, 16 and 11, respectively, the number of rounds is increased to 16.

Differences from the quarterround ChaCha algorithm

Adding constants to the message.
The changed direction of the shift.

BLAKE hashes

  BLAKE-512 ("")
  = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B
    628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8

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

BLAKE2

BLAKE2 (BLAKE2 Website ) is an improved version of BLAKE, one of the five finalists of the SHA-3 hash function contest (mainly improved performance), introduced on December 21, 2012. Developers: Jean-Philippe Aumasson , Samuel Neves , Zooko Wilcox-O'Hearn , and Christian Winnerlein . It was created as an alternative to MD5 and SHA-1 , which were widely used in the past, in which vulnerabilities were found.

Differences from BLAKE

In BLAKE2, unlike BLAKE, there is no addition of constants in the round function. Shear constants are also changed, adding is simplified, a block of parameters is added, which is added to the initializing vectors. In addition, the number of rounds has been reduced from 16 to 12 for BLAKE2b (analogue of BLAKE-512) and from 14 to 10 for BLAKE2s (analogue of BLAKE-256). As a result, the number of beats per bit was reduced from 7.49 for BLAKE-256 and 5.64 for BLAKE-512 to 5.34 and 3.32 for Blake2s and Blake2b, respectively.

BLAKE2 hashes

  BLAKE2b-512 ("")
  = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419
    D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE

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



 BLAKE2s-256 ("") 

 = 69217A3079908094E11121D042354A7C1F55B6482CA1A51E1B250DFD1ED0EEF9 


 BLAKE2s-256 ("The quick brown fox jumps over the lazy dog") 

 = 606BEEEC743CCBEFF6CBCDF5D5302AA855C256C29B88C8ED331EA1A6BF3C8812 


 BLAKE2s-128 ("") 

 = 64550D6FFE2C0A01A14ABA1EADE0200C 
      

        
        
        
      

    
 BLAKE2s-128 ("The quick brown fox jumps over the lazy dog") 

 = 96FD07258925748A0D2FB1C8A1167A73

Comments

↑ For example, a message with a length of 447 bits will be added 1, then 511 zeros (the length will be equal to 447 + 512), then another 1 and 64-bit representation of the number l = 447 - 00 ... 0110111111. Thus, the length will be equal to 447 + 512 + 1 + 64 = 1024, which is a multiple of 512

Sources

↑ ¹ ² BLAKE Documentation on the Official Website , p. 3 Introduction.
↑ BLAKE Official Website
↑ BLAKE Documentation on the Official Website , p. 8 Specification.

Literature

Eli Biham and Orr Dunkelman. A framework for iterative hash functions - HAIFA . - ePrint, 2007 .-- 207 p.

Links

[4] For example, a message with a length of 447 bits will be added 1, then 511 zeros (the length will be equal to 447 + 512), then another 1 and 64-bit representation of the number l = 447 - 00 ... 0110111111. Thus, the length will be equal to 447 + 512 + 1 + 64 = 1024, which is a multiple of 512

[Documentation_Introduction-1] ¹ ² BLAKE Documentation on the Official Website , p. 3 Introduction.

[Site_BLAKE-2] BLAKE Official Website

[Documentation_Specification-3] BLAKE Documentation on the Official Website , p. 8 Specification.