Comparison between this and KangarooTwelve and M14

[DonaldTsang]

What are the speed and security difference between BLAKE3 and KangarooTwelve and K14 by Team Keccak?
Main page: https://keccak.team/kangarootwelve.html
Specification: https://keccak.team/files/KangarooTwelve.pdf
Base implementation: https://github.com/XKCP/XKCP/tree/master/Standalone/KangarooTwelve/Python
Rust Implementation: https://github.com/XKCP/XKCP/tree/master/Standalone/KangarooTwelve/Rust
RFC standard: https://datatracker.ietf.org/doc/draft-viguier-kangarootwelve/

As a side joke, I made this.

There once were two empires in Hashlandia:
The Keccak Empire led by Bertoni, Daemen, Peeters and  VanAssche,
And the BLAKE Empire led by Neves and Aumasson.
A long time ago, there was a war of SHA3, and Keccak was victorious, but it will not last long.
In retaliation, King Neves decided to fire back with the invasion of BLAKE II,
And as King Bertoni sees his empire falling apart because of it, Kangaroo XII has been staged.
After King Neves noticed their schemes, BLAKE III is coming.

[oconnor663]

Take a look at the BLAKE3 paper. We include KangarooTwelve in our benchmarks in the Performance section. There's also a brief discussion of the KangarooTwelve tree layout in Section 7.6.

King Bertoni sees his empire falling apart

Sometimes it's fun to treat these things as a competition, but I also want to be clear that BLAKE3 has benefited heavily from work done by the Keccak team. Their "Sufficient conditions for sound tree and sequential hashing modes" paper was a major influence on the original Bao tree mode, and their subsequent "Sound hashing modes of arbitrary functions, permutations, and block ciphers" paper is the basis for our security argument in section 4.3 of the BLAKE3 spec. @gvanas is also personally responsible for getting me to study the SIMD implementations of K12 and BLAKE2bp/BLAKE2sp.

[DonaldTsang]

@oconnor663 if it is possible, update the graphical benchmark of the red bar charts with SHA3 and KangarooTwelve, that way people can see how advanced BLAKE3 is.

Also good to know that the two teams are collaborating, the more the merrier I guess. <3

Some questions: what about RFC standardization of BLAKE3? Would it be done?

[gvanas]

And as King Bertoni sees his empire falling apart because of it, Kangaroo XII has been staged.

Very funny. Anyway, KangarooTwelve is a constructive proposal for fast hashing that brings together a number of things my colleagues and I have been working on, such as permutation-based cryptography, tree hashing and Sakura coding. I think it is a better way to present it, no? :-)

[oconnor663]

Note that SHA3-256 is in the red bar chart. There are two reasons I didn't include K12 there: 1) I wanted to focus on widely used algorithms, and as far as I know K12 (like BLAKE2bp and BLAKE2sp) is not very widely used. 2) That chart shows performance at 16 KiB of input, which is relatively important because it's the size of the TLS record buffer. At 16 KiB, K12 has not yet reached peak throughput, and including it with a low performance figure didn't seem fair.

how advanced BLAKE3 is

KangarooTwelve is advanced too! Obviously I want to promote my own design, but at the same time I don't want us to get carried away. K12 has a smaller (max) space requirement, and it's going to benefit from SHA-3 hardware acceleration in the future, both of which will be significant benefits for embedded applications. There are also open questions about how difficult it will be for other people to implement BLAKE3 (see Section 5.1 in the spec), and K12 has an important advantage there in terms of simplicity. I hope K12 and BLAKE3 both see a lot of adoption over the next few years.

Some questions: what about RFC standardization of BLAKE3? Would it be done?

I wasn't part of the BLAKE2 RFC process, so others would know more than I do about this sort of thing. Let's split that topic off into a different issue.

[gvanas]

Sometimes it's fun to treat these things as a competition, but I also want to be clear that BLAKE3 has benefited heavily from work done by the Keccak team. Their "Sufficient conditions for sound tree and sequential hashing modes" paper was a major influence on the original Bao tree mode, and their subsequent "Sound hashing modes of arbitrary functions, permutations, and block ciphers" paper is the basis for our security argument in section 4.3 of the BLAKE3 spec. @gvanas is also personally responsible for getting me to study the SIMD implementations of K12 and BLAKE2bp/BLAKE2sp.

Thank you for this comment! Indeed, BLAKE3 is indeed super fast on AVX-512, and tree hashing is a way to exploit this (and the multi-core) parallelism. Implementing this multi-threaded is very nice work IMHO!

One further comment. In symmetric cryptography, we try to separate modes and primitives, making designs more modular. Did you try your Bao mode on top of K12 (or equivalently a 12-round Keccak)?

[gvanas]

Note that SHA3-256 is in the red bar chart. There are two reasons I didn't include K12 there: […]

OK, I understand the reasoning, but I tend to agree with Donald and suggest to include K12, as well as NIST-standard ParallelHash128 and of course Blake* at their peak performance. This would only be fair.

[DonaldTsang]

@oconnor663 in a sense I kind of want both BLAKE3 and K12 to be more commonly used, since the more people who knows about the it, the more people will use it. Which is why the graph can be used as a pitch canvas.
@gvanas Also the bao structure is so revolutionary I am kind of stunned, this is some next level stuff, even more exciting then tree hashing and sakura.

For me though, I am still wondering, why haven't people turned BLAKE3 into a sponge function (a nod to the Keccak team)? I mean NORX has been tried in the CAESAR competition but that is BLAKE2, and seeing a comparison like that would be fun for K12... (I mean NORX-as-a-hash has not been tried either so IDK)

You know what would make this new year season even more wholesome though? Why not bring in the Skein and Groestl team members and have a reunion? 2010 (SHA3 finalist announcement) was 10 years ago after all. I do like Skein's 1024 bit hash, and Groestl's whirlpool-like design as a side note.

[DonaldTsang]

While we are on the subject, I would like to ask @veorq a question:
Since you wrote both https://eprint.iacr.org/2009/438.pdf (Skein Cryptanalysis) and https://eprint.iacr.org/2019/1492.pdf (reducing rounds of crypto), is it possible for you to recommend a reduced round version of Skein (I mean I kind of have a crush on it) and maybe Groestl?

[DonaldTsang]

36/72 rounds are optimal for Skein512, and 36-44/80 rounds are assumed to be optimal for Skein1024.
Also on page 17 of http://www.skein-hash.info/sites/default/files/skein1.3.pdf there is a tree mode.
It might be a good idea to benchmark BLAKE3 vs reduced round Skein, in both linear and tree modes.