Re: [lamps] Do we have a FALCON draft yet?

["Massimo, Jake" <[e-mail]>]

Markku,

Thanks for posting this analysis, it’s very useful!

I’d be happy to help co-author the Falcon I-D should one arise. It was originally planned to have multiple algorithms in an all-encompassing “PQ X.509” draft, but due to the vast differences in the schemes it would have muddied the water and produced a hefty draft. That said, a lot of the more general formatting/material authored for Dilithium could easily transfer over to a Falcon draft, so I’d love to be involved and work with you (it could also more easily facilitate consistency between the I-Ds).

Cheers,
Jake

From: Spasm <[e-mail]> on behalf of "Markku-Juhani O. Saarinen" <[e-mail]>
Date: Monday, 21 November 2022 at 04:09
To: LAMPS <[e-mail]>
Cc: Bas Westerbaan <bas=[e-mail]>, Mike Ounsworth <Mike.Ounsworth=[e-mail]>, "Blumenthal, Uri - 0553 - MITLL" <[e-mail]>
Subject: RE: [EXTERNAL][lamps] Do we have a FALCON draft yet?


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.


Hi,

I have been looking at possibly preparing an I-D for Falcon, but the technical details are currently in flux.

I've been in contact with members of the Falcon design team, and I hear that they're getting around to revising the algorithm for standardization (my understanding from NIST is that they will try to get the Dilithium specs in shape before moving on to address Falcon -- this is private communication and not official.)

One of the issues is that there is a yet another twist to message hash processing with Falcon (surprise, surprise!)

Falcon spec (v1.2, 1 Oct 2020), Sect 3.11.3: "A Falcon signature consists of two strings r and s. They may conceptually be encoded separately, because the salt r must be known before beginning to hash the message itself, while the s value can be obtained or verified only after the whole message has been processed. In a format that supports streamed processing of long messages, the salt r would normally be encoded before the message, while the s value would appear after the message bytes. However, we here define an encoding that includes both r and s."

For purposes of, say, PKI formats having the concatenated pair (r,s) as the signature obviously makes more sense than having the signature in two parts.

The second issue is that SHAKE-256 XOF output is used directly. Unless this is changed, Falcon will be yet another case for API architects to consider:

0. For classical (PKCS #1) RSA or ECDSA you can just hash a message and pass the H(m) to the signing function.

1. For Dilithium, you prefix the message "m" with a hash of Dilithium pub key tr=H(pk) and use that as a prefix to compute H(tr | m). You don't need the signature to start verification, just the public key (the "tr" hash can also be found in the private key).

2. For Falcon verification, it's different again. You grab "r' from the signature (not the keys) and prefix the message with it; str = (r | m). If you're singing, you need to throw dice and get a random r before starting to hash the message. But that's not all; HashToPoint() function uses SHAKE256 XOF output directly -- there is no actual upper bound to the number of bytes needed (albeit statistical ones are easy to work out.) One can also pass the entire Keccak context (200 bytes, containing the prefix r and the mixed message m) to the signing/verification function.

This is a compatibility-breaking issue, unlike the randomized vs. non-randomized aspects of Dilithium singing. As the Falcon spec says, "Of course, any variant deviating from the procedure expressed in algorithm 3 implies that the same message will hash to a different value, which breaks interoperability."  This will have to be addressed by the design team.

Ps. I agree that eliminating potential timing oracles from the current Falcon is trickier/costlier than with most other algorithms. Masking and other electromagnetic (DPA/DEMA) countermeasures for hardware implementations are even trickier -- as required for platform security, smart cards, etc. Unless there is a major design change concerning floating point operations in the Gaussian sampler, this appears to be an "inherent" security consideration for Falcon and, indeed, needs to be discussed in the I-D/RFC.

Cheers,
- markku


Dr. Markku-Juhani O. Saarinen
Staff Cryptography Architect
PQShield Ltd



M:             [phone]

E:              [e-mail]<mailto:[e-mail]>
W:             www.pqshield.com<http://www.pqshield.com/>


On Sun, Nov 20, 2022 at 10:13 PM Blumenthal, Uri - 0553 - MITLL <[e-mail]<mailto:[e-mail]>> wrote:
Completely agree with Bas.
Regards,
Uri


On Nov 20, 2022, at 07:14, Bas Westerbaan <bas=[e-mail]<mailto:[e-mail]>> wrote:
Not that I know of. If someone picks this up, may I urge them to add a warning to the following effect in the earliest draft.

The Falcon signing procedure is difficult to implement in constant time because of its use of floating point arithmetic. By default, it should be assumed that the timing of the creation of the signature leaks the private key. Thus, without careful consideration, it should not be used when signatures are created on-the-fly such as for TLS handshakes. It is safe if floating-point emulation is used (which comes at a performance penalty) or a (custom) FPU with sufficient constant-time guarantees. Verification does not use floating-point arithmetic and does come with the same concerns.

Best,

 Bas



On Sun, Nov 20, 2022 at 12:56 AM Mike Ounsworth <Mike.Ounsworth=[e-mail]<mailto:[e-mail]>> wrote:
For completeness, we also have Kyber [3].

[3]: https://datatracker.ietf.org/doc/draft-ietf-lamps-kyber-certificates/

---
Mike Ounsworth

From: Spasm <[e-mail]<mailto:[e-mail]>> On Behalf Of Mike Ounsworth
Sent: November 19, 2022 5:53 PM
To: 'LAMPS' <[e-mail]<mailto:[e-mail]>>
Subject: [EXTERNAL] [lamps] Do we have a FALCON draft yet?

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 LAMPS,

We have drafts for SPHINCS+ [1] and Dilithium [2] in LAMPS.

Has anyone started one for FALCON yet? (I need something to cross-reference the composite draft against)


[1]: https://datatracker.ietf.org/doc/draft-ietf-lamps-cms-sphincs-plus/<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-ietf-lamps-cms-sphincs-plus/__;!!FJ-Y8qCqXTj2!fJ0iZFzue-XVZBbJ18itKI-6e6y12C3g-v1B6dzJyGsg9sgUnSr-uGDYsyjTI-fvpuSJoWVhNP0h3vCR5xxUkcbW4I-VqfjlT2DqrQ8jQA$>
[2]: https://datatracker.ietf.org/doc/draft-massimo-lamps-pq-sig-certificates/<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-massimo-lamps-pq-sig-certificates/__;!!FJ-Y8qCqXTj2!fJ0iZFzue-XVZBbJ18itKI-6e6y12C3g-v1B6dzJyGsg9sgUnSr-uGDYsyjTI-fvpuSJoWVhNP0h3vCR5xxUkcbW4I-VqfjlT2A2XHyKVQ$>
---
Mike Ounsworth
Software Security Architect, 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.
_______________________________________________
Spasm mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/spasm
_______________________________________________
Spasm mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/spasm
_______________________________________________
Spasm mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/spasm