Independent Submission M-J. Saarinen, Ed. Request for Comments: 7693 Queen's University Belfast Category: Informational J-P. Aumasson ISSN: 2070-1721 Kudelski Security November 2015
The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC)
Abstract
This document describes the cryptographic hash function BLAKE2 and makes the algorithm specification and C source code conveniently available to the Internet community. BLAKE2 comes in two main flavors: BLAKE2b is optimized for 64-bit platforms and BLAKE2s for smaller architectures. BLAKE2 can be directly keyed, making it functionally equivalent to a Message Authentication Code (MAC).
Status of This Memo
This document is not an Internet Standards Track specification; it is published for informational purposes.
This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741.
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc7693.
Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
The BLAKE2 cryptographic hash function [BLAKE2] was designed by Jean- Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, and Christian Winnerlein.
BLAKE2 comes in two basic flavors:
o BLAKE2b (or just BLAKE2) is optimized for 64-bit platforms and produces digests of any size between 1 and 64 bytes.
o BLAKE2s is optimized for 8- to 32-bit platforms and produces digests of any size between 1 and 32 bytes.
Both BLAKE2b and BLAKE2s are believed to be highly secure and perform well on any platform, software, or hardware. BLAKE2 does not require a special "HMAC" (Hashed Message Authentication Code) construction for keyed message authentication as it has a built-in keying mechanism.
The BLAKE2 hash function may be used by digital signature algorithms and message authentication and integrity protection mechanisms in applications such as Public Key Infrastructure (PKI), secure communication protocols, cloud storage, intrusion detection, forensic suites, and version control systems.
The BLAKE2 suite provides a more efficient alternative to US Secure Hash Algorithms SHA and HMAC-SHA [RFC6234]. BLAKE2s-128 is especially suited as a fast and more secure drop-in replacement to MD5 and HMAC-MD5 in legacy applications [RFC6151].
To aid implementation, we provide a trace of BLAKE2b-512 hash computation in Appendix A and a trace of BLAKE2s-256 hash computation in Appendix B. Due to space constraints, this document does not contain a full set of test vectors for BLAKE2.
A reference implementation in C programming language for BLAKE2b can be found in Appendix C and for BLAKE2s in Appendix D of this document. These implementations MAY be validated with the more exhaustive Test Module contained in Appendix E.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].
For real-valued x, we define the following functions:
floor(x) Floor, the largest integer <= x.
ceil(x) Ceiling, the smallest integer >= x.
frac(x) Positive fractional part of x, frac(x) = x - floor(x).
Saarinen & Aumasson Informational [Page 4]
RFC 7693 BLAKE2 Crypto Hash and MAC November 2015
Operator notation in pseudocode:
2**n = 2 to the power "n". 2**0=1, 2**1=2, 2**2=4, 2**3=8, etc.
a ^ b = Bitwise exclusive-or operation between "a" and "b".
a mod b = Remainder "a" modulo "b", always in range [0, b-1].
x >> n = floor(x / 2**n). Logical shift "x" right by "n" bits.
x << n = (x * 2**n) mod (2**w). Logical shift "x" left by "n".
x >>> n = (x >> n) ^ (x << (w - n)). Rotate "x" right by "n".
2.4. Little-Endian Interpretation of Words as Bytes
All mathematical operations are on 64-bit words in BLAKE2b and on 32-bit words in BLAKE2s.
We may also perform operations on vectors of words. Vector indexing is zero based; the first element of an n-element vector "v" is v[0] and the last one is v[n - 1]. All elements are denoted by v[0..n-1].
Byte (octet) streams are interpreted as words in little-endian order, with the least-significant byte first. Consider this sequence of eight hexadecimal bytes:
x[0..7] = 0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF
When interpreted as a 32-bit word from the beginning memory address, x[0..3] has a numerical value of 0x67452301 or 1732584193.
When interpreted as a 64-bit word, bytes x[0..7] have a numerical value of 0xEFCDAB8967452301 or 17279655951921914625.
Here the "nn" byte specifies the hash size in bytes. The second (little-endian) byte of the parameter block, "kk", specifies the key size in bytes. Set kk = 00 for unkeyed hashing. Bytes 2 and 3 are set as 01. All other bytes in the parameter block are set as zero.
Saarinen & Aumasson Informational [Page 5]
RFC 7693 BLAKE2 Crypto Hash and MAC November 2015
Note: [BLAKE2] defines additional variants of BLAKE2 with features such as salting, personalized hashes, and tree hashing. These OPTIONAL features use fields in the parameter block that are not defined in this document.
We define the Initialization Vector constant IV mathematically as:
IV[i] = floor(2**w * frac(sqrt(prime(i+1)))), where prime(i) is the i:th prime number ( 2, 3, 5, 7, 11, 13, 17, 19 ) and sqrt(x) is the square root of x.
The numerical values of IV can also be found in implementations in Appendices C and D for BLAKE2b and BLAKE2s, respectively.
Note: BLAKE2b IV is the same as SHA-512 IV, and BLAKE2s IV is the same as SHA-256 IV; see [RFC6234].
Message word schedule permutations for each round of both BLAKE2b and BLAKE2s are defined by SIGMA. For BLAKE2b, the two extra permutations for rounds 10 and 11 are SIGMA[10..11] = SIGMA[0..1].
The G primitive function mixes two input words, "x" and "y", into four words indexed by "a", "b", "c", and "d" in the working vector v[0..15]. The full modified vector is returned. The rotation constants (R1, R2, R3, R4) are given in Section 2.1.
Compression function F takes as an argument the state vector "h", message block vector "m" (last block is padded with zeros to full block size, if required), 2w-bit offset counter "t", and final block indicator flag "f". Local vector v[0..15] is used in processing. F returns a new state vector. The number of rounds, "r", is 12 for BLAKE2b and 10 for BLAKE2s. Rounds are numbered from 0 to r - 1.
FUNCTION F( h[0..7], m[0..15], t, f ) | | // Initialize local work vector v[0..15] | v[0..7] := h[0..7] // First half from state. | v[8..15] := IV[0..7] // Second half from IV. | | v[12] := v[12] ^ (t mod 2**w) // Low word of the offset. | v[13] := v[13] ^ (t >> w) // High word. | | IF f = TRUE THEN // last block flag? | | v[14] := v[14] ^ 0xFF..FF // Invert all bits. | END IF. | | // Cryptographic mixing | FOR i = 0 TO r - 1 DO // Ten or twelve rounds. | | | | // Message word selection permutation for this round. | | s[0..15] := SIGMA[i mod 10][0..15] | | | | v := G( v, 0, 4, 8, 12, m[s[ 0]], m[s[ 1]] ) | | v := G( v, 1, 5, 9, 13, m[s[ 2]], m[s[ 3]] ) | | v := G( v, 2, 6, 10, 14, m[s[ 4]], m[s[ 5]] ) | | v := G( v, 3, 7, 11, 15, m[s[ 6]], m[s[ 7]] ) | | | | v := G( v, 0, 5, 10, 15, m[s[ 8]], m[s[ 9]] ) | | v := G( v, 1, 6, 11, 12, m[s[10]], m[s[11]] ) | | v := G( v, 2, 7, 8, 13, m[s[12]], m[s[13]] ) | | v := G( v, 3, 4, 9, 14, m[s[14]], m[s[15]] ) | | | END FOR | | FOR i = 0 TO 7 DO // XOR the two halves. | | h[i] := h[i] ^ v[i] ^ v[i + 8] | END FOR. | | RETURN h[0..7] // New state. | END FUNCTION.
We refer the reader to Appendices C and D for reference C language implementations of BLAKE2b and BLAKE2s, respectively.
Key and data input are split and padded into "dd" message blocks d[0..dd-1], each consisting of 16 words (or "bb" bytes).
If a secret key is used (kk > 0), it is padded with zero bytes and set as d[0]. Otherwise, d[0] is the first data block. The final data block d[dd-1] is also padded with zero to "bb" bytes (16 words).
The number of blocks is therefore dd = ceil(kk / bb) + ceil(ll / bb). However, in the special case of an unkeyed empty message (kk = 0 and ll = 0), we still set dd = 1 and d[0] consists of all zeros.
The following procedure processes the padded data blocks into an "nn"-byte final hash value. See Section 2 for a description of various variables and constants used.
FUNCTION BLAKE2( d[0..dd-1], ll, kk, nn ) | | h[0..7] := IV[0..7] // Initialization Vector. | | // Parameter block p[0] | h[0] := h[0] ^ 0x01010000 ^ (kk << 8) ^ nn | | // Process padded key and data blocks | IF dd > 1 THEN | | FOR i = 0 TO dd - 2 DO | | | h := F( h, d[i], (i + 1) * bb, FALSE ) | | END FOR. | END IF. | | // Final block. | IF kk = 0 THEN | | h := F( h, d[dd - 1], ll, TRUE ) | ELSE | | h := F( h, d[dd - 1], ll + bb, TRUE ) | END IF. | | RETURN first "nn" bytes from little-endian word array h[]. | END FUNCTION.
Saarinen & Aumasson Informational [Page 9]
RFC 7693 BLAKE2 Crypto Hash and MAC November 2015
4. Standard Parameter Sets and Algorithm Identifiers
An implementation of BLAKE2b and/or BLAKE2s MAY support the following digest size parameters for interoperability (e.g., digital signatures), as long as a sufficient level of security is attained by the parameter selections. These parameters and identifiers are intended to be suitable as drop-in replacements to MD5 and corresponding SHA algorithms.
Developers adapting BLAKE2 to ASN.1-based message formats SHOULD use the OID tree at x = 1.3.6.1.4.1.1722.12.2. The same OID can be used for both keyed and unkeyed hashing since in the latter case the key simply has zero length.
This document is intended to provide convenient open-source access by the Internet community to the BLAKE2 cryptographic hash algorithm. We wish to make no independent assertion to its security in this document. We refer the reader to [BLAKE] and [BLAKE2] for detailed cryptanalytic rationale behind its design.
In order to avoid bloat, the reference implementations in Appendices C and D may not erase all sensitive data (such as secret keys) immediately from process memory after use. Such cleanup can be added if needed.
[BLAKE] Aumasson, J-P., Meier, W., Phan, R., and L. Henzen, "The Hash Function BLAKE", January 2015, <https://131002.net/blake/book>.
[BLAKE2] Aumasson, J-P., Neves, S., Wilcox-O'Hearn, Z., and C. Winnerlein, "BLAKE2: simpler, smaller, fast as MD5", January 2013, <https://blake2.net/blake2.pdf>.
if (blake2s_init(&ctx, outlen, key, keylen)) return -1; blake2s_update(&ctx, in, inlen); blake2s_final(&ctx, out);
return 0; } <CODE ENDS>
Appendix E. BLAKE2b and BLAKE2s Self-Test Module C Source
This module computes a series of keyed and unkeyed hashes from deterministically generated pseudorandom data and computes a hash over those results. This is a fairly exhaustive, yet compact and fast method for verifying that the hashing module is functioning correctly.
Such testing is RECOMMENDED, especially when compiling the implementation for a new a target platform configuration. Furthermore, some security standards, such as FIPS-140, may require a Power-On Self Test (POST) to be performed every time the cryptographic module is loaded [FIPS140-2IG].
<CODE BEGINS> // test_main.c // Self test Modules for BLAKE2b and BLAKE2s -- and a stub main().
The editor wishes to thank the [BLAKE2] team for their encouragement: Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, and Christian Winnerlein. We have borrowed passages from [BLAKE] and [BLAKE2] with permission.
[BLAKE2] is based on the SHA-3 proposal [BLAKE], designed by Jean- Philippe Aumasson, Luca Henzen, Willi Meier, and Raphael C.-W. Phan. BLAKE2, like BLAKE, relies on a core algorithm borrowed from the ChaCha stream cipher, designed by Daniel J. Bernstein.
Saarinen & Aumasson Informational [Page 29]
RFC 7693 BLAKE2 Crypto Hash and MAC November 2015
Authors' Addresses
Markku-Juhani O. Saarinen (editor) Queen's University Belfast Centre for Secure Information Technologies, ECIT Northern Ireland Science Park Queen's Road, Queen's Island Belfast BT3 9DT United Kingdom