Early propagation of carries in the BLAKE hash function

Question

The BLAKE paper uses round constants derived from $\pi$ to improve diffusion, even if the additions modulo $2^{32}$ are replaced with bitwise XOR when processing a null message and null initial state:

The higher weight in the original model is due to the addition carries induced by the constants $c_0,\dots,c_{15}$. A technique to avoid carries at the first round and get a low-weight output difference is to choose a message such that $m_0 = c_0,\dots,m_{15} = c_{15}$. At the subsequent rounds, however, nonzero words are introduced because of the different permutations.

However, the BLAKE2 paper describes changes it made to BLAKE that remove these constants:

Constants in G initially aimed to guarantee early propagation of carries, but it turned out that the benefits (if any) are not worth the performance penalty. This change saves two xors and two loads per G, that is, 16% of the total arithmetic (addition and xor) instructions.

This statement was made as part of an argument that reducing the number of constants in BLAKE2 does not weaken it, while simultaneously decreasing RAM and ROM footprint. Unfortunately, unlike many of the other trade-offs it discusses, no further explanation is given. What are the benefits of guaranteeing early propagation of carries that lead to BLAKE's constants, and why are these benefits in doubt?

Answer 1

This is already covered by Ella's response, but in short the added nonlinearity at the start buys you very little in terms of security, compared to its cost in number of operations. It would be more effective, and make for a simpler design, for example, to trade all these constant xors by an extra round. Since that part of BLAKE was not pulling its own weight, as noted by the cryptanalysis of the various weakened versions of BLAKE, it was removed.

But besides the small effect on nonlinearity, there is another reason for the existence of the constants—to eliminate symmetries on the underlying block cipher. BLAKE, as well as BLAKE2, are modes of operation on top of a $\{0,1\}^{1024}\times\{0,1\}^{1024}\to \{0,1\}^{1024}$-bit (or $\{0,1\}^{512}\times\{0,1\}^{512}\to\{0,1\}^{512}$) block cipher $E(k, m)$, inspired by the ChaCha core. And like the ChaCha core, when the message words $m_i$ are all 0, or more generally all equal, if the inputs $x_i$ are also, say, all equal, the output words $y_i$ will also be all equal. For example, $$ E\left( \begin{pmatrix} m & m & m & m \\ m & m & m & m \\ m & m & m & m \\ m & m & m & m \\ \end{pmatrix}, \begin{pmatrix} x & x & x & x \\ x & x & x & x \\ x & x & x & x \\ x & x & x & x \\ \end{pmatrix} \right) = \begin{pmatrix} y & y & y & y \\ y & y & y & y \\ y & y & y & y \\ y & y & y & y \\ \end{pmatrix}\,, $$

for some 32- or 64-bit word $m$, $x$, and $y$. This property, often called a symmetry of the round function, makes the underlying block cipher of BLAKE—without the constants—easily distinguished from an ideal cipher. Likewise with BLAKE2. This is even exploited in the "chosen-IV" attacks of a weak variant of BLAKE2.

However, in the actual mode of operation of either BLAKE or BLAKE2, these so-called symmetric states are unreachable by design, via the inclusion of the $IV_0$–$IV_7$ constants in the initial state, so this property is not a security liability.

Answer 2

What are the benefits of guaranteeing early propagation of carries

Addition without carries is equivalent to XOR. Consider the addition of the following two bit strings performed modulo $2^8$:

0000 0001
0000 0010 +
---------
0000 0011

You can see how this is equivalent to the XOR of the two bit strings, despite the fact that we evaluated addition modulo $2^8$.

So if carries don't happen during the first few additions, then those additions can be re-written as XOR.

If all of the additions happened to be equal to XOR then the function would be completely linear, which would make finding preimages easy.

Of course, having all of the additions being equivalent to XOR won't happen in practice, but the general notion is that the more of the state/rounds you can linearize, the more you can improve your attack.

If, for example, no carries happen during the first two rounds, then the first two rounds can be linearized and you can write linear equations to express the state after 2 rounds.

The earlier the carries propagate, the early non-linearity enters into the equations.

why are these benefits in doubt?

I'm not terribly familiar with cryptanalysis of blake/blake2 and the change in the constants, so I can't answer this part completely.

But at least one possible reason is that you can use the inverse of the constants in the input to the function, which would cancel out as the constants are added during the first round.

During later rounds, the hamming weight of the state will be high enough to ensure that plenty of carries propagate without the need for the constants to induce it, and so the constants helping propagation is only really relevant during the first few rounds. But if you can cancel out the constants during (at least) the first round, then they don't really help when and where they're needed.