This should just overwrite the current Falcon implementations, as those are attempting to implement the padded format already

Sorry for stealth-editing the description, @thomwiggers; I wanted to see the PR CI results yesterday but didn't have time to write things up properly. Didn't expect anyone to look at it so soon.

This should just overwrite the current Falcon implementations, as those are attempting to implement the padded format already

The current code already implements the compressed version modulo the value of the CRYPTO_BYTES macro, so that format was basically free. Also, the consensus in liboqs discussions was that it would be nice to support both compressed and padded formats, especially as NIST KATs are only provided for non-padded signatures. Is there a reason to prefer not having both in PQClean?

I'm mainly not sure exactly how well variable-length signature formats are supported by PQClean's tests... Even though the API includes siglen.

Pinging @dstebila to see how we want to approach this from the liboqs side: proceed with only fixed-length for now and perhaps include variable-length later? Revamp the PQClean tests if necessary?

Pinging @dstebila to see how we want to approach this from the liboqs side: proceed with only fixed-length for now and perhaps include variable-length later? Revamp the PQClean tests if necessary?

This PR adds Falcon*-padded, and also makes some changes to Falcon*, the latter of which is the compressed version, right? So is that compressed version variable length in this PR or not? If it is variable length, then can't we already tell from the CI tests whether PQClean tests have a problem with this?

If it is variable length, then can't we already tell from the CI tests whether PQClean tests have a problem with this?

The thing is that accessing the bytes in the signature buffer beyond the length of the signature should probably be categorized as undefined behaviour. The thing with undefined behaviour is that there's a very non-zero chance that these bytes are actually the same each time so if we do something like memcmp(sig_a, sig_b, CRYPTO_BYTES), it still works. We should really go into the tests to check this.

This PR adds Falcon*-padded, and also makes some changes to Falcon*, the latter of which is the compressed version, right?

Yeah, that looks like it is the case. I currently get a different length (always slightly less than CRYPTO_BYTES) each time I call crypto_sign_signature (and passing the wrong length leads to rejection, to boot); I'm using the latest master commit (1b7f6bf).

I have two dumb questions, though:

PADDED: this is the compressed format, but with extra padding bytes to obtain a fixed size known at compile-time.

Does that mean that these signatures are interoperable? Should a compliant verify() interface accept both "padded" and "compressed" signatures?

CT: this is a fixed-size format, which furthermore allows constant-time processing with regard to the signature value and message data. This is meant for uncommon situations in which the signed data is secret but of low entropy, and the public key is not actually public. The CT format is larger than the COMPRESSED and PADDED formats.

I assume this means (a) the CT format is not compatible with the others, and it would need its own entirely separate verify() function? And (b) that due to the "uncommon" comment by Falcon, it's not a high priority target for PQClean to add?

Yeah, that looks like it is the case. I currently get a different length (always slightly less than CRYPTO_BYTES) each time I call crypto_sign_signature (and passing the wrong length leads to rejection, to boot); I'm using the latest master commit (1b7f6bf).

I have two dumb questions, though:

PADDED: this is the compressed format, but with extra padding bytes to obtain a fixed size known at compile-time.

Does that mean that these signatures are interoperable? Should a compliant verify() interface accept both "padded" and "compressed" signatures?

The Falcon reference implementation verifies signatures of both formats using the same code. The caller can provide the format, or if none is provided the verification code infers it.

CT: this is a fixed-size format, which furthermore allows constant-time processing with regard to the signature value and message data. This is meant for uncommon situations in which the signed data is secret but of low entropy, and the public key is not actually public. The CT format is larger than the COMPRESSED and PADDED formats.

I assume this means (a) the CT format is not compatible with the others, and it would need its own entirely separate verify() function? And (b) that due to the "uncommon" comment by Falcon, it's not a high priority target for PQClean to add?

The CT format can be handled by the same verify function. In particular, CT-format signatures have a different header byte which allows for easy differentiation. See the falcon_verify_finish function in the reference code here: https://falcon-sign.info/impl/falcon.c.html

I don't think there's any active development going on in liboqs or PQClean to support the CT format, but it's probably in the "nice to have" category.

Sorry that this PR has been collecting dust for a month or so over the holidays. Now that some relevant downstream work in liboqs is ready to go, I'd like to revive it.

If it is variable length, then can't we already tell from the CI tests whether PQClean tests have a problem with this?

The thing is that accessing the bytes in the signature buffer beyond the length of the signature should probably be categorized as undefined behaviour. The thing with undefined behaviour is that there's a very non-zero chance that these bytes are actually the same each time so if we do something like memcmp(sig_a, sig_b, CRYPTO_BYTES), it still works. We should really go into the tests to check this.

How about this proposal for extending the tests to cover variable-length signatures:

• Fill the signature buffer to capacity with random bytes prior to signing.
• Check the tail of the buffer—the portion that should be unused, based on the returned signature length—to ensure that the random bytes have not been modified.

If we want to make sure that there are no reads beyond the valid signature length, then we could perhaps mark the signature buffer as initially "uninitialized" and use valgrind to check for behaviour that depends on it, as is done in liboqs to check for secret-dependent behaviour. This would be a bit more work but I imagine it would still be doable.

Would adding one or both of these tests help to alleviate your concerns about supporting variable-length Falcon signatures @thomwiggers?

How about this proposal for extending the tests to cover variable-length signatures:

• Fill the signature buffer to capacity with random bytes prior to signing.
• Check the tail of the buffer—the portion that should be unused, based on the returned signature length—to ensure that the random bytes have not been modified.

This sounds like a good test.

If we want to make sure that there are no reads beyond the valid signature length, then we could perhaps mark the signature buffer as initially "uninitialized" and use valgrind to check for behaviour that depends on it, as is done in liboqs to check for secret-dependent behaviour. This would be a bit more work but I imagine it would still be doable.

Would adding one or both of these tests help to alleviate your concerns about supporting variable-length Falcon signatures @thomwiggers?

I also like this a lot, though there is of course a bit of overhead when we run Valgrind --- we currently run the functest test suite with ASAN and Valgrind already. How exactly does this "mark as uninitialized" work?

How about this proposal for extending the tests to cover variable-length signatures:

• Fill the signature buffer to capacity with random bytes prior to signing.
• Check the tail of the buffer—the portion that should be unused, based on the returned signature length—to ensure that the random bytes have not been modified.

This sounds like a good test.

If we want to make sure that there are no reads beyond the valid signature length, then we could perhaps mark the signature buffer as initially "uninitialized" and use valgrind to check for behaviour that depends on it, as is done in liboqs to check for secret-dependent behaviour. This would be a bit more work but I imagine it would still be doable.
Would adding one or both of these tests help to alleviate your concerns about supporting variable-length Falcon signatures @thomwiggers?

I also like this a lot, though there is of course a bit of overhead when we run Valgrind --- we currently run the functest test suite with ASAN and Valgrind already. How exactly does this "mark as uninitialized" work?

Valgrind provides a VALGRIND_MAKE_MEM_UNDEFINED macro. We use it when testing liboqs to mark all output of randombytes as undefined, thereby (hopefully) detecting behaviour that depends on random (i.e., secret) data. For this application I believe it would be much simpler, as it would only be a matter of marking one buffer as undefined, rather than intercepting all calls to randombytes.

Here's the liboqs usage.

Am I interpreting this PR correctly?:

1. The Compressed format will remain the "default" implementation with an unqualified name.
2. The Padded format is being added, under a new interface.
3. The Compressed sign_verify() is being augmented to support Padded signatures reliably, without accidental UB.
4. The Padded sign_verify() will also reliably support verifying Compressed signatures.
5. The CT format is not supported in any capacity, even verification, at this time. Attempts to verify a CT signature will reliably fail without segfaults or out-of-bounds access.

Am I interpreting this PR correctly?:

1. The Compressed format will remain the "default" implementation with an unqualified name.

2. The Padded format is being added, under a new interface.

3. The Compressed `sign_verify()` is being augmented to support Padded signatures _reliably_, without accidental UB.

4. The Padded `sign_verify()` will also reliably support verifying Compressed signatures.

5. The `CT` format is not supported in _any_ capacity, even verification, at this time. Attempts to verify a CT signature will _reliably_ fail without segfaults or out-of-bounds access.

Yes indeed, that's an accurate interpretation.

This is now passing all CI. Notes to make code review easier:

• The falcon-*-padded code is identical (up to namespacing) to the existing Falcon code, with the exception of pqclean.c, which implements padded format signing and verification.
• A check for interoperability between Falcon formats has been added to functest. This required a fair bit of hacking around with preprocessor directives and Makefiles.
• The falcon tests hung in CI for armhf / gcc. I had to disable quite a few in order to get them to complete, including functest and nistkat. :/ This is less than ideal, but looking back at the logs, it seems like the tests have been timing out for a year, since the latest version of Falcon was added, and the workflow has never actually successfully completed.
• The Windows and MacOS version of astyle were incompatible with the Linux version; when one was satisfied the other would fail. I disabled style checking except on Linux for CI tests.

Since I skipped a number of hanging CI tests, I thought it best to pre-integrate the new code into liboqs to take advantage of its CI (which includes running on an actual ARM machine). https://github.com/open-quantum-safe/liboqs/commits/sw-falcon-padded/

Yeah, I think the skipping of tests is unfortunate but probably required. PQClean could use a restructuring of its CI, and we would ideally figure out how to get proper ARM-based tests going (on actual hardware, with accelerators).