1
$\begingroup$

In the standard sponge construction, r bits are consumed in each absorption step, and they get concatenated with c capacity bits. In the first round, the capacity bits are 0, so the r input bits just get zero-extended. Can we instead consume r + c bits in the first round, while maintaining the security properties of a random sponge?

Intuitively, it seems like the capacity bits serve no purpose in the first step, since there's no state from a previous round that needs to be propagated. My intuition could be wrong though.

If it's valid, this optimization would be particularly helpful in SNARK programming. If we're compressing two field elements to one, for example, this would let us use a state width of two field elements instead of three.

$\endgroup$
2
$\begingroup$

Here's how to create a second preimage with your modification.

We'll assume that the original message is at least $2r+c$ bits long, and consists of an initial message segment $M_0$ ($2r+c$ bits) and the rest of the message $M_1$.

After processing block $M_0$, the sponge state will be some setting, with the public $r$ bits at some value $R_0$ and the capacity $c$ bits at some value $C_0$.

Concatenate the values $R_0$ and $C_0$ to be an initial block, and then prepend that to $M_1$, giving $R_0 || C_0 || M_1$.

When hashing that, the sponge construction will take the $R_0$ and $C_0$ bits and set the initial Sponge state to be precisely what it was after the initial processing of $M_0$. Then, it'll process the rest of the message $M_1$; because the state is the same, it'll perform the same operations, and generate the same hash.

And, because the lengths of the two messages are different, the messages are different, and thus we have generated a second preimage.


The OP since asked about the security if the length of the input is fixed. Well, if the length of the output $n$ is at most $r$ (i.e. one squeeze cycle), then it is easy to generate preimages. The method is straight-forward; you start with the final state (with the known $n$ bits in the $r$ region), and arbitrarily select values for the other $r+c-n$ state bits. Then, you run the hash backwards (using the inverse permutation, and arbitrary settings for intermediate message blocks) until you get to the initial state, and then you select a message where the first $r+c$ bits are that initial state, and the rest of the message blocks are those arbitrary message blocks you selected.

If we have $n > r$, this still can be used to reduce the amount of work to find a preimage by a factor of $2^r$

The bottom line: the entire security of SHA-3 comes from the capacity bits; letting the adversary arbitrarily select them breaks things bad...

| improve this answer | |
$\endgroup$
  • $\begingroup$ That makes sense, thanks! I'm particularly interested in fixed-input-length hash functions, so my follow-up question would be whether the scheme is secure when the number of absorptions and squeezes is fixed. Or to narrow it down further (if it's easier to answer), if we take a permutation and drop λ bits of its output, does this create a secure PRF (under an ideal cipher assumption)? Let me know if this would be better as a separate question though. $\endgroup$ – Daniel Lubarov Apr 8 at 15:11
1
$\begingroup$

Actually you cannot and should not do so! The capacity bits affect the sponge structure security and should not be read or written directly! If you do so, the security proofs for sponge structure, assuming the attacker having no direct control on capacity bits, will not be valid any more.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.