View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.codec.digest;
18  
19  import java.util.Arrays;
20  import java.util.Objects;
21  
22  /**
23   * Implements the Blake3 algorithm providing a {@linkplain #initHash() hash function} with extensible output (XOF), a
24   * {@linkplain #initKeyedHash(byte[]) keyed hash function} (MAC, PRF), and a
25   * {@linkplain #initKeyDerivationFunction(byte[]) key derivation function} (KDF). Blake3 has a 128-bit security level
26   * and a default output length of 256 bits (32 bytes) which can extended up to 2<sup>64</sup> bytes.
27   * <h2>Hashing</h2>
28   * <p>Hash mode calculates the same output hash given the same input bytes and can be used as both a message digest and
29   * and extensible output function.</p>
30   * <pre>{@code
31   *      Blake3 hasher = Blake3.initHash();
32   *      hasher.update("Hello, world!".getBytes(StandardCharsets.UTF_8));
33   *      byte[] hash = new byte[32];
34   *      hasher.doFinalize(hash);
35   * }</pre>
36   * <h2>Keyed Hashing</h2>
37   * <p>Keyed hashes take a 32-byte secret key and calculates a message authentication code on some input bytes. These
38   * also work as pseudo-random functions (PRFs) with extensible output similar to the extensible hash output. Note that
39   * Blake3 keyed hashes have the same performance as plain hashes; the key is used in initialization in place of a
40   * standard initialization vector used for plain hashing.</p>
41   * <pre>{@code
42   *      SecureRandom random = SecureRandom.getInstanceStrong();
43   *      byte[] key = new byte[32];
44   *      random.nextBytes(key);
45   *      Blake3 hasher = Blake3.initKeyedHash(key);
46   *      hasher.update("Hello, Alice!".getBytes(StandardCharsets.UTF_8));
47   *      byte[] mac = new byte[32];
48   *      hasher.doFinalize(mac);
49   * }</pre>
50   * <h2>Key Derivation</h2>
51   * <p>A specific hash mode for deriving session keys and other derived keys in a unique key derivation context
52   * identified by some sequence of bytes. These context strings should be unique but do not need to be kept secret.
53   * Additional input data is hashed for key material which can be finalized to derive subkeys.</p>
54   * <pre>{@code
55   *      String context = "org.apache.commons.codec.digest.Blake3Example";
56   *      byte[] sharedSecret = ...;
57   *      byte[] senderId = ...;
58   *      byte[] recipientId = ...;
59   *      Blake3 kdf = Blake3.initKeyDerivationFunction(context.getBytes(StandardCharsets.UTF_8));
60   *      kdf.update(sharedSecret);
61   *      kdf.update(senderId);
62   *      kdf.update(recipientId);
63   *      byte[] txKey = new byte[32];
64   *      byte[] rxKey = new byte[32];
65   *      kdf.doFinalize(txKey);
66   *      kdf.doFinalize(rxKey);
67   * }</pre>
68   * <p>
69   * Adapted from the ISC-licensed O(1) Cryptography library by Matt Sicker and ported from the reference public domain
70   * implementation by Jack O'Connor.
71   * </p>
72   *
73   * @see <a href="https://github.com/BLAKE3-team/BLAKE3">BLAKE3 hash function</a>
74   * @since 1.16
75   */
76  public final class Blake3 {
77  
78      private static final class ChunkState {
79  
80          private int[] chainingValue;
81          private final long chunkCounter;
82          private final int flags;
83  
84          private final byte[] block = new byte[BLOCK_LEN];
85          private int blockLength;
86          private int blocksCompressed;
87  
88          private ChunkState(final int[] key, final long chunkCounter, final int flags) {
89              chainingValue = key;
90              this.chunkCounter = chunkCounter;
91              this.flags = flags;
92          }
93  
94          private int length() {
95              return BLOCK_LEN * blocksCompressed + blockLength;
96          }
97  
98          private Output output() {
99              final int[] blockWords = unpackInts(block, BLOCK_INTS);
100             final int outputFlags = flags | startFlag() | CHUNK_END;
101             return new Output(chainingValue, blockWords, chunkCounter, blockLength, outputFlags);
102         }
103 
104         private int startFlag() {
105             return blocksCompressed == 0 ? CHUNK_START : 0;
106         }
107 
108         private void update(final byte[] input, int offset, int length) {
109             while (length > 0) {
110                 if (blockLength == BLOCK_LEN) {
111                     // If the block buffer is full, compress it and clear it. More
112                     // input is coming, so this compression is not CHUNK_END.
113                     final int[] blockWords = unpackInts(block, BLOCK_INTS);
114                     chainingValue = Arrays.copyOf(
115                             compress(chainingValue, blockWords, BLOCK_LEN, chunkCounter, flags | startFlag()),
116                             CHAINING_VALUE_INTS);
117                     blocksCompressed++;
118                     blockLength = 0;
119                     Arrays.fill(block, (byte) 0);
120                 }
121 
122                 final int want = BLOCK_LEN - blockLength;
123                 final int take = Math.min(want, length);
124                 System.arraycopy(input, offset, block, blockLength, take);
125                 blockLength += take;
126                 offset += take;
127                 length -= take;
128             }
129         }
130     }
131     private static final class EngineState {
132         private final int[] key;
133         private final int flags;
134         // Space for 54 subtree chaining values: 2^54 * CHUNK_LEN = 2^64
135         // No more than 54 entries can ever be added to this stack (after updating 2^64 bytes and not finalizing any)
136         // so we preallocate the stack here. This can be smaller in environments where the data limit is expected to
137         // be much lower.
138         private final int[][] cvStack = new int[54][];
139         private int stackLen;
140         private ChunkState state;
141 
142         private EngineState(final int[] key, final int flags) {
143             this.key = key;
144             this.flags = flags;
145             state = new ChunkState(key, 0, flags);
146         }
147 
148         // Section 5.1.2 of the BLAKE3 spec explains this algorithm in more detail.
149         private void addChunkCV(final int[] firstCV, final long totalChunks) {
150             // This chunk might complete some subtrees. For each completed subtree,
151             // its left child will be the current top entry in the CV stack, and
152             // its right child will be the current value of `newCV`. Pop each left
153             // child off the stack, merge it with `newCV`, and overwrite `newCV`
154             // with the result. After all these merges, push the final value of
155             // `newCV` onto the stack. The number of completed subtrees is given
156             // by the number of trailing 0-bits in the new total number of chunks.
157             int[] newCV = firstCV;
158             long chunkCounter = totalChunks;
159             while ((chunkCounter & 1) == 0) {
160                 newCV = parentChainingValue(popCV(), newCV, key, flags);
161                 chunkCounter >>= 1;
162             }
163             pushCV(newCV);
164         }
165 
166         private void inputData(final byte[] in, int offset, int length) {
167             while (length > 0) {
168                 // If the current chunk is complete, finalize it and reset the
169                 // chunk state. More input is coming, so this chunk is not ROOT.
170                 if (state.length() == CHUNK_LEN) {
171                     final int[] chunkCV = state.output().chainingValue();
172                     final long totalChunks = state.chunkCounter + 1;
173                     addChunkCV(chunkCV, totalChunks);
174                     state = new ChunkState(key, totalChunks, flags);
175                 }
176 
177                 // Compress input bytes into the current chunk state.
178                 final int want = CHUNK_LEN - state.length();
179                 final int take = Math.min(want, length);
180                 state.update(in, offset, take);
181                 offset += take;
182                 length -= take;
183             }
184         }
185 
186         private void outputHash(final byte[] out, final int offset, final int length) {
187             // Starting with the Output from the current chunk, compute all the
188             // parent chaining values along the right edge of the tree, until we
189             // have the root Output.
190             Output output = state.output();
191             int parentNodesRemaining = stackLen;
192             while (parentNodesRemaining-- > 0) {
193                 final int[] parentCV = cvStack[parentNodesRemaining];
194                 output = parentOutput(parentCV, output.chainingValue(), key, flags);
195             }
196             output.rootOutputBytes(out, offset, length);
197         }
198 
199         private int[] popCV() {
200             return cvStack[--stackLen];
201         }
202 
203         private void pushCV(final int[] cv) {
204             cvStack[stackLen++] = cv;
205         }
206 
207         private void reset() {
208             stackLen = 0;
209             Arrays.fill(cvStack, null);
210             state = new ChunkState(key, 0, flags);
211         }
212     }
213 
214     /**
215      * Represents the state just prior to either producing an eight word chaining value or any number of output bytes
216      * when the ROOT flag is set.
217      */
218     private static final class Output {
219 
220         private final int[] inputChainingValue;
221         private final int[] blockWords;
222         private final long counter;
223         private final int blockLength;
224         private final int flags;
225 
226         private Output(final int[] inputChainingValue, final int[] blockWords, final long counter, final int blockLength, final int flags) {
227             this.inputChainingValue = inputChainingValue;
228             this.blockWords = blockWords;
229             this.counter = counter;
230             this.blockLength = blockLength;
231             this.flags = flags;
232         }
233 
234         private int[] chainingValue() {
235             return Arrays.copyOf(compress(inputChainingValue, blockWords, blockLength, counter, flags), CHAINING_VALUE_INTS);
236         }
237 
238         private void rootOutputBytes(final byte[] out, int offset, int length) {
239             int outputBlockCounter = 0;
240             while (length > 0) {
241                 int chunkLength = Math.min(OUT_LEN * 2, length);
242                 length -= chunkLength;
243                 final int[] words = compress(inputChainingValue, blockWords, blockLength, outputBlockCounter++, flags | ROOT);
244                 int wordCounter = 0;
245                 while (chunkLength > 0) {
246                     final int wordLength = Math.min(Integer.BYTES, chunkLength);
247                     packInt(words[wordCounter++], out, offset, wordLength);
248                     offset += wordLength;
249                     chunkLength -= wordLength;
250                 }
251             }
252         }
253     }
254 
255     private static final int BLOCK_LEN = 64;
256     private static final int BLOCK_INTS = BLOCK_LEN / Integer.BYTES;
257     private static final int KEY_LEN = 32;
258     private static final int KEY_INTS = KEY_LEN / Integer.BYTES;
259     private static final int OUT_LEN = 32;
260     private static final int CHUNK_LEN = 1024;
261     private static final int CHAINING_VALUE_INTS = 8;
262 
263     /**
264      * Standard hash key used for plain hashes; same initialization vector as Blake2s.
265      */
266     private static final int[] IV = { 0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19 };
267 
268     // domain flags
269     private static final int CHUNK_START = 1;
270     private static final int CHUNK_END = 1 << 1;
271     private static final int PARENT = 1 << 2;
272     private static final int ROOT = 1 << 3;
273     private static final int KEYED_HASH = 1 << 4;
274     private static final int DERIVE_KEY_CONTEXT = 1 << 5;
275     private static final int DERIVE_KEY_MATERIAL = 1 << 6;
276 
277     /**
278      * Pre-permuted for all 7 rounds; the second row (2,6,3,...) indicates the base permutation.
279      */
280     // @formatter:off
281     private static final byte[][] MSG_SCHEDULE = {
282             { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
283             { 2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8 },
284             { 3, 4, 10, 12, 13, 2, 7, 14, 6, 5, 9, 0, 11, 15, 8, 1 },
285             { 10, 7, 12, 9, 14, 3, 13, 15, 4, 0, 11, 2, 5, 8, 1, 6 },
286             { 12, 13, 9, 11, 15, 10, 14, 8, 7, 2, 5, 3, 0, 1, 6, 4 },
287             { 9, 14, 11, 5, 8, 12, 15, 1, 13, 3, 0, 10, 2, 6, 4, 7 },
288             { 11, 15, 5, 0, 1, 9, 8, 6, 14, 10, 2, 12, 3, 4, 7, 13 }
289     };
290     // @formatter:on
291 
292     private static void checkBufferArgs(final byte[] buffer, final int offset, final int length) {
293         Objects.requireNonNull(buffer);
294         if (offset < 0) {
295             throw new IndexOutOfBoundsException("Offset must be non-negative");
296         }
297         if (length < 0) {
298             throw new IndexOutOfBoundsException("Length must be non-negative");
299         }
300         final int bufferLength = buffer.length;
301         if (offset > bufferLength - length) {
302             throw new IndexOutOfBoundsException("Offset " + offset + " and length " + length + " out of bounds with buffer length " + bufferLength);
303         }
304     }
305 
306     private static int[] compress(final int[] chainingValue, final int[] blockWords, final int blockLength, final long counter, final int flags) {
307         final int[] state = Arrays.copyOf(chainingValue, BLOCK_INTS);
308         System.arraycopy(IV, 0, state, 8, 4);
309         state[12] = (int) counter;
310         state[13] = (int) (counter >> Integer.SIZE);
311         state[14] = blockLength;
312         state[15] = flags;
313         for (int i = 0; i < 7; i++) {
314             final byte[] schedule = MSG_SCHEDULE[i];
315             round(state, blockWords, schedule);
316         }
317         for (int i = 0; i < state.length / 2; i++) {
318             state[i] ^= state[i + 8];
319             state[i + 8] ^= chainingValue[i];
320         }
321         return state;
322     }
323 
324     /**
325      * The mixing function, G, which mixes either a column or a diagonal.
326      */
327     private static void g(final int[] state, final int a, final int b, final int c, final int d, final int mx, final int my) {
328         state[a] += state[b] + mx;
329         state[d] = Integer.rotateRight(state[d] ^ state[a], 16);
330         state[c] += state[d];
331         state[b] = Integer.rotateRight(state[b] ^ state[c], 12);
332         state[a] += state[b] + my;
333         state[d] = Integer.rotateRight(state[d] ^ state[a], 8);
334         state[c] += state[d];
335         state[b] = Integer.rotateRight(state[b] ^ state[c], 7);
336     }
337 
338     /**
339      * Calculates the Blake3 hash of the provided data.
340      *
341      * @param data source array to absorb data from
342      * @return 32-byte hash squeezed from the provided data
343      * @throws NullPointerException if data is null
344      */
345     public static byte[] hash(final byte[] data) {
346         return Blake3.initHash().update(data).doFinalize(OUT_LEN);
347     }
348 
349     /**
350      * Constructs a fresh Blake3 hash function. The instance returned functions as an arbitrary length message digest.
351      *
352      * @return fresh Blake3 instance in hashed mode
353      */
354     public static Blake3 initHash() {
355         return new Blake3(IV, 0);
356     }
357 
358     /**
359      * Constructs a fresh Blake3 key derivation function using the provided key derivation context byte string.
360      * The instance returned functions as a key-derivation function which can further absorb additional context data
361      * before squeezing derived key data.
362      *
363      * @param kdfContext a globally unique key-derivation context byte string to separate key derivation contexts from each other
364      * @return fresh Blake3 instance in key derivation mode
365      * @throws NullPointerException if kdfContext is null
366      */
367     public static Blake3 initKeyDerivationFunction(final byte[] kdfContext) {
368         Objects.requireNonNull(kdfContext);
369         final EngineState kdf = new EngineState(IV, DERIVE_KEY_CONTEXT);
370         kdf.inputData(kdfContext, 0, kdfContext.length);
371         final byte[] key = new byte[KEY_LEN];
372         kdf.outputHash(key, 0, key.length);
373         return new Blake3(unpackInts(key, KEY_INTS), DERIVE_KEY_MATERIAL);
374     }
375 
376     /**
377      * Constructs a fresh Blake3 keyed hash function. The instance returned functions as a pseudorandom function (PRF) or as a
378      * message authentication code (MAC).
379      *
380      * @param key 32-byte secret key
381      * @return fresh Blake3 instance in keyed mode using the provided key
382      * @throws NullPointerException     if key is null
383      * @throws IllegalArgumentException if key is not 32 bytes
384      */
385     public static Blake3 initKeyedHash(final byte[] key) {
386         Objects.requireNonNull(key);
387         if (key.length != KEY_LEN) {
388             throw new IllegalArgumentException("Blake3 keys must be 32 bytes");
389         }
390         return new Blake3(unpackInts(key, KEY_INTS), KEYED_HASH);
391     }
392 
393     /**
394      * Calculates the Blake3 keyed hash (MAC) of the provided data.
395      *
396      * @param key  32-byte secret key
397      * @param data source array to absorb data from
398      * @return 32-byte mac squeezed from the provided data
399      * @throws NullPointerException if key or data are null
400      */
401     public static byte[] keyedHash(final byte[] key, final byte[] data) {
402         return Blake3.initKeyedHash(key).update(data).doFinalize(OUT_LEN);
403     }
404 
405     private static void packInt(final int value, final byte[] dst, final int off, final int len) {
406         for (int i = 0; i < len; i++) {
407             dst[off + i] = (byte) (value >>> i * Byte.SIZE);
408         }
409     }
410 
411     private static int[] parentChainingValue(final int[] leftChildCV, final int[] rightChildCV, final int[] key, final int flags) {
412         return parentOutput(leftChildCV, rightChildCV, key, flags).chainingValue();
413     }
414 
415     private static Output parentOutput(final int[] leftChildCV, final int[] rightChildCV, final int[] key, final int flags) {
416         final int[] blockWords = Arrays.copyOf(leftChildCV, BLOCK_INTS);
417         System.arraycopy(rightChildCV, 0, blockWords, 8, CHAINING_VALUE_INTS);
418         return new Output(key.clone(), blockWords, 0, BLOCK_LEN, flags | PARENT);
419     }
420 
421     private static void round(final int[] state, final int[] msg, final byte[] schedule) {
422         // Mix the columns.
423         g(state, 0, 4, 8, 12, msg[schedule[0]], msg[schedule[1]]);
424         g(state, 1, 5, 9, 13, msg[schedule[2]], msg[schedule[3]]);
425         g(state, 2, 6, 10, 14, msg[schedule[4]], msg[schedule[5]]);
426         g(state, 3, 7, 11, 15, msg[schedule[6]], msg[schedule[7]]);
427 
428         // Mix the diagonals.
429         g(state, 0, 5, 10, 15, msg[schedule[8]], msg[schedule[9]]);
430         g(state, 1, 6, 11, 12, msg[schedule[10]], msg[schedule[11]]);
431         g(state, 2, 7, 8, 13, msg[schedule[12]], msg[schedule[13]]);
432         g(state, 3, 4, 9, 14, msg[schedule[14]], msg[schedule[15]]);
433     }
434 
435     private static int unpackInt(final byte[] buf, final int off) {
436         return buf[off] & 0xFF | (buf[off + 1] & 0xFF) << 8 | (buf[off + 2] & 0xFF) << 16 | (buf[off + 3] & 0xFF) << 24;
437     }
438 
439     private static int[] unpackInts(final byte[] buf, final int nrInts) {
440         final int[] values = new int[nrInts];
441         for (int i = 0, off = 0; i < nrInts; i++, off += Integer.BYTES) {
442             values[i] = unpackInt(buf, off);
443         }
444         return values;
445     }
446 
447     private final EngineState engineState;
448 
449     private Blake3(final int[] key, final int flags) {
450         engineState = new EngineState(key, flags);
451     }
452 
453     /**
454      * Finalizes hash output data that depends on the sequence of updated bytes preceding this invocation and any
455      * previously finalized bytes. Note that this can finalize up to 2<sup>64</sup> bytes per instance.
456      *
457      * @param out destination array to finalize bytes into
458      * @return {@code this} instance.
459      * @throws NullPointerException if out is null
460      */
461     public Blake3 doFinalize(final byte[] out) {
462         return doFinalize(out, 0, out.length);
463     }
464 
465     /**
466      * Finalizes an arbitrary number of bytes into the provided output array that depends on the sequence of previously
467      * updated and finalized bytes. Note that this can finalize up to 2<sup>64</sup> bytes per instance.
468      *
469      * @param out    destination array to finalize bytes into
470      * @param offset where in the array to begin writing bytes to
471      * @param length number of bytes to finalize
472      * @return {@code this} instance.
473      * @throws NullPointerException      if out is null
474      * @throws IndexOutOfBoundsException if offset or length are negative or if offset + length is greater than the
475      *                                   length of the provided array
476      */
477     public Blake3 doFinalize(final byte[] out, final int offset, final int length) {
478         checkBufferArgs(out, offset, length);
479         engineState.outputHash(out, offset, length);
480         return this;
481     }
482 
483     /**
484      * Squeezes and returns an arbitrary number of bytes dependent on the sequence of previously absorbed and squeezed bytes.
485      *
486      * @param nrBytes number of bytes to finalize
487      * @return requested number of finalized bytes
488      * @throws IllegalArgumentException if nrBytes is negative
489      */
490     public byte[] doFinalize(final int nrBytes) {
491         if (nrBytes < 0) {
492             throw new IllegalArgumentException("Requested bytes must be non-negative");
493         }
494         final byte[] hash = new byte[nrBytes];
495         doFinalize(hash);
496         return hash;
497     }
498 
499     /**
500      * Resets this instance back to its initial state when it was first constructed.
501      * @return {@code this} instance.
502      */
503     public Blake3 reset() {
504         engineState.reset();
505         return this;
506     }
507 
508     /**
509      * Updates this hash state using the provided bytes.
510      *
511      * @param in source array to update data from
512      * @return {@code this} instance.
513      * @throws NullPointerException if in is null
514      */
515     public Blake3 update(final byte[] in) {
516         return update(in, 0, in.length);
517     }
518 
519     /**
520      * Updates this hash state using the provided bytes at an offset.
521      *
522      * @param in     source array to update data from
523      * @param offset where in the array to begin reading bytes
524      * @param length number of bytes to update
525      * @return {@code this} instance.
526      * @throws NullPointerException      if in is null
527      * @throws IndexOutOfBoundsException if offset or length are negative or if offset + length is greater than the
528      *                                   length of the provided array
529      */
530     public Blake3 update(final byte[] in, final int offset, final int length) {
531         checkBufferArgs(in, offset, length);
532         engineState.inputData(in, offset, length);
533         return this;
534     }
535 
536 }