Falcon constant time tests failing

[baentsch]

The Falcon CT CI tests are failing since quite a few weeks coincidentally with the last commit (adding uninstall support -- but I somehow cannot imagine how this should impact CT for Falcon). Other thoughts what could be at play welcome.

[SWilson4]

I think it's more likely that #1585 somehow caused the failures, as it touched Falcon source files, and the timing fits. However, as far as I can tell the only changes were to whitespace, so I'm still a little perplexed by the sudden breakage.

At first glance, it looks like at least some of the failures are indeed non-constant-time behaviour. The first one, for example, points to

liboqs/src/sig/falcon/pqclean_falcon-512_avx2/keygen.c

Line 4153 in 78e65bf

if (f[u] >= lim || f[u] <= -lim

which I believe we would consider a "pass", based on the in-line documentation.

I'll be updating the Falcon code shortly to address #1561 / PQClean/PQClean#523 / #1608, so I suggest we delay fixing this after that's done. No sense in possibly having to update the constant-time issues / passes all over again after it lands. How does that sound @baentsch?

Not directly related to the Falcon failures, but worth noting: It seems like the "generic" run is picking up errors in the AVX2 functions. Is this the desired behaviour? I would have expected it to test only the "clean" implementations.

[SWilson4]

Not directly related to the Falcon failures, but worth noting: It seems like the "generic" run is picking up errors in the AVX2 functions. Is this the desired behaviour? I would have expected it to test only the "clean" implementations.

Ah, I see why this is happening. See #1618.

[baentsch]

Bad news: CT testing now has more failures than before -- but then again, we're testing more configs now...

[SWilson4]

Bad news: CT testing now has more failures than before -- but then again, we're testing more configs now...

Especially given that it's no longer just Falcon failing but also BIKE. :( I haven't looked closely at the failures yet to see whether they constitute true non-CT behaviour or not. Will open an issue to track.

[cothan]

I'm very familiar with Falcon code base due to my work with Falcon aarch64. Can you give me a brief instruction how to enable constant time test locally so I can (hopefully) help out?

[baentsch]

I'm very familiar with Falcon code base due to my work with Falcon aarch64. Can you give me a brief instruction how to enable constant time test locally so I can (hopefully) help out?

Thank you very much for this offer, @cothan ! All CT logic is visible in this CI test: In essence, you need a Linux image with valgrind installed (we have prepared "openquantumsafe/ci-ubuntu-focal-x86_64:latest" for this), build liboqs with the required instrumentation for the platform of choice (e.g., cmake args -DOQS_DIST_BUILD=OFF -DOQS_OPT_TARGET=generic -DCMAKE_BUILD_TYPE=Debug -DOQS_ENABLE_TEST_CONSTANT_TIME=ON) and execute the test script. At its beginning a full explanation is contained in comments.

[cothan]

So I made a PR #1646,, at my local test, it passed in AVX2 with haswell config, and Reference with generic config.
I don't see the constant time check is enabled in the PR CI/CD, can someone run enable the check at CI, or run it locally to confirm it?