When padding is necessary for sponge collision resistance

Question

Suppose I use a sponge hash construction with rate $r$, and I have two messages of lengths $\ell_0 r$ and $\ell_1 r$ for $\ell_0,\ell_1\geq0$, and they are not necessarily already correctly padded. Suppose I hash these two messages using the sponge construction, without padding them. Does the lack of restriction on padding, together with the freedom of these messages to be of different lengths, make it feasible to find a collision, ie find two different such messages that have the same sponge output?

I hope that since both messages have length some multiple of the block length, the construction is secure. If the answer is no, then what about the case we enforce one of the two messages to already be correctly padded.

I ask because I don't understand the security analysis behind padding. I have in mind Keccak256 with variable-rate padding.

Update:

Here's one potential answer. By Definition 1. of some keccak team document, a padding rule is sponge-compliant if for block size $r$ we have $$ \forall n\geq0, \forall M,M'\in\mathbb{Z}_2^* \ M\neq M' \implies M||\text{pad}[r](|M|) \neq M'||\text{pad}[r](|M'|)||0^{nr} $$ and also applying the padding rule never results in the empty string. The case I'm describing implies the padding rule that appends nothing leaving the message as is, and the messages are already of size some block multiple. This scheme would be sponge-compliant except for two cases.

1. A message is empty. In that case the padding rule results in the empty string, as forbidden.
2. Message 1 ends with at least r zeros. Then message 2 could equal message 1 less the final block of $r$ zeros, and therefore be a different message. Yet for the case $n=1$ when this message 2 is appended with $r$ zeros it will in fact equal message 1.

I believe these are the only exceptions, and the scheme is otherwise sponge-compliant.

Why the need for protecting against extending one message (M') with any number of zero blocks?

Answer 1

With padding removed and all messages multiple of the rate, Keccak (or a generic sponge-constructed hash) is collision-resistant under appropriate hypothesis on the sponge function and parameters. However it has one somewhat undesirable property: the empty message leaves the sponge in the initial state, that is all-zero, after absorption.

Padding of sponge functions is constructed on top of that, so that

• All padded messages are a multiple of the rate.
• Two distinct messages yield different padded messages,for collision resistance.
• No padded messages is empty, so that there's at least one sponge absorption cycle.

Further, the padding of the SHA-3 functions is such that two distinct (message, function) pairs yield different padded messages. That makes it hard to find $M$, $M'$ with $\operatorname{SHA3-256}(M)=\operatorname{SHAKE256}(M',256)$. or such that $\operatorname{SHA3-224}(M)$ is the first 28 bytes of $\operatorname{SHA3-256}(M')$.