Why is the core ChaCha primitive not good for use in a CRCF? Why create BLAKE?

Question

Why is the core ChaCha primitive not good for use in a collision-resistant compression function (crypto hash)? Why go through the trouble to create BLAKE?

What's wrong with using the core ChaCha primitive unaltered in a Merkle–Damgård like construction to construct a collision-resistant compression function/one-way compression function/Cryptographic hash function.

Is there a practical consideration, or is this just number theoretic?

---

Edit: The following reduces this question without changing it, and summarizes the answer.

Why is the core ChaCha primitive not good for use in a collision-resistant compression function (crypto hash)?

The chacha paper, linked in Lery's answer below, seems to specifically state that compression functions could, indeed, be built on the chacha core primitive. It's on the second to the last page.

"[...] Modifying constants first is helpful for compression functions built on the [chacha] core."

At this point, it becomes safe to say the first question reduces to an argument about what the words "built on" and "good for use in" means. It's not productive to argue semantics, so discussing it further is moot.

Thus, the whole question reduces down to "Why go through the trouble to create BLAKE?" Lary's answer explains this best, so it was chosen. But I'd like to distill out some parts.

Why make BLAKE? What's wrong with core chacha + Merkle–Damgård?

Pure Merkle–Damgård has flaws. BLAKE uses the HAIFA construction, which fixes these flaws by adding a salt and a hash count as extra variables/inputs. What's more important (and quite provocative IMHO) is that HAIFA, in fact, shares the same security requirements and proofs from its core primitive as for Merkle–Damgård.

From the HAIFA paper... (Technical Report CS-2007-15 - 2007)

The same arguments that are used to prove that the Merkle–Damgård construction retains the collision resistance of the underlying compression function, can be used to prove that HAIFA does so as well.

TL;DR: HAIFA basically just 1ups Merkle–Damgård. (Though, does so in a very important way!)

So then, in a practical sense, BLAKE (original) actually is or at least contains a collision-resistant compression function "built on" the chacha core primitive, in a Merkle–Damgård like construction.

In other words, my first question is flawed.

BLAKE doesn't change the core function of chacha in a qualitative way at all, rather it changes how and what data is input to it. (See SEJPM's answer for a reasoning as to why.)

The only modification to the function of the core was apparently a mistake. BLAKE creators fat-fingered the rotations. This, as explained, is not strictly a requirement. Pure chacha core would work just as well.

Answer 1

I'm answering the following which was asked in the original question:

Why is stock chacha20 not good as a cryptographic hash? Why create BLAKE?

Why not simply apply the one-way compression function concept on raw chacha20, specifically its quarterround() function, unaltered.

TL;DR: Chacha was meant as a stream cipher, it needs a different kind of security guarantees to become a hash function. The BLAKE designers tweaked it so that it became one, but they also did more than that. They also had some constraints because of the NIST's SHA3 competitions for which they created BLAKE.

Also, if you ever wondered why BLAKE was using a different direction for its rotation (left shifts instead of right shifts), you might want to read all about it below, because it's amazing!

Why create BLAKE?

If you don't want to buy the book on that topic, written by BLAKE's designers, I'll try to explain some things that might help you understand why we needed BLAKE.

First things first, I'll recall that ChaCha itself is a variant of Salsa20, a stream cipher that was already recognized for its simplicity and high speed. The fact that it is a stream cipher notably means that when you take a message of size $\ell$, you'll get a ciphertext of size $\ell$ out of it, whereas with a hash function you want a fixed size output.

Now, ChaCha consists of a minimal set of basic operations and repeats the same pattern of addition, rotation, and XOR, called "ARX". The main reason to choose ChaCha over Salsa20, is that while using the same numbers of operations than Salsa20 to invertible update four 32-bit state words, ChaCha does so in a different order and updates each word twice rather than once, hence giving each input word a chance to affect each output word. And it also has other nice properties about which you can read in the ChaCha paper.

Now, BLAKE designers wanted to compete in the NIST competition for SHA3, so they were notably required to:

• produce digests of 224, 256, 384 and 512 bits
• support maximum message length of at least $2^{64}-1$ bits
• process data in a one-pass streaming mode, reading each message block only once

The BLAKE designers also decided they wanted to have the same interface as SHA2, which implied parsing input byte arrays to 32- or 64-bit words in a big-endian way (unlike MD5 for example).

Now, what part of BLAKE is actually coming from ChaCha?
Well, its core, the "G" function, which consists of 16 operations and is directly inspired from the "quarter-round" function used by ChaCha. But as I said, ChaCha is using 32-bit words! So, they had to modify it in order to be able to support 64-bit words, they had to if they wanted to be able to match the SHA2 interface so that BLAKE can be a drop-in replacement for SHA2.

You might ask why, and the reason is mostly to allow Blake to take full advantage of the 64 arithmetic that is available on today's CPUs in servers and desktop computers, while still having a 32-bit version with Blake-256 that is more suited for older, or smaller devices.

ChaCha on its side has the goal of being a stream cipher, that is simple, and fast. To do so, and still be compatible with older or smaller devices, having 32-bit words makes sense. Plus, with a stream cipher, you want interoperability between platform without having to choose a specific version depending on your architecture to have better performances, whereas, with a hash function, it is customary to have more choice.

The rest of the design of BLAKE is indeed just a straightforward way to convert ChaCha into a secure hash function, but it still is important to do so while using the right methods, and so you could not "just take ChaCha" to have a hash function, since you still need for example to compress your message into a single fixed-size digest.

Why is stock chacha20 not good as a cryptographic hash?

Well, as mentioned above, ChaCha is a stream cipher, which means that it does not compress a message so that you get a fixed size digest, and it also does not care about the same kind of threats and attacks. (For instance, collision resistance is definitively not something that a stream cipher tries to tackle, but it is crucial to have a secure hash function.)

But as said by SEJPM in his answer, ChaCha is featuring a PRF function at its core, which maps onto the 512-bit space, which is a nice building block for many cryptographic algorithms, from stream cipher to hash function.

So, ChaCha being a stream cipher, it is not fit to be used as a cryptographic hash directly as it stands, but its core ideas were used by BLAKE designers in their compression function with fixed-size output digest. Also, the fact that ChaCha was well understood and studied help the crypto-analysis of BLAKE that ensured it had the right security properties.

Notice also that since you want to hash (almost) arbitrary size input, you need a way to extend the domain of your compression function, and BLAKE is using the HAIFA model to achieve "domain extension" and also its goal of being a secure hash function.

Notice that the later also answers your question about "why there seem to be no Merkle–Damgård like constructions". BLAKE avoids Merkle–Damgård because of its many pitfalls and prefers to use a simplified HAIFA construction instead.

Rough idea of how BLAKE works and its differences with ChaCha

Here I'll try to give you a high-level idea of how BLAKE works, which should also help you spot more differences with how Chacha works.

In order to hash a message $M$ with BLAKE-32 (the closest to Chacha):

The message is first padded so that the length of the padded message is a multiple of 512. But it is always padded with at least 66 bits since it allows for the last 64 bits of the padding to be the binary encoded bit length of the (unpadded) message.

The padded message is then split into 512-bit blocks and iteratively fed to the compression function along with the previous hash value, a 64-bit counter counting the bits already hashed, and an optional 128-bit salt. Before you ask, the previous hash value for the very first block is an initialization vector (IV) that is defined in the BLAKE specification.

Notice that the compression function has a finalization phase, in which you compute the output hash value using its internal state $v_{0 \leq i \leq 15}$ and the salt $s_{0\leq i\leq 3}$ chosen by the user (0 by default): $$h'_i \leftarrow h_i \oplus s_{i \bmod 4} \oplus v_i \oplus v_{i+8}$$ for $i = 0,\dots , 7$. The eight $h'_i$ are the output of the compression function. It might be interesting to note that this can be seen as a particular case of a Davies-Meyer-like construction. (See the BLAKE paper for more.)

It is also useful to note that the "core" G function of BLAKE is also differing from Chacha because it feeds 2 input words XORed with constants (that are defined in the specification and that were removed in the design of BLAKE2) into its state at each execution of the G function.

And notice also that the rotation (shifts) used in the G function are right ones, whereas Chacha is using left rotation. (But this is actually not changing much and is only due to a typo in one of the early specifications...!?! ^^ Congrats for making it so far, you deserved to know the truth!)

Finally to have a more visual idea of these latest points, here is the G function of BLAKE:

$$\begin{align} a &\leftarrow a + b + (m_{\sigma_r(2i)} \oplus c_{\sigma_r(2i+1)})\\ d &\leftarrow (d \oplus a) \ggg 16\\ c &\leftarrow c + d\\ b &\leftarrow (b \oplus c) \ggg 12\\ a &\leftarrow a + b + (m_{\sigma_r(2i+1)} \oplus c_{\sigma_r(2i)}) \\ d &\leftarrow (d \oplus a) \ggg 8 \\ c &\leftarrow c + d \\ b &\leftarrow (b \oplus c) \ggg 7 \end{align}$$

compared to the "quarter-round" function used by ChaCha:

$$\begin{align} a &\leftarrow a + b \\ d &\leftarrow (d \oplus a) \lll 16\\ c &\leftarrow c + d\\ b &\leftarrow (b \oplus c) \lll 12\\ a &\leftarrow a + b \\ d &\leftarrow (d \oplus a) \lll 8 \\ c &\leftarrow c + d \\ b &\leftarrow (b \oplus c) \lll 7 \end{align}$$

If you really want more details about how BLAKE works, the BLAKE paper is actually not too difficult to read.

Answer 2

OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a secure PRF when the first input is the key.

So now that we know what ChaCha is, for the desired functionality of hashing:

At a fundamental level it's unclear how to build a CRHF out of a PRF, because it's unclear how to build a CRHF out of OWFs but it's clear how to build a PRF out of OWFs. So modelling ChaCha as a PRF doesn't suffice here. But it is believed that the core function could be collision resistant, though using the specifically designed for this task Rumba20 is a better option. This of course leaves the question how to actually build a hash function out of it, because again, fixed-length inputs aren't immediately practically useful usually.

One could build a Merkle-Damgard Hash out of ChaCha but there you face the significant problems, that

• each iteration only consumes 128-bit of data,
• the HMAC security proof requires a PRF that can use either input as the key which doesn't immediately follow from our above model, and
• ChaCha only takes 384-bit of input but produces 512-bit, how do you map this for the iteration?

Also Merkle-Damgard suffers from the infamous length-extension attack which is something people don't want anymore in these modern times. This is why we have BLAKE(2) which nicely wraps the core into something more practically useful with more modern properties and with a clear and simple design for usage modes.

Answer 3

• Why is stock chacha20 not good as a cryptographic hash?

You haven't specified what kind of ‘cryptographic hash’ you mean, but since you're comparing it to BLAKE, it sounds like you're looking for collision resistance, which was the central motivation for the whole SHA-3 competition in the first place after MD5 and SHA-1 fell to collision attacks in 2004/2005.

The Salsa20 and ChaCha core functions are not designed or advertised to be collision-resistant, and are obviously not collision-resistant. From the Salsa20 web page:

I originally introduced the Salsa20 core as the "Salsa20 hash function," but this terminology turns out to confuse people who think that "hash function" means "collision-resistant compression function." The Salsa20 core does not compress and is not collision-resistant. If you want a collision-resistant compression function, look at Rumba20. (I wonder what the same people think of the FNV hash function, perfect hash functions, universal hash functions, etc.)

This question is like asking: Why is a fork not good as a soup-eating utensil? Why create a spoon?

(More from djb's response to early versions of this question.)

A function $f$ is collision-resistant if it's hard to find distinct inputs $x \ne y$ such that $f(x) = f(y)$. It's usually interesting only if the inputs can be longer than the output—that is, if it compresses long inputs into short outputs. Neither is the case for Salsa20 or ChaCha.

In contrast, Salsa20 and ChaCha are designed to be pseudorandom. A keyed family of functions $F_k$ is pseudorandom if, to an adversary who doesn't know a secret key $k$ chosen uniformly at random, it's hard to tell a black box that computes $F_k(x)$ on any chosen input $x$ from a black box that just returns independent uniform random answers and caches them for each input. But if the adversary knows $k$, all bets are off.

• Why not simply apply the one-way compression function concept on raw chacha20, specifically its quarterround() function, unaltered.

It's not collision-resistant. For example, if $\Delta = (\mathtt{0x80000000}, \mathtt{0x80000000}, \dotsc)$, then $\operatorname{Salsa20}(x) = \operatorname{Salsa20}(x + \Delta)$. (The same is probably true of ChaCha but I haven't checked specifically.)

There is a derivative of Salsa20 that does aim for collision resistance called Rumba20. This design was essentially abandoned; djb's submission to the SHA-3 competition was CubeHash, based on a cryptographic sponge construction like Keccak, the submission to the competition that was eventually selected as SHA-3.

• Why create BLAKE?

It turns out there's an entire book about that! But the short answer is that the designers thought that a variation on the theme of ChaCha could be used to make a good collision-resistant compression function, which turned out to be true—and we now have BLAKE2 widely used on the internet even if BLAKE didn't win theSHA-3 competition.