Changes to SPHINCS+ specification to prevent multi-user attacks

[Andreas Hülsing]

Dear all,

After feedback from NIST about potential multi-user attacks, the
SPHINCS+ team announces the following changes that will be implemented
in the next version of the specification:

1.) We introduce a new, dedicated construction for the PRF used to
derive the secret key elements for WOTS and FORS. For SHA256, the old
function was defined as

    PRF(PK.seed, ADRS) = SHA-256(PK.seed||ADRS^c).

    The new function is defined as

    PRF(PK.seed, SK.seed, ADRS) = SHA256 (PK.seed || tobyte(0, 64-n) ||
SK.seed || ADRS^c)

    The difference is that it takes the public seed as additional
input. This is a random input sampled by a user during key generation.
Given that the value has n bytes for security parameter n, this value is
unique per user with overwhelming probability. Thereby, the first input
block absorbed by SHA256 creates an at least computationally unique
intermediate hash value. This does not come at any additional cost if an
implementation stores this intermediate hash value and continues
computations from there. Indeed, this is already done for the other
internal functions.

    For SHAKE256, the function simply absorbs the concatenation of the
inputs into a single input block and becomes

    PRF(PK.seed, SK.seed, ADRS) = SHAKE256 (PK.seed || SK.seed || ADRS).

    This is possible because of the greater input block size of SHAKE256.

    Finally, for Haraka we get

    PRF(PK.seed, SK.seed, ADRS) = Haraka512_PK.seed (SK.seed || ADRS).

    (Note that NIST has commented that if it standardizes SPHINCS+ then
it will expect FIPS-compliant implementations to use SHA-2 or SHA-3.)


2.) We change the initialization value of OptRand from the all zero
string to PK.seed. This ensures that also PRF_msg takes a unique, user
dependent input or a random value.

Both changes prevent the possibility that an adversary could run a
multi-target attack to find the secret key input to these functions when
targeting multiple users.

Best wishes,

The SPHINCS+ team

[Scott Fluhrer (sfluhrer)]

One clarification (see SRF); this should have been caught earlier...

-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Andreas Hülsing
Sent: Monday, January 17, 2022 10:40 AM
To: pqc-...@list.nist.gov
Cc: con...@sphincs.org
Subject: [pqc-forum] Changes to SPHINCS+ specification to prevent multi-user attacks

Dear all,

...

2.) We change the initialization value of OptRand from the all zero
string to PK.seed. This ensures that also PRF_msg takes a unique, user
dependent input or a random value.

SRF: This default initialization value is used if you do not use random bits (e.g. from a TRNG) to generate the OptRand value; if you do opt to use random bits during the signing process, you still use that value.

[Mike Ounsworth]

For the relative laymen here; what is the backwards compatibility impact of this change? Sounds like:

* Keygen is changed -- which only matters if for some reason you need deterministic keygen.
* Signing is changed -- so re-signing the same message will yield a different signature, which only matters if you need deterministic signatures.
* Verification is unchanged (?) -- existing signatures should still verify under the updated code?

---
Mike Ounsworth

-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Andreas Hülsing
Sent: January 17, 2022 9:40 AM
To: pqc-...@list.nist.gov
Cc: con...@sphincs.org

Subject: [EXTERNAL] [pqc-forum] Changes to SPHINCS+ specification to prevent multi-user attacks

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://urldefense.com/v3/__https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/83eb4546-b804-ab12-0a2c-2dcdb4df4ff7*40huelsing.net__;JQ!!FJ-Y8qCqXTj2!JHPtmNJaYiuiWkIc_PnYaQbzCGHyohp-7LGhH8mKOQpTmTvsc0sADQDD1ppp9nFW_1dr$ .
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

[William Whyte]

Are there other unaddressed but known concerns with SPHINCS+? If so, maybe it would be a good time to address them as well, even low-priority concerns, since the specification is changing anyway and it might be best to get any potential changes done and out of the way now so it can be stable going forward.

William

-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Andreas Hülsing
Sent: Monday, January 17, 2022 10:40 AM
To: pqc-...@list.nist.gov
Cc: con...@sphincs.org

Subject: [pqc-forum] Changes to SPHINCS+ specification to prevent multi-user attacks

WARNING: This email originated from outside of Qualcomm. Please be wary of any links or attachments, and do not enable macros.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/83eb4546-b804-ab12-0a2c-2dcdb4df4ff7%40huelsing.net.