Falcon Security Proof and Recommendations

[Phillip Gajland]

Hi everyone,


We’d like to share results from our formal security analysis of the Falcon signature scheme. For a full description, please refer to our paper: https://ia.cr/2024/1769.


Executive Summary:
We recommend two small modifications to Falcon:

1. Salt sampling: In the signing procedure, we recommend sampling the salt and computing the hash within the signing loop, rather than outside. This allows us to provide the first formal proof of Falcon in the random oracle model.

2. Hashing the public key: The public key should be included in the hash. This is standard engineering practice and has also been discussed in this forum for its security benefits. Additionally, we provide another reason for including it: it enables tight multi-user security.


Details:
Unfortunately, our analysis shows that despite our modifications to Falcon-512 and Falcon-1024 we cannot prove \emph{strong unforgeability} for either scheme. For comparison, schemes like Dilithium already satisfy strong unforgeability.

For plain unforgeability we are able to show that our modifications to Falcon-512 achieve only 100 bits of provable security. By reducing the number of allowed signing queries from 2^{64} to 2^{57}, we can increase this to 118 bits, nearing the claimed security level. For Falcon-1024, we prove that it meets 256 bits of security for plain unforgeability.

We argue that the recommended changes are minor and can be incorporated at this stage of standardisation. Specifically, we suggest the following changes to the signing procedure (Algorithm 10 in the Falcon specification):

• Move the steps of sampling the salt, hashing the message and salt, and computing the FFT of the hash (Lines 1-3) inside the do while loop (Line 5-8). This modification incurs minimal additional cost since the loop is executed only once or twice in expectation. The costs associated with Gaussian sampling within the loop far outweigh the hashing and FFT costs, even for large messages.
  
• As an alternative for very large messages, one could hash the message M = H’(pk,m) once outside the loop and then compute the salt, an additional hash H(M, r) and the FFT inside. However, we recommend the former suggestion for its efficiency (hashing is cheaper than FFT) and simplicity.
  

Importantly, we do not present concrete attacks against Falcon, nor do we claim that a better security proof is impossible. Rather, we show that our tools combined with currently known proof techniques are insufficient to fully justify the target security claims of Falcon and our modified versions. In fact, Falcon in its current state has no provable security.


For further details, please refer to the paper linked above.

Regards,

Eike, Jonas and Phillip

[Rune Fiedler]

Hi,

including the public key into the hash also provides BUFF security. You
can find the mailing list post introducing our results at [1] and the
full paper at [2].

Best regards,
Samed, Rune, and Marc

[1]
https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/b55cfa29-fb22-4cc6-954e-9f15f95e1f65%40cryptoplexity.de
[2] https://eprint.iacr.org/2024/710

Am 30/10/2024 um 16.46 schrieb Phillip Gajland:
> Hi everyone,
>
>
> We’d like to share results from our formal security analysis of the
> Falcon signature scheme. For a full description, please refer to our
> paper: https://ia.cr/2024/1769.
>
>

> *Executive Summary:
> *We recommend two small modifications to Falcon:

>
> 1. Salt sampling: In the signing procedure, we recommend sampling the
> salt and computing the hash within the signing loop, rather than
> outside. This allows us to provide the first formal proof of Falcon in
> the random oracle model.
>
> 2. Hashing the public key: The public key should be included in the
> hash. This is standard engineering practice and has also been discussed
> in this forum for its security benefits. Additionally, we provide
> another reason for including it: it enables tight multi-user security.
>
>

> *Details:
> *Unfortunately, our analysis shows that despite our modifications to

> Falcon-512 and Falcon-1024 we cannot prove \emph{strong unforgeability}
> for either scheme. For comparison, schemes like Dilithium already
> satisfy strong unforgeability.
>

> For /plain unforgeability/ we are able to show that our modifications to

> Falcon-512 achieve only 100 bits of provable security. By reducing the
> number of allowed signing queries from 2^{64} to 2^{57}, we can increase
> this to 118 bits, nearing the claimed security level. For Falcon-1024,

> we prove that it meets 256 bits of security for /plain unforgeability/.

>
> We argue that the recommended changes are minor and can be incorporated
> at this stage of standardisation. Specifically, we suggest the following
> changes to the signing procedure (Algorithm 10 in the Falcon specification):
>

> * Move the steps of sampling the salt, hashing the message and salt,

> and computing the FFT of the hash (Lines 1-3) inside the do while
> loop (Line 5-8). This modification incurs minimal additional cost
> since the loop is executed only once or twice in expectation. The
> costs associated with Gaussian sampling within the loop far outweigh
> the hashing and FFT costs, even for large messages.

> * As an alternative for very large messages, one could hash the

> message M = H’(pk,m) once outside the loop and then compute the
> salt, an additional hash H(M, r) and the FFT inside. However, we
> recommend the former suggestion for its efficiency (hashing is
> cheaper than FFT) and simplicity.
>
>
> Importantly, we do not present concrete attacks against Falcon, nor do
> we claim that a better security proof is impossible. Rather, we show
> that our tools combined with currently known proof techniques are
> insufficient to fully justify the target security claims of Falcon and
> our modified versions. In fact, Falcon in its current state has no
> provable security.
>
>
> For further details, please refer to the paper linked above.
>
> Regards,
>
> Eike, Jonas and Phillip
>

> --
> 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 <mailto:pqc-
> forum+un...@list.nist.gov>.
> To view this discussion visit https://groups.google.com/a/list.nist.gov/
> d/msgid/pqc-forum/d1ff5a62-6a5e-41f6-9540-290a497e6c27n%40list.nist.gov
> <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/
> d1ff5a62-6a5e-41f6-9540-290a497e6c27n%40list.nist.gov?
> utm_medium=email&utm_source=footer>.

[John Mattsson]

Very interesting and timely paper. Thanks for sharing.

 

>We argue that the recommended changes are minor and can be

>incorporated at this stage of standardisation.

 

I agree that this seems to be the case.

 

>Importantly, we do not present concrete attacks against Falcon, nor do

>we claim that a better security proof is impossible.

 

Yes, but important that NIST describe in FIPS 206 that users should not assume that FN-DSA provides SUF-CMA security.

 

While SUF-CMA is nice to have, many applications can live with UF-CMA. I find it worrying that you could not prove more than 100 bits of security for Falcon+-512 (Qs = 2^64), but as you write your results is a lower bound

 

(I think the paper should write clearly which UF-CMA security you proved for the unmodified Falcon-512 and Falcon-1024, I did not find that information when skimming the paper).

 

Cheers,

John

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Phillip Gajland <gaph...@gmail.com>
Date: Wednesday, 30 October 2024 at 16:48
To: pqc-forum <pqc-...@list.nist.gov>
Cc: eike....@rub.de <eike....@rub.de>, jonas....@rub.de <jonas....@rub.de>, phillip...@rub.de <phillip...@rub.de>
Subject: [pqc-forum] Falcon Security Proof and Recommendations

You don't often get email from gaph...@gmail.com. Learn why this is important

--

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 visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/d1ff5a62-6a5e-41f6-9540-290a497e6c27n%40list.nist.gov.

[Phillip Gajland]

Hi Samed, Rune, and Marc,

Yes, by "This [...] has also been discussed in this forum for its security benefits," we were referring to the BUFF or Pornin & Stern transformation. We can add a note about this in our paper.

Regards,

Eike, Jonas and Phillip

[Phillip Gajland]

Hi John,

Thank you for your feedback.

As we state in the paper, "we were not able to prove the security of Falcon without modifications." While we don't claim that proving security is impossible with different techniques, we didn't succeed in our attempts. Additionally, even if it were provable, it's unclear whether the bit security would be further decreased.

Regards,

Eike, Jonas and Phillip

[John Mattsson]

Thanks,

[Thomas Pornin]

Hello,

thanks for your analysis! The two suggestions do make sense to me (I am one of the co-designers of Falcon, though here I write only for myself).

Some back story about the nonce: in the current Falcon code, there is a "streamed API" in which the signature generation happens in three steps: at the start, the random nonce is generated, and injected into SHAKE256. Then the message is injected. Finally, the SHAKE engine is flipped to output mode, and the output is used to generate a pseudorandom polynomial (modulo X^n+1 and modulo q). This kind of API supports very long messages (e.g. you sign a 3-hour video) but works only if in case of a restart (due to the sampling yielding a vector which is not short enough, either in L2-norm or when encoded) you can reuse the same pseudorandom polynomial, i.e. the same nonce; this is the only way that fits that API, and in any case you'd prefer not to have to rehash gigabytes of data in such a case.

Now of course there is an alternate method, which is quite traditional: when hashing the message to a polynomial, instead of computing H(nonce||msg) (or H(nonce||pubkey||message)), then we can pre-hash the message with a cryptographically secure function H2, and thus end up with H(nonce||H2(message)) (or H(nonce||pubkey||H2(message))). That pre-hashing can be done externally by the caller, it does not even have to be done with foreknowledge of the signature key. This simplifies the API into a single "sign this hash value" function. However, it has the additional requirement that the new hash function H2 (the one for pre-hashing) has to be collision-resistant, while in the previous case there was no such requirement. Historically, in the aftermath of the collisions on MD5 and SHA-1, there was some unease about collision resistance, and having schemes that do not require that property was felt to be important. In my opinion, this is no longer a real problem: we appear to know how to make collision-resistant hash functions, the SHA-3 standardization process showed that. Moreover, this is the path that NIST chose for ML-DSA: in FIPS 204, ML-DSA.Sign() uses a "raw message" while HashML-DSA.Sign() expected a pre-hashed message, and a leading byte is included in the processing to make sure that the two cases are separated.

Thus, in my opinion:

• We should support pre-hashing in a way similar to ML-DSA. This is desirable for pure engineering reasons, namely the ability to hash the data before even knowing which signature algorithm is going to be used with it; it also allows using a different hash function if that is desirable, e.g. for performance reasons.
• If the long-message streaming API works with pre-hashing, then it becomes easy to regenerate the nonce at every restart. It will have negligible impact on performance since restarts are, in practice, quite rare. If it has benefits with regard to proofs of security, so much the better.
• Yes, including the public key in the hashed data is something that we should do too. Again, in an API where pre-hashing is supported and thus signature generation is a single function call (not a three-steps process), then it's easy to do.

Right now, the definition of FN-DSA is in the hands of NIST, not mine, so I can only provide my opinion.

Thomas