Is it possible to adapt BLAKE3 to use 60-bit words?

[VictorTaelin]

HVM has fast 60-bit native words, and slightly slower 64-bit boxed words. A close example would be Ocaml, which has unboxed 63-bit numbers, and only boxed 64-bit numbers. We're looking for the fastest hash function on HVM. Keccak is great, but it uses 64-bit words on its internal states, so, our best bet, so far, is to port it from implementations that use 32-bit numbers, such as JavaScript. That would be sub-optimal. What about Blake? I wonder if it would be possible to implement it using 60-bit words in its internal states, without having to emulate 64-bit words. It would be a different function, but that is fine. Is there any guideline on how to do so safely? Any reference implementation or pseudocode which is parametric on the word size?

[odiferousmint]

This is the first time I have heard of it, I will check it out. At a quick glance... it compares its speed to GHC? Being faster than Haskell's GHC is not a difficult task... Welp. OCaml is great, I think it is multi-threaded now? In any case, what would you like guidelines on exactly? Generally, there is a famous book named Cryptography Engineering by Bruce Schneier, Niels Ferguson, and Tadayoshi Kohno. It has a chapter named Implementation Issues. That is definitely worth a read. It will explain you why exactly my next statement is correct.

Anything JavaScript is sub-optimal and outright absurd in this area, in my humble opinion. I think Ada/SPARK is the best we have so far with its formal verification and whatnot. I do not want to dig into it but here is a PDF about Ada/SPARK that is still relevant today, although a bit dated. If you want new stuff, just check the AdaCore blog. You can do simple tasks with Ada/SPARK such as proving that images will always be successfully encoded!

Speaking of massively parallel... I recently read a lot about parallelized hashing via j-Lanes and j-Pointers tree modes with applications to SHA-256. It provides us parallelization opportunities in a hashing process that is otherwise serial by nature, which results in having a performance advantage on modern processor architectures. It is definitely not new, but worth looking into.

FWIW I am not shilling Ada (perhaps a bit); they are actually supporting Rust. For example take a look at this. It seems like Ada and Rust are starting to grow on each other in this space. :)

By "Blake", did you really mean BLAKE? As in, BLAKE1?

Good luck, by the way!

[oconnor663]

Is there any guideline on how to do so safely? Any reference implementation or pseudocode which is parametric on the word size?

No, changing the word size would be more like designing a brand new hash function than a simple parameter change. Here are some of the issues that you'd need to consider if you wanted to do this, off the top of my head. I'm sure the other authors can point out more that I've missed:

• BLAKE3 inherits the guts of its compression function (particularly the part called "G") from ChaCha, which also uses 32-bit words. There are bitwise rotations in there that are closely related to the word size, and changing the word size would mean picking new rotations. This was done for BLAKE2b, which uses 64-bit words. The rotations you choose have a big impact on both security (you need to ensure good mixing) and performance (most platforms don't directly support bitwise rotation, and you need to think about what's efficient to emulate). I don't have much experience with the cryptanalysis you need to do for the security side of this, but I think it involves a fair amount of trial and error; other folks can describe this part better than I can. It might also turn out that the ChaCha way of doing things just isn't a great fit for word sizes that aren't a power of two?
• Increasing the word size means increasing the overall state size, so you need to do more work to get good mixing. That means you need to increase the number of rounds in the compression function. Compare the 10 rounds of BLAKE2s to the 12 rounds of BLAKE2b. BLAKE3 followed the round reduction recommendations from JP's Too Much Crypto paper, so a 64-bit version of BLAKE3 would probably use 8 rounds (see section 5.3 in that paper). My guess is that a 60-bit-word version would also want 8 rounds, but that's just a guess, and this might depend on the rotations too.
• BLAKE3 permutes the message words in between each round, using a fixed permutation. That permutation was chosen by analyzing a bunch of candidates and picking the one with the lowest "differential probability trail". (See section 7.4 of the BLAKE3 paper.) I'm not sure whether changing the word size would require repeating that analysis, and BLAKE2 did use the same permutations for both 32-bit and 64-bit words, but I'd want to be careful here.
• The BLAKE3 keyed mode takes a 256-bit key, which is exactly the same size (and which goes in the same place) as the 8-word "chaining value". 60-bit words would probably mean 480-bit chaining values. Would you want to use a 480-bit key? You could consider defining the key to be 256-bits and then padding it with 0's internally, trading away some theoretical extra security in exchange for a much more convenient and less footgunny API. Asking users to pad the key themselves would mean that lots of them fail to preserve collision resistance on the key, which probably doesn't matter in most use cases (see also HMAC), but it's not ideal.
• You'd need to decide whether to keep a power-of-two chunk size for the tree mode, or whether to pick a size that's a multiple of your state size. Power-of-two chunks are convenient for implementing tree traversal/building logic, but even multiples are more efficient. This is a tricky tradeoff, and I think doing a good job here would mean building multiple versions and doing a lot of benchmarking. (See also section 4.4 of the KangarooTwelve paper.) Note that the chunk size of BLAKE3 is tuned to be as small as reasonably possible, which assumes that the implementation is using SIMD to hash parent nodes in parallel, so you need to have SIMD optimizations working before you do these benchmarks.
• Speaking of which, the SIMD implementations assume the word size in many places, and they'd probably need to be rewritten from scratch. You're already looking at a rewrite if you're porting things to a new platform, but the new implementations might have less in common with existing ones, so a high-performance port might be more difficult.

So in short, there are some technical and security-sensitive issues that come up if you try to change the word size, and beyond that some issues where moving away from the 32-bit "sweet spot" leads to some awkwardness. If you're in the business of designing new hash functions, it could be an interesting project. But if you know that's not the business you want to be in, then I don't think it's feasible.

[VictorTaelin]

@odiferousmint It is actually very hard to beat GHC; otherwise it wouldn't be the fastest lazy functional compiler in the world! Also, I meant BLAKE3 (it is the latest revision, right?). Regardless, thanks for the comments. Interesting points overall.

@oconnor663 Thanks, extremely good answer. Yes, I'm definitely not in the business of designing new hash functions! If some existing hash function had a parametric word size, it would probably be a great choice for HVM (and an output of 240 bits, key sizes of 480 bits, etc. would be expected). But I get that modifying BLAKE3 with that in mind is clearly not a trivial task; bad luck.