How does BLAKE2 ensure that hash(A) != hash(B) when B = A||0 and both A & B have the same number of blocks?

Question

Suppose I have two arrays :

A = a single byte, being zero. B = two bytes, both being zero.

B = A||0 (i.e. B starts with A, and differs only by appending a zero byte)

BLAKE2(A) != BLAKE2(B)

Yet, according to the scant documentation I can find, BLAKE2 pads with zero bytes.

Given that both an array with just one byte, and an array with two bytes, are well within the size of a single block, theoretically their full-block-length zero-padded equivalents are identical.

So, if it isn't padding the inputs with a length indicator, and if the finalization flag mentioned in the scant documentation is either all binary 1s or else all binary 0s as the scant documentation clearly states (thus providing no indication of which bytes in the final input block are padding), how is BLAKE2 able to make a different hash for these two inputs?

Note: It does make different hashes from these two inputs, and that's a very good thing, and I'm in the process of writing some software that relies on this property of BLAKE2, but I would feel more confident if I understood why/how this is happening. Thanks!

P.S. I tried tagging this BLAKE2 but the system wouldn't let me - apparently the tag doesn't exist yet.

Answer 1

You are right that the padded message by itself is ambiguous.

But the Blake2 compression function does not just take the message block and the chaining value as input. It also takes a finalization flag (to mark the last block and prevent length extensions) and the message size in bytes.

Passing the size to the non final blocks mainly serves to prevent certain multi target attacks. For these blocks the size is always a multiple of the block size. For the final block it's different: Here the size parameter is the total size of the message in bytes and it disambiguates messages which map to the same zero padded message and only differ in size. The flag ensures that compressing a message which ends at the end of the current block, and a message which continues (and thus has the same size argument) have different inputs.

Beyond the specification, which Nova already quoted, it might also be interesting to read:

1. The Skein specification, which uses a similar approach where the tweak contains the length of the message and which inspired the Blake2 padding.
2. My blog post Alternative Blake Padding where I propose a simplified padding, which with some minor tweaks turned into the Blake2 padding.

Answer 2

This preprint of the article published in the proceedings of ACNS 2013 on the official website of BLAKE2 contains on site 15 the answer in a description of the differences between BLAKE and BLAKE2:

Simplified padding. The new padding does not include the message length of the message, unlike BLAKE. However, it is easy to see that the length is indirectly encoded through the counter, and that the padding preserves the unambiguous encoding of the initial padding. That is, the padding simplification does not affect the security of the hash function. Nevertheless, it may be desirable to have a formal proof.