Add Valgrind-based detection of variable-latency instructions #693
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
b325192 to
bfd3e2a
Compare
|
I temporarily added one of the KyberSlash2 vulnerabilities in bfd3e2a to test this this is actually working as intended. It looks something like this: Interestingly this triggers on all versions of gcc (-Os) and clang (-Oz). The former was known and is what we used in the KyberSlash paper, the latter was not known to me and we didn't mention it in the KyberSlash paper. |
The scalar decompression routines so far used a division
by {16,32,1024,2048}. This is not a security concern since
even when compiled into variable-time `div` instructions
as these functions are only operating on public ciphertexts
(the one that comes out of encapsulation, not the one that comes
out of re-encryption).
Yet, it appears good style -- and it avoids having to declassify
the ciphertext in constant-time tests -- to avoid the division
altogether and use a shift instead. Note that since the operands
are unsigned, there is no difference between shift and division.
Signed-off-by: Hanno Becker <beckphan@amazon.co.uk>
Signed-off-by: Matthias J. Kannwischer <matthias@kannwischer.eu>
This commit builds on top of #687 which added Valgrind-based constant-time tests detecting secret-dependent memory accesses and conditional branches. This commit extends this to also detect secret-dependent divisions such as those that lead to the KyberSlash vulnerability. See https://kyberslash.cr.yp.to/. We test for that by using the patch to Valgrind proposed in the KyberSlash paper (see same link). It adds an option --variable-latency-errors=no|yes to valgrind which defaults to no. If you set it to yes, it will complain if you use undefined values in division instructions. This patch has also been sent to the valgrind developers, but was so far not merged. Luckily our nix setup makes it very easy to add a patched valgrind and cache it in the Github cache. Initially this detected some divisions in the scalar_decompress_x functions (divisions by powers of two) when compiling with -O0. Luckily these functions only operate on public ciphertexts (the ct that comes out of encapsulation, not the ct that that comes out of re-encryption). I verified this is the case by explicitly declassifying the ciphertext that comes out of encapsulation which confirmed that there are no further divisions. While this is fine (this ciphertext is public!), it's rather unnecessary as we really don't need divisions there. I instead opted to replace those / divisions in the code by shifts (which is what the compilers do with anything from -O1 anyway). The nix setup may be of independent interest as it makes it very easy to use the patched valgrind (and also a number of different compilers). You can simply run nix develop .#ci_valgrind-varlat_gcc14 and you'll magically end up in a shell with a patched valgrind and gcc14. Currently we have ci_valgrind-varlat_clang14 ci_valgrind-varlat_clang15 ci_valgrind-varlat_clang16 ci_valgrind-varlat_clang17 ci_valgrind-varlat_clang18 ci_valgrind-varlat_clang19 ci_valgrind-varlat_gcc48 ci_valgrind-varlat_gcc49 ci_valgrind-varlat_gcc7 ci_valgrind-varlat_gcc11 ci_valgrind-varlat_gcc12 ci_valgrind-varlat_gcc13 ci_valgrind-varlat_gcc14 This commit also adds new workflows to the CI using those shells and testing our library with the following flags: {-Oz,-Os,-O3,-Ofast,-O3 -ffastmath,-O2,-O1,-O0}. Signed-off-by: Matthias J. Kannwischer <matthias@kannwischer.eu>
bfd3e2a to
3456da6
Compare
There was a problem hiding this comment.
This is great, thanks a lot @mkannwischer.
Do we need new CI tests or can we just amend the existing ones?
Also, do you want to remark the existence of those CT tests in the README? Might be worth it.
hanno-becker
approved these changes
Jan 24, 2025
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This commit builds on top of
#687
which added Valgrind-based constant-time tests detecting
secret-dependent memory accesses and conditional branches.
This commit extends this to also detect secret-dependent
divisions such as those that lead to the KyberSlash
vulnerability.
See https://kyberslash.cr.yp.to/.
We test for that by using the patch to Valgrind proposed
in the KyberSlash paper (see same link).
It adds an option --variable-latency-errors=no|yes to valgrind
which defaults to no. If you set it to yes, it will complain if
you use undefined in division instructions.
This patch has also been sent to the valgrind developers, but was
so far not merged. Luckily our nix setup makes it very easy to
add a patched valgrind and cache it in the Github cache.
Initially this detected some divisions in the scalar_decompress_x
functions (divisions by powers of two) when compiling with -O0.
Luckily these functions only operate on public ciphertexts
(the ct that comes out of encapsulation, not the ct that that
comes out of re-encryption).
I verified this is the case by explicitly declassifying
the ciphertext that comes out of encapsulation which confirmed
that there are no further divisions.
While this is fine (this ciphertext is public!), it's rather
unnecessary as we really don't need divisions there.
I instead opted to replace those / divisions in the code
by shifts (which is what the compilers do with anything
from -O1 anyway).
The nix setup may be of independent interest as it makes it very easy
to use the patched valgrind (and also a number of different compilers).
You can simply run
nix develop .#ci_valgrind-varlat_gcc14
and you'll magically end up in a shell with a patched valgrind
and gcc14.
Currently we have
ci_valgrind-varlat_clang14
ci_valgrind-varlat_clang15
ci_valgrind-varlat_clang16
ci_valgrind-varlat_clang17
ci_valgrind-varlat_clang18
ci_valgrind-varlat_clang19
ci_valgrind-varlat_gcc48
ci_valgrind-varlat_gcc49
ci_valgrind-varlat_gcc7
ci_valgrind-varlat_gcc11
ci_valgrind-varlat_gcc12
ci_valgrind-varlat_gcc13
ci_valgrind-varlat_gcc14
This commit also adds new workflows to the CI using those shells
and testing our library with the following flags:
{-Oz,-Os,-O3,-Ofast,-O3 -ffastmath,-O2,-O1,-O0}.