OFFICIAL COMMENT: Falcon (bug & fixes)

[Thomas Pornin]

Hello,

to my greatest shame, the new Falcon implementation published on 2019-08-02 had two severe bugs in the sampler; one table was wrong, and a scaling factor was applied at the wrong place. The consequences of these bugs are the following:

• Produced signatures were valid but leaked information on the private key.
• Performance was artificially inflated: the rejection sampling was not rejecting often enough, and the signatures were a bit shorter than they should. With the fixed code, signature performance on x86 (with AVX2) is at about 470k cycles (instead of 390k cycles previously) for Falcon-512, with an average signature size of about 657 bytes (instead of 651 bytes).

The implementation has been fixed, and is published on the Falcon Web site: https://falcon-sign.info/

The report on the implementation has been updated: https://falcon-sign.info/falcon-impl-20190918.pdf

This includes a new section on the issues and their correction.

The fact that these bugs existed in the first place shows that the traditional development methodology (i.e. "being super careful") has failed. I had previously predicted that lattice-based cryptography would entail many implementation issues because samplers are hard to test; at that time I did not envision to find myself at the short end of that prediction, but there we are. Falcon is a rather extreme case because it needs a precise, non-trivial distribution (Gaussian distribution, with varying non-integral centres and standard deviations); however, any random sampler is susceptible to be misimplemented in ways that can be hard to detect automatically. In the Falcon implementation, I have added unit tests that check the inner CDT and perform some chi-square tests that should detect the most egregious deviations, but this is far from providing complete assurance of correctness of the implementation. Other members of the Falcon team are currently working on a much more comprehensive framework for statistical tests on samplers.

New packages will soon be sent to interested parties in their respective formats (NIST, SUPERCOP, PQClean...). The fix to the sampler implies changes to the test vectors, and since performance is impacted, new benchmarks should be run.

Special thanks to Markku-Juhani O. Saarinen, who found the bugs and made some extensive statistical analyses.

Thomas

[Elsa Velazquez]

Hello, 

Do the fixes include testing to ensure the FPE is being used correctly, or are the two things checked completely independently of each other?   If so, do the KEMs verify the FPE is done correctly?  If so, is there a way to do so without KEMs?

And, is there any impact on key and stack sizes (aside performance) with these fixes?
Many thanks, 

Elsa

[Thomas Prest]

Hello,

Le 22/09/2019 à 20:54, Elsa Velazquez a écrit :

Hello, 

Do the fixes include testing to ensure the FPE is being used correctly, or are the two things checked completely independently of each other?

The bug and the fixes are independent of floating-point emulation (FPE). FPE is checked (see below), and we are working on providing a comprehensive test suite for checking Gaussian sampling as well.

If so, do the KEMs verify the FPE is done correctly?  If so, is there a way to do so without KEMs?

Do you mean KEMs or KATs? We don't use KATs to test FPE, instead we implement a test function (see test-FP_block() in https://falcon-sign.info/impl/test_falcon.c.html) to check the correct behavior of FPE.

And, is there any impact on key and stack sizes (aside performance) with these fixes?

The fixes have no impact on key and stack sizes.

I hope this answered your questions.

Many thanks, 

Elsa

Cheers,
Thomas

On Wednesday, September 18, 2019 at 8:17:36 AM UTC-6, Thomas Pornin wrote:

Hello,

to my greatest shame, the new Falcon implementation published on 2019-08-02 had two severe bugs in the sampler; one table was wrong, and a scaling factor was applied at the wrong place. The consequences of these bugs are the following:

• Produced signatures were valid but leaked information on the private key.
• Performance was artificially inflated: the rejection sampling was not rejecting often enough, and the signatures were a bit shorter than they should. With the fixed code, signature performance on x86 (with AVX2) is at about 470k cycles (instead of 390k cycles previously) for Falcon-512, with an average signature size of about 657 bytes (instead of 651 bytes).

The implementation has been fixed, and is published on the Falcon Web site: https://falcon-sign.info/

The report on the implementation has been updated: https://falcon-sign.info/falcon-impl-20190918.pdf

This includes a new section on the issues and their correction.

The fact that these bugs existed in the first place shows that the traditional development methodology (i.e. "being super careful") has failed. I had previously predicted that lattice-based cryptography would entail many implementation issues because samplers are hard to test; at that time I did not envision to find myself at the short end of that prediction, but there we are. Falcon is a rather extreme case because it needs a precise, non-trivial distribution (Gaussian distribution, with varying non-integral centres and standard deviations); however, any random sampler is susceptible to be misimplemented in ways that can be hard to detect automatically. In the Falcon implementation, I have added unit tests that check the inner CDT and perform some chi-square tests that should detect the most egregious deviations, but this is far from providing complete assurance of correctness of the implementation. Other members of the Falcon team are currently working on a much more comprehensive framework for statistical tests on samplers.

New packages will soon be sent to interested parties in their respective formats (NIST, SUPERCOP, PQClean...). The fix to the sampler implies changes to the test vectors, and since performance is impacted, new benchmarks should be run.

Special thanks to Markku-Juhani O. Saarinen, who found the bugs and made some extensive statistical analyses.

Thomas

--
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 on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/fce7d4c4-53d4-4e45-915f-770400429b38%40list.nist.gov.