#001 Multi-Target Attacks in SHRINCS

While going through the SHRINCS BIP, something caught my attention. When calculating the secret values used in FORS and WOTS, I expected them to be derived from the master secret seed (sk_seed) alone.

However, we also supply additional inputs, mainly ADRS (which describes the position and type of the operation we're performing) and pk_seed (which is part of the SHRINCS public key).

Two places where we use these inputs are:

  1. Generating secret-key elements: PRF(pk_seed, sk_seed, ADRS). We use a pseudorandom function to derive secret values from sk_seed, with ADRS and pk_seed as additional inputs.
  2. Hash steps on WOTS chains: F(pk_seed, ADRS, M_1). We hash the value from the previous step of the chain, using ADRS and pk_seed.

Now, why do we need pk_seed and ADRS?

Short answer: ADRS provides domain separation to help mitigate multi-target attacks, while pk_seed helps mitigate multi-user attacks.

Let's start with multi-target attacks and ADRS.

Both PRF() and F() use ADRS. Let's ignore pk_seed for simplicity and focus on F() first.

Multi-target preimage attack on F()

Imagine a scenario where we don't use ADRS for F(). We only use F(X).

Suppose an attacker has collected 1 million WOTS signature elements that are outputs of this same hash function.

The attacker can:

  • Choose a random X.
  • Calculate F(X) = Y.
  • Compare Y against the 1 million revealed signature elements.
  • If a match is found, the attacker has found a valid preimage for one of those values.

This doesn't necessarily mean the attacker found the original input used by the signer. Any input producing the same output would be a valid preimage.

In WOTS, this could allow the attacker to move backward along a hash chain, which might help them forge a signature. Finding one preimage doesn't automatically mean they can forge a complete signature.

The interesting part is that one hash computation allows the attacker to test against 1 million targets, instead of just one.

This is a multi-target preimage attack.

What changes when we add ADRS?

Now imagine we use F(ADRS, X).

Each hash operation is associated with an address describing its position, including the chain and hash step.

The attacker can still:

  • Choose a random X and an address ADRS_A.
  • Calculate F(ADRS_A, X) = Y.
  • Compare Y against the 1 million revealed signature elements.

But there's a difference.

Suppose Y matches a signature element that was generated using ADRS_B.

If ADRS_A and ADRS_B are different, the attacker hasn't necessarily found a usable preimage for that signature element.

Why?

Because during verification, the verifier uses ADRS_B, not the address chosen by the attacker.

To find a usable preimage, the attacker needs an X such that:

F(ADRS_B, X) = Y

So adding ADRS doesn't stop the attacker from comparing the hash output against 1 million targets.

What changes is that one hash computation can no longer be used to test for usable preimages across targets that require different addresses.

This is how domain separation helps mitigate multi-target attacks.

← All learning logs