Subject: [lamps] randomized hashes & pqc

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Fri, 11 Jun 2021 09:56:37 +0100

Hello,

*Some observations:*

The prominent NIST PQC lattice sig algorithms (Dilithium and Falcon -- NIST
has stated to standardize at least one of these) and the NIST SP 800-208
stateful signature algorithms (LMS/HSS, XMSS/XMSS^MT) all use randomized
hashing, but not in the way specified in NIST SP 800-106 back in 2009.

Basically, a nonce is prefixed as the first thing of a (SHAKE) hash
computation before the message itself. Hence in verification, one needs to
look at the signature (which contains the nonce) before starting the
message hash.

This is a little different from older PKCS #1 flows. Note that if one takes
the approach of just singing a plain SHA-256 hash of a message using these
algorithms (feeding that hash to be further hashed and signed), this will
effectively halve the security level in both classical or quantum adversary
models.

In signing, the nonce computation happens in various ways; one can use
either h(pk) as the nonce, a PRF of the signature sequence number (for
stateful sigs), or have an entirely random one.. But this is mostly an API
issue, not an IETF problem.

Furthermore, the SHAKE XOF output is directly used for a
sampler/hash-to-point mechanism in Falcon (there is an intermediate hash in
Dilithium). This needs to be an XOF, not SHA-2/3, as many output bytes are
needed for further processing (creating those lattices, essentially).

*Questions / Suggestion:*

I anticipate that (especially in PKI) there will be a need to facilitate
other hash functions apart from the Keccak stuff that the PQC/stateful sig
algorithms use internally. Hybrid classical/pqc schemes may perhaps want to
compute the message hash only once (think of a boot-time firmware
verification, which needs to process a lot of data quickly).

Furthermore, as a hardware interface builder, I really don't want to be
passing multi-gigabyte messages through my signing/verification module
interfaces, just a shorter byte sequence.

So, am I safe in assuming that the byte sequence actually being signed by
these algorithms will be an ASN.1 blob roughly of type:

{  OID_of_RandH, H( nonce | m )  }

Where the OID_of_RandH specifies *both* the hash function and the
randomization mechanism (how was nonce derived)? This would give
authenticated domain separation between different hashes and -- more
importantly -- between different types of randomization pre-padding
mechanisms. So this would be the byte sequence actually going into the
(FIPS 202) engine inside the module.

Cheers,
- markku

Dr. Markku-Juhani O. Saarinen <[email-masked]> PQShield, Oxford UK.

---

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Sun, 13 Jun 2021 20:13:43 +0100

Hi,

Even though my posting wasn't about PQC timelines, but about hash
randomization for (pqc) signatures, I did mention "at least one of" Falcon
and Dilithium being selected. It's more like Falcon "xor" Dilithium that
will be selected at the end of this year. If you didn't attend, the
presentations of last week's NIST PQC Standardization Conference are freely
available; The slides of Dustin Moody (NIST) have the most up to date
information.
https://csrc.nist.gov/Presentations/2021/status-update-on-the-3rd-round

In any case, the same issue affects them both, and also the already
NIST-approved algorithms LMS,HSS,XMSS,XMSS^MT. I'd prefer to have OIDs not
just for the algorithms, but also for the hash randomization mechanisms.

Cheers,
- markku

On Fri, Jun 11, 2021 at 9:56 AM Markku-Juhani O. Saarinen <[email-masked]>
wrote:

> Hello,
>
> *Some observations:*
>
> The prominent NIST PQC lattice sig algorithms (Dilithium and Falcon --
> NIST has stated to standardize at least one of these) and the NIST SP
> 800-208 stateful signature algorithms (LMS/HSS, XMSS/XMSS^MT) all use
> randomized hashing, but not in the way specified in NIST SP 800-106 back in
> 2009.
>
> This is a little different from older PKCS #1 flows. Note that if one
> takes the approach of just singing a plain SHA-256 hash of a message using
> these algorithms (feeding that hash to be further hashed and signed), this
> will effectively halve the security level in both classical or quantum
> adversary models.
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 15 Jun 2021 17:31:36 +0300

> (FIPS 202) engine inside the module.

Even in pre-quantum contexts, I think such thing would be useful for
EdDSA, Since:

- Non-randomized prehashing would weaken things, since EdDSA is pre-
  hashed.
- Prehashed Ed25519 is not compatible with Ed25519 (since there was no
  way to make it sound in compatible way). As consequence, almost
  nothing supports prehashed Ed25519. Prehashing in Ed448 is a flag,
  but I do not think much stuff supports that either.
- As said, large messages are problematic (even if one breaks the
  spec in compatible way in order to eliminate two-pass signing).

And it could also be used with RSA and ECDSA to strengthen signatures.
E.g., WebPKI certificate signatures require randomized hashing (via a
hack), even if using SHA-2 hash functions.

And as said, this gets even more useful if you have more than one
signature over some medium/large amount of data, which will come up
with PQC, as the first PQC signatures will be hybrid ones.

I do not quite understand the thing about randomization mechanisms,
but I am sure I-D about randomized prehashing will say more about how
it works.

So in summary: +1 for this work.

-Ilari

---

From: Russ Housley <[email-masked]>
Date: Tue, 15 Jun 2021 11:26:33 -0400

RFC 8708 includes the object identifier for HSS/LMS.

Russ

> On Jun 13, 2021, at 3:13 PM, Markku-Juhani O. Saarinen <[email-masked]> wrote:
> 
> Hi,
> 
> Even though my posting wasn't about PQC timelines, but about hash randomization for (pqc) signatures, I did mention "at least one of" Falcon and Dilithium being selected. It's more like Falcon "xor" Dilithium that will be selected at the end of this year. If you didn't attend, the presentations of last week's NIST PQC Standardization Conference are freely available; The slides of Dustin Moody (NIST) have the most up to date information. https://csrc.nist.gov/Presentations/2021/status-update-on-the-3rd-round <https://csrc.nist.gov/Presentations/2021/status-update-on-the-3rd-round>
> 
> In any case, the same issue affects them both, and also the already NIST-approved algorithms LMS,HSS,XMSS,XMSS^MT. I'd prefer to have OIDs not just for the algorithms, but also for the hash randomization mechanisms.
> 
> Cheers,
> - markku
> 
> Dr. Markku-Juhani O. Saarinen <[email-masked] <mailto:[email-masked]>> PQShield, Oxford UK.
> 
> 
> On Fri, Jun 11, 2021 at 9:56 AM Markku-Juhani O. Saarinen <[email-masked] <mailto:[email-masked]>> wrote:
> Hello,
> 
> Some observations:
> 
> The prominent NIST PQC lattice sig algorithms (Dilithium and Falcon -- NIST has stated to standardize at least one of these) and the NIST SP 800-208 stateful signature algorithms (LMS/HSS, XMSS/XMSS^MT) all use randomized hashing, but not in the way specified in NIST SP 800-106 back in 2009.
> 
> Basically, a nonce is prefixed as the first thing of a (SHAKE) hash computation before the message itself. Hence in verification, one needs to look at the signature (which contains the nonce) before starting the message hash.
> 
> This is a little different from older PKCS #1 flows. Note that if one takes the approach of just singing a plain SHA-256 hash of a message using these algorithms (feeding that hash to be further hashed and signed), this will effectively halve the security level in both classical or quantum adversary models.
> 
> In signing, the nonce computation happens in various ways; one can use either h(pk) as the nonce, a PRF of the signature sequence number (for stateful sigs), or have an entirely random one.. But this is mostly an API issue, not an IETF problem.
> 
> Furthermore, the SHAKE XOF output is directly used for a sampler/hash-to-point mechanism in Falcon (there is an intermediate hash in Dilithium). This needs to be an XOF, not SHA-2/3, as many output bytes are needed for further processing (creating those lattices, essentially). 
> 
> Questions / Suggestion:
> 
> I anticipate that (especially in PKI) there will be a need to facilitate other hash functions apart from the Keccak stuff that the PQC/stateful sig algorithms use internally. Hybrid classical/pqc schemes may perhaps want to compute the message hash only once (think of a boot-time firmware verification, which needs to process a lot of data quickly).
> 
> Furthermore, as a hardware interface builder, I really don't want to be passing multi-gigabyte messages through my signing/verification module interfaces, just a shorter byte sequence.
> 
> So, am I safe in assuming that the byte sequence actually being signed by these algorithms will be an ASN.1 blob roughly of type:
> 
> Where the OID_of_RandH specifies both the hash function and the randomization mechanism (how was nonce derived)? This would give authenticated domain separation between different hashes and -- more importantly -- between different types of randomization pre-padding mechanisms. So this would be the byte sequence actually going into the (FIPS 202) engine inside the module.
> 
> Cheers,
> - markku
> 
> Dr. Markku-Juhani O. Saarinen <[email-masked] <mailto:[email-masked]>> PQShield, Oxford UK.
> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm

---

From: Russ Housley <[email-masked]>
Date: Tue, 15 Jun 2021 11:30:37 -0400

> On Jun 15, 2021, at 10:31 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

There was a slightly different approach taken in RFC 6210.  I am unaware of any lessons from implementations.  Are others?

Russ