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

["Markku-Juhani O. Saarinen" <[e-mail]>]

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]
W:             www.pqshield.com


On Sun, Nov 20, 2022 at 10:13 PM Blumenthal, Uri - 0553 - MITLL <
[e-mail]> wrote:

> Completely agree with Bas.
>
> Regards,
> Uri
>
> On Nov 20, 2022, at 07:14, Bas Westerbaan <bas=
> [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]> 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]> *On Behalf Of * Mike Ounsworth
>> *Sent:* November 19, 2022 5:53 PM
>> *To:* 'LAMPS' <[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]
>> https://www.ietf.org/mailman/listinfo/spasm
>>
> _______________________________________________
> Spasm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/spasm
>
> _______________________________________________
> Spasm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/spasm
>