Re: [lamps] [EXTERNAL] Re: [UNVERIFIED SENDER] RE: How do we plan to solve the hash-then-sign paradigm in Dilithium, Falcon and Sphincs+?

[Mike Ounsworth <[e-mail]>]

> I am saying this is not necessary imo because it will not get used like PrehashEdDSA did not.

I'm not sure that you can make "It turned out that nobody used it" type arguments based on EdDSA because has not (yet) been adopted into any of the hard cases. It's not FIPS-approved. We don't have WebPKIs at scale on EdDSA (ex.: Let's Encrypt is still rooted in ECDSA P-384). I can't imagine any PIV card or ePassport CAs are using EdDSA.

So I think that pointing at something that hasn't yet had to deal with the hard cases, and say "Look, they didn't have any problems!"

---
Mike Ounsworth

From: Spasm <[e-mail]> On Behalf Of Kampanakis, Panos
Sent: December 12, 2022 3:13 PM
To: John Gray <John.Gray=[e-mail]>; [e-mail]
Subject: [EXTERNAL] Re: [lamps] [UNVERIFIED SENDER] RE: How do we plan to solve the hash-then-sign paradigm in Dilithium, Falcon and Sphincs+?

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

> The easiest solution seems to define a prehash version of the PQ algorithms, but if that is not preferred, we are open to other solutions.

I am saying this is not necessary imo because it will not get used like PrehashEdDSA did not. TLS, IKE, SSH, X.509, CMS all use PureEdDSA. Also I am not sure OCSP or CRLs have an issue here because the message to be signed/verified is available as a whole to both the signer and the verifier.

PKCS#11 includes an incremental API. The CKM_ECDSA_SHA256 mechanism is used with the incremental API which allows the signer/verifier to take the message piece by piece. So PKCS##11 could define a mechanism like CKM_FALCON_SHA3-512 which prehashes the message and it could have CKM_PUREFALCON mechanism which does not. Or it could do the same thing with one mechanism CKM_FALCON which based on the input parameter can prehash or not. This is what PKCS#11 has today for EdDSA. It is the CKM_EDDSA mechanism which takes optional CK_EDDSA_PARAMS. So, LAMPS does not need to specify anything in this case. PKCS#11 can take care of it like they did with EdDSA.


From: John Gray <John.Gray=[e-mail]<mailto:John.Gray=[e-mail]>>
Sent: Monday, December 12, 2022 3:29 PM
To: Kampanakis, Panos <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Subject: [EXTERNAL] [UNVERIFIED SENDER] RE: [lamps] How do we plan to solve the hash-then-sign paradigm in Dilithium, Falcon and Sphincs+?


CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.

Thanks for the reply Panos,

I am a bit confused by your reply.  On one hand you say we need to use pre-hashing for use-cases like the PKCS#11 big message (and also the use-cases I mention in my previous email).  EdDSA had a similar issue and defined a HashEdDSA to handle that case.  You suggest we should follow that case, which sound great, and I agree.   However, then you say lamps should only specify and use the pure versions of signatures.  Are you suggesting hash versions of the PQ algorithms be defined somewhere else, or do you mean we just digest when needed for the handful of use-cases that need it and not worry about defining hash versions of the algorithms?   PKCS#11 as an API could require pre-hashing, but what if PKCS#11 is not being used?

Perhaps an information best practices document for these types of use-cases needs to be written?  We don't want to cause interop issues.  For example, if a CRL is signed using a digest of the CRL verses the full message using a PQ signature, you have two different signature outputs.  How would an end-entity verifier know which method was used?  Try one and if it fails, try the other?  That doesn't seem good.   Another approach would be to update 5280 to say CRL signing should be over a digest of the data to be signed.  Then at least there would be no ambiguity.  I am not saying that should be done either, I would just like there to be no ambiguity for the verifier.

The easiest solution seems to define a prehash version of the PQ algorithms, but if that is not preferred, we are open to other solutions.


Cheers,

John Gray
Entrust

From: Kampanakis, Panos <kpanos=[e-mail]<mailto:kpanos=[e-mail]>>
Sent: Monday, December 12, 2022 3:01 PM
To: John Gray <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Subject: [EXTERNAL] RE: [lamps] How do we plan to solve the hash-then-sign paradigm in Dilithium, Falcon and Sphincs+?

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

As discussed before, this existed with EdDSA which ended up standardizing Pure and Prehash versions. In the end, only Prehash ended up getting used almost everywhere. So, I would suggest to follow the same logic as with PureEdDSA https://www.rfc-editor.org/rfc/rfc8410<https://urldefense.com/v3/__https:/www.rfc-editor.org/rfc/rfc8410__;!!FJ-Y8qCqXTj2!ZOQNbCxQcFausvZgqh55FDqgCowunlVQ0LFH2ud86mrhI8aNOdinzUxjQG9ihRE13qfLnu0_G8mocpHh6qiqHmSv72u2pnGE$>


   [...] EdDSA has

   defined two modes: the PureEdDSA mode without prehashing and the

   HashEdDSA mode with prehashing.  The convention used for identifying

   the algorithm/curve combinations is to use "Ed25519" and "Ed448" for

   the PureEdDSA mode.  This document does not provide the conventions

   needed for the prehash versions of the signature algorithm.

The only case where it breaks (that I am aware of) is in PKCS#11 with big messages (incremental API) with Falcon and SPHINCS+ (not Dilithium). In these cases the PKCS#11 spec will need to digest before signing which is something they already specified for EdDSA (and the incremental API).

So, I don't think LAMPS should specify any Prehash versions.  Imo, LAMPS should specify and use only the Pure versions of the PQ signatures in X.509, CRLs, CMS etc.






From: Spasm <[e-mail]<mailto:[e-mail]>> On Behalf Of John Gray
Sent: Monday, December 12, 2022 12:23 PM
To: [e-mail]<mailto:[e-mail]>
Subject: [EXTERNAL] [lamps] How do we plan to solve the hash-then-sign paradigm in Dilithium, Falcon and Sphincs+?


CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.


We are working on making transition plans from existing signatures to the PQ candidates, and are wondering how lamps / X509 plans to address the pre-hashing of data before signatures (also known as hash-then-sign).   The Dilithium, Falcon and Sphincs+ drafts do not have a signature mode where the toBeSigned message is first hashed, and then signed.   Many PKI systems today actually rely on being able to hash (aka 1-way compress) a message that will be sent over a network to an HSM device for signing.    Some use cases:



Signing CRL (especially large combined CRL's):

The CA's that sign CRL's today would typically send a hash (32-bytes for SHA-256 for example) to an HSM for signing.    The network bandwidth required is therefore reduced from x Megabytes to 32-bytes.   With Dilithium, Sphincs+ or Falcon the entire message will have to be sent (unless a pre-hash mode of Signature operation is added to Dilithium, Sphincs+ or Falcon).



OCSP signing:

OCSP response are small, but instead of signing thousands to millions of 32-byte hashes,  it might be 1000 or more bytes each, which again magnifies the network requirement by many times.   With larger signatures due to PQ algorithms, this will be magnified even more.



CSR Signing:

A local USB token device or HSM would need to sign the full CSR.



Other use-cases?



We know many protocols like CMS include pre-hashing in the protocol, so that resolves the issue because the digest is taken as part of the protocol.  However, for all the cases which are not part of a protocol this will be another hurdle to hinder the transition to Post Quantum for many existing applications in production today.



Is there anyone working to solve this issue?   The simplest solution would seem to be to have signatures defined for Dilithium, Falcon and Sphincs+ (and any future PQ selections) which pre-hash.   I know there has already been discussions on this mailing list in this regard.   I know there was much discussion on why it shouldn't be done because it reduces the security to the collision resistance of the chosen hash function, or for other reasons, but that doesn't provide a solution.   If we accept the reduction of the message to the size of a hash for protocols like CMS, and non-protocol use-cases today (RSA and EC), why is it not acceptable to pre-hash for these use-cases with Dilithium, Falcon and Sphincs+?    There must be a practical solution otherwise it will likely delay adoption of these new algorithms in many environments which could be an even greater security risk.

Suggestions?


John Gray
Entrust

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.