jvz commented on a change in pull request #79: URL: https://github.com/apache/commons-codec/pull/79#discussion_r589888807
########## File path: src/main/java/org/apache/commons/codec/digest/Blake3.java ########## @@ -0,0 +1,505 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.codec.digest; + +import java.util.Arrays; +import java.util.Objects; + +/** + * Implements the Blake3 algorithm providing a {@linkplain #initHash() hash function} with extensible output (XOF), a + * {@linkplain #initKeyedHash(byte[]) keyed hash function} (MAC, PRF), and a + * {@linkplain #initKeyDerivationFunction(byte[]) key derivation function} (KDF). Blake3 has a 128-bit security level + * and a default output length of 256 bits (32 bytes) which can extended up to 2<sup>64</sup> bytes. + * <h2>Hashing</h2> + * <p>Hash mode calculates the same output hash given the same input bytes and can be used as both a message digest and + * and extensible output function.</p> + * <pre>{@code + * Blake3 hasher = Blake3.initHash(); + * hasher.update("Hello, world!".getBytes(StandardCharsets.UTF_8)); + * byte[] hash = new byte[32]; + * hasher.doFinalize(hash); + * }</pre> + * <h2>Keyed Hashing</h2> + * <p>Keyed hashes take a 32-byte secret key and calculates a message authentication code on some input bytes. These + * also work as pseduo-random functions (PRFs) with extensible output similar to the extensible hash output. Note that + * Blake3 keyed hashes have the same performance as plain hashes; the key is used in initialization in place of a + * standard initialization vector used for plain hashing.</p> + * <pre>{@code + * SecureRandom random = new SecureRandom(); // or SecureRandom.getInstanceStrong() in Java 8+ + * byte[] key = new byte[32]; + * random.nextBytes(key); + * Blake3 hasher = Blake3.initKeyedHash(key); + * hasher.update("Hello, Alice!".getBytes(StandardCharsets.UTF_8)); + * byte[] mac = new byte[32]; + * hasher.doFinalize(mac); + * }</pre> + * <h2>Key Derivation</h2> + * <p>A specific hash mode for deriving session keys and other derived keys in a unique key derivation context + * identified by some sequence of bytes. These context strings should be unique but do not need to be kept secret. + * Additional input data is hashed for key material which can be finalized to derive subkeys.</p> + * <pre>{@code + * String context = "org.apache.commons.codec.digest.Blake3Example"; + * byte[] sharedSecret = ...; + * byte[] senderId = ...; + * byte[] recipientId = ...; + * Blake3 kdf = Blake3.initKeyDerivationFunction(context.getBytes(StandardCharsets.UTF_8)); + * kdf.update(sharedSecret); + * kdf.update(senderId); + * kdf.update(recipientId); + * byte[] txKey = new byte[32]; + * byte[] rxKey = new byte[32]; + * kdf.doFinalize(txKey); + * kdf.doFinalize(rxKey); + * }</pre> + * <p> + * Adapted from the ISC-licensed O(1) Cryptography library by Matt Sicker and ported from the reference public domain + * implementation by Jack O'Connor. + * </p> + * + * @see <a href="https://github.com/BLAKE3-team/BLAKE3";>BLAKE3 hash function</a> + * @since 1.16 + */ +public final class Blake3 { + // TODO: migrate to Integer.BYTES after upgrading to Java 8 + private static final int INT_BYTES = Integer.SIZE / Byte.SIZE; + + private static final int BLOCK_LEN = 64; + private static final int BLOCK_INTS = BLOCK_LEN / INT_BYTES; + private static final int KEY_LEN = 32; + private static final int KEY_INTS = KEY_LEN / INT_BYTES; + private static final int OUT_LEN = 32; + private static final int CHUNK_LEN = 1024; + private static final int CHAINING_VALUE_INTS = 8; + + // standard hash key used for plain hashes; same initialization vector as Blake2s + private static final int[] IV = + { 0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19 }; + + // domain flags + private static final int CHUNK_START = 1; + private static final int CHUNK_END = 1 << 1; + private static final int PARENT = 1 << 2; + private static final int ROOT = 1 << 3; + private static final int KEYED_HASH = 1 << 4; + private static final int DERIVE_KEY_CONTEXT = 1 << 5; + private static final int DERIVE_KEY_MATERIAL = 1 << 6; + + private final EngineState engineState; + + private Blake3(final int[] key, final int flags) { + engineState = new EngineState(key, flags); + } + + /** + * Resets this instance back to its initial state when it was first constructed. + */ + public void reset() { + engineState.reset(); + } + + /** + * Updates this hash state using the provided bytes. + * + * @param in source array to update data from + */ + public void update(final byte[] in) { + Objects.requireNonNull(in); + update(in, 0, in.length); + } + + /** + * Updates this hash state using the provided bytes at an offset. + * + * @param in source array to update data from + * @param offset where in the array to begin reading bytes + * @param length number of bytes to update + */ + public void update(final byte[] in, final int offset, final int length) { + Objects.requireNonNull(in); + engineState.inputData(in, offset, length); + } + + /** + * Finalizes hash output data that depends on the sequence of updated bytes preceding this invocation and any + * previously finalized bytes. Note that this can finalize up to 2<sup>64</sup> bytes per instance. + * + * @param out destination array to finalize bytes into + */ + public void doFinalize(final byte[] out) { + doFinalize(out, 0, out.length); + } + + /** + * Finalizes an arbitrary number of bytes into the provided output array that depends on the sequence of previously + * updated and finalized bytes. Note that this can finalize up to 2<sup>64</sup> bytes per instance. + * + * @param out destination array to finalize bytes into + * @param offset where in the array to begin writing bytes to + * @param length number of bytes to finalize + */ + public void doFinalize(final byte[] out, final int offset, final int length) { + Objects.requireNonNull(out); + engineState.outputHash(out, offset, length); + } + + /** + * Squeezes and returns an arbitrary number of bytes dependent on the sequence of previously absorbed and squeezed bytes. + * + * @param nrBytes number of bytes to finalize + * @return requested number of finalized bytes + */ + public byte[] doFinalize(final int nrBytes) { + final byte[] hash = new byte[nrBytes]; + doFinalize(hash); + return hash; + } + + /** + * Constructs a fresh Blake3 hash function. The instance returned functions as an arbitrary length message digest. + * + * @return fresh Blake3 instance in hashed mode + */ + public static Blake3 initHash() { + return new Blake3(IV, 0); + } + + /** + * Constructs a fresh Blake3 keyed hash function. The instance returned functions as a pseudorandom function (PRF) or as a + * message authentication code (MAC). + * + * @param key 32-byte secret key + * @return fresh Blake3 instance in keyed mode using the provided key + */ + public static Blake3 initKeyedHash(final byte[] key) { + Objects.requireNonNull(key); + if (key.length != KEY_LEN) { + throw new IllegalArgumentException("Blake3 keys must be 32 bytes"); + } + return new Blake3(unpackInts(key, KEY_INTS), KEYED_HASH); + } + + /** + * Constructs a fresh Blake3 key derivation function using the provided key derivation context byte string. + * The instance returned functions as a key-derivation function which can further absorb additional context data + * before squeezing derived key data. + * + * @param kdfContext a globally unique key-derivation context byte string to separate key derivation contexts from each other + * @return fresh Blake3 instance in key derivation mode + */ + public static Blake3 initKeyDerivationFunction(final byte[] kdfContext) { + Objects.requireNonNull(kdfContext); + final EngineState kdf = new EngineState(IV, DERIVE_KEY_CONTEXT); + kdf.inputData(kdfContext, 0, kdfContext.length); + final byte[] key = new byte[KEY_LEN]; + kdf.outputHash(key, 0, key.length); + return new Blake3(unpackInts(key, KEY_INTS), DERIVE_KEY_MATERIAL); + } + + /** + * Calculates the Blake3 hash of the provided data. + * + * @param data source array to absorb data from + * @return 32-byte hash squeezed from the provided data + */ + public static byte[] hash(final byte[] data) { + final Blake3 blake3 = Blake3.initHash(); + blake3.update(data); + return blake3.doFinalize(OUT_LEN); + } + + /** + * Calculates the Blake3 keyed hash (MAC) of the provided data. + * + * @param key 32-byte secret key + * @param data source array to absorb data from + * @return 32-byte mac squeezed from the provided data + */ + public static byte[] keyedHash(final byte[] key, final byte[] data) { + final Blake3 blake3 = Blake3.initKeyedHash(key); + blake3.update(data); + return blake3.doFinalize(OUT_LEN); + } + + private static void packInt(final int value, final byte[] dst, final int off, final int len) { + for (int i = 0; i < len; i++) { + dst[off + i] = (byte) (value >>> i * Byte.SIZE); + } + } + + private static int unpackInt(final byte[] buf, final int off) { + return buf[off] & 0xFF | (buf[off + 1] & 0xFF) << 8 | (buf[off + 2] & 0xFF) << 16 | (buf[off + 3] & 0xFF) << 24; + } + + private static int[] unpackInts(final byte[] buf, final int nrInts) { + final int[] values = new int[nrInts]; + for (int i = 0, off = 0; i < nrInts; i++, off += INT_BYTES) { + values[i] = unpackInt(buf, off); + } + return values; + } + + // The mixing function, G, which mixes either a column or a diagonal. + 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) { + state[a] += state[b] + mx; + state[d] = Integer.rotateRight(state[d] ^ state[a], 16); + state[c] += state[d]; + state[b] = Integer.rotateRight(state[b] ^ state[c], 12); + state[a] += state[b] + my; + state[d] = Integer.rotateRight(state[d] ^ state[a], 8); + state[c] += state[d]; + state[b] = Integer.rotateRight(state[b] ^ state[c], 7); + } + + private static void round(final int[] state, final int[] msg, final byte[] schedule) { + // Mix the columns. + g(state, 0, 4, 8, 12, msg[schedule[0]], msg[schedule[1]]); + g(state, 1, 5, 9, 13, msg[schedule[2]], msg[schedule[3]]); + g(state, 2, 6, 10, 14, msg[schedule[4]], msg[schedule[5]]); + g(state, 3, 7, 11, 15, msg[schedule[6]], msg[schedule[7]]); + + // Mix the diagonals. + g(state, 0, 5, 10, 15, msg[schedule[8]], msg[schedule[9]]); + g(state, 1, 6, 11, 12, msg[schedule[10]], msg[schedule[11]]); + g(state, 2, 7, 8, 13, msg[schedule[12]], msg[schedule[13]]); + g(state, 3, 4, 9, 14, msg[schedule[14]], msg[schedule[15]]); + } + + // pre-permuted for all 7 rounds; the second row (2,6,3,...) indicates the base permutation + private static final byte[][] MSG_SCHEDULE = { + { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, + { 2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8 }, + { 3, 4, 10, 12, 13, 2, 7, 14, 6, 5, 9, 0, 11, 15, 8, 1 }, + { 10, 7, 12, 9, 14, 3, 13, 15, 4, 0, 11, 2, 5, 8, 1, 6 }, + { 12, 13, 9, 11, 15, 10, 14, 8, 7, 2, 5, 3, 0, 1, 6, 4 }, + { 9, 14, 11, 5, 8, 12, 15, 1, 13, 3, 0, 10, 2, 6, 4, 7 }, + { 11, 15, 5, 0, 1, 9, 8, 6, 14, 10, 2, 12, 3, 4, 7, 13 } + }; + + private static int[] compress( + final int[] chainingValue, final int[] blockWords, final int blockLength, final long counter, + final int flags) { + final int[] state = Arrays.copyOf(chainingValue, BLOCK_INTS); + System.arraycopy(IV, 0, state, 8, 4); + state[12] = (int) counter; + state[13] = (int) (counter >> Integer.SIZE); + state[14] = blockLength; + state[15] = flags; + for (int i = 0; i < 7; i++) { + final byte[] schedule = MSG_SCHEDULE[i]; + round(state, blockWords, schedule); + } + for (int i = 0; i < state.length / 2; i++) { + state[i] ^= state[i + 8]; + state[i + 8] ^= chainingValue[i]; + } + return state; + } + + private static Output parentOutput( + final int[] leftChildCV, final int[] rightChildCV, final int[] key, final int flags) { + final int[] blockWords = Arrays.copyOf(leftChildCV, BLOCK_INTS); Review comment: Not sure if it's worth commenting in the code, but there are various parts of the code like this line where I intentionally copy the array larger than the original to zero-extend a new array to fill in afterwards. Some byte array idioms :) ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected]
