Hashing list: concatenation vs prepending

In Schnorr's NIZK proof there is an interesting remark:

Within the hash function, there must be a clear boundary between any two concatenated items. It is RECOMMENDED that one should always prepend each item with a 4-byte integer that represents the byte length of that item.

I know, that it's generally a good practice for preventing length-extension attacks. But, look closely at the challenge:

$c = H(g \Vert V \Vert A \Vert \mathsf{UserID} \Vert \mathsf{OtherInfo})$

$A$ is a valid public key -> fixed length

$g$ is a a generator -> fixed length

Suppose both $\mathsf{UserID}$ & $\mathsf{OtherInfo}$ have fixed length as well.

It seems that in this particular case, Plain concatenation can be safe because all but one of the inputs have a fixed length.

Is it so? How vulnerable is Plain concatenation when all (or all but one) inputs have a fixed length compared to Prepending the length?

• If there is a canonical way of representing the input of the hash blocks, as long as that input is unique (over all the possible input) and as long as intermediate state of the hash isn't exposed I'd say you are safe. – Maarten Bodewes Jan 23 '18 at 17:06
• @MaartenBodewes What exactly do you mean by intermediate state of the hash? Data inside the hash function? Suppose, it's SHA-256. Also, I'm a bit unsure whether input that contains one value (g^v mod p, v - random) with a non-fixed length can be called unique representation. If it was not for exponentiating a random - sure, but in this case... On the one hand, you can't check that it's indeed in a form g^r mod p, unless you can break DL. On the other, I don't know if it's even relevant. – pintor Jan 24 '18 at 8:54
• @MaartenBodewes, Hmm, I think that if I fix the length of V, everything should be fine. – pintor Jan 24 '18 at 10:04
• It was a generalization of the length extension attack. That leaks a possible intermediate state as output if the longer messages are acceptable. I generalized it as no specific hash function was specified - SHA-3 has pre/post processing that makes that kind of attack impossible. – Maarten Bodewes Jan 24 '18 at 10:13
• @MaartenBodewes, ok, I get it. Btw, how collision would affect the security of NIZK? Even if the collision exists, It seems almost impossible to forge proof. – pintor Jan 24 '18 at 15:39

The whole issue comes from the fact that regular collision resistant hash functions are defined over binary strings. What you are trying to construct is a collision resistant hash function over a different domain, namely a set of tuples.

To construct a collision resistant hash function for some domain $D$ from a collision resistant hash function for $\{0,1\}^*$ what is necessary is to encode elements of $D$ as elements of $\{0,1\}^*$. If $\mathsf{H} : \{0,1\}^* \to \{0,1\}^n$ is the original hash function and $\mathsf{E} : D \to \{0,1\}^*$ is an efficient encoding function then $\mathsf{H} \circ \mathsf{E} : D \to \{0,1\}^n$ is a hash function for domain $D$.

However, if it is easy to find collisions in $\mathsf{E}$, then $\mathsf{H} \circ \mathsf{E}$ is not collision resistant, since any collision in $\mathsf{E}$ directly implies a collision in $\mathsf{H} \circ \mathsf{E}$. So to show that $\mathsf{H} \circ \mathsf{E}$ is collision resistant we need that $\mathsf{E}$ is also collision resistant. Since $\mathsf{E}$ does not need to be compressing, the easiest way to ensure that it is collision resistant is to ensure that it is collision free by ensuring that it is a unique encoding.

If $\mathsf{E}$ is a unique encoding, then it is easy to show that $\mathsf{H'} = \mathsf{H} \circ \mathsf{E}$ is collision resistant whenever $\mathsf{H}$ is. Assume towards contradiction that there exists an efficient algorithm $\mathcal{A}$ capable of finding collisions in $\mathsf{H'}$. I.e., $\mathcal{A}$ outputs $x,x' \in D^2$ such that $x \neq x'$ and $\mathsf{H'}(x) = \mathsf{H'}(x')$. By definition of $\mathsf{H'}$ this implies that there are encodings $e := \mathsf{E}(x)$ and $e':= \mathsf{E}(x')$ such that $\mathsf{H}(e)=\mathsf{H}(e')$. And by the fact that the encoding is unique and $x \neq x'$ we have that $e \neq e'$. Therefore an algorithm $\mathcal{B}$ that simply runs $\mathcal{A}$ and encodes the outputs finds collisions in $\mathsf{H}$ with the same probability with which $\mathcal{A}$ finds collisions in $\mathsf{H'}$. Therefore, since $\mathsf{H}$ is collision resistant, so must be $\mathsf{H'}$.

It thus follows that all you need is a unique encoding of your tuples into binary strings. And as correctly observed, if all (or all but one) of the constituent parts of the tuple are of fixed length then simple concatenation is in fact a unique encoding.

However, it should be stressed that this requires all participants to always check that all elements of the tuple they are encoding actually have the required length and rejecting them otherwise. This a check that is easily missed (or maybe even skipped for "efficiency"). Whereas prepending the length -- even for fixed length elements -- ensures that even unchecked malformed tuples will not be able to cause collisions.

Indeed, hashing a concatenation of data items all of fixed length (and non-optional) except perhaps one, is safe from these attacks trying to find different data items leading to the same concatenation. In that case, prepending length is unnecessary. It is not bad either, but it requires care: the endianness and unit (bits or octets) must be defined for interoperability, and the maximum length must be considered.