Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

BLAKE (hash function)

From Wikipedia, the free encyclopedia
Cryptographic hash function
BLAKE
General
DesignersJean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
Derived fromLAKE[1]
SuccessorsBLAKE2
CertificationSHA-3 finalist
Detail
Digest sizes224, 256, 384 or 512 bits
StructureHAIFA construction
Rounds14 or 16
Speed8.4cpb onCore 2 for BLAKE-256; 7.8 cpb for BLAKE-512

BLAKE is acryptographic hash function based onDaniel J. Bernstein'sChaChastream cipher, but a permuted copy of the input block,XORed with round constants, is added before each ChaCha round. LikeSHA-2, there are two variants differing in theword 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 andBLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, whileBLAKE-512 andBLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.

TheBLAKE2 hash function, based on BLAKE, was announced in 2012. TheBLAKE3 hash function, based on BLAKE2, was announced in 2020.

History

[edit]

BLAKE was submitted to theNIST 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 candidates but lost toKeccak in 2012, which was selected for theSHA-3 algorithm.

Algorithm

[edit]

LikeSHA-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 diagonala b c d, which is combined with 2 words of messagem[] and two constant wordsn[]. It is performed 8 times per full round:

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

In the above,r is the round number (0–13), andi 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.

"BLAKE reuses the permutation of the ChaCha stream cipher with rotations done in the opposite directions. Some have suspected an advanced optimization, but in fact it originates from a typo in the original BLAKE specifications", Jean-Philippe Aumasson explains in his "Crypto Dictionary".[2]

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.

Tweaks

[edit]

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.

Example digests

[edit]

Hash values of an empty string:

BLAKE-224("") =7dc5313b1c04512a174bd6503b89607aecbee0903d40a8a569c94eedBLAKE-256("") =716f6e863f744b9ac22c97ec7b76ea5f5908bc5b2f67c61510bfc4751384ea7aBLAKE-384("") =c6cbd89c926ab525c242e6621f2f5fa73aa4afe3d9e24aed727faaadd6af38b620bdb623dd2b4788b1c8086984af8706BLAKE-512("") =a8cfbbd73726062df0c6864dda65defe58ef0cc52a5625090fa17601e1eecd1b628e94f396ae402a00acc9eab77b4d4c2e852aaaa25a636d80af3fc7913ef5b8

Changing a single bit causes each bit in the output to change with 50% probability, demonstrating anavalanche effect:

BLAKE-512("The quick brown fox jumps over the lazy dog") =1f7e26f63b6ad25a0896fd978fd050a1766391d2fd0471a77afb975e5034b7ad2d9ccf8dfb47abbbe656e1b82fbc634ba42ce186e8dc5e1ce09a885d41f43451BLAKE-512("The quick brown fox jumps over the lazy dof") =a701c2a1f9baabd8b1db6b75aee096900276f0b86dc15d247ecc03937b370324a16a4ffc0c3a85cd63229cfa15c15f4ba6d46ae2e849ed6335e9ff43b764198a

(In this example 266 matching bits out of 512 is about 52% due to the random nature of the avalanche.)

BLAKE2

[edit]
BLAKE2
General
DesignersJean-Philippe Aumasson, Samuel Neves,Zooko Wilcox-O'Hearn, Christian Winnerlein
Derived fromBLAKE
Detail
Digest sizesup to 64 bytes (BLAKE2b); up to 32 bytes (BLAKE2s); arbitrary (BLAKE2X)
Rounds10 or 12
Speed3.5cpb onCore i5 (Ivy Bridge) for BLAKE2b[3]

BLAKE2 is a cryptographic hash function based on BLAKE, created by Jean-Philippe Aumasson, Samuel Neves,Zooko Wilcox-O'Hearn, and Christian Winnerlein. The design goal was to replace the widely used, but broken,MD5 andSHA-1 algorithms in applications requiring high performance in software. BLAKE2 was announced on December 21, 2012.[4] Areference implementation is available underCC0, theOpenSSL License, and theApache License 2.0.[5][6]

BLAKE2b is faster than MD5, SHA-1, SHA-2, and SHA-3, on 64-bit x86-64 and ARM architectures.[5] Its creators state that BLAKE2 provides better security than SHA-2 and similar to that of SHA-3: immunity tolength extension, indifferentiability from a random oracle, etc.[7]

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 forBLAKE2b (successor of BLAKE-512), and from 14 to 10 forBLAKE2s (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 onmulti-core processors;BLAKE2bp (4-way parallel) andBLAKE2sp (8-way parallel).

BLAKE2X is a family ofextendable-output functions (XOFs). Whereas BLAKE2 is limited to 64-byte digests, BLAKE2X allows for digests of up to 256 GiB. BLAKE2X is itself not an instance of a hash function, and must be based on an actual BLAKE2 instance. An example of a BLAKE2X instance could beBLAKE2Xb16MiB, which would be a BLAKE2X version based on BLAKE2b producing 16,777,216-byte digests (or exactly 16MiB, hence the name of such an instance).[8]

BLAKE2b and BLAKE2s are specified in RFC 7693. Optional features using the parameter block (salting, personalized hashes, tree hashing, et cetera), are not specified, and thus neither is support for BLAKE2bp, BLAKE2sp, or BLAKE2X.[9]

Initialization vector

[edit]

BLAKE2b uses an initialization vector that is the same as the IV used by SHA-512. These values aretransparently obtained by taking the first 64 bits of the fractional parts of the positive square roots of the first eight prime numbers.

IV0 = 0x6a09e667f3bcc908// Frac(sqrt(2))IV1 = 0xbb67ae8584caa73b// Frac(sqrt(3))IV2 = 0x3c6ef372fe94f82b// Frac(sqrt(5))IV3 = 0xa54ff53a5f1d36f1// Frac(sqrt(7))IV4 = 0x510e527fade682d1// Frac(sqrt(11))IV5 = 0x9b05688c2b3e6c1f// Frac(sqrt(13))IV6 = 0x1f83d9abfb41bd6b// Frac(sqrt(17))IV7 = 0x5be0cd19137e2179// Frac(sqrt(19))

BLAKE2b algorithm

[edit]

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

Algorithm BLAKE2bInput:      MMessage to be hashed      cbMessageLen: Number, (0..2128)Length of the message in bytes      KeyOptional 0..64 byte key      cbKeyLen: Number, (0..64)Length of optional key in bytes      cbHashLen: Number, (1..64)Desired hash length in bytesOutput:      HashHash of cbHashLen bytesInitialize State vectorh withIV   h0..7 ← IV0..7Mix key size (cbKeyLen) and desired hash length (cbHashLen) into h0   h0 ← h0 xor 0x0101kknnwherekk is Key Length (in bytes)nnis Desired Hash Length (in bytes)Each time we Compress we record how many bytes have been compressed   cBytesCompressed ← 0   cBytesRemaining  ← cbMessageLenIf there was a key supplied (i.e. cbKeyLen > 0)then pad with trailing zeros to make it 128-bytes (i.e. 16 words)and prepend it to the messageMif (cbKeyLen > 0)then      M ← Pad(Key, 128) || M      cBytesRemaining ← cBytesRemaining + 128end ifCompress whole 128-byte chunks of the message, except the last chunkwhile (cBytesRemaining > 128)do      chunk ← get next 128 bytes of messageM      cBytesCompressed ← cBytesCompressed + 128increase count of bytes that have been compressed      cBytesRemaining  ← cBytesRemaining  - 128decrease count of bytes inM remaining to be processed      h ← Compress(h, chunk, cBytesCompressed, false)false ⇒ this is not the last chunkend whileCompress the final bytes fromM   chunk ← get next 128 bytes of messageMWe will get cBytesRemaining bytes (i.e. 0..128 bytes)   cBytesCompressed ← cBytesCompressed+cBytesRemainingThe actual number of bytes leftover inM   chunk ← Pad(chunk, 128)IfM was empty, then we will still compress a final chunk of zeros   h ← Compress(h, chunk, cBytesCompressed, true)true ⇒ this is the last chunkResult ← first cbHashLen bytes of little endian state vector hEnd Algorithm BLAKE2b

Compress

[edit]

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

Function CompressInput:      hPersistent state vector      chunk128-byte (16 double word) chunk of message to compress      t: Number, 0..2128Count of bytes that have been fed into the Compression      IsLastBlock: BooleanIndicates if this is the final round of compressionOutput:      hUpdated persistent state vectorSetup local work vector V   V0..7 ← h0..7First eight items are copied from persistent state vectorh   V8..15 ← IV0..7Remaining eight items are initialized from theIVMix the 128-bit countert into V12:V13   V12 ← V12xor Lo(t)Lo 64-bits of UInt128t   V13 ← V13xor Hi(t)Hi 64-bits of UInt128tIf this is the last block then invert all the bits in V14if IsLastBlockthen      V14 ← V14xor 0xFFFFFFFFFFFFFFFFTreat each 128-byte messagechunk as sixteen 8-byte (64-bit) wordsm   m0..15 ← chunkTwelve rounds of cryptographic message mixingfor ifrom 0to 11doSelect message mixing schedule for this round.BLAKE2b uses 12 rounds, while SIGMA has only 10 entries.      S0..15 ← SIGMA[imod 10]Rounds 10 and 11 use SIGMA[0] and SIGMA[1] respectively      Mix(V0, V4, V8,  V12, m[S0], m[S1])      Mix(V1, V5, V9,  V13, m[S2], m[S3])      Mix(V2, V6, V10, V14, m[S4], m[S5])      Mix(V3, V7, V11, V15, m[S6], m[S7])      Mix(V0, V5, V10, V15, m[S8],  m[S9])      Mix(V1, V6, V11, V12, m[S10], m[S11])      Mix(V2, V7, V8,  V13, m[S12], m[S13])      Mix(V3, V4, V9,  V14, m[S14], m[S15])end forMix the upper and lower halves of V into ongoing state vector h   h0..7 ← h0..7xor V0..7   h0..7 ← h0..7xor V8..15Result ← hEnd Function Compress

Mix

[edit]

TheMix function is called by theCompress 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 MixInputs:        Va, Vb, Vc, Vdfour 8-byte word entries from the work vector V        x, ytwo 8-byte word entries from padded message mOutput:        Va, Vb, Vc, Vdthe modified versions of Va, Vb, Vc, Vd   Va ← Va + Vb + xwith input   Vd ← (Vdxor Va)rotateright 32   Vc ← Vc + Vdno input   Vb ← (Vbxor Vc)rotateright 24   Va ← Va + Vb + ywith input   Vd ← (Vdxor Va)rotateright 16   Vc ← Vc + Vdno input   Vb ← (Vbxor Vc)rotateright 63Result ← Va, Vb, Vc, VdEnd Function Mix

Example digests

[edit]

Hash values of an empty string:

BLAKE2s-224("") =1fa1291e65248b37b3433475b2a0dd63d54a11ecc4e3e034e7bc1ef4BLAKE2s-256("") =69217a3079908094e11121d042354a7c1f55b6482ca1a51e1b250dfd1ed0eef9BLAKE2b-384("") =b32811423377f52d7862286ee1a72ee540524380fda1724a6f25d7978c6fd3244a6caf0498812673c5e05ef583825100BLAKE2b-512("") =786a02f742015903c6c6fd852552d272912f4740e15847618a86e217f71f5419d25e1031afee585313896444934eb04b903a685b1448b755d56f701afe9be2ce

Changing a single bit causes each bit in the output to change with 50% probability, demonstrating anavalanche effect:

BLAKE2b-512("The quick brown fox jumps over the lazy dog") =a8add4bdddfd93e4877d2746e62817b116364a1fa7bc148d95090bc7333b3673f82401cf7aa2e4cb1ecd90296e3f14cb5413f8ed77be73045b13914cdcd6a918BLAKE2b-512("The quick brown fox jumps over the lazy dof") =ab6b007747d8068c02e25a6008db8a77c218d94f3b40d2291a7dc8a62090a744c082ea27af01521a102e42f480a31e9844053f456b4b41e8aa78bbe5c12957bb

Users of BLAKE2

[edit]

Implementations

[edit]

In addition to the reference implementation,[6] the following cryptography libraries provide implementations of BLAKE2:

BLAKE3

[edit]
BLAKE3
General
DesignersJack O'Connor, Samuel Neves, Jean-Philippe Aumasson,Zooko Wilcox-O'Hearn
First publishedJanuary 9, 2020; 5 years ago (2020-01-09)
Derived fromBao,BLAKE2
Detail
Digest sizes256 bits, arbitrarily extensible
StructureMerkle tree
Rounds7
Speed0.49cpb on Cascade Lake-SP with AVX-512[25]

BLAKE3 is a cryptographic hash function based on Bao and BLAKE2, created by Jack O'Connor, Jean-Philippe Aumasson, Samuel Neves, andZooko Wilcox-O'Hearn.[26] It was announced on January 9, 2020, atReal World Crypto.[27]

BLAKE3 is a single algorithm with many desirable features (parallelism,XOF,KDF,PRF andMAC), in contrast to BLAKE and BLAKE2, which are algorithm families with multiple variants. BLAKE3 has abinary tree structure, so it supports a practically unlimited degree of parallelism (both SIMD and multithreading) given long enough input. The officialRust andC implementations[28] aredual-licensed as public domain (CC0) and theApache License.[29]

BLAKE3 is designed to be as fast as possible. It is consistently a few times faster than BLAKE2. The BLAKE3 compression function is closely based on that of BLAKE2s, with the biggest difference being that the number of rounds is reduced from 10 to 7, a change based on the assumption that current cryptography is too conservative.[30] In addition to providing parallelism, the Merkle tree format also allows for verified streaming (on-the-fly verifying) and incremental updates.[28]

Users of BLAKE3

[edit]

References

[edit]
  1. ^Aumasson, Jean-Philippe; Meier, Willi; Phan, Raphael C.-W. (2008)."The Hash Function Family LAKE"(PDF). InNyberg, Kaisa (ed.).Lecture Notes in Computer Science.Fast Software Encryption. Vol. 5086.Springer. pp. 36–53.doi:10.1007/978-3-540-71039-4_3.Archived(PDF) from the original on 2025-04-17.
  2. ^Aumasson, Jean-Philippe (2021).Crypto Dictionary: 500 Tasty Tidbits for the Curious Cryptographer. No Starch Press.ISBN 9781718501409.
  3. ^"BLAKE2 – an alternative to MD5/SHA-1".
  4. ^O'Whielacronx, Zooko (21 December 2012)."introducing BLAKE2 – an alternative to SHA-3, SHA-2 and MD5". Archived fromthe original on 5 October 2016. Retrieved27 January 2016.
  5. ^ab"BLAKE2".blake2.net.
  6. ^ab"BLAKE2 official implementations".GitHub. Retrieved7 July 2019.
  7. ^Aumasson, Jean-Philippe; Neves, Samuel; Wilcox-O’Hearn, Zooko; Winnerlein, Christian (2013)."BLAKE2: simpler, smaller, fast as MD5"(PDF).Cryptology ePrint Archive. IACR.
  8. ^"BLAKE2X"(PDF).
  9. ^Saarinen, M-J; Aumasson, J-P (November 2015).The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC).IETF.doi:10.17487/RFC7693.RFC7693. Retrieved4 December 2015.
  10. ^"About Chef Habitat".docs.chef.io.
  11. ^"coreutils/src/blake2/".github.com.
  12. ^"librsync/src/blake2/".github.com.
  13. ^"WhatsApp Security Whitepaper"(PDF).
  14. ^"WinRAR archiver, a powerful tool to process RAR and ZIP files".rarsoft.com.
  15. ^"Igor Pavlov's response to a user request for BLAKE3 support in 7-Zip".sourceforge.net.
  16. ^"rmlint — rmlint (2.8.0 Maidenly Moose) documentation".rmlint.readthedocs.io.
  17. ^"WireGuard: Next Generation Kernel Network Tunnel"(PDF).
  18. ^"work".docs.nano.org.
  19. ^"signatures".docs.nano.org.
  20. ^"key derivation".docs.nano.org.
  21. ^"Autolykos: The Ergo Platform PoW Puzzle"(PDF).ergoplatform.org.
  22. ^"Linux 5.17 Random Number Generator Seeing Speed-Ups, Switching From SHA1 To BLAKE2s".www.phoronix.com.
  23. ^"Subscriber Signing - Beckn".
  24. ^"checksum for Windows".corz.org.
  25. ^"BLAKE3 – one function, fast everywhere"(PDF).GitHub.
  26. ^"An earlier version of Bao specified its own custom tree mode, which eventually grew into BLAKE3".GitHub.
  27. ^"JPA and I announced BLAKE3 at the RWC lightning talks..."Hacker News.
  28. ^ab"BLAKE3 official implementations".GitHub. Retrieved12 January 2020.
  29. ^"This work is released into the public domain with CC0 1.0. Alternatively, it is licensed under the Apache License 2.0".GitHub.
  30. ^Aumasson, Jean-Philippe (2020).Too Much Crypto(PDF). Real World Crypto Symposium.
  31. ^Larabel, Michael (13 October 2023)."OpenZFS 2.2 Released With Block Clning, Linux Container Support & Better Performanceo".Phoronix. Retrieved21 May 2025.

External links

[edit]
Common functions
SHA-3 finalists
Other functions
Password hashing/
key stretching functions
General purpose
key derivation functions
MAC functions
Authenticated
encryption
modes
Attacks
Design
Standardization
Utilization
General
Mathematics
Retrieved from "https://en.wikipedia.org/w/index.php?title=BLAKE_(hash_function)&oldid=1298750678"
Categories:
Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp